Looking for help with daabbc library

[goeshard]

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 + h - 1 do
        for col = x, x + w - 1 do
            local tile_index = tilemap.get_tile(tilemap_url, layer, col, row)
            if tile_index == 17 then -- ground tile hard coded?
                local tile_x = (col - 1) * tile_width
                local tile_y = (row + 0.22) * tile_height -- these modifiers are what got the debug lines drawn in the correct place (shrug)
                local aabb_id = daabbcc.insert_aabb(M.static_group, tile_x, tile_y, tile_width, tile_height, collision_bits.GROUND)

                M.ground_data[aabb_id] = { type = "GROUND", x = tile_x, y = tile_y, width = tile_width, height = tile_height }

            end
        end
    end
end

function M.add_player(player_url, player_width, player_height)
    M.player_aabb_id = daabbcc.insert_gameobject(M.dynamic_group, player_url, player_width, player_height, collision_bits.PLAYER)
end

local function debug_draw_aabb(aabb_data, color)
    for _, data in pairs(aabb_data) do
        local x, y = data.x, data.y
        local width, height = data.width, data.height

        msg.post("@render:", "draw_line", { start_point = vmath.vector3(x, y, 0), end_point = vmath.vector3(x + width, y, 0), color = color })
        msg.post("@render:", "draw_line", { start_point = vmath.vector3(x, y, 0), end_point = vmath.vector3(x, y + height, 0), color = color })
        msg.post("@render:", "draw_line", { start_point = vmath.vector3(x + width, y, 0), end_point = vmath.vector3(x + width, y + height, 0), color = color })
        msg.post("@render:", "draw_line", { start_point = vmath.vector3(x, y + height, 0), end_point = vmath.vector3(x + width, y + height, 0), color = color })
    end
end

function M.debug_draw(player_pos)
    debug_draw_aabb(M.ground_data, vmath.vector4(1, 0, 0, 1))
    debug_draw_aabb({ { x = player_pos.x - 46 / 2, y = player_pos.y - 54 / 2, width = 46, height = 54 } }, vmath.vector4(0, 1, 0, 1))
end

function M.query_player()
    local result, count = daabbcc.query_id(M.static_group, M.player_aabb_id, collision_bits.GROUND)
    return result, count
end

return M

You can visualize what’s going on here.

I found it really strange that the only way I could get the debug lines drawn in the correct place was if I added random 0.22 here

local tile_y = (row + 0.22) * tile_height

And it’s unfortunate that the player assets has a lot of extra space because I don’t think I can draw a more precise collision box using insert_gameobject, but these really are secondary issues.

The bigger issue is that collisions are being detected regardless of where the player is on the map. For instance in the picture, even though he is in the air, he has ground contact.

function check_collisions(self)
    local query_result, result_count = collision.query_player()
    if query_result then

        for i = 1, result_count do
            local aabb_id = query_result[i]
            local data = collision.ground_data[aabb_id]
            if data then
                print(string.format("Collision with %s at (%d, %d)", data.type, data.x, data.y))
                if data.type == "GROUND" then
                    self.velocity.y = 0
                    self.ground_contact = true
                end
            else
                print("Unknown collision!")
            end
        end
    end
end

It detects three collisions, even though the player is in the air. As far as I can tell it detects collision no matter where the player is on the map.

DEBUG:SCRIPT: Collision with GROUND at (0, 35)
DEBUG:SCRIPT: Collision with GROUND at (16, 35)
DEBUG:SCRIPT: Collision with GROUND at (16, 19)

I know that this is probably an error on my part. But I’m not sure what could be going on.

I’d appreciate any insight from someone with more experience on this library.

[goeshard]

Update:

I realized that I don’t need different groups for static and dynamic. I’m not sure how that got into my head. I replaced both groups with one group, M.group

It’s starting to be what you would expect but

It looks like I need to figure out a technique to correct the distance traveled into the collision.

If I’m not mistaken, these are the distances is that correct?

pprint(query_result)

{ --[[0x787002ba1b60]]
  1 = 321,
  2 = 315,
  3 = 319,
  4 = 317
}

There is four of them because my player box is overly wide and occupies four tiles. In the default Defold approach, there is a “normal” that it used.

[selimanac]

@goeshard

It looks like I need to figure out a technique to correct the distance traveled into the collision.

Generally, you don’t need to. You can simply stop moving your object in the current direction when a collision occurs. This approach is simple and sufficient for most cases.
You can get direction from movement or using raycasts

