Pathfinding in realen 3D-Umgebungen (z.B. Gebäude)

Question

Gibt es einen Pfadfindungsalgorithmus, der auch für reale 3D-Umgebungen geeignet ist, z.B. echte Gebäude mit mehreren Treppen usw. Eine C++ - Bibliothek oder eine offene Implementierung wäre großartig ;-) Eine Lösung, die ich sah, war Djikstra, aber ich frage mich, ob es etwas Besseres gibt. Normal A * würde nicht besser funktionieren als Djikstra, da die Entfernungsheuristik nicht gut funktioniert (Position eine Etage über dem Ziel). Eine andere Lösung, über die ich derzeit nachdenke, ist die Abbildung der 3D-Umgebung auf einem 2D-Graphen. Wenn es also eine verfügbare C++ - Implementierung/Bibliothek gibt, wäre es auch hilfreich.

Answer 1

Wenn der Pfad die Fähigkeit berücksichtigen muss, durch Hindernisse zu navigieren (d. H. Die Bewegung ist die einer Entität mit bekanntem Volumen im Raum), dann würde ich empfehlen, die Literatur zur Roboterbewegungsplanung zu lesen. Die Idee eines Konfigurationsraums ermöglicht es Ihnen, Änderungen in der Pose zu handhaben, um mit Hindernissen umzugehen. Sehen Sie das klassische Lehrbuch von Jean-Claude Latombe

Für einfachere Szenarien können Sie wahrscheinlich mit Pfadplanungsalgorithmen in der ersten Person Computerspielen machen tun, die Dijkstra ähnlich sind, A * (example)

Answer 2

Für einen Approximationsalgorithmus Sie können das 3D leicht auf eine 1D-Kurve abbilden und einen Octree mit einem grauen Code durchlaufen. Auf diese Weise können Sie jeden Pfad neu anordnen. Ich weiß nicht, ob es eine Garantie gibt, innerhalb der optimalen Lösung zu sein, aber es muss besser sein als jede heuristische Methode.