15. Combining Collision Shapes

[[programvideogames]]In this lecture we cover using the fractal code cycle method to combine our tile-sized collision shapes into larger ones.

This allows us to have larger levels with more entities without having to worry about performance.

It also means we can separate the concept of tiles and collision shapes.

I've made a few changes to our setup. The camera zoom is now adjusted to 1 so we can see all of our level geometry, and I'm rendering our tiles as orange lines instead of white squares with gray outlines. This gives us a clearer view of what we're working with.

Our goal today is to optimize our collision detection. Currently, we're checking against hundreds of individual tile squares, which isn't efficient, especially when we start adding more entities and projectiles. We don't want to be testing against squares that are far from our player or entities.

So, we're going to combine these smaller squares into larger rectangles. This will significantly reduce the number of collision checks we need to perform.

Let's start by thinking about our inputs and desired outputs. Our input is these collision objects - all these small squares. Our output should be a set of larger rectangles that efficiently encompass these squares.

Here's an important observation: in our solid_tiles array, the tiles are stored sequentially along the x-axis, then wrapping to the next line. This means that adjacent tiles in memory are also adjacent on the x-axis, unless we're wrapping to a new line.

With this in mind, here's our strategy:

1. Loop through every tile.
2. Start with a "dummy" rectangle matching our first tile.
3. For each subsequent tile, check if it's directly adjacent to our current rectangle.
4. If it is, expand our rectangle to include it.
5. If it's not (either due to a gap or wrapping to a new line), finalize our current rectangle and start a new one.

Let's implement this. First, we'll create a new dynamic array called 'solid_tiles' using the temporary allocator:

solid_tiles := make([dynamic]Rect, context.temp_allocator)

Now, let's loop through our tiles, creating these wide rectangles:

wide_rect := solid_tiles[0]
wide_rects := make([dynamic]Rect, context.temp_allocator)

for i in 1..< len(solid_tiles) {
    rect := solid_tiles[i]

    if rect.x == wide_rect.x + wide_rect.width {
        wide_rect.width += TILE_SIZE
    } else {
        append(&wide_rects, wide_rect)
        wide_rect = rect
    }
}

append(&wide_rects, wide_rect)

Great, now we've got our wide rectangles. This is already much better - we've significantly reduced the number of objects we're checking against for our physics!

But we can do even better. Our next step is to combine these wide rectangles vertically. To do this efficiently, we need to sort our wide rectangles. We'll sort first by x-position, then by y-position. This ensures that rectangles that can be combined vertically will be adjacent in our array:

slice.sort_by(wide_rects[:], proc(a, b: Rect) -> bool {
    if a.x != b.x do return a.x < b.x
    return a.y < b.y
})

Now that our rectangles are sorted, we can combine them vertically using a similar process to our horizontal combination:

big_rect := wide_rects[0]

for i in 1..<len(wide_rects) {
    rect := wide_rects[i]

    if rect.x == big_rect.x && big_rect.width == rect.width && big_rect.y + big_rect.height == rect.y {
        big_rect.height += TILE_SIZE
    } else {
        append(&gs.colliders, big_rect)
        big_rect = rect
    }
}

append(&gs.colliders, big_rect)

And there we have it! We've successfully consolidated our collision objects into larger rectangles. This is going to help with performance a lot, especially as we add more complex elements to our game.

Before we wrap up, let's clean up our code a bit. We'll remove the global state for the arrays we no longer need, and update our physics update function to use our new colliders:

physics_update(gs.entities[:], gs.colliders[:], dt)
behavior_update(gs.entities[:], gs.colliders[:], dt)

We'll also update our drawing code to use the new colliders:

for rect in gs.colliders {
    rl.DrawRectangleLinesEx(rect, 1, rl.ORANGE)
}

for rect in gs.colliders {
    rl.DrawRectangleRec(rect, {255, 255, 255, 40})
}

Anywhere solid_tiles was used is now colliders.

safety_check: {
    _, hit_ground_left := raycast(pos + {0, size.y}, DOWN * 2, gs.colliders[:])
    if !hit_ground_left do break safety_check

    _, hit_ground_right := raycast(pos + size, DOWN * 2, gs.colliders[:])
    if !hit_ground_right do break safety_check

    // ... rest of the safety check code remains the same
}

That's it for this lecture. We've significantly optimized our collision detection by consolidating our small tile squares into larger rectangles. This will make our game run much more efficiently, especially as we add more entities and complexity.

In our next lecture, we'll be improving the visuals by implementing actual tile graphics instead of these colored rectangles. While the underlying mechanics are crucial, the visual aspect is also important for player engagement.

Thanks for joining me today, and I'll see you in the next one!