Wie man ein Labyrinth programmgesteuert durchquert, wenn man in einer Sackgasse steckt

Question

Es ist ziemlich einfach, vorwärts durch das Labyrinth zu gehen, aber ich weiß anscheinend nicht, wie ich rückwärts durch das Labyrinth gehen kann, um eine neue Route auszuprobieren, wenn man in eine Sackgasse gerät, ohne zu weit zurückzugehen?

Answer 1

Verwenden Zurückverfolgen indem Sie einen Stapel früherer Richtungsentscheidungen aufbewahren.

Answer 2

Der einfachste (zu implementierende) Algorithmus bestünde darin, einfach einen Stapel der Orte, an denen Sie waren, und die Route, die Sie von jedem Ort aus genommen haben, aufzubewahren, es sei denn, Sie erhalten diese Informationen durch Backtracking.

Um zurückzugehen, entfernen Sie einfach alte Standorte vom Stapel und suchen Sie nach weiteren Ausgängen von diesem Standort, bis Sie einen alten Standort mit einem ungetesteten Ausgang finden.

Wenn Sie wissen, dass das Zurückverfolgen zu einem Standort von unten erfolgt, indem Sie die Ausgänge jedes Mal in derselben Reihenfolge testen (d. h.Als Sie das letzte Mal am alten Standort waren, sind Sie hinuntergegangen), dann wählen Sie danach einfach die nächste Richtung aus runter.

Ich bin mir nicht ganz sicher, was du damit meinst geht zu weit zurück Allerdings gehe ich davon aus, dass Sie zu dem vorherigen Ort zurückkehren möchten, an dem Sie ungetestete Routen haben. Ist das nicht das, was Sie wollen?

Beachten Sie: Wenn Sie nicht versuchen, den Weg vom Startpunkt bis zu Ihrem aktuellen Standort im Auge zu behalten und diese Quadrate bei der Suche nach neuen Routen zu meiden, könnten Sie sich am Ende im Kreis bewegen, was den Stapel letztendlich zu groß machen würde.

Eine einfache rekursive Methode, die den eingeschlagenen Pfad markiert und niemals markierte Bereiche betritt, kann dies leicht bewerkstelligen.

Auch wenn Ihr Ding Wenn jemand, der sich durch das Labyrinth bewegt, etwas intelligenter ist, als sich nur zu bewegen und Wände zu treffen (anzuhalten), da er von seinem aktuellen Punkt aus in alle Richtungen sehen kann, habe ich andere Algorithmen, die helfen könnten.

Answer 3

Eric Lippert hat eine Reihe von Artikeln über die Erstellung eines geschrieben C#-Implementierung von A*, was möglicherweise effizienter ist.