GMGE Physics Part 2 of 3 - Collision Detection

Introduction

Physics engines that support complex shapes and rotations exist, but are often sluggish due to a lot of complicated math. GMGE is intended build Progressive Web App games written in Javascript, so with regards to physics and the types of games that can be built, there have to be some constraints. The first self-imposed constraint is that it is a 2D-only engine. The second constraint is that it is limited to two types of colliders.

GMGE supports 2 types of colliders, rectangles(referred to as boxes, specifically axis-aligned boxes) and circles. If we support rectanges (elongated squares), why not elipses (elongated circles)? We'll get into details below, but the short answer is twofold:

1. Collision detection for a circle is trivial, the distance from its center. The same is not true for an ellipse. (Give it a try, draw an ellipse and determine the distance from its center to all the points on its surface.) There is no difference in collision detection between squares and rectangles, you check the top, bottom, left and right sides.
2. Calculating the surface normal on a circle is much easier than on an elipse. For a circle it is the normalized ray from the center to the point of contact. The same is not true for an ellipse, even axis-aligned (except for exactly 4 points on its surface.) Contrast that to determining the surface normals between squares and rectangles, they are identical.

GMGE supports physics layers. What is a physics layer? Think of it as grouping all the same types of objects into their own layer. Then you can define which layers can collide with other layers. For example, say you have the player, a ghost, and walls. You could have 3 physics layers. One for the player; one for the ghost; and one for all the walls. The player cannot move through walls, but the ghost can. We also want to know if the ghost ever catches the player. You would then configure the layers so that the player layer interacts with ghost and wall layers; the ghost layer only interacts with the player layer; and the wall layer only interacts with the player layer. This is basically the broad-phase collision detection mechanism in GMGE.

Part 1 of this series of physics articles covered motion. This installment, part 2, is all about collision detection. Part 3 will show how to resolve collisions.

Collision Map

As mentioned in the intro, GMGE supports physics layers. Specifically up to 31 user-defined layers. Why 31? JavaScript only does bit-wise operations on 32 bit numbers, and GMGE reserves one layer as a default layer, leaving 31 available for use.

The collision map is an array of arrays. The outer array is a list of all physics layers 0 to n-1. Each of those array slots contains another array that is just a list of the layers that the current layer is allowed collide with. Using our player, ghost and wall example from the intro, here is how the collision map would be defined.

Notice that the default layer interacts with itself. That means that any game object assigned to the default layer will collide with all other objects on that layer. However, if there are multiple ghosts, they will not collide with each other as the collison map is currently defined. If you wanted your ghosts to collide with each other, you would add them to their own layer.

Collision Mask

Since walking the array of layers that a layer should interact with is relatively slow, the collision map is converted into a collision (bit) mask. This allows for really fast checking to see if two objects can interact with each other or not.

Building the collision mask is pretty simple. For each layer, walk the list of layers it should interact with, and raise 2 to the power of that level, adding it to the running total for that layer.

For our example, the collison mask would look like this in binary form.

When we have an object and want to see if we should test it against another object, we do 2 bit-wise AND operations. We do collisonMask[object1.layer] & (2 ** object2.layer), and the reverse, and if either are non-zero results we do our fine-grained collision detection.

gmgeTTT(n) returns 2 to the power n, or Two-To-The n

Colliders

As previously mentioned, GMGE has two types of colliders. Box (axis-aligned rectangles) and circle colliders. Each collider type has tests for colliding with the same or the other type of collider. (Technically, there is a third collision test for each collider type against a specific point in the game world, but that is for touch collisions when a player presses on a touchscreen device. Since they aren't involved in physics, I'm going to skip explaining them.)

There are 3 types of collisions possible in regards to game objects colliding with each other. Circle and circle (CvC); rectangle and rectangle (RvR); and circle versus rectangle (CvR). Knowing the type of collider in advance is required to run the proper collision test. Therefore, the first thing that happens is figure out the two types of colliders (box and/or circle) we are dealing with between the two objects being tested.

At that point, it comes down to doing some comparisons and a little math. We want to be able to detect the three situations illustrated below. For now, we don't care how much they overlap, nor what direction they were moving. We just to quickly be able to tell if they are colliding.

