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

astrochili · April 9, 2025, 7:31am

Hi,

I will make a guess that what you want to do is possible both without using Defold physics and without the manifold function in daabbbcc if you would like to use circle collicion shapes.

When two square sized units overlap, we know the positions, sizes and radii of both of them. We can simply get the distance between their centres and if the distance is less than the sum of their radii move the unit along the vector between their centres to compensate this distance.

Or is this a naive solution?

It seemed to me that circle collision shape of units is more preferable to square for more dense positioning. But if there is no need in it and square collisions are akay, it’s easier to use the manifold function in daabbcc of course, I suppose it’s written in C++ and already does its job optimally.

selimanac · April 9, 2025, 7:48am

Sure you can. If you have a (relatively) small number of circle collisions, you’re good to go. I’d like to share my experience on this:

I was working on a prototype (just for fun) using daabbcc as a broad phase and radius-based separation. I did something similar to what you described (circle collision + separation), initially using Lua:

But in the end, I had to move all the logic to C/C++. There’s a huge (and I mean huge) performance difference between using Lua (even with LuaJIT) and C/C++. I couldn’t manage to handle 200 units at the same time in Lua(of course, this might be due to my own poor implementation ) CPU usage would hit 100%. But with C/C++, I was able to handle around 500 units with only 25–30% CPU usage. Even using Box2D for this might be a better option when working with Lua(since it handles all movement/collision calculations at C).

I’m still tinkering with implementing circular manifold generation in this library…

astrochili · April 9, 2025, 8:12am

Sounds like a really good idea, it seems appropriate here, even though the library is about rectangles

Alex_8BitSkull · April 9, 2025, 8:14am

Thanks for the advice!

For me this is critical. I could do something like this manually in Lua, but this kind of many-to-many check in update() would destroy performance for me I am sure.

selimanac · April 9, 2025, 8:18am

Yeah, this is also my concern. I’m still not sure if this fits in this library or not. Also, my entire structure is based on rectangles, so it requires a lot of refactoring and testing. But I guess I’ll do it eventually anyway

astrochili · April 9, 2025, 8:22am

So in the performance comparison, did you end up with a combination of built-in physics + daabbcc to support circular shapes, or did you go with rectangles only, but all in one daabbcc system?

Alex_8BitSkull · April 9, 2025, 8:27am

I use built-in physics for positioning (unit to unit, and also tilemap collision objects for unit-to-world).

For everything else I use DAABBCC (e.g. damage, target finding, etc).

I didn’t spend a great deal of time thinking about this. I use DAABBCC wherever I can for performance purposes. Wasn’t sure how to implement positioning using DAABBCC so I used the built-in physics. Performance seemed okay, so I moved on!

goeshard · April 9, 2025, 8:38am

If only I had waited a small amount of time, I could have used your manifold detection or whatever it’s called! I ended up making a platformer with your library without it though and it was fun; definitely a learning experience.

I would share the code for how I did it, but most likely people should just do it the new way.

selimanac · April 9, 2025, 8:44am

How nice to hear that

No, please do share if it is fine for you.

I also completed a platformer example project using manifold stuff. I’m waiting for version 1.10.0 to be released, but it’s ready here:

goeshard · April 9, 2025, 9:01am

Okay, so I already shared this with selimanac privately, but here is a game that was made with daabbcc, before the manifold detection existed.

Fair warning: most people consider this game to be a rage game, so…

So the collision is handled using a combination of raycasts and overlap detection.

github.com/divSelector/GOTY-Defold

modules/collision.lua

main-daabbcc

local utils = require "modules.utils"
local state = require "modules.state"
local audio = require "modules.audio"


local M = {}

local collision_bits = {
    PLAYER     = 1, -- (2^0)
    GROUND     = 2, -- (2^1)
    PROJECTILE = 4, -- (2^2)
    ENEMY      = 8, -- (2^3)
    PASSABLE   = 16 -- (2^4)
}

