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

to query the navigation graph for particular item types as well as for spe
-
cific node indexes. You’ll be seeing exactly how this is done later in the
chapter.
z
TIP When designing the maps for some games it’s a good idea to place fre
-
quently used items such as ammunition and armor directly in the most
commonly used paths of the game agents. This helps the agents because they
will tend to stay focused on the more important game objectives instead of hav
-
ing to run around searching for weapons and ammo.
Using Spatial Partitioning to Speed Up Proximity Queries
One of the most frequently used methods of a path planning class is a func
-
tion that determines the closest visible node to a given position. If this
search is undertaken by iterating through all the nodes in order to find the
closest, the performance will be in O(n
2
) time: Each time the number of
nodes doubles, the time taken to search them increases fourfold. As you
saw in Chapter 3, the efficiency of such searches can be improved by using
a spatial partitioning technique such as cell-space partitioning, BSP trees,
quad-trees, or any other of the numerous methods available. For navigation
graphs of over a couple hundred nodes, spatial partitioning gives dramatic
speed increases as the search time becomes a function of the node density,
O(d), rather than the number of nodes; and since the density of nodes
throughout navgraphs tends to be fairly consistent, the time taken to do a
node proximity query will be constant. Consequently, the
Raven_Game class
partitions a navgraph’s nodes using the cell-space method when a map is
loaded.
Ü
NOTE There is no code written for this chapter per se. All the demos have
been created by compiling the Raven project files with certain options switched
on or off to demonstrate each technique I discuss. Because of this, the demos
use compiled Lua script files to prevent you from twiddling with options that may
crash the demos. For full twiddling rights, please compile the Raven project
proper!
Creating a Path Planner Class
The majority of the remainder of this chapter will be spent following the
development of a path planning class capable of executing and managing
the numerous graph search requests required by a Raven bot. This class is
called
Raven_PathPlanner and each bot will own an instance of it. The class
will start off simple, but as the chapter progresses its capabilities will be
expanded incrementally, providing the opportunity to demonstrate how to
solve many of the typical problems encountered when developing a path
planning AI.
First let’s consider the minimum functionality a path planning object
must provide. A Raven bot at the very least should be able to plan a path
342 | Chapter 8
Creating a Path Planner Class
from its current position to any other location, given that both positions are
valid and navigable, and a path is possible. A Raven bot should also be
capable of planning the least cost path between its current position and a
specific item type, such as a health pack. As a result, the path planning
class must have methods for searching the navgraph for such paths and for
accessing the resultant path data. With these features in mind let’s have a
first try at a path planning class.
class Raven_PathPlanner
{
private:
//for legibility
enum {no_closest_node_found = -1};
private:
//A pointer to the owner of this class
Raven_Bot* m_pOwner;
//a local reference to the navgraph
const Raven_Map::NavGraph& m_NavGraph;
//this is the position the bot wishes to plan a path to reach
Vector2D m_vDestinationPos;
//returns the index of the closest visible and unobstructed graph node to
//the given position. If none is found it returns the enumerated value
//"no_closest_node_found"
int GetClosestNodeToPosition(Vector2D pos)const;
public:
Raven_PathPlanner(Raven_Bot* owner);
//finds the least cost path between the agent's position and the target
//position. Fills path with a list of waypoints if the search is successful
//and returns true. Returns false if unsuccessful
bool CreatePathToPosition(Vector2D TargetPos, std::list<Vector2D>& path);
//finds the least cost path to an instance of ItemType. Fills path with a
//list of waypoints if the search is successful and returns true. Returns
//false if unsuccessful
bool CreatePathToItem(unsigned int ItemType, std::list<Vector2D>& path);
};
This class provides the minimum functionality a game agent requires. Let’s
take a closer look at the methods that create the paths.
Practical Path Planning | 343
Creating a Path Planner Class

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