Efficient path-finding on 2D tile-based multilevel map

Question

It's a question I've been thinking about for some time... How do you effiently find a path on a 2D tile-based multilevel map? The map I use, for example, is 2048 on 2048 tiles wide. It has 14 levels and levels are connected by stairs, ladders, rope holes, ...

How would you introduce level-changing tiles into A* in an efficient way? I know it is possible to add multilevel path-finding by just adding edges from an up-node to the corresponding down-node. But then path-finding isn't very efficient.

For example. What if the current node (e.g. [100, 100, 7]) is directly under the goal (i.e. [100, 100, 8]), and we can't go up anywhere near the current node. Instead we first have to go down some levels, and then up again, only then to reach the goal. A lot non-existing paths will be considered (= a lot of time and computation) before we finally find an existing path.

Feedback appreciated, Gillis

Answer 1

That would depend on what you're using for your heuristic. However, even if you're using shortest distance, the search algorithm will still work. It will spread out evenly until it finds somewhere to go down.

If you're already doing that and just want to find a way to improve the speed, there's a few options you can use.

• Add precursors to your search. If the result is on the next level down, add a requirement that the algorithm must first find a way down. The heuristic for this can be an average of the distance from all the ways down on the current level. Though you may find a way down that's not connected to part of the lower level you want to go to.

• Add "reachability" information to your grid. Do a breadth first search on each level after it's created. Mark each tile that's reachable with a "reachability" zone ID. Continue this until every tile is marked. For example, each tile with the ID "1" is reachable from every other tile with the ID "1" on the same level. Now when you're searching for a way down, you can rank the ladders based on which zone they connect to. If the tile you're trying to reach on the next level down is in zone "4" and you have a ladder on your current level that leads to zone "4" you can head for that one directly.

You can even extend the "reachability" idea to extend multiple levels. I would use a separate ID for that. This second ID would basically tell you if one tile was completely disconnected from another, so you could forgo the search entirely pretty quickly.

Basically the best way to speed up the searches is to add more data to your world. With better data your algorithm will be able to make better decisions about which paths to try and which to avoid. All in all, speeding up your search.

Answer 2

There's nothing intrinsic to the multi-level aspect that makes this harder or less efficient. A regular heuristic should work fine on a 3D map just as it does on a 2D map. What seems to be the issue for you is that certain edges make the graph maze-like, which makes the heuristic less effective. It's just a side-effect of your chosen design that these edges tend to be the vertical ones.

I would therefore suggest an approach that prioritises the vertical route before the overall route. Preprocess the map to have a graph of vertical connections between the levels, with the relevant distances between each connection precalculated. This lets you create a top-level path from one of the 14 levels to another, and you then need to construct the start, middle, and end of this path. The start is the route to the first vertical connection, the middle is the route from each vertical connection to the next, and the end is the route from the last vertical connection to the destination. Depending on memory availability it may even be practical to precalculate all the segments of the middle parts so that you only need to run A* on the first and last levels, since everything in between can be looked up from a table.

This won't necessarily produce the shortest path, as the distance travelled on the first and last levels might not lead to the optimal vertical connections. But the path is likely to be among the shorter options. You might consider running some tests and comparing the length of these paths with the slow-but-optimal naïve A* search to see how often the length is suboptimal, and how often that happens.

Answer 3

I honestly don't know the A* algorithm, but I know it's an extension of Dijkstra, and Dijkstra's doesn't have a limit to the number of nodes connected with each node. Here, the nodes are the tiles, so I guess you could check for every tile the algorithm visits, if it's a tile connected to a ladder, rope, etc, and add that tile to the path? Just guessing. Also, if each level forms a connected graph, avoid going through all levels but chekcing if starting and end points are in the same levels.

Hope I helped something, I've programmed a couple of algorithms to find paths that had things like yours, levels and all that (from another perspective), and I didn't have any particular trouble, I just did what I told you.

Answer 4

Some reading for those unfamiliar with HPA.

Some points in pseudo random order:

• HPA is perfectly applicable in 3D.
• It may be wise to shape the clusters according to where paths are expected to be, in this case keeping them 1 tile high is probably appropriate.
• A cluster may internally be split so that two entry points do not have a connecting path within the cluster, this is why your grand scale algorithm search a graph of exit nodes rather than clusters, since this graph will reflect the unconnectedness.
• A* lose effectiveness as the terrain grow more mazelike, this is true for HPA as well, but it remains a clear performance improvement.
• It is possible to add more levels to the optimization, for instance you could group your 16x16 clusters into 64x64 superclusters, further reducing the number of nodes in the initial graph.