Moon Herder: Grid Collision

In Moon Herder I can have up to 450 stars on screen. I need to update them because I want to make them blink and rotate randomly, and I also need to run collision detection with them. Only an idiot would iterate over 450 indexes inside the game’s main loop, while randomly selecting indexes and checking distances… So I used a grid. And here’s how.

First I sliced the screen into columns and rows:

1
2
3
4
 
_cols = game.screenWidth / TILE;
 
_rows = game.screenHeight * 0.85 / TILE;

I used only part of the height because I add the ground picture at the bottom, and therefore I don’t want stars overlapping the ground.

Next I create an array of Cells. I use the CGPoint structure to save time, and a bit of boxing and unboxing here with NSValue won’t kill anyone.

1
2
3
4
5
6
7
8
9
10
 
for (r = _rows - 1; r >= 0; r--) {
 
	for (c = 0; c < _cols; c++) {
 
		[_grid_cells addObject:[NSValue valueWithCGPoint:ccp(c,r)]];
 
	}
 
}

Then I shuffle the array using a NSMutableArray category (you find that in the source code.) My thanks to David Wagner for that code.

So now each cell knows its X and Y position on stage, but the array containing the cells was shuffled. So all I have to do to spread the stars on the stage randomly, is to loop through the grid cell array until all stars available are on screen.

But… I need to use grid logic. So I have a second array, this one containing all Stars that can be put on screen, inside a pool, so these Star object have not been initialized yet, they are just empty husks.

For each cell from the shuffled grid array I can find its correct index in the Grid with this formula:

1
2
 
index = position.y * _cols + position.x;

You need to understand Grid collision logic for this code to make sense, so here is a brief overview: With grid collision I can find which cells the Moon is currently overlapping in the grid, like this:

1
2
3
4
 
int col = moon.x / _tile_size;
 
int row  = (_screenSize.height - moon.y) / _tile_size;

Notice that I’m still using logic from the flipped Y axis in ActionScript. But the logic stands. I divided the screens into tiles, and now I can find a specific tile (cell) where a point is, in this case the moon’s position.

With that I can find the exact star placed in that cell:

1
2
3
4
5
6
 
int col = moon.x / _tile_size;
 
int row  = (_screenSize.height - moon.y) / _tile_size;
 
Star * star = [_manager starFromPool:row * _manager.columns + col];

In the game I then determine if that star is currently active, meaning it is visible to the player. In that case, a collision has occurred.

And in every screen I use this logic to select which stars should blink and rotate.

I do that by selecting a total range of stars to be updated at a given time. Say 30 stars. I then find these stars using the same Grid logic I’ve just shown. I update them for a while, then skip to the next 30 stars. Of course if the screen currently contains less than 30 stars, I adjust the logic accordingly. But with this I can skip the larger iteration inside the main loop, only handling 30 stars at a time instead of potentially 450 stars.

Once again the code is currently on GitHub.