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

[selimanac]

@roccosaienz

I have found the same issue for: daabbcc.insert_aabb and daabbcc.insert_gameobject.

Thank you; I fixed those typos

@roccosaienz

Another question. It seems to me that the query methods return nil also for count when there is no collision. Should it be better to return count = 0? Of course, this is not important at all.

You’re right; it should actually return 0. I’ll check it now

[selimanac]

@roccosaienz

Another question. It seems to me that the query methods return nil also for count when there is no collision. Should it be better to return count = 0? Of course, this is not important at all.

I recently updated the entire library and missed that. I’ve updated the v3.x branch with the fix. Counts should return 0 now for all queries and raycast results.

[Pawel]

Thank you for this extension!

I’m testing it now and it’s super easy to check for collisions with AABBs and check raycasts! Here’s a super quick example of using one area to change character’s acceleration and friction!

Blue AABB marks an area, where character behaves like on ice
Red is character’s AABB.
Yellow is character’s velocity.

[roccosaienz]

Hi @selimanac

I would be interested in having an aabb linked to the world_position of a game object. Indeed I have an animated hierarchy of game objects and I need an aabb tracking a game object that is not the root of the hierarchy. (I hope this make sense).

Do you think you could implement this? If this is not possible, I will change the design and track the root of the hierarchy.

Thank you in any case! And thank you for this amazing extension!

Ciao!

[selimanac]

@roccosaienz

I would be interested in having an aabb linked to the world_position of a game object. Indeed I have an animated hierarchy of game objects and I need an aabb tracking a game object that is not the root of the hierarchy. (I hope this make sense).

If I understand correctly, you want me to use get_world_position instead of get_position for AABBs, right?

Do you want to use the world position for every game object or just some? I think I can handle both cases by adding an optional boolean (world or local) to insert_gameobject and new_group. Does this work for you?

This should be easy to add, maybe today or within the next couple of days.

[roccosaienz]

@selimanac Thank you for your kind answer!

Yes, I need get_worid_position instead of get_pposition. Not for every game object, just for some of them. So I would say that a boolean in insert_game_object would be perfect.

I hope this does not create performance problem…

Thank you again!

[selimanac]

@roccosaienz

Yes, I need get_worid_position instead of get_pposition. Not for every game object, just for some of them. So I would say that a boolean in insert_game_object would be perfect.

I’ve updated the v3.x branch with an optional get_world_position.
I haven’t updated the documentation yet; I’d like you to try it first. If it works for you, I’ll proceed with updating the docs.

The last argument of aabbcc.insert_gameobject is now a optional get_world_position flag (boolean: true/false). The default value is false.

local aabb_id = daabbcc.insert_gameobject(group_id, go_url, width, height, collision_bits.ENEMY, true)
-- OR , if you are not using collision bits:
local aabb_id = daabbcc.insert_gameobject(group_id, go_url, width, height, nil, true)

@roccosaienz

I hope this does not create performance problem…

I don’t think so; the impact should be minimal. C/C++ is incredibly fast, so I’m not too concerned about these kinds of condition checks.

[roccosaienz]

@selimanac Thank you soooo much!

The option flag seems to work fine for me! Great!

[goeshard]

I posted a new thread that I should have posted here but didn’t:

Looking for help with daabbc library

I have a collision module local M = {} local collision_bits = { PLAYER = 1, -- (2^0) GROUND = 2, -- (2^1) } local tile_width = 16 local tile_height = 16 function M.init() M.static_group = daabbcc.new_group(daabbcc.UPDATE_INCREMENTAL) M.dynamic_group = daabbcc.new_group(daabbcc.UPDATE_FULLREBUILD) M.player_aabb_id = nil M.ground_data = {} end function M.add_tilemap(tilemap_url, layer) local x, y, w, h = tilemap.get_bounds(tilemap_url) for row = y, y +…

[selimanac]

@selimanac

About collision resolution using DAABBCC

It is possible to add basic collision resolution(aka manifold generation) to this library for resolving contact points, depth, side, normal, etc. The first version of this library actually included this feature . However, it was poorly designed, and since no one was using it, I decided to remove it.

If your project has a serious need for collision resolution, I can reintroduce it with a better design. Please let me know about your requirements and your project.

