Polygons

Circles and AABBs work as colliders for many enemies, but not for long, thin or L-shaped ones. A circle or a rectangle around them covers a lot of empty space. For those, the game uses a convex hull around the sprite’s outer edge. A convex hull can’t follow inward corners, so an L-shaped sprite still has some empty space inside its hull, but less than inside a circle or a rectangle.

This post covers the hull collider, the collision tests for it, and the tool that builds the hulls from the sprites.

Two Kinds of Test

The game has two kinds of collision test. The discrete test asks: “Do these two shapes overlap now?” The swept test from the last post asks: “Did these two shapes touch at any point during this frame?” The swept test is what stops a fast bullet from tunneling through an enemy.

For circles and AABBs, the swept test builds the Minkowski sum of the two shapes and casts a ray against it. The same works for two convex polygons, because their Minkowski sum is again a convex polygon. But building that polygon and casting against it is more work, so the game uses a different algorithm for hulls.

The Discrete Test: Separating Axis

The discrete test uses the separating axis test. For each edge normal of both shapes, project both shapes onto that axis. If the projections don’t overlap on some axis, the shapes are apart. If they overlap on every axis, the shapes overlap, and the axis with the smallest overlap gives the shortest way to push them apart. It only needs dot products.

Circle against polygon and box against polygon have their own, simpler functions. Pairs of circles and boxes keep their existing code.

The Swept Test: Conservative Advancement

Running the discrete test at a few points in time during the frame doesn’t work: a fast object can be in front of a thin polygon at one sample and behind it at the next.

The swept test uses conservative advancement instead. Erin Catto’s GDC talk on continuous collision (PDF) explains it. It works like this:

  1. Measure the distance between the two shapes at the current time in the frame.
  2. Move time forward by that distance divided by the speed at which the gap is closing.
  3. Repeat until the distance is zero (a hit) or the frame is over (a miss).

The step never skips past the moment of contact. Two convex shapes that move in a straight line close the gap fastest at the moment it is measured, and never faster later in the frame. So “distance divided by current closing speed” is the earliest time they can touch. If the gap isn’t closing at all, they can’t touch in this frame, and the loop stops.

The loop is capped at 12 steps. In a test with bullets against every hull in the game, from every direction and at up to 30 pixels per frame, no case needed more than 8.

The swept test assumes the shapes don’t rotate during the frame. A hull can rotate from one frame to the next, but the test treats each shape as sliding in a straight line with its end-of-frame rotation.

Measuring the Distance: GJK

Step 1 needs the distance between two convex shapes. The game uses GJK for that. The distance between two shapes A and B equals the distance from the origin to their Minkowski difference A − B: the shape made of all points a − b, with a in A and b in B. It is the Minkowski sum of A and B mirrored through the origin.

GJK builds a set of up to three points on A − B. In every step, it keeps the point or edge of that set that is closest to the origin. The game finds it by computing the closest point on each candidate edge and keeping the nearest one. That costs a few more calculations than the textbook version, but is easier to get right.

Smaller Decisions

  • A hull has at most 16 vertices. Creating a bigger one throws an exception. The limit lets every collision check use a fixed-size buffer on the stack, so no check allocates memory.
  • The constructor fixes the vertex order. If the vertices run clockwise, it reverses them. A hull with the wrong order would give wrong results without any error.
  • The contact point of two overlapping polygons is the vertex of the first polygon that reaches deepest into the second. Two overlapping polygons have no single exact contact point. This one is cheap and stable, which is enough for placing hit sparks.

Hulls from Pixels

The hulls are not drawn by hand. A tool reads the sprite’s PNG and builds the hull from its alpha channel:

  1. Every pixel at or above an opacity threshold counts as solid.
  2. For every row, keep only the leftmost and rightmost solid pixel. The pixels between them can’t change a convex hull.
  3. Build the convex hull of those pixels with the monotone chain algorithm. Each pixel counts as a full square, so the hull reaches the outer edges of the sprite.
  4. If the hull has more than 16 vertices, remove vertices with the Visvalingam-Whyatt algorithm: repeatedly drop the vertex whose triangle with its two neighbours has the smallest area.

The tool writes a small .collider.json file next to the PNG. The game loads it automatically with the texture. Sprites without one fall back to a circle or a box.

The tool is a standalone .NET tool and library in its own repository , and it knows nothing about the game. More on its project page .

Animated Sprites

The player ship’s sprite is a strip: five 36×36 roll frames side by side in one 180×36 image. The tool splits a strip into frames and builds one hull per frame, relative to that frame. If an image’s width is an exact multiple of its height, it is treated as a strip of square frames. A --frame-width option covers other layouts.

Five placeholder roll frames in one strip, each with its own convex hull drawn in red

A placeholder strip with five roll frames, each with its convex hull, scaled 4x.

In the game, the ship has one collider that holds all five hulls. Every frame, the roll animation tells it which hull is active, and switching is cheap. It is one collider rather than five because the ship’s cutscenes turn all of its colliders off and on again, which would enable all five at once.

Asteroids work the same way, with 16 to 32 tumble frames each. A small reusable component passes the current animation frame to every multi-frame hull of its object.

Circle and box colliders don’t have frames. The tool only produces hulls, so only hulls need them.

Next up: hit sparks. When a bullet hits something, sparks should bounce off the surface it hit. For that, the game needs to know which way the surface faces. The collision tests work that out as a side effect. The next post is about how that direction gets from the collision test to the sparks.

Resources