Tl

Figure 8-17. A mock-up of our game world

Our world will look like this later on, but for now, let's overlay a spatial hash grid. How big should the cells of the hash grid be? There's no silver bullet, but I tend to choose it to be five times bigger than the biggest object in the scene. In our example, the biggest object is the cannon, but we do not collide anything with the cannon. So let's base the grid size on the next biggest objects in our scene, the targets. These are 0.5x0.5 meters in size. A grid cell should thus have a size of 2.5x2.5 meters. Figure 8-18 shows the grid overlaid onto our world.

 9 10 I 11 t h ■ ■ 5 i ) ■ ° 1 1 1 3 4 r ■

Figure 8-18. Our cannon world overlaid with a spatial hash grid consisting of 12 cells

Figure 8-18. Our cannon world overlaid with a spatial hash grid consisting of 12 cells

We have a fixed number of cells—in the case of the cannon world, 12 cells to be exact. We give each cell a unique number, starting at the bottom-left cell, which gets the ID 0. Note that the top cells actually extend outside of our world. This is not a problem; we just need to make sure all our objects stay inside the boundaries of our world.

What we want to do is figure out which cell(s) an object belongs to. Ideally we want to calculate the IDs of the cells the object is contained in. This allows us to use the following simple data structure to store our cells:

List<GameObject>[] cells;

That's right, we represent each cell as a list of GameObjects. The spatial hash grid itself is then just composed of an array of lists of GameObjects.

Let's think about how we can figure out the IDs of the cells an object is contained in. Figure 8-18 shows a couple of targets that span two cells. In fact, a small object can span up to four cells, and an object bigger than a grid cell can span even more than four cells. We can make sure this never happens by choosing our grid cell size to be a multiple of the size of the biggest object in our game. That leaves us with the possibility of one object being contained in at most four cells.

To calculate the cell IDs for an object, we can simply take the four corner points of its bounding rectangle and check which cell each corner point is in. Determining the cell that a point is in is easy—we just need to divide its coordinates by the cell width first. Say we have a point at (3,4) and a cell size of 2.5x2.5 meters. The point would be in the cell with ID 5 in Figure 8-18.

We can divide each the point's coordinates by the cell size to get 2D integer coordinates , as follows:

cellX = floor(point.x / cellSize) = floor(3 / 2.5) = 1 cellY = floor(point.y / cellSize) = floor(4 / 2.5) = 1

And from these cell coordinates, we can easily get the cell ID:

cellId = cellX + cellY x cellsPerRow = l + l x 4 = 5

The constant cellsPerRow is simply the number of cells we need to cover our world with cells on the x-axis:

cellsPerRow = ceil(worldWidth / cellSize) = ceil(9.6 / 2.5) = 4

We can calculate the number of cells needed per column like this:

cellsPerColumn = ceil(worldHeight / cellSize) = ceil(6.4 / 2.5) = 3

Based on this we can implement the spatial hash grid rather easily. We set up it up by giving it the world's size and the desired cell size. We assume that all the action is happening in the positive quadrant of the world. This means that all x- and y-coordinates of points in the world will be positive. That's a constraint we can accept.

From the parameters, the spatial hash grid can figure out how many cells it needs (cellsPerRow x cellsPerColumn). We can also add a simple method to insert an object into the grid that will use the object's boundaries to determine the cells it is contained in. The object will then be added to each cell's list of objects that it contains. In case one of the corner points of the bounding shape of the object is outside of the grid, we'll just ignore that corner point.

We will reinsert every object into the spatial hash grid each frame after we update its position. However, there are objects in our cannon world that don't move, so inserting them anew each frame is very wasteful. We'll thus make a distinction between dynamic objects and static objects by storing two lists per cell. One will be updated each frame and only hold moving objects, and the other will be static and only modified when a new static object is inserted.

Finally we need a method that returns a list of objects in the cells of an object we'd like to collide with other objects. All this method will do is check which cells the object in question is in, retrieve the list of dynamic and static objects in those cells, and return them to the caller. We'll of course have to make sure that we don't return any duplicates, which can happen if an object is in multiple cells.

Listing 8-10 shows the code (well, most of it). We'll discuss the SpatialHashGrid.getCellIds() method in a minute, as it is a little involved.

