Game Programming Patterns / Optimization Patterns

Spatial Partition

×

This book is a work in progress!

If you see a mistake, find something unclear, or have a suggestion, please file a ticket. To know when new chapters are up, join the mailing list:

Thank you!

— Bob (@munificentbob)

Intent

Efficiently locate nearby objects by storing them in a data structure organized by their position.

Motivation

Games let us visit other worlds, but those worlds typically aren’t so different from our own. They often share the same basic physics and tangibility of our world. This is why they can feel real despite being crafted of mere bits and pixels.

One bit of fake reality that we’ll focus on here is location. Game worlds have a sense of space and objects are somewhere in that space. This manifests itself in a bunch of ways. The obvious one is physics — objects move, collide, and interact — but there are other examples. The audio engine may take into account where sound sources are relative to the player so that distant sounds are quieter. Online chat may be restricted to other players close to yourself.

This means your game engine often needs to answer to the question, "what objects are near this location?" If it has to answer this enough times each frame, it can start to be a performance bottleneck.

Units on the field of battle

Say we’re making a real-time strategy game. Opposing armies with hundreds of units will clash together on the field of battle. Warriors need to know which nearby enemy to swing their blade at. The naïve way to handle this is by looking at every pair of units and seeing how close they are to each other:

void handleMelee(Unit* units[], int numUnits)
{
  for (int a = 0; a < numUnits - 1; a++)
  {
    for (int b = a + 1; b < numUnits; b++)
    {
      if (units[a]->position() == units[b]->position())
      {
        handleAttack(units[a], units[b]);
      }
    }
  }
}

Here we have a doubly-nested loop where each loop is walking all of the units on the battlefield. That means the number of pairwise tests we have to perform each frame increases with the square of the number of units. Each additional unit you add has to be compared to all of the previous ones. With a large number of units, that can spiral out of control.

Drawing battle lines

The problem we’re running into is that there’s no underlying order to the array of units. To find a unit near some location, we have to walk the entire array. Now imagine we simplify our game a bit. Instead of a 2D battlefield, imagine it’s a 1D battle line.

In that case, we could make things easier on ourselves by sorting the array of units by their position on the battleline. Once we do that, we can use something like a binary search to find nearby units without having to scan the entire array.

The lesson is pretty obvious: if you store your objects in a data structure organized by their location, you can find them much more quickly. This pattern is about applying that idea to spaces that have more than one dimension.

The Pattern

A set of objects each have a position in space. Store them in a spatial data structure that organizes them by that position. This data structure lets you efficiently query for objects at or near a location. When an object’s position changes, update the spatial data structure so that it can continue to find it.

When to Use It

This is a common pattern for storing both live, moving game objects and also the static art and geometry of the game world. Sophisticated games often have multiple spatial partitions for different kinds of content.

The basic requirements for this pattern are that you have a set of objects that each have some kind of position and that you are doing enough queries to find objects by location that your performance is suffering.

Keep in Mind

Spatial partitions exist to knock an O(n) or O(n²) operation down to something more manageable. The more objects you have, the more valuable that becomes. Conversely, if your n is small enough, it may not be worth the bother.

Since this pattern involves organizing objects by their position, objects that change their position are harder to deal with. You’ll have to reorganize the data structure to keep track of the object at its new location, and that adds code complexity and spends CPU cycles. Make sure the trade-off is worth it.

A spatial partition also uses additional memory for its bookkeeping data structures. Like many optimizations, it trades memory for speed. If you’re shorter on memory than you are clock cycles, that may be a losing proposition.

Sample Code

The nature of patterns is that they vary: each implementation will be a bit different and spatial partitions are no exception. Unlike other patterns, though, many of these variations are well-documented. Academia likes publishing papers that prove performance gains. Since what I care about is just the concept behind the pattern, I’m going to show you the simplest spatial partition: a fixed grid.

A sheet of graph paper

Here’s the basic idea: imagine the entire field of battle. Now superimpose a grid of fixed-size squares onto it, like a sheet of graph paper. Instead of storing our units in a single array, we put them in the cells of this grid. Each cell stores the list of units whose position is within that cell’s boundary.

When we handle combat, we only consider units within the same cell. Instead of comparing every unit in the game with every other one, we’ve partitioned the battlefield into a bunch of smaller mini-battlefields, each with many fewer units.

A grid of linked units

OK, let’s get coding. First, some prep work. Here’s our basic unit class:

class Unit
{
  friend class Grid;

public:
  Unit(Grid* grid, double x, double y)
  : grid_(grid),
    x_(x),
    y_(y)
  {}

  void move(double x, double y);

private:
  double x_, y_;
  Grid* grid_;
};

Each unit has a position (in 2D), and a pointer to the Grid that it lives on. We make Grid a friend class because, as we’ll see, when a unit’s position changes, it has to do an intricate dance with the grid to make sure everything is updated correctly.