Almost ready! I’m quite happy with the results this time.

[selimanac]

v3.0.1 released

Release notes: v3.0.1 Released! · selimanac/defold-daabbcc · Discussion #13 · GitHub

Basic platformer example using new manifold generation is on the way…

[goeshard]

I have a system worked out now that’s quite improved from what I originally posted here but I’ll have to look at yours and see what I can learn from it. My approach works only because I tried different things until it worked but its most likely very imperfect.

[roccosaienz]

Hi @selimanac , thank you for your amazing work with this extension.

I am using a sort query to get the closest aabb_id’s to a given point. In my situation I have many aabb_id intersecting the query aabb_id (almost all the screen), let’s say 100 aabb_id. But I only need to get the 10 (say) closest aabb_id, not all 100.

Could it be possible to implement a special function for such a query? Or an optional parameter to an existing function? With the actual API I need to set a high max query result count; but it seems to me that I am wasting a lot of time by sorting 100 aabb_id to just use very few of them.

Of course I may be wrong and sorting all 100 aabb_id’s is not time consuming at all; I am not an expert of sorting algorithm.

I hope I have been clear enough and what I wrote does make sense…

Thank you!

[selimanac]

The simple answer is that you don’t need to worry about it unless you experience a performance drop. Sorting 100 or even 1k items isn’t an issue, even in Lua. C is much faster. I wouldn’t recommend it, but handling 10k items should still be fine.

@roccosaienz

I am using a sort query to get the closest aabb_id’s to a given point. In my situation I have many aabb_id intersecting the query aabb_id (almost all the screen), let’s say 100 aabb_id. But I only need to get the 10 (say) closest aabb_id, not all 100.

The problem is figuring out which 10 items to select without sorting all 100.
You could use a trick: perform a raycast to the desired distance and sort the raycast results, or use multiple aabbs around the actual aabb. (Just suggestions—I’m not sure about your exact scenario.)

@roccosaienz

Could it be possible to implement a special function for such a query? Or an optional parameter to an existing function?

I have no idea how to approach this, and I’m not sure if it’s necessary or overkill. Do you have any suggestions?

@roccosaienz

but it seems to me that I am wasting a lot of time by sorting 100 aabb_id to just use very few of them.

Are you wasting a lot of frame time sorting 100 aabbs? Did you profile this? I’m pretty sure sorting 100 or even 1k shouldn’t be noticeable.

In the recent version (v3.0.1), I had to replace radix sort with qsort. Radix sort had been there from the beginning and is incredibly fast. Unfortunately, it’s no longer a reliable choice, so I had to swap it with qsort. If you’re noticing any performance differences between v3.0.0 and v3.0.1, this might be the cause. That said, the impact should still be minimal(unnoticeable).

[roccosaienz]

Many thanks for your complete and very clear explanation.

The game I am trying to develop is always at the 60fps limit. So I am very cautious and increasing the max query result limit from 32 to 100 seemed like a dangerous move.

What you tell reassures me!

I apologise for wasting your time. That is the only time wasted, not the one by the CPU

[selimanac]

@roccosaienz

The game I am trying to develop is always at the 60fps limit. So I am very cautious and increasing the max query result limit from 32 to 100 seemed like a dangerous move.

It is hard to say for sure, and suggesting numbers is a risky move for me. There are lots of things going on in your game logic which I don’t know.

I tested using Defold BunnyMark before, with 6k sprites and nearly 500 collisions per game object at 60 FPS (on my setup, of course). But this does mean nothing. It is just for fun.

https://x.com/selimanac/status/1843187723059990985

@roccosaienz

I apologise for wasting your time. That is the only time wasted, not the one by the CPU

No worries. I’d be glad to help. I’m not sure what to do to handle this situation right now, but if it causes a problem in the future, please let me know

[selimanac]

Testing daabbcc3D

daabbcc3d-test

[selimanac]

Ray-casting is ready.

bullet1

[selimanac]

This was supposed to be a basic daabbcc3D example(and test project), but I can’t stop myself from adding more stuff!

daabbcc3d test

[Alex_8BitSkull]

I think the community is desperate for more good 3D examples, so you should keep going!