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

v3.0 released

Special thanks to 8BitSkull for his support with DAABBCC.

Discussions & Release Notes

Documentation

14 Likes

Wonderful work! Implemented in my current project and appears to be working great. :partying_face:

The migration document is missing one line:

Replace all aabb.query_sort() to daabbcc.query_aabb_sort()

I would have made the change myself but couldn’t see an edit button.

5 Likes

I got error:

Max Query Result Count reached: 32

I guess this means one single query yielded >32 results? Can this max limit be changed somehow? If no, or if it’s a bad idea, can I choose how it is handled perhaps? I can imagine some circumstances where I don’t want this to cause an error, but rather stop listing query results when it exceeds 32.

Yes, of course. You can set the value in the game.project file. You can fine-tune the optimum value.

It is not a bad idea. You can go over those numbers, no problem.

this error is just a text; it shouldn’t cause a crash or problem.
You have to be getting nil for query? If not, please let me know.
Also, as far as I know, those error, info, and warning messages are not available in the release version, like print or pprint.

2 Likes

I am evaluating this extension for my game. I just need collision detection, so I would be fine with what the extension does.

But why should I use DAABBCC and not the built in Box2D physic engine? Is it faster? Is it lighter?

Many thanks for any help!

Ciao!

1 Like

We can simply say that this is a small part (only the broad phase) of Box2D.

Most physics engines I know have two phases: broad phase and narrow phase. The broad phase quickly checks for potential overlaps, usually using structural data (like trees), and it’s fast.

If the broad phase detects overlaps, then the narrow phase takes over, using the broad phase results to generate detailed manifolds. This phase is more computationally expensive (and slower).

Physics engines also perform many calculations (mass, force, friction, etc.) to simulate real-world physics accurately. Even if you’re only using it for simple collision checks, it generates a type of rotatable polygon, which can also be quite resource-intensive.

Since this is just a small part of Box2D, we can say yes. But Box2D isn’t that large when compiled, so we’re talking about kilobytes here. I don’t know the exact size difference, as I haven’t measured it because it wasn’t a major concern for me.

If the broad phase alone is sufficient for your needs, then yes. There are simply fewer calculations involved, so you benefit from less costly operations, which can improve speed and allow for more collision objects. And, since it’s only a small part of Box2D, it also uses less memory.

I can’t answer this question for you since I don’t know your specific requirements or where you plan to use it. You might not even need a library for this purpose.

Many people use Box2D because it’s a built-in solution in almost every engine. IMHO, it’s often unnecessary to use a complex physics simulation engine for most 2D game genres, as it can be a poor use of resources.

Finally, there was no Box2D on the C64, Amiga, or even in early PC games. Those developers handled collisions with elegant and often very simple methods because they had limited resources. So why don’t we? This approach gives you more room to polish your game, add more entities, and optimize overall performance.

4 Likes

Thanks! Your answer is crystal clear! I will definitely try DAABBCC! The build size is not a problem at all for me but I am very interested in having many colliding objects.

Thank you very much for your work with this extension!

Ciao!

1 Like

Maybe @Alex_8BitSkull would like to share his thoughts on this, as he managed many colliding objects in Void Scrappers and Bore Blasters.

3 Likes

I am pretty naive when it comes to optimisations, yet I consistently opt to develop very performance intense games. This is because I stand on the shoulder of giants like the Defold devs or extension makers like Selim :slight_smile:

There have been bottlenecks, but DAABBCC is not one of them! I have hundreds (if not thousands) of colliding objects at a time. If you have lots of collisions and performance is a consideration, then I would use DAABBCC. Like Selim says, many games don’t actually need super elaborate collision handling.

3 Likes

Thank you! Yes, Defold is awesome!

During the search for a publisher for our first game on Switch; they always suggested us to use Unity for the next game since it is the industry standard. I learnt Unity but it has always been a pain to use it… After one year I gave up and returned to Defold.

6 Likes

This might be obvious, but one main consideration when choosing between this library and Box2D is whether you need rotated objects. As far as I understand it, AABBCC work with non rotated rectangles only.

Two other Lua solutions could be Bump (non rotated objects only, but with collision resolution) and Hardon Collider, which allows rotated objects (circle, rectangle or point) and basic collision resolution.

