Game Development Reference
In-Depth Information
plex games may not require an AI, such as
Rock Band
. The same can be said for
games that are 100% multiplayer and have no
NPCs
(non-player characters). But
for any game where the design dictates that NPCs must react to the actions of the
player, AI algorithms become a necessity.
Pathfinding
Pathfinding is the solution to a deceptively simple problem: Given points A and
B, how does an AI
intelligently
traverse the game world between them?
The complexity of this problem stems from the fact that there can be a large set
of paths between points A and B but only one path is objectively the best. For ex-
ample, in
Figure 9.1
, both the red and blue paths are potential routes from point A
to B. However, the blue path is objectively better than the red one, simply because
it is shorter.
Figure 9.1
Two paths from A to B.
So it is not enough to simply find a single valid path between two points. The ideal
pathfinding algorithm needs to search through all of the possibilities and find the
absolute best path.
Representing the Search Space
The simplest pathfinding algorithms are designed to work with the
graph
data
structure. A graph contains a set of
nodes
, which can be connected to any number
of adjacent nodes via
edges
. There are many different ways to represent a graph in
memory, but the most basic is an adjacency list. In this representation, each node
contains a list of pointers to any adjacent nodes. The entire set of nodes in the
graph can then be stored in a standard container data structure.
Figure 9.2
illus-
trates the visual and data representations of a simple graph.
