0

私は、stackoverflow に投稿された他の質問をいくつか読んでいますが、検索アルゴリズムの数に少し圧倒されています。私はコードや、アルゴリズムの背景やおそらくいくつかの sudo コードを超えるページを探しているわけではありません。A* のようなアルゴリズムがあることは知っていますが、時間がないため、このアルゴリズムでプログラムを完成できるかどうかわかりません。迷路はサーバー プログラムを使用して生成され、ソルバーはサーバーに接続して、より多くのプレイヤー ピースにコマンドを送信します。サーバー プログラム内のメソッドにアクセスできません。D&D の迷路のように作られた迷路を解かなければなりません。ゲームの基本的な概要は次のとおりです。

古典的な D&D コンピューター ゲームはダンジョン (迷路) で構成されており、ゲームの目的はダンジョンを通り抜け、迷路の「入口」から入り、「出口」から出ることにあります。物事をより困難にするために、ダンジョンのレイアウトはアプリオリに知られておらず、障害物 (ゾンビ、ターピット、ドア) があり、通路に沿って見つかったオブジェクト (運賃、はしご、鍵) を使用して克服する必要があります。仕方。

他の投稿の多くは、迷路を完成させるために障害物を心配する必要がないことに気づきました。これは、障害物を補うためにアルゴリズムを適応させる大きな問題でしょうか? 右手の法則のようなものが迷路を解くのにうまくいくかどうか、そうでない場合は、迷路を解くのにできるだけ単純なアルゴリズムになるかどうか疑問に思っていました(プログラムをすぐに完成させなければならないという事実のため)。Objective-C でこのプログラムをもう一度完成させなければならないことを知っているので、他のリンクは素晴らしいでしょう。これが発生した場合、右手の法則よりも強力なものを実装したいと思います。助けてくれてありがとう。

4

2 に答える 2

1

単純な迷路の場合は、基本的に交差点に到達するまでパスに沿って「歩きます」。その時点で、すべてのオプションを記録します。次に、1 つを選択します (好きなヒューリスティックを使用して、右手のテクニックを使用すると、常に「右に行く」ことになります)。オプションを記録したら、それをスタックに詰め込みます。その後、先に進みます。

行き止まりを読んだら、「戻る」か、可能であれば単にスタックをポップして別のオプションを選択し、そこから続行します。戻るには、スタックに各移動を記録し、最後の交差点に到達するまでスタックを巻き戻し始めます。

モンスターなど、「行き止まり」として、通過できるもの、またはアイテムが不足していることに注意して、これを続けることができます. 次に、交差点でこれらの通行可能な行き止まりを記録して、出口を探して交差点に戻ってきた場合に、「鍵」や「剣」など、通過する必要があるものがないか在庫を確認できるようにします。戻ってきたら、未踏のパスのオプションと、倒すことができるものによってブロックされたパスのオプションを確認してください。モンスターを倒せるアイテムがあれば、そのルートを取り直し、モンスターを倒して先へ進むことができます。

この手法がサイクルのある迷路で機能するかどうかは覚えていません。以前にスポットを訪れたことがあるかどうかは常にわかるはずなので、「パンくずリスト」の跡を残したり、見た場所を記録したりできます。

最適なパスや最適なスコアリング パスを教えてくれるわけではなく、出くわすたびに出口にたどり着くだけです。

交差点を発見すると、ダンジョンをメモリ内の接続されたグラフとして表すこともできます。グラフの各ノードは交差点であり、各ノード間でかかるパスの長さ (ステップ数) はグラフの遷移です。 . このグラフの障害物をノードとして表すこともできます。

したがって、吸血鬼に遭遇した場合、それはホールの端にある出口のないノードになります. 後で、十字架と木製の杭を手に入れると、吸血鬼がどこにいるかが「わかり」、グラフをたどって吸血鬼に戻ることができます(もちろん、動いていないと仮定します)。

秘訣は、実際にこのグラフを構築し、ストック グラフ トラバーサル アルゴリズム (多数ありますが、それほど難しくありません) を使用して、あるノードから別のノードに移動することです。

しかし、単純な迷路を横断するには、スタック テクニックが非常にうまく機能します。

補遺:

単純な迷路の場合は、1 つのスタックで十分です。マップがどのようにレイアウトされているか、どのようにナビゲートするかなどはわかりません。

しかし、できることは、移動するたびに、その移動をスタックに置くだけです。次に、バックトラックしたい場合は、スタックをポップし始め、交差点に戻るまで移動の反対方向に進み、そこから移動します。

これは、まだレイアウトがわからないツリーの単純な「深さ優先」検索です。しかし、他の方法でどこにいたかを追跡することも重要です。たとえば、迷路が床と壁のピースの大規模な配列として表されている場合、単純なリストに入力した各床のピースの座標を取得できます。

これは、迷路にサイクルがある場合に、既に歩いたスペースに「前進」したくないためです。明らかに、バックトラックするときにそれを行う必要があります。しかし、探索するときは、自分が何を見て、何を見ていないかを知る必要があります。それを追跡する方法は、マップのデータ構造によって異なります。

次の簡単な迷路を考えてみましょう:

# ########
# ########
# # #    #
# # #### #
# #a    b#
# # #### #
#   #    #
##### ####
#    c   #
# ########

場所 a、b、および c でのみスタックにプッシュする必要があることがわかります。行ったことのあるフロアをマークできる場合、マップは最初の交差点で次のようになります。

#.########
#.########
#.# #    #
#.# #### #
#.#a    b#
#.#.#### #
#. .#    #
##### ####
#    c   #
# ########

そして、スタックは次のようになります。

{d,d,d,d,d,d,d,l,u}

7 ダウンの場合は、左に 1 つ、上に 1 つ。

地図をマークできない場合は、代わりに座標を追跡できます。それはすべて依存します。

于 2011-09-24T21:35:07.010 に答える
0

個人的には、再帰を使用してパスを見つけようとします。トラップを処理する if ステートメントと、パスを通知する return ステートメント以外のステートメントを使用できます。

  public static int recursion(int x, int y) {
    if (location == end) {
      return 0; //found the end
    }
    if (deadEnd) {
      //backtrack
    }
    if (trapName) {
      //put whatever you need to do to get around it
    }
    if (x+1 <= edge) {
      recursion(x+1,y); //Moves right
    }
  }

これは多かれ少なかれ疑似コードです。それが役立つことを願っています!

于 2011-09-25T03:16:16.480 に答える