Optimization

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 one of the programming TAs.

Table of Contents

• Project Overview
• Project Structure
• Part 1: Optimization
• Part 2: Gameplay
• Aside: Basic Physics
• Submission

Project Overview

Download: Optimization.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 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.016. If you see 0.033 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 are some tools built into Intellij, though we do not have a lot of experience with them.

Goal

Download: OptSolution.jar

We have provided a very rough FPS counter for you in the top right of the game window. By rough we mean that it always caps the FPS measurement at 60 (so no advantage for fast monitors) and only starts to falter when it hits 58. You should use this counter to measure the performance of your solution.

On your instructors M2 Max, the current version of the project will see its framerate drop when the game reaches 1500 shells. On the other hand, the solution above sees no framerate drops until it reaches 10000 shells, which is an order of magnitude improvement.

Your solution needs to be within 90% of our solution. To determine this, run the solution on your machine and note the number of shells that cause the performance to drop below 60 (even if only to 58 FPS). Your solution should be able to handle 90% of that many shells with no drop in FPS.

Project Structure

To shake things up a bit, we have made this project slightly different from previous labs. Our main class no longer implements the LibGDX class Game. Instead, we implement the class ApplicationAdapter. This is an alternate root class for your game. All LibGDX games typically implement one of these two classes.

By choosing to implement ApplicationAdapter, we no longer have support for the Screen. interface. Instead, we define our own interface: Scene. Note that the root class must manage its scenese explicitly (unlike Screens, which are handled automatically). In particular, your root class must call update and draw explicitly in the active scene. For those of your that took 1110, it is very similar to how we structured Assignment 7.

With that said, once you get past the structure of the root class, everything is pretty similar to the previous labs. Everything is broken up into model, view, and controller, as illustrated in the dependency diagram below. We have omitted LoadingScene because it is not directly relevant to the game architecture.

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

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.

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 Java class 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<GameObject> objects, int offset) method located right after the constructor. This method is incredibly slow. Right now, the game experiences a significant amount of lag on the instructor’s machine when just over 1500 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 resolveCollision. 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 resolveCollision(TYPE_1 a, TYPE_2 b) function corresponding to the two colliding types.

While resolveCollision 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.

Part 1: 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 to initialize the grid of cells. The number of cells should be adjustable.

We recommend that you add new values to the file constants.json, which defines the physics constants in use for this lab. Note that the current constructor for CollisionController already uses this file. However, you should defer construction of your data structures to the resize method.

You will also need to alter the method processCollision right after the collision. The code that you will replace it with can get a little complex, so we recommend that you add several new methods and attributes of your own.

You should avoid modifying any of the restitution code in the regions marked 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.

Part 2: 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 us 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₂</i> 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.

Submission

Due: Wed, Feb 12 at 11:59 PM

For this assignment, you will submit another ZIP file, the following files:

• README.txt, explaining your gameplay changes and acceleration structure
• Any source (.java) file that you have modified.
• The file constants.json if you made any modifications.
• Any images that you may have added or modified (explain in your readme).
• An executable Jar of your solution.

Submit this zip file as lab3code.zip to CMS