Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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

share|improve this question
    
Similar to the issues faced in Dwarf Fortress. Have a look at this article for some little hints. –  Byte56 Dec 28 '12 at 22:39
1  
Why wouldn't A* work? If you've implemented A* correctly, it will eventually search the whole map (even with multiple levels -- there's nothing inherently 2D about A*, although it's often taught with a regular 2D grid as a demonstration, it doesn't need its nodes to be laid out that way) and it'll find any route to the destination, if one exists. Even if it has to back up in order to get there. –  Trevor Powell Dec 28 '12 at 23:04
    
That's the problem, it will search the whole map. I should've added that it works multilevel, but it's not efficient at all. See my previous comment: gamedev.stackexchange.com/questions/46392/… –  gillis Dec 28 '12 at 23:08

4 Answers 4

up vote 2 down vote accepted

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.

share|improve this answer
    
I like the idea of adding a zone ID to nodes! Does this seem like a good way to "tag" them? Get a list of all nodes. Pop the first node of the list, tag it with a zone and iterate all neighbours while popping them of the open list. When no more neighbours are available, go to the next available node. Increase zone ID and tag all neighbours. –  gillis Dec 28 '12 at 22:55
    
That sounds like a rather efficient way of doing it, yes. To easily extend that to multiple levels you can just keep lists of zone IDs that have ladders into other zone IDs, making a simple connectivity graph without the need to iterate over all the nodes again. –  Byte56 Dec 28 '12 at 22:58
    
Cool! And then just do pathfinding on the zones? With zones as nodes and the stairs between the zones as edges? –  gillis Dec 28 '12 at 23:03
    
Yep. Then use your HPA to get around the small obstacles. But knowing the general direction will help a lot. –  Byte56 Dec 29 '12 at 3:40

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.

share|improve this answer
    
Yes, if you made a 2D map maze-like it'd have similar problems. 3D is worse for graph search mostly because the branching factor can be higher. –  amitp Dec 29 '12 at 19:54

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.

share|improve this answer
    
But 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 other non-existing paths will be considered (= a lot of time and computation) before we finally find the existing path. Is there any way to speed this up? Preprocessing? –  gillis Dec 28 '12 at 22:03
    
Ok, I don't know how to speed that up, Dijskstra, and as I've seen on wikipedia, A*, go through every tile, so you can be sure that it will get to the point. What I can think is that you could subdivide you map into groups (big groups) of tiles to form a connected graph of a lot less nodes, say that if the whole map is 1000x1000x1000, you could get a graph whose nodes are groups of directly connected tiles and you could reduce that to 10x10x10 bigger groups. You can first, by A* or Dijstra, and knowing how these are connected get a general path, and then modify A* so it never leave the nodes. –  MyUserIsThis Dec 28 '12 at 22:12
    
I continue with what I say up. I'm imagining a big maze made out of rooms with obstacles, every room is made out of tiles so instead of greedily, heuristically or bruteforce a path through tiles, do it first between the rooms, knowing how they're connected, so you can build a path of rooms, and then don't let the A* leave these rooms: that should be easier by just checking if a tile belongs to a room that is in your general path. –  MyUserIsThis Dec 28 '12 at 22:16
    
That's what I have already done, but I want it even more efficient :) Here's a good read on how the clustering and the pathfinding on them is done: aigamedev.com/open/review/near-optimal-hierarchical-pathfinding and cs.ualberta.ca/~mmueller/ps/hpastar.pdf –  gillis Dec 28 '12 at 22:19

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.
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.