DAABBCC - Dynamic Tree(aka AABB Tree) native extension for fast AABB collision detection

The Defoldmine
#1

DAABBCC

This is a Dynamic Tree(aka AABB Tree) native extension for Defold Engine.
DAABBCC build by using Box2D’s Dynamic Tree.

Credits

Radix sort by Mathias Westerdahl
Box2D by Erin Catto

What is DAABBCC?

A Dynamic AABB Tree is a binary search algorithm for fast overlap testing. Dynamic AABB trees are well-suited for general-purpose use and can handle moving objects efficiently. This data structure provides an effective method for detecting potential overlap between objects.

DAABBCC is not a physics engine. It does not include narrow-phase collision detection or manifold generation.

It is particularly well-suited for casual games, platformers, bullet-hell, top-down games, server-side headless builds that do not require narrow-phase collision detection.

Discussions & Release Notes

Documentation

Toss a Coin to Your Witcher

If you find my Defold Extensions useful for your projects, please consider supporting it.
I’d love to hear about your projects! Please share your released projects that use my native extensions. It would be very motivating for me.

16 Likes
Bump in Defold
#2

Small updates and a bug fixes

  • Small but important bug fixed in core aabb.cc library. That fix cause a ~25% speed gain. Speedup might be greater for situations where there are many slow moving, or static objects
  • A few bugs fixed in the platformer example source on Github.
  • RemoveAll is added. Now you can remove all AABBs from a tree.
    https://github.com/selimanac/DAABBCC#--removeall

Planning

5 Likes
#3

Aabb.cc lib is updated. tinyc2 is removed and latest cute_c2.h is added

5 Likes
#4

Version 2.0

This is a complete rewritten version of daabbcc by using Box2D’s Dynamic Tree.

  • API revised and simplified
  • Nearly 6x performance increment according to v1.x (4800 sprites vs 500 sprites)
  • Low cpu usage
  • Experimental narrow phase collision detections removed
9 Likes
#5

Very cool!

2 Likes
#6

Is there a limitation for number of groups?

1 Like
#7

Yes, but it is not a blocker: https://github.com/selimanac/DAABBCC#notes

1 Like
#8

I get this error when trying to export to HTML5. Any idea why?

/game.project
	The file obtained from https://github.com/selimanac/DAABBCC/archive/v2.0.zip is not a valid zip

Defold 1.3.0.

#9

That’s usually github acting up.
(Also, we haven’t changed anything with our library fetching code)

#10

There seem to be an issue with the dependency itself. Not sure if it’s a Github quirk, or something else?

Going to this file in a browser: https://github.com/selimanac/DAABBCC/archive/v2.0.zip

Shows this:
the given path has multiple possibilities: #<Git::Ref:0x00007fec3b616de8>, #<Git::Ref:0x00007fec3b616ca8>

Going to Releases in Github shows a slightly different URL:
https://github.com/selimanac/DAABBCC/archive/refs/tags/v2.0.zip

This works! Probably worth updating the references to avoid this confusion.

#11

It seems github has updated their way of serving older links.

Go to the releases page, and select the version you want:

Right clicking on v2.0.zip gives me this link:

2 Likes
#12

I guess Github made some changes. I update the link, I hope it is fine now.

4 Likes
#13

Just used this extension for the first time. Thank you @selimanac , excellent work.

I have a couple of questions.

  1. This might be a limitation of AABB, but is there a way to detect which query result is closest to the queried position? My tests indicate that the table order is unrelated to this, probably just the order in which the entries were added to the group.

  2. I use go.animate to move a lot of objects in a performant way. However I need to constantly update the aabb position for these objects, which means go.get_position. In my test, doing lots of updates was worse than the collision checking. Is there a way to automate these position updates to make it cheaper?

Again, thanks for an excellent extension!

1 Like
#14

Hi @Alex_8BitSkull

I would like to let you know that unfortunately I have no intention to update this extension anymore. But you can feel free to contribute.

  1. You can simply check/compare positions on Lua side. It might be possible on the C, but to be honest I don’t remember.
  2. It might be possible by using dmGameObject .
    I was using go.set_positions not the go.animate. When using set_positions you don’t need to get it again. You can simply put all positions to a table and change there.
3 Likes
#15

I suspected you were done with the extension, but thank you for taking the time to answer my questions anyway.

Unfortunately any C work is far beyond my expertise, so I am forced to hope someone more knowledgeable than me will take a stab at either of those features! I think they could both be really useful.

For the first point, having the C side be able to output the order of positions would be much quicker than having to do a bunch of iterations and vmath on the Lua side. For the second point, having the extension tie in with go.animate somehow would unlock huge performance potential for games with a large number of colliding objects.

Just thinking out loud, hoping to nerd snipe someone :slight_smile:

1 Like
#16

Yes, the dmGameObject namespace has getPosition() but it requires a dmGameObject::HInstance. Not sure if there is a way to pass ids from Lua and turn them into dmGameObject::HInstance. If there is then you could provide the extension with a bunch of ids to keep updated and in the extension update function you could get the positions and update the aabb’s. @JCash will know if this is possible or not.

3 Likes
#17

New version is available for testing. This version includes automated position updates for Defold Gameobjects and result sorting.

More on Github

Release Notes for 2.1

  • It is now possible to sort results by distance. Use raycast_sort, query_id_sort, query_sort according to your needs #5.
  • Automated position updates for Defold Gameobjects #6.
  • External Array and HashTable libs are removed.
  • Group limit removed(Previously, it was limited to 20)
  • Remove Gameobject when AABB or Group removed
  • Clear function added for removing and reseting everything.
  • Stop/Resume for automated Gameobject position update.
  • All query results return nil when it is empty. No need to check #count anymore.

And also there is a simple game build with it for testing purpose only. It wasn’t built for playability :

17 Likes
#18

Wow, great release!

2 Likes
#19

Wow, indeed! Thank you so much, @selimanac! :heart:

1 Like
#20

I have the same question for built-in raycasts - but in case of DAABBCC:

.raycast() should receive world or local positions?