Ich arbeite an einem Projekt mit einem virtuellen Roboter (Turtles in der ComputerCraft-Mod für Minecraft), wo der Roboter in einem Labyrinth von Tunneln wäre und sich darin navigieren müsste. Die Welt ist praktischerweise bereits in Kacheln unterteilt (ein kartesischer 2D-Graph von ihnen, mit einem booleschen passierbaren/nicht passierbaren Wert für jeden), und der Roboter, der die Tunnel baut, wird sie so abbilden, wie er geht.Pathfinding mit Teleportern
Darüber hinaus gibt es Teleporter "Abkürzungen" verstreut in Bereichen, in denen Roboter schnell zwischen ihnen gelangen müssen.
Die Frage ist: Was ist der beste Weg, den Roboterpfad zu seinem Ziel zu finden? Wie würde das System Gebiete identifizieren, die Teleporter benötigen? A * ist der bekannteste Algorithmus, aber gibt es andere, die besser zur Anwendung passen? Bitte denken Sie daran, dass ich sehr wenig Erfahrung mit Pathfinding-Algorithmen habe, also müssen Sie die Dinge vielleicht in Grundbegriffe unterteilen, damit ich sie verstehen kann. Irgendwelche Vorschläge?
Warum nicht zuerst A * ausprobieren und sehen, wie es funktioniert? –
könnte ich sicherlich, aber ich würde annehmen, A * nimmt keine "Abkürzungen" wie die Teleporter ohne einen Hack in Betracht. Ich muss herausfinden, wie der Algorithmus ein bisschen mehr funktioniert. – Schilcote
Was hacken? Ich denke A * kann mit Null-Länge Kanten gut funktionieren. Ich bin neugierig. –