This is a short look at a game I made called Last Circle, how I designed the collision detection for it, and what I learned. The player controls a blue-turquoise octagon by moving and shooting in the cardinal directions(N, S, W, E).

The challenge was to create a somewhat complex 2-D game without the help of a physics engine.

A First Attempt

Collisions detection was based on geometric calculation. All entities (enemies, walls and the player) were given geometric dimensions, and at each game tick a check was run to see if any of these dimensions overlapped.

The most straightforward way I thought to do this was by checking each object's bounds against every other object's bounds. This is obviously gets inefficient quickly, as each added entity adds another $n$ collision checks.

To make this a bit better, I reduced the number of collision checks by cutting the play region up into smaller regions and only do check between entities in that area.

In this diagram we would first sort the four entities into separate lists for each region, then we would go through and only check for collisions for each region. For region (0,0) that would be entities A, B, and D. For region (0,1), that would be entities B, C, and D.

With this method, I eliminated a lot of checks between objects that are too far apart to collide. It also gives us a nice way to track the presence of entities in any particular area on the game field.

Calculating Collisions Between Circular Entities

Most of the entities in this game were circular, which is great because checking for collisions between circles is easy. If two circles A and B have radii R and r respectively then all we have to do is check that their relative separation distance, $\delta S$, is greater than the sum of their two radii. If $\vec{S_1}$ and $\vec{S_2}$ represent the positions of the two entities then a collision check is true if,

$\tag{1} |\vec{S_1}-\vec{S_2}| < R$

which is the same as,

$\tag{2} (S_{1,x} - S_{2,x})^2 + (S_{1,y} - S_{2,y})^2 < R^2$

Here we compare the squares of both sides to avoid having to use the expensive square root operation.

Calculating Collisions Between Rectangular And Circular Entities

Calculating the distance between the edge of a circle and the edge of a rectangle is a bit more complicated.

With a rectangle, the distance from the center of a circle to the edge of the rectangle depends on your position relative to circle, so more calculation is needed.

1  public boolean entityIntersectsRect(Rectangle rect, Entity e){
2
3    double circleDistanceX = Math.abs(e.getCenterX() - rect.getCenterX()); 
4    double circleDistanceY = Math.abs(e.getCenterY() - rect.getCenterY());
5
6    if(circleDistanceX > (e.getRadius() + rect.getWidth()/2)) {return false;}
7    if(circleDistanceY > (e.getRadius() + rect.getHeight()/2)) {return false;}
8
9    if(circleDistanceX < (e.getRadius() + rect.getWidth()/2)) {return true;}
10    if(circleDistanceY < (e.getRadius() + rect.getHeight()/2)) {return true;}
11
12   cornerSquareDistance = ((circleDistanceX - rect.getWidth()/2)^2 + 
13                  (circleDistanceY - rect.getHeight()/2)^2)
14   return (cornerSquareDistance <= e.getRadius()^2);
15
16  }

The above code takes the bounds of a rectangle rect and circular entity e and determines if they are colliding with three checks.

• The first two lines determine the $x$ and $y$ distances between the two objects.
• The second two lines check for the "easy case" where a collision is impossible because the relative distance is greater than the radius of the circle and the maximum bounds of the rectangle. In the diagram, the corresponds to the circle being in the green region.
• The next two lines check for the easy case where a collision is guaranteed because the rectangles bounds are greater than the separation distance. This corresponds to the grey and orange sections on the diagram.
• The last lines compute the more difficult case where the circle can intersect the corner of the rectangle. It accomplishes this by calculating the distance from the center of the circle to the edge of the rectangle and then comparing this to the radius of the circle. If the radius is larger than this distance, then the function returns false corresponding to circles in the red region, or true for circles who intersect the white region.

A Better Way - Using the Quadtree Structure

As I later learned, this is not the best way to do collision detection. It turns out that there is an elegant solution for this problem that can be extended into three dimensions. It in essence sorts all entities into a quad tree data structure and performs collision checks only on entities that are near each other. See the links below for more information on quadtrees. In the end, I ended up keeping my collision detection method and moved onto another project that uses this quadtree and the Barnes-Hut algorithm to solve the N-Body Problem here.

Further Reading

• A visualization of quadtree collision detection using C++: Link
• An introduction and tutorial for quadtrees: Link