Pathfinding With Signposts
Today I’m going to talk about the signpost algorithm for pathfinding. This is a way of preprocessing your dungeon map and caching the results in ‘signposts’ to enable very fast pathfinding between any two arbitrarily-chosen points on the map. The effect varies with different kinds of maps, but signpost pathfinding is cheapest where strategies like A* are most expensive – that is, in longer-range pathfinding with lots of twists and turns – and signpost pathfinding is least accurate where strategies like A* are cheapest – that is, in short-range pathfinding across an open space. So the best application of this technology is to do pathfinding when the desired paths are long or complicated, leaving the exhaustive-search optimal strategies like A* for shorter-range searches.
What you can expect using signposts really depends on what kind of maps your game generates. For maps in which few path alternatives are available, a few signposts can make perfectly optimal pathfinding proceed much faster than strategies like A*. For large, moderately complex maps with a lot of loops and open areas, ‘several’ signposts can speed up pathfinding for long complex paths by a factor of about four over A*, while admitting something like five percent extra path length on average – up to ten percent in some cases, but actually finding optimal paths in others. Signposts won’t provide much speedup on very short-range pathfinding, and produce observably suboptimal results when both origin and destination are in the same open area; other strategies should be used at very short range. You will probably prefer not to use it unless the pathfinding is to cover at least some minimum distance.
A ‘signpost’ is a data structure that that gives the shortest stepwise distance from some location on the map to every other location on the map. Signposts are important because you can use that data to very quickly find an optimal route from any square to the signpost. Read the signpost data to find the stepwise distance from the origin square to the signpost. At least one of its neighbor squares will have a stepwise distance to the signpost (which you can also get from the signpost) that is shorter by exactly the same distance that it is from the origin square to that neighbor. Step from the origin to any such neighbor; it doesn’t matter which. Having done so you are guaranteed to have taken one step on an optimal path toward the signpost.
Signposts are also important because these paths are reversible. Connectivity on a regular roguelike grid map has the same costs regardless of what direction you’re going, so you can find an optimal path from a signpost to any square on the map in exactly the same way – just traverse it in the other direction.
And that means that if you want to go from any point to any other, and you have a signpost, you can find a path to the signpost from the origin, then find a path from the signpost to the destination, and paste them together. That gives you a path without doing an expensive search.
It will not be an optimal path, unless the signpost happened to be on an optimal path between those two points. But there are four things that make it better.
First, at every point along the path, you can detect all steps that are on optimal paths to the signpost. Therefore, you can start at whichever end has the longer stepwise distance, and try to step toward the other end directly. If you can get there without stepping off of an optimal path to the signpost, you are done, because you have just found an optimal path between the two points.
Second, because you know both the origin and destination of the path you’re trying to find, you can pick the longest possible path segment leading away from the signpost that is on an optimal path for both origin and destination – and chop that segment off of both before you join them, giving you a path which might go nowhere near your signpost. If the dungeon is a ‘spanning tree’ with exactly one path between any two points, or in any case where the above trick could possibly have worked, this trick is guaranteed to find an optimal path.
The third thing is that given a signpost, you can check the stepwise length of the path available via that signpost very quickly. So if you have a dozen signposts scattered around your map, you can quickly compare them and find the one that offers you the shortest path.
The fourth thing is that when you calculate a path using each of two or more different signposts, you can check to see if the paths cross and, if so, whether you can find a shorter total path by using one up to the point of crossing and the other after the point of crossing. You can then take this new shorter path and check it against the path generated by using a third signpost to see if you find a different crossing. And a fourth, and a fifth, etc, although there is a rapidly diminishing rate of return on trying to improve paths in this way.
In some cases there is absolutely no point in trying to improve your path. For example, If you ‘win’ initially when trying to step from origin to destination without leaving the optimal path to the signpost, you have an optimal path. An equivalent situation can occur when you initially try to find the longest possible shared segment for source and destination from a signpost. If you find that there is an optimum path from the signpost to the destination that actually goes through the origin, or from the signpost to the origin that goes through the destination, the maximum shared segment which you will chop out of your combined path actually contains all of one segment or the other. When either of these things happens, what remains after chopping it out is a provably optimal path, and all attempts to improve on it will be futile.
The path you will find using one signpost has two optimal segments (or one in the cases above, but as noted it’s pointless to try to improve on that). One endpoint of the first is the origin, and one endpoint of the second is the destination. If one of the optimal segments of a path from a different signpost crosses one of these segments but shares its endpoint with the other, then the new segment from the crossing point to the shared endpoint is guaranteed to be no longer than the original path from the crossing point to the shared endpoint, and may be shorter. If you started with the signpost that gave you the shortest path available via a single signpost, this is in fact the only possible crossing scenario that will shorten your path. Therefore the new path will also be a path composed of two optimal segments, which will be in turn subject to the same property.
There is a strategy for placing signposts to guarantee optimal pathfinding. Such complete coverage may be used to establish an upperbound on the number of signposts you need for a given map. A single signpost can be used to instantly find optimal paths within a ‘spanning tree’ map – that is, a map in which there is only one path between any two points. Whenever you modify a spanning tree map by adding a connection, you create a loop; for each such new connection, you will need to add a signpost whose point any path through that new connection must cross. This guarantees that any optimal path within that map, either must pass through one of the signposts (and can therefore be discovered by using that signpost) or occurs in a segment of the map which has the spanning tree property (and can therefore be discovered using either signpost). Every map may be characterized as a spanning tree with additional connections.
Some properties of signposts are surprising. It matters where your signposts are placed, because you want to use them to give you choices between possible paths. But if you aren’t using so many that you can guarantee optimal paths, it doesn’t matter nearly as much as you might suppose that each signpost should be placed optimally, because usually segments that go from a suboptimally-placed signpost to the nearest major hallway will get chopped off anyway. The spanning tree property above means that if the origin and destination are within a so-called ‘perfect maze’ an optimal path can always be efficiently found using a single signpost. Finally, provably optimal paths are more frequently found using signposts that are far from both origin and destination than using signposts that are closer to both, provided either that the origin is between the signpost and destination, or the destination is between the signpost and the origin.
If your maps are large, you may want to use more signposts, each of which contains only local information about overlapping areas. Pathfinding then would need to stitch together several segments; origin to some intermediate signpost to some other intermediate signpost to destination. But for most maps that are relevant to roguelike games, four signposts would be plenty. Even for games with very large levels it’s hard to imagine needing more than a dozen.
Anyway, if you use signposts, do experiment with them. If you have signposts which are well-placed relative to origin and destination, it’s rarely worth trying more than three times to improve a signpost-generated path. But always experiment and benchmark, because what constitutes ‘good placement’ for signposts is in some ways counterintuitive, and unless you can actually see test results you may not be able to easily predict the effect, both on path quality and compute time required to find it, of seemingly small changes or of maps having different character.