Here’s a sketch of the grid:

class Grid
{
public:
  Grid()
  {
    // Clear the grid.
    for (int x = 0; x < NUM_CELLS; x++)
    {
      for (int y = 0; y < NUM_CELLS; y++)
      {
        cells_[x][y] = NULL;
      }
    }
  }

  static const int NUM_CELLS = 10;
  static const int CELL_SIZE = 20;
private:
  Unit* cells_[NUM_CELLS][NUM_CELLS];
};

Note that each cell is just a pointer to a unit. Next, we’ll extend Unit with next and prev pointers:

class Unit
{
  // Previous code...
private:
  Unit* prev_;
  Unit* next_;
};

This lets us organize units into a doubly-linked list, instead of an array.

Each cell in the grid points to the first unit in the list of units within that cell and each unit has pointers to the ones before and after it in the list. We’ll see why soon.

Entering the field of battle

The first thing we need to do is make sure new units are actually placed into the grid when they are created. We’ll make Unit handle this in its constructor:

Unit(Grid* grid, double x, double y)
: grid_(grid),
  x_(x),
  y_(y),
  prev_(NULL),
  next_(NULL)
{
  grid_->add(this);
}

This add() method is defined like so:

void Grid::add(Unit* unit)
{
  // Determine which grid cell it's in.
  int cellX = (int)(unit->x_ / Grid::CELL_SIZE);
  int cellY = (int)(unit->y_ / Grid::CELL_SIZE);

  // Add to the front of list for the cell it's in.
  unit->prev_ = NULL;
  unit->next_ = cells_[cellX][cellY];
  cells_[cellX][cellY] = unit;

  if (unit->next_ != NULL)
  {
    unit->next_->prev_ = unit;
  }
}

It’s a little finicky, like linked list code always is, but the basic idea is pretty simple. We find the cell the unit is sitting in and then add it to the front of that list. If there is already a list of units there, we link it in after the new unit.

A clash of swords

Once all of the units are nestled in their cells, we can let them start hacking at each other. With this new grid, the main method for handling combat look like this:

void Grid::handleMelee()
{
  for (int y = 0; y < NUM_CELLS; y++)
  {
    for (int x = 0; x < NUM_CELLS; x++)
    {
      handleCell(cells_[x][y]);
    }
  }
}

It just walks each cell and then calls handleCell on it. As you can see, we really have partitioned the battlefield into little isolated skirmishes. Each cell then handles its combat like so:

void Grid::handleCell(Unit* unit)
{
  while (unit != NULL)
  {
    Unit* other = unit->next_;
    while (other != NULL)
    {
      if (unit->x_ == other->x_ &&
          unit->y_ == other->y_)
      {
        handleAttack(unit, other);
      }
      other = other->next_;
    }

    unit = unit->next_;
  }
}

Aside from the pointer shenanigans to deal with walking a linked list, you’ll note that this is exactly like our original naïve method for handling combat: it compares each pairs of units to see if they’re in the same position.

The only difference is that we no longer have to compare all of the units in the battle to each other, just the ones close enough to be in the same cell. That’s the heart of the optimization.

Charging forward

We’ve solved our performance problem, but we’ve created a new problem in its stead. Units are now stuck in their cells. If you move a unit past the boundary of the cell that contains it, units in the cell won’t see it anymore, but nor will anyone else. Our battlefield is a little too partitioned.

To fix that, we’ll need to do a little work each time a unit moves. If it crosses a cell’s boundary lines, we need to remove it from that cell and add it to the new one. First, we’ll give Unit a method for changing its position:

void Unit::move(double x, double y)
{
  grid_->move(this, x, y);
}

Presumably, this gets called by the AI code for computer-controlled units and by the user input code for the player’s. All it does is hand-off control to the grid, which then does:

void Grid::move(Unit* unit, double x, double y)
{
  // See which cell it was in.
  int oldCellX = (int)(unit->x_ / Grid::CELL_SIZE);
  int oldCellY = (int)(unit->y_ / Grid::CELL_SIZE);

  // See which cell it's moving to.
  int cellX = (int)(x / Grid::CELL_SIZE);
  int cellY = (int)(y / Grid::CELL_SIZE);

  unit->x_ = x;
  unit->y_ = y;

  // If it didn't change cells, we're done.
  if (oldCellX == cellX && oldCellY == cellY) return;

  // Unlink it from the list of its old cell.
  if (unit->prev_ != NULL)
  {
    unit->prev_->next_ = unit->next_;
  }

  if (unit->next_ != NULL)
  {
    unit->next_->prev_ = unit->prev_;
  }

  // If it's the head of a list, remove it.
  if (cells_[oldCellX][oldCellY] == unit)
  {
    cells_[oldCellX][oldCellY] = unit->next_;
  }

  // Add it back to the grid at its new cell.
  add(unit);
}

