Multilevel 2D grid graph and A*

Question

I've coded up a little grid based dungeon game. Everything working quite nicely in a Tile[,]. The AI uses basic GOAP for tasks and A* for moving around. Tile reachability is done using a floodfill.

Thinking about what my next step would be, I decided to change the art style from being the typical dungeon to a more sci-fi approach and thought it'd be great to have multiple levels.

This is where I ran into a problem because A* in a 2d grid I understand. But adding extra levels makes it a wee bit harder. My initial thoughts would be to add connections to the next levels in 'stairs' or 'elevator' tiles and adding these to the neighbor list of a Tile for evaluation by A*.

But this throws my heuristic for a loop. I'm using Manhattan distance.

TL;DR: How should I improve my heuristic for multi level path finding?

Answer 1

If you go for this connections approach your heuristic will be made up of two parts. First you find the closest connection point to the target level and apply classic Manhattan distance from your current location to this stairs/elevator. Next you check the distance on the target level from the connection point to the actual target, again just Manhattan. You should probably add some costs for the elevator/stairs as well. This should give you a pretty valid estimation of the costs.

Another approach would be threedimensional geometry, so you calculate ypur Manhattan distance with also the height difference in mind: H = dh * dh + dw * dw + dl * dl. Then you add some factor for the "up"-cost and your are good to go. This is surely faster than the first approach but also not very exact if you cannnot change levels at any time. It could still be valid if your "up"-cost is high enough, but that depends on the maps.

Depending on how you implemented your algorithm this should work without much change to your actual pathfinding code, but you will have to keep track auf multiple levels and move your agent from one plane to another.