Pathfinding in real 3D environments (e.g Buildings)

Question

Is there a pathfinding algorithm also suited for real 3D environments e.g. real Buildings with multiple stairs etc. A C++ library or open implementation would be splendid ;-) One solution I saw was Djikstra but I wonder whether there is something more optimal. Normal A* would not work better then Djikstra since the distance heuristic does not work well (Position one floor above destination). Another solution that I'm currently pondering is the mapping of the 3d environment on a 2d graph. So if there is some available C++ implementation/library going this way it would be helpful too.

Answer 1

If the path has to take into account the ability to navigate through obstacles (i.e. the movement is that of some entity with known volume in space), then I'd recommend looking into the literature on robot motion planning. The notion of a configuration space allows you to handle changes in pose in order to deal with obstacles. See the classic textbook by Jean-Claude Latombe

For simpler scenarios, you can probably make do with path planning algorithms used in first person computer games, which are similar to Dijkstra, A* (example)

Answer 2

For an approximation algorithm you can easily map the 3d to a 1d curve and traverse an octree with a gray code. That way you can reorder each path. I don't know if there is a guarantee to be within the optimum solution but it must be better then any heuristic method.