Game Development Reference
In-Depth Information
agents and another used by flying agents. That way, you could easily have it so the
ground agents tend to stick to the roads, while the flying agents don
'
t really care. The
weights can even be dynamic. Let
re making a real-time strategy game, and
you want the flying units to avoid the guard towers the player sets up. One way of
solving this problem would be to have the guard towers themselves increase the
weight of nearby arcs. The flying units would tend to avoid them.
'
s say you
'
Rude NPC Behavior Should Be Corrected
When I was working at Super-Ego Games, I worked on an adventure game for
the PlayStation 3 called Rat Race, which was set in an office. Being an
adventure game, one of the major things you did was talk to the NPCs.
Unfortunately, other NPCs would plow right through the middle of these
conversations. We ended up creating conversation pathing objects that would
spawn in the middle of conversations, which would significantly raise the
weight of any arcs within a radius around that point. We also forced NPCs
with affected arcs in their path to replan. This caused NPCs to do the polite
thing and walk around the conversation.
There are many different searching algorithms to choose from, but A* (pronounced
A-Star) happens to be one of the most common used for this purpose. When most
people think of pathfinding, they think of A*. As I mentioned, A* is really just a
general-purpose search algorithm that happens to fit the problem of pathfinding
really well. It will find a path with a relatively small cost and do it fairly quickly.
There are many different implementations of A*, but they all come from the
same basic algorithm. A* was first described in 1968 by Peter Hart, Nils Nilsson,
and Bertram Raphael.
The A* algorithm works by analyzing each node and assigning it three values. The
first is the total cost to this node by the current path so far. This value is usually
referred to as g,orgoal. The second value is an estimated cost from this node to
the goal. It
'
s often referred to as h,orheuristic. The third value is an estimated cost
from the start of the path through this node to the goal, which is really just g+h.
This value is often called f,orfitness.
The point of these three values is to keep track of your progress so you know how
well you
s a calcu-
lated value (the sum of the costs of every node in the path so far), but how do you
find out how to calculate h and, by extension, f? The only rule for calculating h is
that it can
'
re doing. The value of g is something you know for sure since it
'
'
t be greater than the actual cost between this node and the goal node. Of