That’s a mouthful of code, but it’s pretty straightforward. The first bit checks to see if we’ve crossed a cell boundary at all. If not, we can just update the unit’s position and we’re done.

If it has left its current cell, we remove it from that cell’s linked list and then add it back to the grid. Just like with a new unit, that will then insert it in the linked list for its new cell.

This is why we’re using a doubly-linked list: we can very quickly add and remove units from lists just by setting a few pointers. With lots of units moving around each frame, that can be important.

At arms’ length

This seems pretty simple, but I have cheated in one way. In the example I’ve been showing, units only interact when they have the exact same position. That’s true for checkers and chess, but less true for more realistic games. Those usually have attack distances to take into account.

This pattern still works fine. Instead of just checking for an exact location match, you’ll do something more like:

if (distance(unit, other) < ATTACK_DISTANCE)
{
  handleAttack(unit, other);
}

When range gets involved, though, there’s a corner case you need to consider: units in different cells may still be close enough to interact.

Here, B is within A’s attack radius even through their centerpoints are in different cells. To handle this, you will need to compare units not just in the same cell, but in neighboring cells too. To do this, first we’ll split the inner loop out of handleCell():

void Grid::handleUnit(Unit* unit, Unit* other)
{
  while (other != NULL)
  {
    if (distance(unit, other) < ATTACK_DISTANCE)
    {
      handleAttack(unit, other);
    }

    other = other->next_;
  }
}

Now we have a function that will take a single unit and a list of other units and see if there are any hits. Then we’ll make handleCell() use that:

void Grid::handleCell(int x, int y)
{
  Unit* unit = cells_[x][y];
  while (unit != NULL)
  {
    // Handle other units in this cell.
    handleUnit(unit, unit->next_);

    unit = unit->next_;
  }
}

Note also that we pass in the coordinates of the cell now and not just its unit list. Right now, this doesn’t do anything differently than the previous example, but we’ll expand it slightly:

void Grid::handleCell(int x, int y)
{
  Unit* unit = cells_[x][y];
  while (unit != NULL)
  {
    // Handle other units in this cell.
    handleUnit(unit, unit->next_);

    // Also try the neighboring cells.
    if (x > 0 && y > 0) handleUnit(unit, cells_[x - 1][y - 1]);
    if (x > 0) handleUnit(unit, cells_[x - 1][y]);
    if (y > 0) handleUnit(unit, cells_[x][y - 1]);
    if (x > 0 && y < NUM_CELLS - 1)
    {
      handleUnit(unit, cells_[x - 1][y + 1]);
    }

    unit = unit->next_;
  }
}

Those additional handleUnit() calls look for hits between the current unit and units in four of the eight neighboring cells. If any unit in those neighboring cells is close enough to the edge to be within the unit’s attack radius, it will find the hit.

We only look at half of the neighbors for the same reason that the inner loop starts after the current unit: to avoid comparing each pair of units twice. Consider what would happen if we did check all eight neighboring cells.

Let’s say we have two units in adjacent cells, close enough to hit each other, like the previous example. If, for each unit, we looked at all eight cells surrounding it, here’s what would happen:

  1. When we are finding hits for A, we would look at its neighbor on the right and find B. So we’d register an attack between A and B.
  2. Then, when we are finding hits for B, we would look at its neighbor on the left and find A. So we’d register a second attack between A and B.

Only looking at half of the neighboring cells fixes that. Which half doesn’t matter at all.

There’s another corner case you may need to consider too. Here, I’m assuming the maximum attack distance is smaller than a cell. If you have small cells and large attack distances, you may need to scan a bunch of neighboring cells, several rows out.

Design Decisions

There’s a relatively short list of well-defined spatial partitioning data structures, and one option would be to just go through them one at a time here. Instead, I tried to organize this by their essential characteristics. My hope is that once you do learn about quatrees and BSPs and the like, this will help you understand how and why they work, and why you might choose one over the other.

Is the partition hierarchical or flat?

Our grid example partitioned space into a single flat set of cells. In contrast, hierarchical spatial partitions divide the space into just a couple of regions. Then, if one of these regions still contains many objects, it’s subdivided. This process continues recursively until every region has fewer than some maximum number of objects in it.

Does the partitioning depend on the set of objects?

In our sample code, the grid spacing was fixed beforehand and then we just slotted units into cells. Other partitioning schemes are adaptable: they pick partition boundaries based on the actual set of objects and where they are in the world.

The goal is have a balanced partitioning, where each region has roughly the same number of objects in order to get the best performance. Consider in our grid example if all of the units were clustered in one corner of the battlefield. They’d all be in the same cell, and our code for finding attacks would regress right back to the original O(n²) problem that we’re trying to solve.

Are objects only stored in the partition?

You can treat your spatial partition as the place where the objects in your game live, or you can consider it just a secondary cache to make look-up faster, while also having another collection that holds just the list of objects directly.

See Also