Ich durchquere ein 16x16 Labyrinth mit meiner eigenen A * Implementation.
Alles ist gut. Nach der Durchquerung möchte ich jedoch herausfinden, welche Wand mir den besten alternativen Weg geben würde. Abgesehen davon, jeden Block zu entfernen und A * auf dem Labyrinth neu zu spielen, was ist eine cleverere und elegantere Lösung?
Ich dachte, geben Sie jedem Wandknoten (ignoriert von A *) einen vorläufigen F-Wert und ändern Sie die Knotenstruktur, um auch eine n-große Liste von node *tentative_parent zu haben, wobei n die Anzahl der Wände im Labyrinth ist . Könnte das machbar sein?
Wenn Sie der Liste der zu berücksichtigenden Knoten einen Knoten hinzufügen, fügen Sie auch ein Flag hinzu, ob der Pfad durch diesen Knoten bereits durch eine Wand gegangen ist.
%Vor%Wenn Sie dann mögliche Pfade von einem Knoten betrachten, wenn Sie nicht durch eine Wand gegangen sind, betrachten Sie benachbarte Wände als faire Pfade.
%Vor%Sie müssen bereits die Entfernung vom Startknoten zum aktuellen Knoten, der gerade verarbeitet wird, beibehalten, und Sie verwenden, was Sie bereits eingerichtet haben.
Vollständiger Beweis des Konzepts:
Wir sehen, dass operator== definiert ist, um auch zu berücksichtigen, ob der Pfad bereits eine Wand getroffen hat oder nicht. Dadurch können wir den Knoten bei Bedarf zweimal betrachten, wenn wir in der geschlossenen Menge nachsehen, ob wir diesen Knoten bereits gefunden haben. Dies ist der Fall im mittleren Flur im Beispiellabyrinth in der Quelle unten.
Die Teile des Codes, die mit #ifdef I_AM_ALLOWED_TO_GO_THROUGH_A_WALL markiert sind, zeigen die Teile, die benötigt werden, um einen normalen A * -Algorithmus zu erweitern, um durch eine einzelne Wand gehen zu können.
Suchen nach Kandidatenbereichen für die Wandentfernung:
Entlang Ihres ursprünglichen A * gefundenen Pfads behalten Sie die vorherige Entfernung bei, und wenn die vorherige Entfernung größer als die aktuelle Entfernung ist, notieren Sie sich den vorherigen Knoten mit a Potenzial für eine Wandentfernung.
Ich behaupte, dass es Fälle mit den meisten Auswirkungen erfassen wird:
Beispiel 1:
%Vor%Wo:
R (0,0) ist dein Kaninchen-schauender Kursläufer G (2,0) ist das Ziel
In diesem Fall beginnen wir bei (0,0) mit einem Abstand von 2. Die nächste verfügbare Bewegung ist (0,1) mit einem Abstand von 2,23 (Wurzel aus 5). Ihre Entfernung ist gerade gewachsen, so dass Ihr früherer Standort das Potenzial für einen Mauerriss hatte.
Beispiel 2:
%Vor%Start: (0,0) Ende: (6,6) A * Kurs: (0,0), (1,1), (2,2), (3,3), (4,4), (5,5), (6,6) Abstände: 8.5, 7.1, 5.7, 4.2, 2.8, 1.4 (oder Quadratwurzel von 72, 50, 32, 18, 8, 2) Keine optimale Wand zum Entfernen.
Bestimmen der zu entfernenden Wand:
Zeichnen Sie eine Linie zwischen Ihrem markierten Knoten und Ihrem Zielknoten. Die erste Wand entlang dieser Linie (am nächsten zum markierten Knoten) geht nach unten. Geben Sie etwas Fuzz, um Ihre Wand entlang einer geraden Diagonale zu entfernen, die nur Ecken treffen würde. Vergleichen Sie Ihre alternativen Pfade, um den kürzesten zu finden.