O'Reilly logo

Programming Game AI by Example by Mat Buckland

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

You can watch the non-penetration constraint in action by running the
craftily named Non Penetration Constraint.exe demo. Try altering the
amount of separation to see what effect it has on the vehicles.
Ü
NOTE For large numbers of densely packed vehicles such as you would see
in big congested flocks, the non-penetration constraint will fail occasionally and
there will be some overlap. Fortunately, this is not usually a problem as the
overlap is difficult to see with the human eye.
Coping with Lots of Vehicles: Spatial Partitioning
When you have many interacting vehicles, it becomes increasingly ineffi
-
cient to tag neighboring entities by comparing each one with every other
one. In algorithm theory, something called Big O notation is used to
express the relationship of time taken to the number of objects being pro
-
cessed. The all-pairs method we have been using to search for neighboring
vehicles can be said to work in O(n
2
) time. This means that as the number
of vehicles grows, the time taken to compare them increases in proportion
to the square of their number. You can easily see how the time taken will
escalate rapidly. If processing one object takes 10 seconds, then processing
10 objects will take 100 seconds. Not good, if you want a flock of several
hundred birds!
Large speed improvements can be made by partitioning the world space.
There are many different techniques to choose from. You’ve probably
heard of many of them — BSP trees, quad-trees, oct-trees, etc. — and may
even have used them, in which case you’ll be familiar with their advan-
tages. The method I use here is called cell-space partitioning, sometimes
called bin-space partitioning (that’s not short for binary space partitioning
by the way; in this case “bin” really means bin). With this method, 2D
space is divided up into a number of cells (or bins). Each cell contains a list
of pointers to all the entities it contains. This is updated (in an entity’s
update method) every time an entity changes position. If an entity moves
into a new cell, it is removed from its old cell’s list and added to the current
one.
This way, instead of having to test every vehicle against every other, we
can just determine which cells lie within a vehicle’s neighborhood and test
against the vehicles contained in those cells. Here is how it’s done step by
step:
1. First of all, an entity’s bounding radius is approximated with a box.
See Figure 3.18.
2. The cells that intersect with this box are tested to see if they contain
any entities.
126 | Chapter 3
Coping with Lots of Vehicles: Spatial Partitioning
3. All the entities contained within the cells from step 2 are examined to
see if they are positioned within the neighborhood radius. If they are,
they are added to the neighborhood list.
Ü
3D NOTE If you are working in 3D, simply make the cells cubes and use a
sphere as the neighborhood region.
If entities maintain a minimum separation distance from each other, then
the number of entities each cell can contain is finite and cell space parti-
tioning will operate in O(n) time. This means the time taken to process the
algorithm is directly proportional to the number of objects it’s operating on.
If the number of objects is doubled, the time taken is only doubled and not
squared as with O(n
2
) algorithms. This implies the advantage you gain
using space partitioning over the standard all-pairs technique is dependent
on how many agents you have moving around. For small numbers, say less
than fifty, there is no real advantage; but for large numbers, cell-space par
-
titioning can be much faster. Even if the entities do not maintain a
minimum separation distance and there is occasional overlap, on average
the algorithm will perform much better than O(n
2
).
I have implemented cell-space partitioning as a class template:
CellSpacePartition. This class uses another class template, Cell, to define
the cell structure.
template <class entity>
struct Cell
{
//all the entities inhabiting this cell
std::list<entity> Members;
//the cell's bounding box (it's inverted because the Windows' default
//coordinate system has a y-axis that increases as it descends)
InvertedAABBox2D BBox;
How to Create Autonomously Moving Game Agents
| 127
Coping with Lots of Vehicles: Spatial Partitioning
Figure 3.18. Cell-space partitioning. The circled vehicles are those within the white
vehicle’s neighborhood region.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required