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 a Position
Planning a path from a bot’s current location to a target location is straight-
forward. The path planner must:
1. Find the closest visible unobstructed graph node to the bot’s current
location.
2. Find the closest visible unobstructed graph node to the target location.
3. Use a search algorithm to find the least cost path between the two.
The following code uses these steps. The comments should be adequate
explanation.
bool Raven_PathPlanner::CreatePathToPosition(Vector2D TargetPos,
std::list<Vector2D>& path)
{
//make a note of the target position
m_vDestinationPos = TargetPos;
//if the target is unobstructed from the bot's position, a path does not need
//to be calculated, and the bot can ARRIVE directly at the destination.
//isPathObstructed is a method that takes a start
//position, a target position, and an entity radius and determines if an
//agent of that size is able to move unobstructed between the two positions.
//It is used here to determine if the bot can move directly to the target
//location without the need for planning a path.
if (!m_pOwner()->GetWorld()->isPathObstructed(m_pOwner->Pos(),
TargetPos,
m_pOwner->BRadius()))
{
path.push_back(TargetPos);
return true;
}
//find the closest unobstructed node to the bot's position.
344 | Chapter 8
Creating a Path Planner Class
Figure 8.8. Planning a path to a position
//GetClosestNodeToPosition is a method that queries the navigation graph
//nodes (via the cell-space partition) to determine the closest unobstructed
//node to the given position vector. It is used here to find the closest
//unobstructed node to the bot’s current location.
int ClosestNodeToBot = GetClosestNodeToPosition(m_pOwner->Pos());
//if no visible node found return failure. This will occur if the
//navgraph is badly designed or if the bot has managed to get itself
//*inside* the geometry (surrounded by walls) or an obstacle.
if (ClosestNodeToBot == no_closest_node_found)
{
return false;
}
//find the closest visible unobstructed node to the target position
int ClosestNodeToTarget = GetClosestNodeToPosition(TargetPos);
//return failure if there is a problem locating a visible node from
//the target.
//This sort of thing occurs much more frequently than the above. For
//example, if the user clicks inside an area bounded by walls or inside an
//object.
if (ClosestNodeToTarget == no_closest_node_found)
{
return false;
}
//create an instance of the A* search class to search for a path between the
//closest node to the bot and the closest node to the target position. This
//A* search will utilize the Euclidean straight line heuristic
typedef Graph_SearchAStar< Raven_Map::NavGraph, Heuristic_Euclid> AStar;
AStar search(m_NavGraph,
ClosestNodeToBot,
ClosestNodeToTarget);
//grab the path
std::list<int> PathOfNodeIndices = search.GetPathToTarget();
//if the search is successful convert the node indices into position vectors
if (!PathOfNodeIndices.empty())
{
ConvertIndicesToVectors(PathOfNodeIndices, path);
//remember to add the target position to the end of the path
path.push_back(TargetPos);
return true;
}
else
{
//no path found by the search
return false;
}
}
Practical Path Planning
| 345
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