Game Development Reference
then the NPC will place a higher utility on time, thus avoiding the river.
Utility values can be represented on a graph as weights on the edges,
as shown in Figure 5.4 . In this example, to travel from waypoint C2 to A2
directly via B2 will cost the NPC 3+3 = 6 points. Assuming a high number
means less desirable, we might attribute these weights with travel time
and say this route will take the NPC 6 hours. Further examination of the
graph shows that it will only cost 4 hours to travel from waypoint C2 to
A2 via points C1, B1, and A1.
In order to implement waypoints effectively in a game there needs to
be an efficient way to search through them to find the most appropriate
5.4.1 Searching Through Waypoints
There are High methods to find the shortest path from one node to another
in a graph. These include algorithms such as breadth-first search (BFS) and
depth-first search (DFS).
The BFS takes the given starting node and examines all adjacent nodes. Nodes
that are adjacent to a starting node are ones that are connected directly to
the starting node by an edge. In turn, from each of the adjacent nodes, nodes
adjacent to these are examined. This process continues until the end node is
found or the search for adjacent nodes has been exhausted. The algorithm
can be written as Listing 5.3 .
Listing 5.3 A Breadth-First Search Algorithm
1. Let i = 1.
2. Label starting node as i.
3. Find all unlabeled nodes adjacent to at least one node with label i. If there
are no adjacent nodes, stop because we have run out of nodes. If the
ending node is found, stop because we have found a path.
4. Label all nodes found in step 3 with i + 1.
5. Let i = i + 1, go to step 3.
This algorithm will always find the shortest path (Euclidean distance) from
the start to the end vertices, assuming that each vertex is the same distance
apart. For example, in a maze game where the environment is represented
by a grid of squares of equal size, each square represents a node for the
purposes of the algorithm. As shown in Figure 5.5 , the starting square
is labeled with a 1. Radiating out from this square, all adjacent squares
are labeled with a 2. All squares adjacent to the 2 squares not already
labeled with a 1 or a 2 are labeled with a 3. This process continues until
the destination square is found. This can be quite a long way of searching,
as almost all squares in the grid will be examined. This algorithm can be