Game Development Reference

In-Depth Information

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

paths.

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