Game Development Reference
In-Depth Information
course, the more accurate the guess, the faster you can find a path. In this case, a
simple distance check will suffice:
diff = pathingNodePosition - goalNodePosition
heuristic = diff.Length()
This allows us to easily calculate f.
The algorithm also maintains a priority queue called the open set. The open set is a
list of nodes that are being considered, and the node with the lowest fitness score is
at the front of the queue. The process starts with the node nearest the starting loca-
tion. During each iteration of the algorithm, the front node is popped off the queue.
The neighbors of this node are evaluated (potentially updating their magic values)
and added to the open set. This process continues until the node removed from the
queue is the goal node. Note that it
s quite possible to see the goal node from a par-
ticular neighbor and ignore it if its f score is not low enough. This simply means that
you haven
'
t found the best path yet. Once you have processed a node, you mark it as
closed. This allows you to ignore neighbors you
'
ve already processed. If the open set
ever becomes empty before finding the goal node, it means you
'
'
re done, and no path
could be found.
You Can
'
t Always Get There from Here
No matter how solid you think the data is, there are times when you won
'
tbe
able to find a path. Make sure that you have a graceful recovery plan.
Agents Can Be Stubborn
While working on Rat Race for Super-Ego Games, our solution to failing to find
a path was to re-run the higher decision-making logic. Unfortunately, the
decision was almost always to try and do the exact same thing. Since AI was
only updating once a second, the NPC would take a half step, stop, play a
confused-looking idle animation (many of our idle animations were confused
looking; it was a comedy game after all), and then repeat the process. Our
solution was to have them abandon that particular decision, which meant that
they couldn
'
t choose it the second time around.
I
'
ve written a complete (albeit simple) pathfinding system that
'
s included with the
'
source code for this topic. It
s a bit lengthy to reprint here, but you can check it out
yourself. The code is highly commented, and if you have any questions, you can
