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.
As always, this assignment has a particular set of design features that we expect you to focus on. This time, we will focus on testing; so, there are no new design features. Here’s the list of the other design features we’ve already highlighted:
- code duplication
- good variable and function names
- procedural decomposition
- “overcommenting” (e.g., the comments do not explain things that are already clear from the code itself)
- usage of whitespace
- overmodularization (e.g., modularizing into functions that actually make the code less clear)
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)
void *“info” body field
- Giving the scene information about which bodies are associated with force creators
- Deferred body removal (see below)
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)
As with last week, this demo may run particularly slowly if compiled with asan. When you wish to run your demo, please run the command
make NO_ASAN=true all, instead of the regular
make all, or else you may experience demo slowdown.
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.
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.
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):
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
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
createforce creator functions now need to be modified to pass in a list of relevant bodies
scene_add_force_creatorfunction 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.
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: