A flat map has but one level in its representation. It's rare for games to have only one level -- often there is a "tile" level and then a "sub-tile" level in which objects can move within a tile. However, it's common for path-finding to occur on only one of the levels.
A hierarchal map has many levels in its representation. A heterogenous hierarchy typically has a fixed number of levels, each with different characteristics. Ultima VI, for example, has a "world" map, on which are cities and dungeons. You can enter a city or dungeon and be in a second map level. In addition, there are "layers" of worlds on top of one another, making for a three-level hierarchy. A homogeneous hierarchy has an arbitrary number of levels, each with the same characteristics. Quad trees and oct trees can be considered to be homogeneous hierarchies.
In a hierarchal map, path-finding may occur on several levels. For example, if a 1024x1024 world was divided into 64x64 "zones", it may be reasonable to find a path from the player's location to the edge of the zone, then from zone to zone until reaching the desired zone, then from the edge of that zone to the desired location. At the coarser levels, long paths can be found more easily because the path-finder does not consider all of the details. When the player actually walks across each zone, the path-finder can be invoked again to find a short path through that zone. By keeping the problem size small, the path-finder can run quicker.
Through most of this document I've assumed that A* was being used on a grid of some sort, where the "nodes" given to A* were grid locations and the "edges" were directions you could travel from a grid location. However, A* was designed to work with arbitrary graphs, not only grids.
One form of graph that you may want to use if your game does not have terrain, and has polygonal obstacles, is based on "navigation points".
In this diagram, I've marked the corners of every obstacle with a blue dot. In addition, the start and end points are blue dots. These navigation points are the nodes to feed to A*. In addition, A* needs to know which points are connected. To determine this, look at each pair and decide whether the straight line between the two points is unobstructed. In this diagram, these edges are the light blue lines. The third piece of information A* needs is distances between the points. Depending on how your units move, that can be manhattan distance, diagonal grid distance, or straight line distance.
A* will then consider paths from navigation point to navigation point.
The dotted green line is one such path. This is much faster
than looking for paths from grid point to grid point, as you have only
2 + 4*(#obstacles)
navigation points, instead of xsize *
ysize
grid locations. When there are no obstacles in the way, A*
will do very well -- the start point and end point will be connected
by an edge, and A* will find that path immediately, without expanding
any other navigation points. Even when there are obstacles to
consider, A* will jump from corner to corner until it finds the best
path, which will still be much faster than looking for a path from a
grid location to another.
If your units can only move on roads, you may want to consider giving A* the road and intersection information. Each intersection will be a node in the graph, and each road will be an edge. A* will find paths from intersection to intersection, which is typically much faster than exploring all possible directions, one grid space at a time. To save time, build the node/edge graph ahead of time instead of when you run A*.
For some applications, your units may not start and end on intersections. To handle this case, each time you run A*, you will need to modify the node/edge graph. Add the starting and ending points as new nodes, and add edges between these points and their nearest intersections. After path-finding, remove these extra nodes and edges from the graph so that the graph is ready to be used for the next invocation of A*.
In this diagram, the intersections are blue circles. In addition, the start and end points are blue circles. These are the nodes in the graph for A*. The edges are the roads between the nodes, and these edges should be given the driving distance along each road (shown in black text).
In the "roads as edges" framework, you can incorporate one-way roads as unidirectional edges in the graph.
If you want to assign costs to turning, you can extend the framework a bit: instead of nodes being locations, consider nodes to be a <location, direction> pair (a point in state space), where the direction indicates what direction you were facing when you arrived at that location. Replace edges from X to Y with edges from <X, dir> to <Y, dir> to represent a straight drive, and from <X, dir1> to <X, dir2> to represent a "turn". Each edge represents either a straight drive or a turn, but not both. You can then assign costs to the edges representing turns.
If you also need to take into account turn limitations, such as "only right turns", you can use a variation of this framework in which the two types of edges are always combined. Each edge represents an optional turn followed by a straight drive. In this framework, you can represent restrictions like "you can only turn right": include an edge from <X, north> to <Y, north> for driving straight, and an edge from <X, north> to <Z, east> for the right turn followed by a drive, but don't include <X, north> to anything west, because that would mean a left turn, and don't include anything south, because that would mean a U-turn.
In this framework, you can model a large city downtown, in which you have one-way streets, turn restrictions at certain intersections (often prohibiting U-turns and sometimes prohibiting left turns), and turn costs (to model slowing down and waiting for pedestrians before you turn right). Compared to grid maps, A* can find paths in road graphs environment fairly quickly, because there are few choices to make at each graph node, and there are relatively few nodes in the map.
Back: References | Up: Home | Next: Goals |
Last modified: Sun Nov 18 11:32:17 2001 From Amit's Game Programming Site | Copyright (C) 2000, Amit J. Patel |