Artifact: Collision

Collision is an important part of every game, but can be very challenging. Some games require only simple collision detection: Tile based games makes due with axis aligned box to box collision detection while many space-shooter type games will only require simple circle collision detection.

Given that our game has free form movement we would need a more advanced type of collision to make sure that the game feels right. This we could either achieve with pixel-perfect collision detection or with convex polygon collision detection. Personally, I’m not a fan of pixel-perfect collision. It’s very limited, especially when considering animation, and doesn’t provide enough feedback for a somewhat proper collision handling. Therefore we decided to go with convex polygon collision detection. We’re using the separate axis theorem, since it provides information about the collision that can be used when handling the collision rather than just a true or false value. I’ve used this theorem previously, but only with rotated rectangles. This time we’re using convex polygon shapes. There isn’t too much difference, but circle to polygon collision detection will be harder to achieve than circle to rotated rectangle collision detection.

Of course, before doing this relatively expensive between every object in the game, you want to do a broad phase collision check. There are different ways to do this, but arguably the cheapest would be to use axis aligned bounding boxes.

Separate Axis Theorem (SAT) looks at all vertices of both polygons projected onto each axis of both polygons. This sounds advanced, but it’s a fairly simple process.

To get an axis from a polygon you subtract a vertex from a subsequent one.

axis0 = v0 – v1, axis1 = v1 – v2, axis2 = v2 – v3 … axisn = vn – v0

To project a vertex onto an axis you need the formula

projection_n = axis_n × ((v_n · axis_n) / (axis_n(x)² × axis_n(y)²)

Okay, so the math is rather complicated, but we’re almost done here! We have the points projected to the axis, but we need to know if, and how much, the projections overlap. For this we will use the dot product of the projected vertex and the axis

dot_n = projection_n · axis_n

then check for the smallest and biggest dot_n. and compare them to the smallest and biggest dot_n of the other polygon’s projected vertices on the same axis. If there is no overlap, there is no collision. If we go through all the axes like this and store what the smallest overlap is and on what axis we can determine not only if there is a collision, but also get the smallest distance to break the collision.

This can also be done with circles vs polygons where you would check the center of the circle against either the axes or the vertices of the polygon depending on where the circle is in relation to the polygon. This is using voronoi areas, but this is slightly more advanced and I won’t go into it here.

There are some really great tutorials on this out on the web.

I can recommend N tutorial A for its thorough breakdown of the theorem.

About Malcolm Yllenius

2015 Programming

View all posts by Malcolm Yllenius →