単純な迷路の場合は、基本的に交差点に到達するまでパスに沿って「歩きます」。その時点で、すべてのオプションを記録します。次に、1 つを選択します (好きなヒューリスティックを使用して、右手のテクニックを使用すると、常に「右に行く」ことになります)。オプションを記録したら、それをスタックに詰め込みます。その後、先に進みます。
行き止まりを読んだら、「戻る」か、可能であれば単にスタックをポップして別のオプションを選択し、そこから続行します。戻るには、スタックに各移動を記録し、最後の交差点に到達するまでスタックを巻き戻し始めます。
モンスターなど、「行き止まり」として、通過できるもの、またはアイテムが不足していることに注意して、これを続けることができます. 次に、交差点でこれらの通行可能な行き止まりを記録して、出口を探して交差点に戻ってきた場合に、「鍵」や「剣」など、通過する必要があるものがないか在庫を確認できるようにします。戻ってきたら、未踏のパスのオプションと、倒すことができるものによってブロックされたパスのオプションを確認してください。モンスターを倒せるアイテムがあれば、そのルートを取り直し、モンスターを倒して先へ進むことができます。
この手法がサイクルのある迷路で機能するかどうかは覚えていません。以前にスポットを訪れたことがあるかどうかは常にわかるはずなので、「パンくずリスト」の跡を残したり、見た場所を記録したりできます。
最適なパスや最適なスコアリング パスを教えてくれるわけではなく、出くわすたびに出口にたどり着くだけです。
交差点を発見すると、ダンジョンをメモリ内の接続されたグラフとして表すこともできます。グラフの各ノードは交差点であり、各ノード間でかかるパスの長さ (ステップ数) はグラフの遷移です。 . このグラフの障害物をノードとして表すこともできます。
したがって、吸血鬼に遭遇した場合、それはホールの端にある出口のないノードになります. 後で、十字架と木製の杭を手に入れると、吸血鬼がどこにいるかが「わかり」、グラフをたどって吸血鬼に戻ることができます(もちろん、動いていないと仮定します)。
秘訣は、実際にこのグラフを構築し、ストック グラフ トラバーサル アルゴリズム (多数ありますが、それほど難しくありません) を使用して、あるノードから別のノードに移動することです。
しかし、単純な迷路を横断するには、スタック テクニックが非常にうまく機能します。
補遺:
単純な迷路の場合は、1 つのスタックで十分です。マップがどのようにレイアウトされているか、どのようにナビゲートするかなどはわかりません。
しかし、できることは、移動するたびに、その移動をスタックに置くだけです。次に、バックトラックしたい場合は、スタックをポップし始め、交差点に戻るまで移動の反対方向に進み、そこから移動します。
これは、まだレイアウトがわからないツリーの単純な「深さ優先」検索です。しかし、他の方法でどこにいたかを追跡することも重要です。たとえば、迷路が床と壁のピースの大規模な配列として表されている場合、単純なリストに入力した各床のピースの座標を取得できます。
これは、迷路にサイクルがある場合に、既に歩いたスペースに「前進」したくないためです。明らかに、バックトラックするときにそれを行う必要があります。しかし、探索するときは、自分が何を見て、何を見ていないかを知る必要があります。それを追跡する方法は、マップのデータ構造によって異なります。
次の簡単な迷路を考えてみましょう:
# ########
# ########
# # # #
# # #### #
# #a b#
# # #### #
# # #
##### ####
# c #
# ########
場所 a、b、および c でのみスタックにプッシュする必要があることがわかります。行ったことのあるフロアをマークできる場合、マップは最初の交差点で次のようになります。
#.########
#.########
#.# # #
#.# #### #
#.#a b#
#.#.#### #
#. .# #
##### ####
# c #
# ########
そして、スタックは次のようになります。
{d,d,d,d,d,d,d,l,u}
7 ダウンの場合は、左に 1 つ、上に 1 つ。
地図をマークできない場合は、代わりに座標を追跡できます。それはすべて依存します。