CS 3 (Spring 2023) Project 05: Collision Detection

In this project, you will add more abstractions necessary to write a simple version of the game space invaders.

If you run into Makefile/compilation errors, you can run the script cs3-check-files to check that you’ve ported over all required files. The script will tell you which files are missing in the terminal, or you can check the .required-files file in your repo. If all required files are present, the terminal will not print anything.

Code Correctness


This week there is only one demo, but it will require some substantial “upgrades” to the scene and body abstractions. These “upgrades” would have been necessary to implement for your game anyway, though. The “upgrades” include:


The demo this week is a simple version of Space Invaders.

Your game demo must have the following features (but feel free to play around and implement anything you want otherwise):


As usual, we will need more features to implement the new demo. Most of them are described in the docmentation, but we repeat some important information in the spec below.


This week, you will implement collision detection, i.e. checking if two polygons intersect. For simplicity, we will assume the polygons are convex. You must implement the separating axis method to check for collisions:

Check if there is a line that separates the polygons, putting one polygon on each side of the line. This method will require minimal modifications to implement collision resolution next week, since it already computes the direction that the polygons bounce off.

Separating axis

Aside: Projection

The projection of a polygon onto a line is the line segment containing the projections of all points in the polygon onto the line, shown as the thick blue line below. For example, if the line is the x-axis, the projection of the polygon is the segment from the minimum x value of any vertex to the maximum x value of any vertex.

sa x projection

The projection of a vertex onto a general line can be found by the dot product of the vertex with a unit vector pointing along the line, since that computes the component of the vertex in the direction of the line.

sa dot

To find the projection of a polygon onto a line, we compute the dot product of each vertex with the line’s unit vector and take the minimum and maximum values.

sa projection


Two polygons do not intersect iff the projections of the polygons onto some axis (black) do not overlap. The red line perpendicular to this axis is a separating axis: the axis splits the plane with one polygon on each side.

sa no collide

Two polygons intersect iff the projections of the polygons onto all axes overlap. The red line shows the overlap.

sa collide

It is not sufficient to check a single axis, since every pair of polygons has some axis where their projections overlap. However, if there is a separating axis, then without loss of generality, there is a separating axis perpendicular to an edge of one of the polygons. For example, if one polygon has 3 sides and the other has 6, we need to check 9 axes (those perpendicular to the 9 edges) to be sure the polygons intersect.

If the projections of the polygons onto one of those axes do not overlap, you should conclude that the polygons do not intersect and skip the other axes. If the polygons are far apart, then their projections onto most axes will not overlap and this algorithm will quickly determine that they do not intersect.

An example with all axes drawn (from http://www.dyn4j.org/2010/01/sat/):

all projections

An example where some projections overlap, but others do not such that there is a separating axis (red):

more projection

For more information see http://www.dyn4j.org/2010/01/sat/ or https://gamedevelopment.tutsplus.com/tutorials/collision-detection-using-the-separating-axis-theorem–gamedev-169.

Body “info” field

Different applications will need to use different extra information about bodies. For example, for Space Invaders, you will need to be able to differentiate between the player and enemies. Thus, you should add auxilliary data to the body as a void *. Since this means there is extra information to pass into body_init, this will necessitate creating a second constructor that includes a value for the void *.

Giving the scene additional information about force creators

Last week, the scene didn’t need to know which bodies were attached to force creators, but that has to change now. In particular, we need to remove bodies as a result of collisions which needs to trigger the removal of the related force creators. We will handle this in several steps. The biggest change is to the interface to add force creators to the scene. In fact, it’s such a big change that we need to “deprecate” the old function scene_add_force_creator. Library writers can mark functions as “deprecated” if they should no longer be used, but they still need to exist for backwards compatibility. The new function scene_add_bodies_force_creator will replace this function and allow the scene to store which bodies are associated with which force creators.

Unfortunately, this change triggers a few others as well:

Delayed body and force creator removal

Giving the scene access to the relationship between bodies and force creators allows it to take ownership of managing their lifetimes. That is, the scene can now be responsible for actually freeing the bodies and removing the force creators from itself. This gets very convoluted very quickly if we attempt to have the force creators do this work; so, we’ll employ another design pattern: delaying action. We will make scene_tick responsible for actually doing the removal at the end. Thus, body_remove should now “set a flag” to indicate that it is ready to be deleted by the scene rather than immediately actually deleting itself. Make sure to review the documentation in the body and scene header files for specifics.


Grading this week will be based on: