Programming Lab 3: Optimization

Due: Wednesday, February 12th at 11:59 pm

Performance is a major issue in games. The more things that you have on the screen, the slower your game will run. For this lab you will learn how to optimize your game, particularly when handling collision detection.

Once again, this lab is not due during this lab period, but it is to your advantage to work through (and/or learn) as much as you can now, while assistance is immediately available. If you are experiencing any problems, contact a programming TA by e-mail to ask questions or to arrange a help meeting.

The Game

Project: OptimumLab.zip

This game is a remake of a minigame from Super Mario RPG. In this version, red and green shells fall down from the top of the screen. You control a beetle-shaped "ship" at the bottom of the screen, and if a shell hits your beetle, you lose. Your beetle can move from left to right to dodge shells and can shoot at the shells to destroy them. Green shells are destroyed in one hit, while red shells turn into green shells when hit by shots. When a green shell is destroyed it explodes into several stars which radiate outwards in semi-random directions and act as bullets (thereby possibly creating chain reactions of explosions).

Download the project file and unzip the source somewhere convenient. You should know how to get this working from the previous labs. This contains the source code for an incomplete version of the game. In this version, collision detection is implemented well but poorly handled. Once the game gets upwards of 1500 shells, the game slows down significantly.

This is a problem because shells will be constantly falling from the top of the screen. Over time, the number of objects on the screen may get quite high. Checking for collisions between each shell and every other shell in the in the game is O(n²), which is prohibitively expensive. You have to do something to optimize this poor version of collision detection.

While you are free to do any sort of optimizations that you can think of, we suggest that you use the concept of simulation islands. In this strategy, you should

• Divide the screen up into cells
• Check only for collisions within a cell, or between neighboring cells.

In addition, you should eliminate any other boneheaded decisions in our collision detection algorithm that hurt performance. How you find these poorly performing parts is up to you. You can try to find these by hand. There is a parameter delta in the update loop of your code that indicates the number of elapsed seconds since the last animation frame. 60 fps (the goal) should have a delta close to 0.16. If you see 0.33 seconds, you are closer to 30 fps.

If you want more information, LibGDX does provide some additional classes with basic profiling information. If you are feeling very brave, you can rely on a code profiler. There is one built into Eclipse, though we have heard mixed things about it.

Goal

If you look at the delta value, you will see that the current project drops to 30 fps (0.33 seconds) at around 1200 shells. Even at lower values, you will occasionally see 0.33 seconds for an isolated frame. We think that is either an artifact of ArrayList of the garbage collector kicking in (we are still not quite sure)). If we really wanted consistent performance, we would use memory pools and custom list structures. We did not do this because it would make the lab a lot harder. So the rule is that isolated frames of 0.33 seconds are okay, sustained 30 fps is not.

Our solution can easily handle 8000 shells on the screen while hovering around 0.17 seconds per frame (with the occasional one-frame hiccup). That is what you should be aiming for, with a minimum of 6000 shells.

The Code

At this point, the game architecture should start to look very similar to previous labs. Everything is broken up into model, view, and controller, as illustrated in the dependency diagram below. We have omitted LoadingMode and the utility classes because they are not directly relevant to the game architecture.

While these classes may look familiar to you, they are some important differences that we cover below.

GameCanvas

In the attempt to keep the previous game labs simple, we sacrificed simplicity in the GameCanvas class. The canvas typically required multiple passes and there was a lot of specific logic embedded in the class. This time, we have a much simple GameCanvas illustrating the proper way to implement it. There is only a single pass, and all the models use the same (or an overloaded version of the same) drawing method.

Of course, this is possible because we are only drawing sprites, and we are always using the same blending setting. In the last programming lab, we will see a more interesting GameCanvas

GameObject

The primary model class is GameObject. This defines the spatial attributes for the object and stores the appropriate textures. As GameObject is an abstract class, it only exists for polymorphism reasons. The real work is done in the subclasses: Shell, Star, Bullet, and Ship.

For organizational reasons, we have put all of the subclasses into their own package. This cuts down on the clutter in our source code directory. It also helps us enforce dependency conventions.

As general rule, any class in a subpackage should avoid any references to a class in its parent package. So the class Bullet should never refer to any other class outside of edu.cornell.cs3152.lab3.entity. As a result, we once again have passive models that do not do much more than set and store attributes.

You will note from the diagram above that there is one major exception to this rule. The GameObject classes all refer to GameCanvas. This is an interesting exception that we will discuss much later in class when we cover component-based architecture.

GameplayController

Our decision to use passive models once again for this lab causes some interesting design challenges. The various models are constantly interacting with the world, spawning new objects. For example, the ship needs to add bullets to the world and exploding shells need to add stars to the world. How can we do that if the models cannot access the rest of the game world.

This is the purpose of the GameplayController. This controller manages all of the functionality that we want to put into our model (because that is how we were trained when we learned OO programming) but cannot. This results in some interesting behavior. For example, when it is time for the ship to fire, it simply sets an isFiring flag. The GameplayController processes the result of this ship fire, and resets the weapon. We will learn more about this programming style when we learn about game architecture later next week.

Another interesting feature of the GameplayController is garbage collection. When a shell (or the ship) is destroyed, we need to remove it from the list of game objects. Removing multiple items from a list is extremely expensive. Either the list is O(1) to access and O(n) to delete (because it has to shift elements down the array) or it is O(n) to access and O(1) delete (e.g. a linked list). Either way, this means that removing a lot of elements is O(n²).

Instead, we handle deletion in the same way that a stop-and-copy garbage collector works. At the end of each animation frame, we copy all the live objects from the list and ignore the deleted objects. This means, of course, that objects are not actually deleted until the end of the animation frame. Again, as we shall see later next week, this is exactly the behavior that we want.

CollisionController

This class handles all of the collision code and is the primary class for this lab. Indeed, for part 1 of the lab (you will add some extra gameplay features in part 2), this is the only file that you need to modify.

To help you make sense of this file, you should understand that collision detection consists of two parts:

Collision Detection

Finding a pair of objects that had collided with one another

Collision Resolution

Changing the velocity or position of the objects in reaction to this collision.

The first part, collision detection, is managed by the processCollisions(List objects, int offset) method located right after the constructor. This method is incredibly slow. Right now, the game experiences a significant amount of lab when just over 1000 objects are introduced. It is your responsibility to solve this problem.

The second part is the one that we have (mostly) handled for you. The two important methods for resolution are processCollision(GameObject o1, GameObject o2) and handleCollision. The processCollision method uses the getType() method of the two objects to determine the types of objects that are colliding (e.g. shell - shell, ship - star, etc.). It will then call a special handleCollision(TYPE_1 a, TYPE_2 b) function corresponding to the two colliding types.

While handleCollision has been implemented for you, it is important to understand how it works and its implications for gameplay. The reaction to a collision depends on the types of objects involved.

Shell-Shell Collision

This is the most complex of the collisions. When two shells collide, they bounce off of one another. To do this, the method not only changes the velocities of the shells, but also change their positions such that they are no longer interpenetrating. If you are interested, we go into some of the physics below.

Shell-Other Collision

In these cases, both the shell and the object it collides with are be destroyed. If the ship is destroyed, this will end the game. For dramatic effect, some of these methods calculate some form of "knockback".

Nonshell-Nonshell Collision

Generally speaking, other types of collisions do not result in anything happening. But you may want to change this behavior in the second part of the lab.

Optimization

In order to optimize collision detection, you will want to create a grid of collision cells. To do this, you should modify the CollisionController class. You will need to alter the constructor initialize the grid of cells. The number of cells should be adjustable. You can either add a parameter to the constructor, or have a default constant in the class (why not both?).

You will also need to alter the method processCollision right after the collision. Finally, you will need to add several new methods and fields of your own.

You should avoid modifying any of the restitution code in the regions mark DO NOT MODIFY. You may modify them in part 2, but you should not need to modify them for the first part.

How you define your cells is up to you. Note that processCollision receives a brand new list of objects every animation frame (since we are garbage collecting at the end of each frame). Therefore, you do not want a data structure that persists across multiple frames. Instead, you want to clear your structure and repopulate it each animation frame. As objects are continually moving, this makes sense.

When you are designing your collision cells, try to be speed-conscious. While your game screen is relatively small, if you were to have a wide open scrollable terrain you could have tens of thousands of collision cells, at which point speed would become a real factor. Try to think of a framework that doesn't require performing some action on all collision cells (even empty ones) every frame.

To test out your code, there is a Flood button ('F'), which floods the playfield with shells. The game should not slow down with tons of shells handled. Try shrinking down the shells and making sure you can handle a couple thousand shells without any slowdown caused by collision. Note that the flood button will also work once you die giving another way to test.

Gameplay

In addition to implementing collision detection, you will improve upon the game with at least two good new gameplay elements. There are no limits on what these can be, but they should be non-trivial, cool, and make the game more fun. These additions will be graded not only on implementation quality but also on creativity.

We are intentionally not giving you any ideas so you can come up with your own. However, it is very important that your changes are significant. Simply adding a counter and calling it a score is not enough to be considered a significant change. On the other hand, designing and implementing a more complex scoring system (including all appropriate mechanics and display modifications) might be interesting. If you're wondering if your idea is acceptable, please contact the programming TAs, and we will gladly help you on this.

Make sure your additions actually make the game more fun, interesting, or unique. Your README file should include what sort of additions you made, how you did them, and why you decided they would be good things to include. Careful documentation of your gameplay changes is very important.

Aside: Basic Collision Physics

This particular lab was more important in years past, before physics engines became so prevalent. However, the danger of a physics engine is that it is a "black box", and hence somewhat unpredictable. It is always nice to understand what is going on underneath.

The hardest part of collision detection is actually collision resolution, particularly getting objects to bounce off of one another properly. In this lab, we treated collisions as two circles colliding,as depicted in the figure below.

Detecting the collision is the easy part. Once we know that the shells have hit each other, we need to find their new velocities. Each Shell has its velocity, so we already know v₁ and v₂. We can find w₁and w₂ by projecting v₁ and v₂ onto a vector pointing from the center of s₁ to the center of s₂. A w vector represents the component of the velocity that acts in the collision (it is normal to the collision surface). To get a reasonable final velocity for a shell, simply take away its contribution and add the other shell's contribution. In short, the final velocity for the first shell would be v₁-w₁+w₂. Note that this model is perfectly elastic. Since we often want some energy loss, we scale the final velocities by some factor in order to dampen them. Finally, we change the positions of the shells to ensure they are no longer in contact after the collision has been handled.

Turning It In

You should create a ZIP file with three components:

• README.txt, a file explaining your gameplay changes and acceleration structure
• Any source (.java) file that you have modified.
• Any images that you may have added or modified (explain how to include in your readme).
• An executable Jar of your solution.

Submit this zip file as "lab3prog.zip" to CMS.

Due: Wednesday, February 12th at 11:59 pm