行き止まりに陥ったときにプログラムで迷路を横断する方法

Question

迷路を前に進むのは非常に簡単ですが、行き止まりに突き当たった場合に、あまり戻らずに迷路を後退して新しいルートを試す方法がわかりません。

Answer 1

使用 後戻り 以前の方向決定の積み重ねを保持することによって。

Answer 2

最も単純な (実装する) アルゴリズムは、バックトラッキングによってその情報が得られない限り、これまでに訪れた場所のスタックと、それぞれの場所からたどったルートを保持することです。

戻るには、スタックから古い場所を取り出し、テストされていない出口を持つ古い場所が見つかるまで、その場所からさらに出口があるかどうかを確認します。

毎回同じ順序で出口を一貫してテストすることで、ある場所へのバックトラックが下から来ることがわかっている場合 (つまり、前回古い場所にいたときは下に行きました)、その後は次の方向を選択するだけです。 下.

何を言っているのか全く分かりません 戻りすぎます ただし、未テストのルートがある前の場所に戻りたいと思うと思いますが、それは希望ではありませんか?

出発点から現在位置までの経路を追跡し、新しいルートを見つけるときにそれらの四角形を避けるようにしないと、円を描くことになり、最終的にスタックが大きくなりすぎる可能性があることに注意してください。

通過するパスをマークし、マークされた領域には決して入らない単純な再帰的メソッドを使用すると、これを簡単に実行できます。

また、あなたの場合は、 もの 迷路を移動する機能は、現在位置から全方向を確認できるという点で、単に移動して壁にぶつかる (停止する) ことができるよりもわずかに賢明です。私には役立つかもしれない他のアルゴリズムがあります。

Answer 3

Eric Lippert は、 A* の C# 実装, 、そのほうが効率的かもしれません。