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

Question

迷路を前進するのはとても簡単ですが、迷路を戻って新しいルートを試す方法がわかりません。

Answer 1

以前の方向決定のスタックを保持することにより、バックトラッキングを使用します。

Answer 2

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

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

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

あまりにも遠くに戻るということの意味がよくわかりませんが、テストされていないルートがある前の場所に戻りたいと思うと思いますが、それはあなたが望んでいることではありませんか?

出発点から現在の場所までのパスを追跡しようとしない限り、新しいルートを見つけようとするときにそれらの正方形を避けようとすると、最終的にスタックが大きくなりすぎる可能性があることに注意してください.

たどる経路をマークし、マークされた領域には入らない単純な再帰的な方法で、これを簡単に行うことができます。

また、迷路を移動するものが、現在のポイントからすべての方向を見ることができるという点で、移動して壁にぶつかる (停止する) よりも少し賢い場合は、役立つかもしれない他のアルゴリズムがあります。

Answer 3

Eric Lippert は、より効率的なA*の C# 実装の作成に関する一連の記事を作成しました。