1 Like

This is not a missing feature of this library; in general, AABBs(rectangles) cannot be rotated. This is why AABB’s cheap to use.

I rather use box2D if I have to. C/C++ solutions always be faster.
There are also relatively simple methods for basic collision resolution, such as using raycasting or comparing the positions and/or rotations (directions) of two game objects etc…

5 Likes

Yes I agree it’s not a missing feature, just the way it works! Which is an important difference to be aware of when deciding to use it or not.

I also agree it makes sense to use Box2D in a lot of cases. But there are some cases where it might be better to use a Lua library. One example is a Defold multiplayer game using Namama. Box2D isn’t natively supported by Nakama, but Lua libraries can be used (with some limitations). If you wanted to verify physics collection server side, Bump or HC would be viable options.

2 Likes

Nice to know that.
I don’t know the details of Nakama, but I thought the best way to handle a game on the server side is to use a headless build of Defold. Minimizing memory and CPU consumption is very important on the server side. This is why I added the update frequency function to this library.

Going a little off topic here but, yes! That would be amazing. Is this technically possible? Running a headless version of Defold, that is.

Using bob, yes… You can specify build -variant as debug, release or headless version of dmengine

3 Likes

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.

1 Like

:raising_hand_man:

This might be useful for me…! I am currently using the Defold built-in system for really basic crowd management (units jostle each other for position). They all also already have AABB entries however for the combat aspect.

Looking at my current script, all I use is the normal and distance.

I don’t know how you would design it. Can it be made optional? I wouldn’t want it to negatively impact the performance of basic collision detection, because most times I don’t need these variables.

2 Likes

Could you elaborate a bit more? What do you mean by a built-in system? I’m mostly using very basic separation, and it works pretty well; something like this: x.com . I don’t know if this suits your project but I can share the resources if you like.

What do you mean by distance?
Distance has a different meaning here. Manifold generation only occurs when two AABBs collide, which is very similar to a built-in Collision messages in Defold
Otherwise you have to calculate the distance.

Yes, this is exactly what I’m thinking. I thought about making it optional since it’s a somewhat expensive operation.

Most important question is what is your deadline for project? :smiley:

What I mean by using the built-in system is that I am using collision objects in Defold:

I then set a physics listener and run this script to apply accumulated adjustments:

local CONTACT_POINT_EVENT = hash("contact_point_event")
local PLAYER = hash("player")
local UNIT = hash("unit")
local OBSTACLE = hash("obstacle")

local crowd_adjustments = {}
local crowd_positions = {}

local function accumulate_crowd_adjustments(id, position, offset)
	if not crowd_adjustments[id] then
		crowd_adjustments[id] = vmath.vector3(0, 0, 0)
	end
	crowd_adjustments[id] = crowd_adjustments[id] + offset
	crowd_positions[id] = position
end

local function apply_crowd_adjustments()
	for id, adjustment in pairs(crowd_adjustments) do
		go.set_position(crowd_positions[id] + adjustment, id)
	end
	crowd_adjustments = {}  --clear adjustments after applying
	crowd_positions = {}
end

local function perform_crowding(data, data_other, distance)
	--player exceptions (don't collide with units, but respect obstacles)
	if data.group == PLAYER then
		if data_other.group ~= OBSTACLE then
			return
		end
	end
	--obstacle exceptions (only collide with other obstacles)
	if data.group == OBSTACLE then
		if data_other.group ~= OBSTACLE then
			return
		end
	end

	if data_other.group == OBSTACLE then
		--complete and immediate adjustment for obstacles
		accumulate_crowd_adjustments(data.id, data.instance_position, data.normal * distance)
	else
		--gradual adjustment for crowding
		accumulate_crowd_adjustments(data.id, data.instance_position, data.normal * distance * 0.25)
	end
end

local function physics_callback(self, event, data)

	if event == CONTACT_POINT_EVENT then
		perform_crowding(data.a, data.b, data.distance)
		perform_crowding(data.b, data.a, data.distance)
	end

end

function init(self)
	physics.set_listener(physics_callback)
end

function update(self, dt)
	apply_crowd_adjustments()
end

function final(self)
	crowd_adjustments = {}
end

The end result is something similar to the video you linked!

Mid-2025 earliest :joy: