Map representations

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. There are a variety of map representations that can be used with A*.

Grid

A grid map uses a uniform subdivision of the world into small regular shapes called "tiles". Common grids in use are square, triangular, and hexagonal. Grids are simple and easy to understand; thus, I have focused on them in this document.

Polygonal maps

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.

You can read more about generating the links between vertices on this forum post.

Flat

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 pathfinding to occur on only the larger level.

Hierarchical

Pathfinding algorithms tend to be worse than linear: if you double the distance needed to travel, it takes more than twice as long to find the path. You can think of pathfinding as searching some area like a circle―when the circle's diameter doubles, it has four times the area.

One way to reduce the problem is to have multiple levels of searching. For example, to get from your home to a location in another city, you would find a path from your chair to your car, from the car to the street, from the street to a freeway, from the freeway to the edge of the city, from there to the other city, then to a street, to a parking lot, and finally to the door of the destination building. There are several levels of searching here:

  • At the street level, you are concerned with walking from one location to a nearby location, but you do not go out on the street.
  • At the city level, you go from one street to another until you find the freeway. You do not worry about going into buildings or parking lots, nor do you worry about going on freeways.
  • At the state level, you go from one city to another on the freeway. You do not worry about streets within cities until you get to your destination city.

Dividing the problem into levels allows you to ignore most of your choices. When moving from city to city, it is quite tedious to consider every street in every city along the way. Instead, you ignore them all, and only consider freeways. The problem becomes small and manageable, and solving it becomes fast.

A hierarchical map has many levels in its representation. A heterogenous hierarchy typically has a fixed number of levels, each with different characteristics. Ultima V, 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 hierarchical map, pathfinding 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 pathfinder does not consider all of the details. When the player actually walks across each zone, the pathfinder can be invoked again to find a short path through that zone. By keeping the problem size small, the pathfinder can run quicker.

You can use multiple levels with graph-searching algorithms such as A*. One paper on this topic is Hierarchical A*: Searching Abstraction Hierarchies Efficiently. You do not need to use the same algorithm at each level.

A similar approach is to use varying resolution. First, plot a path with low resolution. As you get closer to a point, refine the path with a higher resolution. This approach can be used with path splicing to avoid moving obstacles.

Wraparound maps

If your world is spherical or toroidal, then objects can "wrap" around from one end of the map to the other. In such a world, it's not clear how to give A* the information it needs. The shortest path could lie in any direction, so all directions must be explored.

One approach is to restrict your world so that all paths will not wrap around more than once. With this restriction, you can treat the map as being adjacent to copies of itself. With a square map, create four neighboring copies adjacent to the original and perform pathfinding on this new map. Put the goal in the center (original) map and put a copy of the starting position on the original and each of the four copies. Then create a synthetic starting node that has an edge leading to each of the five starting positions with zero cost and find a path from the synthetic starting node to the goal.

Road maps

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 pathfinding, 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.

Duals

The road network example shows that the representation of locations as vertices and edges as connections between locations is not necessary. You can swap vertices and edges in many cases. On a square grid map, you can make the vertices the center of the border between two adjacent squares. You can make the edges the connections within a square between the edges. This form of graph makes it easier to represent very thin objects like walls that are placed between squares.

Skip links

A pathfinding graph constructed from a grid typically assigns a vertex to each location and an edge to each possible movement from a location to an adjacent location. The edges are not constrained to be between adjacent vertices. A "skip link" is an edge between non-adjacent vertices. It serves to shortcut the pathfinding process.

What should the movement cost be for a skip link? There are two approaches:

  • Make the cost match the movement cost of the best path. This preserves nice properties of A*, like finding optimal paths. To give A* a nudge in the right direction, break the tie between the skip link and the regular links by reducing the skip link's cost by 1% or so.
  • Make the cost match the heuristic cost. This makes a much stronger impact on performance but you give up optimal paths.

Adding skip links is an approximation of a hierarchical map. It takes less effort but can often give you many of the same performance benefits.

Waypoints

A waypoint is a point along a path. Waypoints can specific to each path or be part of the game map. Waypoints can be entered manually or computed automatically. In many real-time strategy games, players can manually add path-specific waypoints by shift-clicking. When automatically computed along a path, waypoints can be used to compress the path representation. Map designers can manually add waypoints (or "beacons") to a map to mark locations that are along good paths or an algorithm can be used to automatically mark waypoints on a map.

Since the goal of skip links is to make pathfinding faster when those links are used, skip links should be placed between waypoints. This will maximize their benefit.

If there are not too many waypoints, the shortest paths between each pair of waypoints can be precomputed beforehand. The common case will then be a unit following its own path until it reaches a waypoint, and then it will follow the precomputed shortest path between waypoints, and finally it will get off the waypoint highway and follow its own path to the goal.

Using waypoints or skip links with false costs can lead to suboptimal paths. It may be possible to smooth out a bad path in a post-processing step or in the movement algorithm.