Warum verläuft der A * Pfad manchmal in geraden Linien und manchmal in Diagonalen? (Java)

Question

Ich bin dabei, ein einfaches 2D-Grid-basiertes Sim-Spiel zu entwickeln und bin voll funktionsfähig.

Ich habe die Antwort in meiner vorherigen Frage als Grundlage für die Implementierung der A * Pfadsuche verwendet. (Pathfinding 2D Java game?).

Um Ihnen wirklich zu zeigen, was ich frage, muss ich Ihnen diese Videoaufnahme zeigen, die ich gemacht habe. Ich teste nur um zu sehen, wie die Person zu einem Ort bewegen würde und wieder zurück, und das war das Ergebnis ...

http://www.screenjelly.com/watch/Bd7d7pObyFo

Verschiedene Wahl des Pfades abhängig von der Richtung, ein unerwarteten Ergebnis. Irgendwelche Ideen?

Answer 1

Wenn Sie sich für eine einfache-ish Lösung suchen, könnte darauf hindeuten, ich ein bisschen Randomisierung?

Was ich meine, ist dies: in der Cokeandcode-Beispiel gibt es die Nested-for-Loops, die die "Nachfolgerstaaten" generieren (um den AI-Begriff zu verwenden). Ich beziehe mich auf den Punkt, an dem es sich über das 3x3-Quadrat um den "aktuellen" Zustand dreht, und fügt neue Positionen auf dem Stapel hinzu, die berücksichtigt werden sollen.