Raycast

Another approach might be using Tile Raycast and combining it with DAABBCC:

GitHub - selimanac/defold-tile-raycast: Ray Casting in tiled worlds using DDA...

There is a example of it:

GitHub - selimanac/defold-tile-raycast-platformer

@goeshard

If I’m not mistaken, these are the distances is that correct? There is four of them because my player box is overly wide and occupies four tiles.

No, they are not. They are overlapping AABB IDs. In your case you are hitting 4 tiles.

Queries

More info about what is this lib and not:

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

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 calcu…

@goeshard

In the default Defold approach, there is a “normal” that it used.

There is no collision resolution (e.g., normals) in this library. It is an expensive process, and I am considering implementing it as an optional feature.

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

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 …

[goeshard]

@selimanac

Generally, you don’t need to. You can simply stop moving your object in the current direction when a collision occurs. This approach is simple and sufficient for most cases.
You can get direction from movement or using raycasts

I see. What made me assume that it worked similarly to the default Defold way is how the point it stops at is different on every jump.

@selimanac

No, they are not. They are overlapping AABB IDs. In your case you are hitting 4 tiles.

That makes sense. It’s a good thing I asked. I would have wasted time thinking otherwise.
Actually, it was this page of the wiki that refers to distances which is where I got that confusion from.

Queries

@selimanac

Another approach might be using Tile Raycast and combining it with DAABBCC

I will study this example and see if that helps.

Thanks for the response.

[goeshard]

What is it about a platformer that makes you want to use a combination of the tile-raycast lib and the aabb lib? It seems to me like the aabb should have everything it needs to stop one aabb from moving into another aabb, yet I can’t get that effect.

[selimanac]

@goeshard

What is it about a platformer that makes you want to use a combination

It is a choice. Alternative way of handling many tiles.

@goeshard

It seems to me like the aabb should have everything it needs to stop one aabb from moving into another aabb, yet I can’t get that effect.

This library has nothing to do with stopping anything. It’s up to you to handle movement and stopping objects.

I’m not sure how you manage collisions, but your dt or speed might be so large for a single frame time. You can simply set the position to the upper bound of the tile before applying the actual position to the moving gameobject.

If you want to dig in, I have an very old example here. It’s not updated and might not work with the latest version of the library. Additionally, it doesn’t use tiles like you do, but it might give you an idea.

GitHub - selimanac/DAABBCC-Platformer: Custom collision detection example with...

https://selimanac.itch.io/daabbcc-platformer

[goeshard]

@selimanac

This library has nothing to do with stopping anything. It’s up to you to handle movement and stopping objects.

I’m not sure how you manage collisions, but your dt or speed might be so large for a single frame time. You can simply set the position to the upper bound of the tile before applying the actual position to the moving gameobject.

I see what you mean. I’ll think about it.

I might just go back to the branch where I’m using the default collision handling so that I can just keep building the game instead of thinking about underlying systems.

But it’s going to bother me. This is the second time I’ve come back to your library wanting to figure it out, and I got farther than last time. But it’s difficult to justify staying stuck on the same problem when I could go back to the other way. But it keeps popping back into my head, because that way is not perfect.

[selimanac]

I’ll try to develop a simple example when I got time.
I think @Pawel is working on something for platformers but I’m not sure what he is using for collisions. Maybe he might help you better than me.
https://x.com/WitchcrafterRPG/status/1863386145356169561

[Pawel]

Ok, so it’s time to warm up my rusty fingers, I see

For the player character or maybe some bosses I do 3 steps, for rest of stuff only 1. point:

1. Check aabbs overlaps.
2. If aabb overlap occurs with ground, I do additional raycast (I do in 8 directions, but 4 is enough most of the time), but raycast is whole inside AABB.
3. If there is a raycast detection it means I penetrated some amount inside, so I do another raycasts, shorter and shorter until I don’t have any match. During each check I accumulate the penetration distance.

The code might be refactored still, especially the penetration calculation - in the end I can store all the data I need, center points of aabbs and their sizes, so raycasts might be totally not needed, but this is so fast now, so I don’t care for now.

local function check_ground_raycasts(self)
-- Check for more precise collisions with walls using raycasts
for _, DIR_BIT in pairs(collision_directions) do
	if not self.collisions[GROUND][DIR_BIT] then
		local result, matched = aabb.raycast(self.position, DIR_BIT, self.size.x, self.size.y, GROUND)
		if matched and matched > 0 and result then
			self.collisions[GROUND][DIR_BIT] = self.collisions[GROUND][DIR_BIT] and math.max(self.collisions[GROUND][DIR_BIT], 1) or 1
			local penetration = 0
			while matched do
				result, matched = aabb.raycast(self.position, DIR_BIT, self.size.x - (penetration*2), self.size.y - (penetration*2), GROUND)
				if matched and matched > 0 and result then
					penetration = penetration + 1
				end
			end
			self.collisions[GROUND][DIR_BIT] = math.max(self.collisions[GROUND][DIR_BIT], penetration)
		end
	end
end 
end

Above are the raycast checks so steps 2. and 3.

This is step 1. that uses it:

function M.get_all(self)
-- Check all AABBs collisions
local collisions, count = aabb.query(self.aabb_id)
self.collisions[GROUND] = {}

-- Initially set all direction for ground detection to false
for _, DIR_BIT in pairs(collision_directions) do
	self.collisions[GROUND][DIR_BIT] = false
end

-- Handle different types of collided AABB
if count and count > 0 and collisions then
	for i = 1, count do
		if aabb.get_group(collisions[i]) == GROUND then
			check_ground_raycasts(self)
		end
	end
end

return self.collisions
end

collision_directions are bits associated with direcitons, e.g. UP = 0x01, UP_LEFT = 0x02, LEFT = 0x04, and so on.

I store all information about collisions that happened in this update() call in (self.collisions)

self.collisions[GROUND][SOME_DIR] will store in case of raycasts penetration values, so I use them in movement module, to correct the player position, when penetration happens. Of course in other parts of movement code, I reset velocity and acceleration in this direction, but correction must happens, if you don’t want player to be stuck “inside” ground.

Here is e.g. my horizontal correction:

local function horizontal_position_correction(self, dt)
	local ground_coll = self.collisions[config.physics.group.GROUND]

	local position_x = self.position.x

	local penetration = ground_coll[DIR.UP_LEFT] or ground_coll[DIR.DOWN_LEFT] or ground_coll[DIR.LEFT]
	if penetration and penetration > 1 then
		position_x = position_x + penetration
	end

	penetration = ground_coll[DIR.UP_RIGHT] or ground_coll[DIR.DOWN_RIGHT] or ground_coll[DIR.RIGHT]
	if penetration and penetration > 1 then
		position_x = position_x - penetration
	end

	return position_x
end

As a side effect, because I do it in 8 directions, it allows to also correct player’s position when walking on small “stairs”

That’s just my approach

I calculate corrections, apply velocity (that is affected by acceleration - user input) and then at the end also round values to integers:

function M.calculate_position(self, dt)
	self.position.x = horizontal_position_correction(self, dt)
	self.position.y = vertical_position_correction(self, dt)

	-- Calculate new position based on established velocity
	self.position = self.position + self.velocity * dt

	-- Round position to nearest integer
	self.position.x = defmath.round(self.position.x)
	self.position.y = defmath.round(self.position.y)

	return self.position
end

[selimanac]

@Pawel

If there is a raycast detection it means I penetrated some amount inside, so I do another raycasts, shorter and shorter until I don’t have any match. During each check I accumulate the penetration distance.

Hmmm. I guess I should add the manifold generation now. It might make things easier.

[goeshard]

Wow I wish that I came back here to read this sooner. Yesterday I bashed my head into the wall trying to get it perfect with just overlap testing.

I switched to using the sort variant of query so I could get the closest collision.

function M.query_player()
    local result, count = daabbcc.query_id_sort(M.group, M.player_aabb_id, collision_bits.GROUND)
    return result, count
end

This handles most of the collision.