M.TILES = {
    GROUND = 17,
    SPRING = 88,
    QUESTION = 33,
    INFO = 34,

This file has been truncated. show original

This is 733 lines of collision code so… while I’m not going to walk you through all of it, there’s some useful functions in there that you can just drop in and use, like drawing the aabbs for tilemap, normalizing the results from raycast and overlap so you can handle them all together.

Of course some stuff you will think, “why did he do it this way.” IDK, I did my best.

selimanac · April 9, 2025, 9:11am

Thank you, this is great work.

This applies to all of us sometimes we look back and think, ‘Why did I do it this way?’ But we all do our best.

roccosaienz · April 9, 2025, 10:38am

Loving the game!

selimanac · April 16, 2025, 6:55am

Since Defold 1.10.0 (what a great release!!) is out, I can share the source of this platformer example project.

Meanwhile, I also added Live Update to the game collection. Now at least music and sound effects are loaded after the game launches.

You should consider it a basic prototype, not something ready for production. It might contain issues, but those issues are not related to this library.

Notes:

This is not a beginner friendly project, nor is it an easy-to-use module or a plug-and-play platformer solution.
There is no upscaling support. I might add it sometime in the future. Feel free to contribute: Upscaling · Issue #1 · selimanac/defold-daabbcc-example-platformer · GitHub
It has become difficult to set up VMs on ARM macOS, and I no longer have access to Windows or Linux. So, I haven’t been able to test the project on those platforms.
I’m using a custom version of Defos because the default one wouldn’t focus (activate) borderless fullscreen on macOS. You might want to use the default one.
It’s not perfect but game is mobile friendly
Live Update(html5 bundle) feature require Defold version >= 1.10.0 because of the issue

Thanks

Special thanks to Paweł Jarosz and 8BitSkull for their support.

aikelb · April 24, 2025, 5:22pm

I’ve been trying to make the repo work on my Intel macOS laptop, but something is not working (seems to be related with the camera and , maybe?). The input, music and sfx are working, but the screen is empty.

@selimanac also mention that could be related with the newer GLFW version. I tried forcing OpenGL in the appmanifest but nothing happened. With Vulkan it just crashes.

Anyone else has the same issue?

Thanks! and great work @selimanac !

selimanac · April 24, 2025, 5:44pm

I have no idea why this happens. I’ve been using macOS since the beginning of the project, and it works fine with both OpenGL and Vulkan.

It crashes because of ImGui when Vulkan is selected. Could you please try removing ImGui?

Remove it from the dependencies:

Then Project → Fetch Libraries
Set Vulkan using manifest:

Let’s see if it works with Vulkan.

selimanac · April 24, 2025, 5:50pm

Ah, one more thing ; are you using a Retina device? I’m using the new window.get_display_scale(), but I couldn’t test its result since I don’t have a Retina screen. You can test it by setting data.window_scale = 1 manually.

Also print(window.get_display_scale()) could be useful

github.com/selimanac/defold-daabbcc-example-platformer

scripts/loading.script

17cb4af89


      
          				msg.post(const.PROXY.GAME, "async_load")
          			end)
          		else
          			print("Failed to download archive ", download_path, "from", url, ":", response.status)
          		end
          	end, nil, nil, { path = download_path })
          end
          
          function init(_)
          	data.game.is_mobile = device.mobile() or device.tablet()
          	data.window_scale = window.get_display_scale()
          
          	--  lazy way for mobile camera bounds
          	if data.game.is_mobile then
          		const.CAMERA.BOUNDS_MIN = const.CAMERA.MOBILE_BOUNDS_MIN
          		const.CAMERA.BOUNDS_MAX = const.CAMERA.MOBILE_BOUNDS_MAX
          	end
          
          	init_defos()
          
          	msg.post(const.PROXY.SCRIPT, const.MSG.LOAD_GAME)

selimanac · April 24, 2025, 6:11pm

I found my old Intel MacBook Air(none retina). The x64 bundle works if it’s Vulkan, but if it’s OpenGL…

Unfortunately, I’m not able to install Defold on this very old device to test the Editor build.

aikelb · April 24, 2025, 10:58pm

Sorry, busy afternoon.

Vulkan + removing ImGui did the trick! Also works by setting it to OpenGL & Vulkan.

print(window.get_display_scale()) is 2 on my end.

But I have no idea why it doesn’t work on OpenGL

selimanac · April 25, 2025, 6:25am

Probably because it chooses Vulkan.

Thank you. So you have a Retina display. As far as I can see from your screenshot, the camera zoom looks OK.

I have no idea either. OpenGL was deprecated a long time ago, probably starting with macOS 10.14. Apple might not be updating the old Intel graphics drivers for OpenGL anymore. So it’s better to stick with Vulkan on macOS, since it actually translates to Metal. I don’t think this problem is only related to this project (though it might be, since I have a custom render.script and shaders). You should test it with your own projects.

aikelb · April 25, 2025, 6:56am

Yeah, I know. I haven’t been able to work with Defold in the last few months -and the editor improved a lot in that time! But with so many changes, probably my projects will have some issues too. Anyway, at least now I now this is something that may help upgrading them.

Thanks for your support!