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

Deliverables

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:

• Collision Detection (but NOT resolution–that’s next week)
• A void * “info” body field
• Giving the scene information about which bodies are associated with force creators
• Deferred body removal (see below)

Demo

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):

• There must be several rows of enemies that move in approximately the same way as our demo (that is, across the screen, then down a “row” repeatedly)
• Both the player and the enemies must shoot projectiles at each other (the enemies automatically, and the player when the space bar is pressed)
• The player must move back and forth based on presses of the arrow keys
• The demo should stop when (1) the player is shot, (2) the player clears all space invaders, or (3) the space invaders ‘fall’ below the ground. This can be accomplished by calling exit(0) when one of these conditions are met
• The player and enemy shapes must roughly match the shapes presented in the video (they cannot just be circles or rectangles)

“Upgrades”

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.

Collisions

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.

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.

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.

Separation

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.

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

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/):

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

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:

• The scene needs to store extra information
• The create force creator functions now need to be modified to pass in a list of relevant bodies
• The scene_add_force_creator function should be modified to call the new one instead of duplicating functionality

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

Grading this week will be based on:

• functionality
• design