function check_collisions(self, pos)
    local query_result, result_count = collision.query_player()

    if not query_result and (self.wall_contact_left or self.wall_contact_right) then
        print("No query result")
        self.wall_contact_left = false
        self.wall_contact_right = false
    end

    if query_result and result_count > 0 then
        local first_collision = query_result[1]
        local aabb_id = first_collision.id
        local data = collision.ground_data[aabb_id]

        if data and data.type == "GROUND" then
            local y_offset = 18
            local x_offset = 15.01
            local tile_top = data.y + data.height
            local tile_bottom = data.y
            local tile_left = data.x
            local tile_right = data.x + data.width

            -- Check for above and below collisions
            local is_above_tile = pos.y >= tile_top
            local is_below_tile = pos.y + (54 / 2) < tile_bottom
            local is_right_of_tile = pos.x - (46 / 2) < tile_right and pos.x > tile_left
            local is_left_of_tile = pos.x + (46 / 2) + 1000000 > tile_left and pos.x < tile_right


            -- Handle collision from above (landing)
            if is_above_tile then
                -- print("Hit from above")
                pos.y = tile_top + y_offset
                self.ground_contact = true
                msg.post("/camera#controller", "follow_player_y", { toggle = false })
                self.velocity.y = 0

            -- Handle collision from below
            elseif is_below_tile then
                -- print("Hit from below")
                pos.y = tile_bottom - (y_offset * 2)
                self.velocity.y = 0
                self.is_jumping = false

            -- Handle left collision
            elseif is_right_of_tile then
                -- print("Hit from the left")
                pos.x = tile_right + x_offset
                self.velocity.x = 0
                self.wall_contact_left = true

            -- Handle right collision
            elseif is_left_of_tile then
                -- print("Hit from the right")
                pos.x = tile_left - (x_offset * 2) - 1
                self.velocity.x = 0
                self.wall_contact_right = true
            end
        else
            print("Unknown collision!")
        end
    end
    
    return pos
end

This mostly works but due to the way the collision is handled, it causes oscillating self.wall_contact_* values which has a variety of undesired effects for my game.

So it came to me when I woke up this morning that a combination of raycasting and overlap testing would do the trick.

function M.raycast_player(player_pos, sprite_flipped, max_distance)
    local player_height = 54
    local direction = sprite_flipped and -1 or 1

    local ray_offsets = {
        0,                       -- center
        player_height / 2 - 10,  -- top
        -player_height / 2 + 10  -- bottom
    }

    local results = {}

    for _, offset in ipairs(ray_offsets) do
        local ray_start = vmath.vector3(player_pos.x, player_pos.y + offset, 0)
        local ray_end = vmath.vector3(player_pos.x + direction * max_distance, player_pos.y + offset, 0)

        local result, count = daabbcc.raycast(M.group, ray_start.x, ray_start.y, ray_end.x, ray_end.y, collision_bits.GROUND)
        
        table.insert(results, {result = result, count = count, ray_start = ray_start, ray_end = ray_end})
    end

    if debug then
        local blue = vmath.vector4(0, 0, 1, 1)

        for _, ray_data in ipairs(results) do
            debug_draw_raycast(ray_data.ray_start, ray_data.ray_end, blue)

            if ray_data.count then
                for _, aabb_id in ipairs(ray_data.result) do
                    local tile = M.ground_data[aabb_id]
                    if tile then
                        debug_draw_aabb({ tile }, blue, tile_draw_x_offset, tile_draw_y_offset)
                    end
                end
            end
        end
    end

    return results
end



function M.update_wall_contact(player, player_pos)

    local raycast_results = M.raycast_player(player_pos, player.sprite_flipped, 26)

    player.wall_contact_left = false
    player.wall_contact_right = false

    for _, result in ipairs(raycast_results) do
        if result.result then
            if player.sprite_flipped then
                player.wall_contact_left = true
            else
                player.wall_contact_right = true
            end
        end
    end
end

It’s a mess but it works.

I think Pawel’s solution is more robust so I will probably study that once I run into issues with this one.

Thanks to selim for the library. It’s hard to figure out but once you do its not bad, like anything I guess.

nevermind the low quality video.

[goeshard]

This actually brings me to another question actually…

Is it possible to set a small aabb box within the gameobject?
You can see that mine is way too big.

I was considering giving the player a child gameobject that is a smaller and transparent and inserting that.

[selimanac]

@goeshard

Is it possible to set a small aabb box within the gameobject?

Sure, you can set the sizes to whatever you want. Is this what you are asking for?

AABBs - daabbcc.insert_gameobject(group_id,go_url,width,height,[category_bit])

[goeshard]

Ah nice.

But if I’m not mistaken, it’s only possible to make a smaller box oriented in the center or am I not being creative?

What if for example you need to take more off the top than off the bottom. Is it possible to set the start position of the box relative to the parent size?

[selimanac]

@goeshard

What if for example you need to take more off the top than off the bottom. Is it possible to set the start position of the box relative to the parent size?

Okay, got it now. As you suggested, you can simply add an empty GameObject for the offset (position)

[goeshard]

yeah I think that should work. Thanks again!

I wish I knew how to use this library for my last game. It was a horde game so there was too many collisions for Box2D and I had to think of terrible work arounds. That’s why I was determined to learn it this time.