Sometimes, it’s not the time needed to calculate a path, but the space used by paths for hundreds of units that is the limiting factor. Pathfinders require space for the algorithm to run, plus space to store a path. The temporary space required for the algorithm to run (with A*, the OPEN and CLOSED sets) typicaly is larger than the space required to store the resulting path. By restricting your game to compute only one path at a time, you can minimize the amount of temporary space needed. In addition, the choice of data structure for your OPEN and CLOSED sets can make a big difference for minimizing temporary space. This section will instead focus on minimizing the space used by the resulting paths.
Locations vs. directions#
A path can be either locations or directions. Locations take more space, but have the advantage that it is easy to determine an arbitrary location or direction in the path without traversing the path. When storing directions, only the direction can be determined easily; the location can only be determined by going through the entire path, following the directions. In a typical grid map, locations may be stored with two 16-bit integers, making each step take 32 bits. There are far fewer directions, however, so they can take less space. If the unit can move in only four directions, each step takes only 2 bits; if the unit can move in six or eight directions, each step takes 3 bits. Either of these is a significant savings over storing locations in the path. Hannu Kankaanpaa suggests that you can further reduce the space requirement by storing the relative direction (“turn right 60 degrees”) instead of the absolute direction (“go north”). Some relative directions may not make sense for some types of units. For example, if your unit is moving north, it’s unlikely that the next step is to go south. In a six directional game, you have only five meaningful directions. On some maps, perhaps only three of those directions (straight, left 60 degrees, right 60 degrees) make sense, but on other maps, turning right 120 degrees may be a valid move (for example, when going up a steep mountain path with switchbacks).
Path compression#
Once a path can be found, it can be compressed in some way. A general purpose compression algorithm could be used, but will not be discussed here. A compression algorithm specific to paths could be used to shorten either location-based paths or direction-based paths. Before deciding, look at typical paths in your game to decide which kind of compression will work best. In addition, consider ease of implementation (and debugging), the size of the code, and whether it really matters. If you have a limit of 300 units and only 50 are walking at any one time, and paths are short (100 steps), the total memory requirement might only be <50k anyway, and not worth worrying about compression.
Location storage#
In maps where obstacles rather than terrain are the main influence in determining paths, there may be many straight-line segments in the path. If this is the case, then a path need contain only the endpoints (sometimes called waypoints) of those line segments. Movement consists of examining the next point on the path and moving in a straight line towards it.
Direction storage#
When directions are stored, it may be the case that a particular direction is followed many times in a row. You can take advantage of that common pattern to store the path in less space.
One way to store the path is to store both a direction and a number which indicates how many times the unit should move in that direction. Unlike the optimization for location storage, this optimization can make things worse if a direction is not taken many times in a row. Also, for many straight lines where location compression is useful, direction compression is not, since the line may not be aligned with one of the walking directions. With relative directions, you can eliminate “keep going forward” as a possible direction. Hannu Kankaanpaa points out that with an eight direction map, you can eliminate forwards, backwards, and the 135 degree left and right turns (assuming your map allows it), and you can then store each direction with only two bits.
Another way to store the path is to use variable length encoding. The idea is to use a single bit (0) for the most common step: go straight. Use a 1 to mark a turn, and follow the 1 by some number of bits to represent the turn. In a four directional map, you can turn only left or right, so you might use 10 for left and 11 for right.
Variable length encoding is more general and may compress better than run length encoding for mixed paths, but not as well for long straight paths. The sequence (north, straight six steps, turn left, straight three steps, turn right, straight five steps, turn left, straight two steps) is represented as [(NORTH, 6), (WEST, 3), (NORTH, 5), (WEST, 2)] with run length encoding. If each direction is two bits and each distance is eight bits, this path requires 40 bits to store. With variable length encoding, you use one bit for each step and two bits for each turn—[NORTH 0 0 0 0 0 0 10 0 0 0 11 0 0 0 0 0 10 0 0]—a total of 24 bits. If the initial direction and each turn imply one step, you can save one bit per turn, resulting in 20 bits to store the path. However, longer paths can take more space with variable length encoding. The sequence (north, straight two hundred steps) is [(NORTH, 200)] with run length encoding, a total of 10 bits. The same sequence with variable length encoding is [NORTH 0 0 ...], a total of 202 bits.
Computed waypoints#
A waypoint is a point along a path. Instead of storing every step along the way, after pathfinding a post-processing step can collapse multiple steps into a single waypoint, usually at places where the path changes direction or at major locations like cities. The movement algorithm will then follow a path between waypoints.
Limited path length#
Given that map conditions or orders may change, it may not make sense to store a long path, since at some point the remainder of the path may not be of any use. Each unit can store a fixed number of steps at the beginning of the path, and then use path recalculation when the path has almost been traversed. This approach allows for control of the amount of data used per unit.
Summary#
Paths can potentially take up a lot of space in a game, especially when the paths are long and there are many units present. Path compression, waypoints, and beacons reduce the space requirements by storing many steps in a small amount of data. Waypoints rely on straight-line segments being common so that we have to store only the endpoints, while beacons rely on there being well-known paths calculated beforehand between specially marked places on the map. If paths still take up too much space, the path length can be limited, resulting in the classic time-space tradeoff: to save space, information can be forgotten and recalculated later.