DAABBCC: Dynamic AABB Tree native extension with Branch and Bound Algorithm

The Defoldmine
#1

DAABBCC
DAABBCC2400×666

This is a Dynamic AABB Tree native extension with Branch and Bound Algorithm for Defold Engine.
DAABBCC build by using Box2D’s Dynamic Tree.

Branch and Bound implementation by Randy Gaul
Radix sort by Mathias Westerdahl
Box2D Copyright (c) 2009 Erin Catto http://www.box2d.org

What is DAABBCC?

A Dynamic AABB Tree is a binary search algorithm for fast overlap testing. Dynamic AABB trees are good for general purpose use, and can handle moving objects very well. The data structure provides an efficient way of detecting potential overlap between objects. DAABBCC does not contain narrow-phase collision detection.

You can use it whenever precise collision manifold(narrow-phase) is not required.

Installation

You can use the DAABBCC in your own project by adding this project as a Defold library dependency.
Open your game.project file and in the dependencies field under project add:

https://github.com/selimanac/DAABBCC/archive/refs/tags/v2.1.2.zip

Example

GitHub - selimanac/space-shooter-daabbcc

Release Notes

2.1.2

  • Internal Update Frequency added. Default value is set from game.project file (display.frequency).
    It is now possible to set a new internal(independent from Defold game loop) update frequency by using aabb.update_frequency().
  • Fixed #9

2.1.1

  • Table count added to query results.
  • Documentation update

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.

2.0

This is a complete rewritten version 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

1.1

Final 1.x release.

  • Updated cute_c2 version to 1.05

1.0

Initial release.

15 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?