Eine relativ einfache Lösung wäre, dass Code ein Bit (sollte :)) werden isolieren und haben es, sagen wir, eine LinkedList von Knoten vor dem Rest der Verarbeitungsschritt erzeugt. Dann Containers.Shuffle (oder ist es Generics.Shuffle?), Verknüpfte Liste, und setze die Verarbeitung dort fort. Im Grunde genommen, haben Sie eine Routine sagen "createNaiveNeighbors (Knoten)" , die eine LinkedList = {(node.x-1, node.y), (node.x, node.y-1) ...} zurückgibt (bitte Verzeihen Sie das Pidgin-Java, ich versuche (und immer scheitere), kurz zu sein.

Sobald Sie die verknüpfte Liste jedoch erstellen, sollten Sie nur in der Lage sein, eine "für (Node n: myNewLinkedList)" anstelle von die

for (int x=-1;x<2;x++) { 

    for (int y=-1;y<2;y++) { 

und noch genau die gleichen Körper-Code verwenden!

Was dies tun würde, im Idealfall ist, eine Art „shake up“ die Reihenfolge der Knoten betrachtet und Wege zu erzeugen, näher die Diagonale, aber ohne die Heuristik zu ändern. Die Pfade sind immer noch die effizientesten, aber normalerweise näher an der Diagonale.

Der Nachteil ist natürlich, wenn Sie mehrmals von A nach B gehen, kann ein anderer Weg genommen werden. Wenn das nicht akzeptabel ist, müssen Sie möglicherweise eine drastische Änderung in Betracht ziehen.

Hoffe, das hilft! -Agor

Answer 2

Beide Pfade haben die gleiche Länge, so dass der Algorithmus seine Aufgabe gut erfüllt - er sucht den kürzesten Weg. Der A * -Algorithmus spezifiziert jedoch nicht den kürzesten Pfad, den er benötigt. Implementierungen nehmen normalerweise den "ersten" kürzesten Weg. Ohne Ihre zu sehen, ist es unmöglich, genau zu wissen, warum, aber wenn Sie jedes Mal die gleichen Ergebnisse erzielen möchten, müssen Sie Prioritätsregeln hinzufügen (so dass der gewünschte Pfad zuerst bei der Suche angezeigt wird).

Answer 3

Der Grund ist der Pfad, den der Algorithmus verwenden soll.
Ich kenne die Heuristik, die Ihr A * verwendet, nicht, aber im ersten Fall muss es zuerst zum Ende des Tunnels gehen und plant dann den Weg vom Ende des Tunnels zum Ziel.

Im zweiten Fall gehen die einfachsten Bewegungen zu den Zielen, bis sie an die Wand stoßen und dann den Weg von der Wand zum Ziel planen.

Most A * Ich weiß, arbeiten mit einer Sichtlinie Heuristik oder Manhattan Distance im Falle einer Welt Block. Diese Heuristiken geben Ihnen den kürzesten Weg, aber im Falle von Hindernissen, die einen Weg von der Sichtlinie unterscheiden, hängen die Wege von Ihrem Ausgangspunkt ab.
Der Algorithmus wird die Sichtlinie so lange wie möglich gehen.

Answer 4

Wenn ich rechts gesehen habe, bewegt sich die Kugel zuerst in einer geraden Linie nach rechts, weil sie nicht direkt auf das Ziel zukommt (der Weg ist blockiert). Dann geht es in einer geraden Linie auf das Ziel zu. Es sieht nur diagonal aus.

Answer 5

Steht Ihre Suche zuerst in der 'nach unten' Richtung? Dies könnte den Algorithmus erklären. Versuchen Sie es zuerst zu ändern, und ich wette, Sie würden das entgegengesetzte Verhalten sehen.

Answer 6

Die wahrscheinlichste Antwort ist, dass es direkt nach Süden geht, wenn es in Richtung Süden geht; Geht man in die entgegengesetzte Richtung, ist dies keine Wahl, so dass der Teilpfad stückweise optimiert wird, mit dem Ergebnis, dass alternierende Aufwärts/Quer-Bewegungen als am besten angesehen werden.

Wenn Sie möchten, dass es entlang der Diagonalen zurückgeht, müssen Sie einige Punkte von Interesse entlang des Pfades identifizieren (zum Beispiel die Mündung des Tunnels) und diese in Ihrer Heuristik berücksichtigen. Alternativ können Sie sie in Ihrem Algorithmus berücksichtigen, indem Sie einen Teilpfad neu berechnen, der einen interessanten Punkt durchläuft.

Früher haben sie eine vorkompilierte statische Analyse von Karten durchgeführt und pathfinding Marker an Chokepoints platziert. Abhängig davon, was Ihr endgültiges Ziel ist, könnte das auch hier eine gute Idee sein.

Wenn Sie wirklich daran interessiert sind, das Lernen, was los ist, würde ich vorschlagen, die Schritte der A * Suche zu machen. Angesichts Ihrer Frage könnte es für Sie sehr aufschlussreich sein.

Answer 7

Der Grund, warum eigentlich ziemlich einfach: der Weg wird immer versuchen, die niedrigste heuristischen möglich zu haben, weil sie in einem gierigen Weise sucht. Dem Ziel näher zu kommen ist ein optimaler Weg.

Wenn Sie diagonale Bewegung erlaubt, würde dies nicht passieren.

Answer 8

In jedem Fall ist es lieber den Weg, der sie näher an ihr Ziel Knoten früher nimmt, das, was ist A * ist entworfen.

Answer 9

Abhängig von der Implementierung Ihres Astar werden Sie verschiedene Ergebnisse mit der gleichen Heuristik sehen, wie viele Leute erwähnt haben. Dies liegt an Bindungen, wenn zwei oder mehr Pfade die Reihenfolge bestimmen, in der Sie Ihre offene Menge anordnen, wird bestimmt, wie der endgültige Pfad aussehen wird. Sie erhalten immer den optimalen Pfad, wenn Sie eine zulässige Heuristik haben, aber die besuchten Knoten erhöhen sich mit der Anzahl der Verbindungen, die Sie haben (relativ zu einer Heuristik, die nicht so viele Verbindungen erzeugt).

Wenn Sie nicht denken, dass der Besuch von mehr Knoten ein Problem ist, würde ich vorschlagen, die Randomisierung (was ist Ihre derzeitig akzeptierte Antwort) Vorschlag. Wenn Sie denken, dass die Suche nach mehr Knoten ein Problem ist und optimieren möchte, würde ich vorschlagen, eine Art Tiebreaker zu verwenden. Es scheint, dass Sie Manhattan-Entfernung verwenden, wenn Sie euklidische Distanz verwenden, wenn zwei Knoten als Tiebreaker binden, erhalten Sie mehr gerade Pfade zum Ziel und Sie werden weniger Knoten besuchen. Dies wird natürlich keine Fallen oder Blockierung der Sichtlinie zum Ziel gegeben.

Um zu vermeiden, dass Knoten mit blockierenden Elementen im Sichtlinienpfad besucht werden, würde ich vorschlagen, eine Heuristik zu finden, die diese blockierenden Elemente berücksichtigt. Natürlich sollte eine neue Heuristik nicht mehr Arbeit machen als eine normale A-Star-Suche.

Ich würde vorschlagen, Blick auf my question, da es einige Ideen und Lösungen für dieses Problem produzieren könnte.