Get out of the walls, you stupid bug!

Finally able to resume work on the game with help from my good friend Afternoon Caffeine, I tidied up a collision detection problem I was having, illustrated by the video below.

When a block is destroyed in the game, it counts down a timer until it reappears, then asks the game if it’s OK to come back. This amounts to asking whether there’s something else in the world occupying that space, and bailing out if so. It’s incredibly important to answer this question correctly, because the terrain is composed solely of its perimeter edge, and once a game entity falls into the interior of this loop shape it won’t be able to get out.

The issue is that I was trying to keep track of each game entity manually and determine if any of them overlapped a given area of space. This looks something like this:

public static bool EntitiesOverlapping(PolygonShape shape, Transform transform) {
    Manifold manifold = new Manifold();
    foreach ( IGameEntity ent in Instance._entities ) {
        Transform entTransform = IdentityTransform(ent.Position);
        PolygonShape entShape = ent.Shape;
        if ( entShape != null ) {
            Collision.CollidePolygons(ref manifold, shape, ref transform, entShape, ref entTransform);
            if ( manifold.PointCount > 0 ) {
                return true;
            }
        }
    }
    Transform playerTransform = Player.Instance.Transform;
    PolygonShape playerShape = Player.Instance.Shape;
    Collision.CollidePolygons(ref manifold, shape, ref transform, playerShape, ref playerTransform); 
    return manifold.PointCount > 0;
}

There are a couple issue with this approach. One, it’s inefficient when there are a large number of entities nowhere near the target area. Two, it only works with PolygonShapes, and then only if the entity is composed of exactly one of these shapes.

I tried to convert the code to work with axis-aligned bounding boxes (AABBs), but then I was having way too much trouble getting them to match up when the entity’s body was rotated, as happens with the beetle enemies.

If only someone would write some sort of, I don’t know, engine to manage collisions between simulated objects… Oh yeah. This code was old enough that I still was pretty unfamiliar with most of the features of Box2D when I wrote it, and didn’t know enough to let the engine do the heavy lifting for me. This is not only much faster, since Box2D uses quad trees to cull out bodies that aren’t nearby, but is much harder for me to screw up.

public static bool EntitiesOverlapping(AABB aabb) {
    bool overlapping = false;
    Instance._world.QueryAABB(fixture => {
        if ( fixture.GetUserData().IsPlayer || fixture.GetUserData().IsEnemy ||
                fixture.GetUserData().IsProjectile || fixture.GetUserData().IsDoor ) {
            overlapping = true;
            return false;
        }
        return true;
    }, ref aabb);

    return overlapping;
}

AABB collisions aren’t as accurate as polygon collisions, but since the whole point of this exercise is to be conservative with when a block can reappear, it’s just fine.

If you’ve made it this far, enjoy this bonus video from Burning Man!

One thought on “Get out of the walls, you stupid bug!

Leave a Reply

Your email address will not be published. Required fields are marked *