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.
Search Nedrilad ::

Custom Search