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

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

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.