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

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

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

4 Likes

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

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

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

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

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

Wow, great release!

2 Likes

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

1 Like

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

.raycast() should receive world or local positions?

Don’t know :smiley:
it doesn’t matter in DAABBC. It just returns what you give it to it.
Except for the new Gameobject function. It gets local position (basically go.get_position). But there is GetWorldPosition() in the API so I can implement it if you need to.

1 Like

I am still testing the update, but here are my findings so far:

I am unable to build the example game project. I get a message:

/components/collections/main.collection
	The file 'null' could not be loaded.

I can’t figure out how to fix this.

Is there a difference between aabb.remove() and aabb.remove_gameobject()? The documentation implies they do the same thing.

Is gameobject position update iteration ON by default? It seems to be the case - might need to add that explicitly to docs.

I never saw this . Which example is that, build-in one or space-shooter? If space-shoter, then sprite scale9(1.3.7) can be the problem.
Let me check… I’ll let you know…

No difference at all right now.
aabb.remove_gameobject() is here for future use case.

Yes it is ON by default but it is not iterating when it is size is 0.

3 Likes

this is not related to aabbcc…
I was eager to test new sprite slice9 feature on 1.3.7 and I forgot to remove it :slight_smile: So it can’t work on 1.3.6 right now. I’m going to remove the slice9 and push it again in a while. Meanwhile, you can remove it from main.collection file using the text editor(just search for slice9, size and size_mode)

EDIT: Just removed the slice9 on git repo and it works on 1.3.6 now.

3 Likes

I can confirm this works for me now! Thank you.

@selimanac Thank you for all your work on this update.

I am driving myself crazy trying to make even a simple example work. After not being able to get the gameobject tracking to work, I reverted to the old method which I have worked with before.

The old method works for me in 2.0, but not in 2.1. I have no idea why.

This is the test. The moving square is tracked via AABB, and in update I check for collisions with the static square.

Code for gameobject tracking (does not work):


local aabb_group = nil
local static_square = nil
local moving_square = nil

function init(self)

	static_square = go.get_id("static_square")
	moving_square = go.get_id("moving_square")

	aabb_group = aabb.new_group()

	local moving_id = aabb.insert_gameobject(aabb_group, msg.url(moving_square), 100, 100)
	print(moving_id)

	go.animate(moving_square, "position", go.PLAYBACK_LOOP_PINGPONG, vmath.vector3(450,150,0), go.EASING_LINEAR, 5, 0, nil)
end

function update(self, dt)
	
	local position = go.get_position(static_square)
	local hits = aabb.query(aabb_group, position.x, position.y, 100, 100)
	if hits then
		pprint(hits)
	end
end

Old style code, which requires aabb.update() (works in 2.0, does not work in 2.1):

local aabb_group = nil
local static_square = nil
local moving_square = nil
local moving_id = nil

function init(self)

	static_square = go.get_id("static_square")
	moving_square = go.get_id("moving_square")

	aabb_group = aabb.new_group()

	moving_id = aabb.insert(aabb_group, 150, 450, 100, 100)
	print(moving_id)

	go.animate(moving_square, "position", go.PLAYBACK_LOOP_PINGPONG, vmath.vector3(450,150,0), go.EASING_LINEAR, 5, 0, nil)
end

function update(self, dt)

	local moving_position = go.get_position(moving_square)
	aabb.update(aabb_group, moving_id, moving_position.x, moving_position.y, 100, 100)
	
	local position = go.get_position(static_square)
	local hits = aabb.query(aabb_group, position.x, position.y, 100, 100)
	if hits then
		pprint(hits)
	end
end

Project is here:
aabb_gameobject_test.zip (4.7 KB)

I have to assume I am doing something silly, because your example project works.

Thanks for the help!

1 Like

I’m looking to it… looks like there is something wrong with .query
aabb.query_id works on your example by the way. I highly recommend you to use .insert as much as possible.

Is this because the iteration to update the gameobject position is costly? So for static objects that makes sense, but for objects that move (e.g. using go.animate) then presumably it should be better to use insert_gameobject rather than insert + continually doing update (which would require go.get_position)?

This is what exactly I meant to say. It is better to put static gameobjects by using aabb.insert. It saves from iteration.
For moving gameobject aabb.insert_gameobject.

1 Like

I found the problem. It is related to this and effects aabb.query and aabb.query_short

I push the fix at same 2.1 branch. Please clean your .internal folder or remove/add the extension again.

Keep on testing :slight_smile: Let me know if anything goes wrong.

3 Likes