Gibt es einen Anfang und ein Ziel, wie findet man den kürzesten Weg in einem Navigationsnetz?

Ich googeln „A * -Algorithmus auf Navigation Mesh“ nur falsche Wege, um g-Werte zu schätzen, wie diesesGibt es einen Anfang und ein Ziel, wie findet man den kürzesten Weg in einem Navigationsnetz?

oder diese

Durch die Länge des blauen Zusammenfassung Liniensegmente erhalten wir den g-Wert, der jedoch überschätzt wird (g-Wert sollte unterschätzt werden). Dieser Algorithmus gibt einen optimierten Pfad zurück, ist jedoch nicht garantiert der kürzeste.

Die einzige Art, wie ich denken kann, ist ein Sichtbarkeitsgraphen zu zeichnen Masche auf Basis der Navigations .Aber, dass zu viel Speicher kosten würde.

Gibt es andere Möglichkeiten, Netz den kürzesten Weg in einer Navigation zu berechnen?

Quelle

2016-03-19 iouvxz

Ich denke, dass Sie den A * -Algorithmus ein bisschen mehr studieren sollten, besonders welche Annahmen es macht und welche Garantien es bietet. Damit können Sie auch sinnvollere Fragen stellen. Zum Beispiel fehlt Ihrer Frage eine genaue Definition dessen, was * Sie * an der A * -Ausgabe für falsch halten. –

@UlrichEckhardt A * ist richtig, aber ich kann den A * -Algorithmus nicht anwenden, um das Navigationsdiagramm direkt zu verbinden. A * benötigt ein typisches Diagramm mit Knoten und Kanten, damit es eine Dijkstra-ähnliche Suche anwenden kann, um den kürzesten Pfad zu finden die Suche ist abgeschlossen, kein Pfad kann kürzer sein als der Pfad, den er jetzt zurückgegeben hat. Aber Navigations-Mesh ist kein Graph mit nur Knoten und Kanten, es besteht aus passierbaren Bereichen, also habe ich gegoogelt, wie ich A * auf das Navigations-Mesh anwenden kann. – iouvxz

Diese Artikel betrachten entweder die Zick-Zack-Pfade, die durch alle Polygone gehen, oder die Zick-Zack-Pfade, die durch den Mittelpunkt aller Kanten gehen, als den g-Wert. Aber das ist falsch, diese Art von g-Wert überschätzt die Entfernung von Startpunkt zum aktuellen Polygon (oder zur aktuellen Kante). Wenn die Suche abgeschlossen ist, werden alle nicht ausgewählten Pfade überschätzt und aufgegeben. – iouvxz

Um einen kürzesten Weg näher aus, was Sie bedeuten, sollten Sie mit Fixpunkten als A-Sterne-Knoten stoppen das heißt mit Zentrum der Dreiecke oder in der Mitte triangles'edge stoppen.

Versuchen Sie, die Punkte als A-Stern zu bewegen ausbreitet. Zum Beispiel verwenden A-Star Knoten auf triangles'edge die sind:

entweder der Schnittpunkt der Kante des Dreiecks der nächsten A-Sternknoten mit dem Segment von vorherigen A-Sternknoten und dem Ziel gebildet
oder der nächste Punkt von der Kreuzung auf dem Dreieck Rand oben erwähnten nächsten A-Sternknoten

oder versuchen, den Pfad-Knoten zu ändern, nachdem Sie Ihren A-Sternes, wie sie derzeit durchgeführt Berechnung ähnlich mit Kriterien.

Beachten Sie, dass dies den letzten Weg (auf Ihren Zeichnungen als die rote Linie) glätten. Aber dies wird nur dazu beitragen, die Überschätzung zu reduzieren, das garantiert nicht die kürzesten Wege zu finden, wie Sie es meinten.

besser, versuchen Sie den Pfad-Knoten zu ändern, nachdem Ihren A-Sternes mit Zentrum von triangles'edges Berechnung, string a.k.a Trichter Algorithmus zieht mit. Dadurch erhalten Sie den kürzesten Pfad durch die Dreiecke, die vom Ausgabepfad des A-Sterns durchlaufen werden.

Quelle

2016-04-28 19:12:23 Brice

Ich entschied mich schließlich, einen Sichtbarkeitsgraphengenerator in C++ zu implementieren, es ist die einzige vernünftige Lösung. – iouvxz

Gibt es einen Anfang und ein Ziel, wie findet man den kürzesten Weg in einem Navigationsnetz?

Antwort

Verwandte Themen