Game Development Reference

In-Depth Information

In the graph of
Figure 5.3
, an NPC wanting to move from waypoint A

to waypoint L could not simply plot a straight line between the two

waypoints as they are not connected directly by an edge. The NPC then

has the choice of navigating from waypoint A to waypoint L with the

following sequences: A,M,J,K,L or A,B,C,D,E,F,I,J,K,L or A,M,I,J,K,L. The

second sequence is obviously longer than the others, although all are

legitimate paths. So how do you determine the best path from one

waypoint to another?

Usually you will want an NPC to move from one waypoint to another via

the shortest path. Often the meaning of shortest refers to the Euclidian

distance between points, but not always. In real-time strategy (RTS)

games where maps are divided up into grids of differing terrain, the

shortest path from one point to another may not be based on the actual

distance, but on the time taken to traverse each location; for example, the

shortest Euclidean distance from point C2 to point A2 of
Figure 5.4
will

take an NPC through a river. Moving through the river may take the NPC

twice as long as if it were to go the longer distance across the bridge. The

definition of shortest is therefore left up to a matter of utility. The term

utility
originates in classical game theory and refers to the preferences

of game players. If time is more important to an NPC than distance,

FIG 5.4
An example tiled strategy game map showing different terrain and a graph with utilities.