Listing 8-10. Excerpt from SpatialHashGrid.java: A Spatial Hash Grid Implementation package com.badlogic.androidgames.framework.gl;

import java.util.ArrayList; import java.util.List;

import android.util.FloatMath;

public class SpatialHashGrid {

List<GameObject>[] dynamicCells; List<GameObject>[] staticCells; int cellsPerRow; int cellsPerCol;

float cellSize;

List<GameObject> foundobjects;

As discussed we store two cell lists, one for dynamic and one for static objects. We also store the cells per row and column so we can later decide whether a point we check is inside or outside of the world. The cell size needs to be stored as well. The celllds array is a working array that we'll use to temporarily store the four cell IDs a GameObject is contained in. If it is only contained in one cell, then only the first element of the array will be set to the cell ID of the cell that contains the object entirely. If the object is contained in two cells, then the first two elements of that array will hold the cell ID, and so on. To indicate the number of cell IDs we set all "empty" elements of the array to -1. The foundObjects list is also a working list, which we'll return upon a call to getPotentialColliders(). Why do keep those two members instead of instantiating a new array and list each time one is needed? Remember the garbage collector monster.

@SuppressWarnings("unchecked")

public SpatialHashGrid(float worldWidth, float worldHeight, float cellSize) { this.cellSize = cellSize;

this.cellsPerRow = (int)FloatMath.cei!(worldWidth/cellSize);

this.cellsPerCol = (int)FloatMath.ceil(worldHeight/cellSize);

int numCells = cellsPerRow * cellsPerCol;

dynamicCells = new List[numCells];

staticCells = new List[numCells];

dynamicCells[i] = new ArrayList<GameObject>(l0); staticCells[i] = new ArrayList<GameObject>(l0);

foundObjects = new ArrayList<GameObject>(l0);

The constructor of that class takes the world's size and the desired cell size. From those arguments we calculate how many cells are needed, and instantiate the cell arrays and the lists holding the objects contained in each cell. We also initialize the foundObjects list here. All the ArrayLists we instantiate will have an initial capacity of ten GameObjects. We do this to avoid memory allocations. The assumption is that it is unlikely that one single cell will contain more than ten GameObjects. As long as that is true, the arrays don't need to be resized.

public void insertStaticObject(GameObject obj) { int[] celllds = getCelllds(obj); int i = 0; int cellId = -l;

while(i <= 3 && (cellId = cellIds[i++]) != -l) { staticCells[cellId].add(obj);

public void insertDynamicObject(GameObject obj) { int[] cellIds = getCellIds(obj); int i = 0; int cellId = -l;

while(i <= 3 && (cellId = cellIds[i++]) != -l) {

Next up are the methods insertStaticObject() and insertDynamicObject(). They calculate the IDs of the cells that the object is contained in via a call to getCellIds(), and insert the object into the appropriate lists accordingly. The getCellIds() method will actually fill the celllds member array.

public void removeObject(GameObject obj) { int[] celllds = getCellIds(obj); int i = 0; int cellId = -1;

while(i <= 3 && (cellId = cellIds[i++]) != -1) { dynamicCells[cellId].remove(obj); staticCells[cellId].remove(obj);

We also have a removeObject() method, which we'll use to figure out what cells the object is in and then delete it from the dynamic and static lists accordingly. This will be needed when a game object dies, for example.

public void clearDynamicCells(GameObject obj) { int len = dynamicCells.length; for(int i = 0; i < len; i++) { dynamicCells[i].clear();

The clearDynamicCells() method will be used to clear all dynamic cell lists. We need to call this each frame before we reinsert the dynamic objects, as discussed earlier.

public List<GameObject> getPotentialColliders(GameObject obj) { foundObjects.clear(); int[] cellIds = getCellIds(obj); int i = 0; int cellId = -1;

while(i <= 3 && (cellId = cellIds[i++]) != -1) { int len = dynamicCells[cellId].size(); for(int j = 0; j < len; j++) {

GameObject collider = dynamicCells[cellId].get(j); if(!foundObjects.contains(collider)) foundObjects.add(collider);

len = staticCells[cellId].size(); for(int j = 0; j < len; j++) {

GameObject collider = staticCells[cellId].get(j); if(!foundObjects.contains(collider)) foundObjects.add(collider);

return foundObjects;

Finally there's the getPotentialColliders() method. It takes an object and returns a list of neighboring objects that are contained in the same cells as that object. We use the working list foundObjects to store the list of found objects. Again, we do not want to instantiate a new list each time this method is called. All we do is figure out which cells the object passed to the method is in. We then simply add all dynamic and static objects found in those cells to the foundObjects list and make sure that there are no duplicates. Using foundObjects.contains() to check for duplicates is of course a little suboptimal. But given that the number of found objects will never be large, it is OK to use it in this case. If you run into performance problems, then this is your number one candidate to optimize. Sadly, that's not trivial, however. We could use a Set, of course, but that allocates new objects internally each time we add an object to it. For now, we'll just leave it as it is, knowing that we can come back to it should anything go wrong performance-wise.

The method I left out is SpatialHashGrid.getCellIds(). Listing 8-11 shows its code. Don't be afraid, it just looks menacing.

Listing 8-11. The Rest of SpatialHashGrid.java: Implementing getCellIds()

public int[] getCellIds(GameObject obj) {

int xl = (int)FloatMath./Ioor(obj.bounds.lowerLeft.x / cellSize);

int yl = (int)FloatMath./Ioor(obj.bounds.lowerLeft.y / cellSize);

int x2 = (int)FloatMath./Ioor((obj.bounds.lowerLeft.x + obj.bounds.width) / cellSize);

int y2 = (int)FloatMath./Ioor((obj.bounds.lowerLeft.y + obj.bounds.height) / cellSize);

if(xl >= 0 && xl < cellsPerRow && yl >= 0 && yl < cellsPerCol) cellIds = xl + yl * cellsPerRow;

else cellIds = -l; cellIds[l] = -l; cellIds = -l; cellIds = -l;

if(xl >= 0 && xl < cellsPerRow) { if(yl >= 0 && yl < cellsPerCol)

cellIds[i++] = xl + yl * cellsPerRow; if(y2 >= 0 && y2 < cellsPerCol)

if(yl >= 0 && yl < cellsPerCol) { if(xl >= 0 && xl < cellsPerRow)

cellIds[i++] = xl + yl * cellsPerRow; if(x2 >= 0 && x2 < cellsPerRow)

int ylCellsPerRow = y1 * cellsPerRow; int y2CellsPerRow = y2 * cellsPerRow; if(xl >= 0 && xl < cellsPerRow && yl > cellIds[i++] = xl + ylCellsPerRow; if(x2 >= 0 && x2 < cellsPerRow && yl > cellIds[i++] = x2 + ylCellsPerRow; if(x2 >= 0 && x2 < cellsPerRow && y2 > cellIds[i++] = x2 + y2CellsPerRow; if(xl >= 0 && xl < cellsPerRow && y2 > cellIds[i++] = xl + y2CellsPerRow; while(i <= 3) cellIds[i++] = -l;

return cellIds;

The first four lines of this method just calculate the cell coordinates of the bottom-left and top-right corners of the object's bounding rectangle. We already discussed this calculation earlier. To understand the rest of this method, we have to think about how an object can overlap grid cells. There are four possibilities:

■ The object is contained in a single cell. The bottom-left and top-right corners of the bounding rectangle thus both have the same cell coordinates.

■ The object overlaps two cells horizontally. The bottom-left corner is in one cell and the top-right corner is in the cell to the right.

■ The object overlaps two cells vertically. The bottom-left corner is in one cell and the top-right corner is in the cell above.

■ The object overlaps four cells. The bottom-left corner is in one cell, the bottom-right corner is in the cell to the right, the top-right corner is in the cell above that, and the top-left corner is in the cell above the first cell.

All this method does is make a special case for each of these possibilities. The first if statement checks for the single-cell case, the second if statement checks for the horizontal double-cell case, the third if statement checks for the vertical double-cell case, and the else block handles the case of the object overlapping four grid cells. In each of the four blocks we make sure that we only set the cell ID if the corresponding cell coordinates are within the world. And that's all there is to this method.

Now, the method looks like it would take a lot of computational power. And indeed it does, but less than its size would suggest. The most common case will be the first one, and processing that is pretty cheap. Can you see opportunities to optimize this method further?

 = 0 && yl < cellsPerCol) = 0 && yl < cellsPerCol) = 0 && y2 < cellsPerCol) = 0 && y2 < cellsPerCol)
0 0