Lisp Game Jam Log #5

Screenshot showing a game with several items and characters. Each item and character has a colored box highlighting it. Not as much progress today, since I had to work. But I did managed to implement broad phase collision detection (BPCD) between entities and tiles. BPCD is a quick first pass to narrow down the number of possible collisions that need to be tested more carefully. In this case, I’m looking for tiles that are near enough to an entity that there might possibly be a collision.

Full-featured physics engines often use spatial hashing for BPCD, but since tiles are laid out in a fixed grid, I can find nearby tiles by converting the entity’s bounding box from worldspace coordinates (pixels) into tilespace coordinates (row/column).

I programmed a simple debug overlay to visualize the results. In the screenshot above, each entity’s bounding box is highlighted in red, and tiles that were detected during BPCD are highlighted in green. Empty air tiles are omitted from BPCD because they have their nonsolid property set to true, which means they don’t need to be considered at all during collision detection.

Eventually I will need to do collision detection between entities and other entities. I can’t use the tilespace coordinates trick for that, since entities aren’t arranged in a grid. But, I expect there to be fewer than 20 entities in the game simultaneously, so for BPCD I can probably get away with brute force, simply iterating through every entity. If that turns out to be too slow, I could do some crude spatial partioning, organizing the entities into 50-by-50-pixel bins.

There is still the matter of narrow phase collision detection, where I check each entity’s precise shape against the precise shape of the tiles. Because some tiles have different shapes (slopes, half-height, etc.), it is not enough just to check whether the bounding boxes intersect.

And after narrow phase collision detection, I’ll need to respond to the collision, by adjusting the entity’s position and velocity so it won’t pass through solid tiles. And, some collisions will need to trigger gameplay actions (e.g. a player colliding with a coin would cause the player to take the coin). As mentioned in the last post, I’m pretty sure I would have saved time by using a prebuilt physics engine, but at least I’m gaining experience!