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

[selimanac]

@totebo

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.

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

@totebo

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.

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…

[totebo]

@selimanac

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

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.

[selimanac]

@totebo

If you wanted to verify physics collection server side, Bump or HC would be viable options.

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.

[totebo]

@selimanac

the best way to handle a game on the server side is to use a headless build of Defold

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

[selimanac]

@totebo

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

Defold project builder manual

[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.

[Alex_8BitSkull]

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.

[selimanac]

@Alex_8BitSkull

Defold built-in system for really basic crowd

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.

@Alex_8BitSkull

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

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.

@Alex_8BitSkull

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.

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?

[Alex_8BitSkull]

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!

@selimanac

Most important question is what is your deadline for project?

Mid-2025 earliest

[selimanac]

@Alex_8BitSkull

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

Let me think about this for a while… I’m currently working on a similar project which includes separation using AABBs, and I’m handling all my separation code in C/C++. Maybe I can make it a separate extension for your case.

[roccosaienz]

I have a (maybe stupid) question. I am reading the online documentation of the extension. In many places I find something like

local group_id = daabbcc.insert_aabb(group_id, x, y, width, height, collision_bits.PLAYER)

should this be

local aabb_id = daabbcc.insert_aabb(group_id, x, y, width, height, collision_bits.PLAYER)

? I mean, the return value is an aabb_id and not a group_id, isn’t it? Or am I missing something?

[selimanac]

@roccosaienz

? I mean, the return value is an aabb_id and not a group_id, isn’t it? Or am I missing something

You’re right. I recently updated the docs, so I must have messed this up. Sorry about that—I’ll fix it.
You can check the return value type in the ‘Returns’ section of this function.

@roccosaienz

In many places

I just find it at this one: AABBs · selimanac/defold-daabbcc Wiki · GitHub
Could you let me know where else I might have made a typo?

[roccosaienz]

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

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.

Thank you for your work with this extension!

[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.