While trying to resolve the issue in http://www.gamedev.net/community/forums/topic.asp?topic_id=465874 I have a more complicated one in mind I figured I'd get out of the way now. I have an idea of how to do what I'm planning to do, but want some other opinions since there's probably a much easier/efficient way. Say I have an isometric map with a little maze on it, and a pathfinder in place that lets the NPC navigate it on it's own. Now, let's introduce a second floor. Say I want the little dude to navigate the maze, to the entrance of floor 2, then navigate the maze on that. I made a crude drawing to show what I mean: http://www.innerfilth.com/~mike/example1.jpg I want the blue dot to move somewhere onto the green level. I figured just have him pathfind to the entrance, move up there, then do some more pathfinding. Here's where it gets complicated though: http://www.innerfilth.com/~mike/example2.jpg Say he's starting on one of the green panels and I want him to move to the other one. Say there are multiple exists/entrances for each one. How would I handle this? I was going to have the pathfinder work backwards in this case. Say there's multiple entrances to the second floor, the pathfinder would work backwards from the goal to see which entrances total on the map can lead to it, then find a path from each of these entrances to the player, to see which is best. It gets more complicated if there's 4 floors with like 6 entrances each and they go all over the place. Before I dedicate a lot of time to it is my idea the way to go or is there a better way?

A* just navigates a node graph. there's nothing that restricts it to 2D. Think of the floors as separate graphs that are linked to other floors via the stairs. i.e. the stairs connect a node on floor A to another node on floor B. Now A* will happily solve the path for you with zero modifications to your code (assuming you implemented your code nicely, of course [smile])

The only potential trick is finding which floor graph you are currently on. It sounds like you won't have this problem since you're a tile based game; your characters position is exactly equal to a node position. In 3D shooters and whatnot it can be a little more complicated but you can just find the floor to which you are closest.

-me

Well I'm gonna do a bit of self-publicity, but you can check this :

http://www.gamedev.net/community/forums/topic.asp?topic_id=469197

It solves the problem of having multiples levels.

and for all the details on how to do it, check : http://www.gamasutra.com/features/20020405/smith_pfv.htm

I guess my only problem is figuring out how to calculate the hueristic. Not sure how to do that since each level is it's own array.

Unless that's the problem and I shouldn't do it like that.

The children node of a layer-switching node (a staircase) would include the higher layers, so there's no real problem there. Your heuristic would probably still be a normal distance formula, only with the Z direction appropriately scaled. If your Z size between layers is the same size of the X or Y, then this isn't an issue.

If you scale the Z by anything more than the height (cost) of the stairs then the heuristic becomes inadmissible.

Here's some more options:

1. Just add in the z distance * cost of traversing the stair tile. The heuristic will be always admissible, but will be very inaccurate if you're nowhere near the stairs. Searches will also be slow, especially if you have to go the 'wrong way' to get to the stairs.

2. Add together two of your existing heuristics - one to get to the stairs, and the other to get back. If there's more than one set of stairs you'll probably want to pick the closest one.

3. Precompute the path to the stairs for each tile. All you need to do for this is store a 'distance from nearest stairs' value in each tile. Of course if the map can change over time the precomputed result won't be perfect, but it should still be better than the other options.

To compute that distance from nearest stairs do a breadth first search from each of the stairs on a level simultaneously, and mark the squares with distances as you go. You'll need two values in each square - one for stairs up, and one for stairs down. Any tiles the dfs didn't get to should be marked as unreachable (searches to unreachable areas will be really really slow unless you precompute that).

This will find the optimal path very quickly if the nearest stairs for both start and end are the same, and will require a bit more searching if they aren't.