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

Planning a Path to an Item Type
A* is the better algorithm to search for the least cost path from the bot’s
current position to a specific target position, but what about when the least
cost path is required to a item type — such as a rocket launcher — where
there may be many instances in the environment of the particular type? To
calculate the heuristic cost during an A* search, the algorithm must have
both a source position and a target position. Consequently, when using A*
to search for the closest instance of an item type, a search must be com-
pleted for each instance present in the game world before the one with the
least cost path can be chosen as the best item to move toward. This is okay
if your map contains only a handful of instances of an item, but what if it
contains many? After all, it’s not uncommon for RTS game environments
to include dozens or even hundreds of instances of resources like trees or
gold. That means numerous A* searches will be necessary to locate just
one item. This is not good.
When many similar item types are present, Dijkstra’s algorithm is the
better choice. As you’ve learned, Dijkstra’s algorithm “grows” a shortest
path tree outward from the root node until either the target has been
reached or the entire graph has been explored. As soon as the item searched
for is located, the algorithm will terminate and the SPT will contain the
path from the root to the closest item of the desired type. In other words, no
matter how many instances of an item type are present in the game world,
Dijkstra’s algorithm only needs to be run once to find the least cost path to
one of them
As it stands, the Dijkstra’s algorithm class used thus far in this book will
only terminate when a particular node index is found. As a result, the code
346 | Chapter 8
Creating a Path Planner Class
Figure 8.9. Planning a path to an item type
needs to be altered so the search will terminate upon the location of an
active item type (a giver-trigger). This can easily be achieved by specifying
as a template parameter a policy that acts as a termination condition. For
example:
template <class graph_type, class termination_condition>
class Graph_SearchDijkstra
{
/* OMITTED */
};
A termination condition policy is a class containing a single static method,
isSatisfied, which returns true if the conditions required for termination
are fulfilled. The signature of
isSatisfied looks like this:
static bool isSatisfied(const graph_type& G, int target, int CurrentNodeIdx);
A modified Dijkstra’s algorithm can use such a policy to determine when
the search should conclude. To facilitate this, the line:
//if the target has been found exit
if (NextClosestNode == m_iTarget) return;
found in Graph_SearchDijkstra::Search is replaced with:
//if the target has been found exit
if (termination_condition::isSatisfied(m_Graph,
m_iTarget,
NextClosestNode))
{
//make a note of the node index that has satisfied the condition. This
//is so we can work backward from the index to extract the path from
//the shortest path tree.
m_iTarget = NextClosestNode;
return;
}
Before this adapted algorithm can be used though, an appropriate termina
-
tion condition policy must be created. In Raven, item types are represented
by giver-triggers. Therefore, when searching for an item type, a search
should terminate when a graph node that has its
m_ExtraInfo field pointing
to an active trigger of the correct type is located.
Here is the termination condition policy class that ends a search based
upon those criteria:
template <class trigger_type>
class FindActiveTrigger
{
public:
template <class graph_type>
static bool isSatisfied(const graph_type& G, int target, int CurrentNodeIdx)
{
bool bSatisfied = false;
Practical Path Planning | 347
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