RvR - If we know the the position of all 8 sides, 4 for each rectangle, it is a single if statement testing that obj1.left < obj2.right and obj1.right > obj2.left and obj1.top > obj2.bottom and obj1.bottom < obj2.top

CvC - This one is easy too. If the length-squared of the vector from obj1 to obj2 > the square of sum of their radii: (r1 + r2)^2

CvR - This one is more complicated. To do it quickly, we find the closest point on the rectangle to the circle. That can be done quickly by clamping circle.x between rectangle.left and rectangle.right, and then clamping circle.y between rectangle.top and rectangle.right. Clamping looks like this:

With the point on the rectangle closest to the circle, we can define the vector from that point to the center of the circle. If its length squared is < the radius squared of the circle, then they are colliding.

We use the length-squared of things whenever possible to avoid making a more costly squareroot function call. Whenever we truly need to know the distance or length, then we have no choice and have to make a squareroot call.

Collision Surface Normal(sn)

CvR and RvR

For CvR and RvR collisions, the method is very similar. Object A is either a circle or a rectangle, and object B is always a rectangle. We find the point on B that is closest to the center of A. See the Clamp( ) function above. The closest point(cp) will identify the edge or corner closest to A. If it is an edge, we are basically done. Since the rectangles are all axis-aligned, we know the 4 possible surface normals.

top/up = [0, 1]; bottom/down = [0, -1]; left = [-1, 0]; right = [1, 0]

The closest point (cp) is clamped to the boundaries of B. Since the cp is on the top edge of B, the surface normal (sn) is up

However in the case of a corner being the closest point, we want to choose a side. The reason why we don't use a corner and its normal will be explained in Part 3. For now, just know we will always choose an edge. We give preference to the edges aligned with the direction of gravity in the case of a corner hit. For example, if gravity points down, then we will choose either the top or bottom edge depending on the corner involved. Top-left and top-right use the top edge, and the other 2 corners use the bottom edge.

The thought behind this has to do with in most platform games you want to be on the side of a collider that gravity is pushing you toward. Think of the player or an enemy object in a platformer game, we want them to move along the platforms and allow near misses on jumps to still land on the platform, making them more forgiving.

If the objects are moving somewhat quickly, especially toward each other, the center of A can be within the boundaries of B. When that happens, using Clamp to find the closest point doesn't work, because it returns the coordinates of A. To find the proper edge, we find the shortest distance from the center of A to each side of B. In this case the top edge is the shortest distance, so B's collision surface normal will be [0, 1] up.

CvC

Circle vs circle is a little different, but also more straightforward. To get the surface normal (sn) We simply normalize the vector from B to A.

Collision Depth

The end goal is to get colliding objects out of collision and moving on their merry ways. In Part 3, we'll apply an impulse to the colliding objects to adjust their positions to push them out of collision with each other. The amount of the push is determined by the collision depth.

If you remember the case above where the center of A was within the boundaries of B and we had to find the shortest distance from A to each side of B. In that case we calculated the collision depth, and stored that in the collision object.

In the case of circle vs circle, the collision depth is the sum of A's and B's radii minus the distance from A to B.

This leaves the case where A's center is outside of B. We just need to find the distance from A to the closest point (cp). Or in reality the closest edge. Since we have already determined the collision surface normal, we know the direction and edge we need to get the distance to. For instance if the surface normal is [0, 1], we know that we want A.y - B's top edge.

Tracking Multiple Collisions

After all the game objects have moved (see Part 1), we want to identify all of the collisions that occurred during the frame all at once, and then resolve them all (see Part 3). In order to track all of the collisions in a frame, we store them in an array of collision objects as they are detected.

A collision object is a simple structure that has a reference to each game object involved, a reference to both colliders involved, the surface normal at the point of collision, and the depth of the collision. (We have a reference to the specific collider, because it could either be a physics or trigger collider. Those can be completely different sizes or shapes. When resolving physics collisions, we need to know the specifics about the colliders.)

That is pretty much it for collision detection. However, when we resolve collisions we will be pushing objects around a little to get them out of collision. Doing so can create more collisions. If we go back to a stack of boxes, pushing any box other than the top one is guaranteed to create or worsen a different collision. To that end we actually keep looping doing detection and resolution until things settle down... enough.