1

私たちは現在、ゲームをプログラミングしています (これはかなり未知の言語です: modula 2)。遭遇した問題は次のとおりです: 17 x 12 のグリッドに迷路があります (完全な迷路ではありません)。コンピュータは、始点 (9, 12) から終点 (9, 1) までの道を生成する必要があります。いくつかのアルゴリズムを見つけましたが、ロボットが戻らなければならないときに機能しません。

xxxxx
    x
=>  x
    x
  xxx

また：

    xxxxx
        x
xxxxxx  x
     x  x
     x  x
xxxxxx  x
=>      x
xxxxxxxxx

最初の例のタイプの解決策を見つけましたが、2 番目のタイプは解決できず、2 番目のタイプの解決策を作成すると、ロボットが最初のタイプの状況でスタックしてしまいます。

それはたくさんのコードなので、私はアイデアを与えます：

WHILE (最終目的地に到達していない) DO { 障害物がない場合は右に進みます: 障害物に遭遇した場合は右に進みます, 右に行けるまで試してください. もう上がれない場合は右に行けるまで下ってみてください. （最初にブロックされた場所から始めて）、もう下に行けない場合は、左に 1 歩進んで、テストしたスペースをブロックで埋めます。}

これは、最初のタイプの問題では機能しますが、2 番目の問題では機能しません。今では、私が間違って始めた可能性があるので、特にアルゴリズムを改善する方法について、より良いアルゴリズムまたはソリューションを求めています。

どうもありがとう！！

4

4 に答える 4

2

あなたのアルゴリズムは、入り口から迷路に入り、壁を抱きしめ、外に出ようとしたときにのみ機能したことを覚えていると思います。例えば、迷路の途中にある「島」からスタートするとうまくいきません。

幅優先探索を見てください。これにより、移動したいセルへの最短経路も得られます。基本的には、同じセルに 2 回アクセスしたくない (そうする理由はありません) ため、各セルから分岐します。

最初の例です。数字は、矢印から各セルに到達するまでに必要なステップ数で、おそらくパターンを認識することができます。

xxxxx
3212x
2101x
3212x
43xxx

もちろん、必要に応じて、セルごとに、このセルへの以前の最適なパスを追跡することにより、たどったパスを再構築できます。

幅優先探索は、各グリッド セル間の距離が一定であると仮定して機能します。隣接するセル間の距離が異なる場合は、次のクラスの問題を調べることができます:最短経路の問題。

于 2010-03-19T14:32:20.803 に答える
2

任意の方法を見つけたいだけでなく、可能な限り最短の方法も見つけたいので、おそらくパス検索アルゴリズムを実装する必要があります。最も一般的なパス検索アルゴリズムはDijkstraとA*です。迷路全体のレイアウトを知っていれば、ある地点から別の地点までの最短経路が得られます。

于 2010-03-19T14:32:58.027 に答える
1

あなたは問題を、キャラクターが迷路を通り抜けていると考えています。私はそれをしません。私は迷路を水が流れる一連のトンネルとして想像します (つまり、答えはあらゆる方向に流れます)。したがって、迷路を文字列の 2 スペース配列として表し、null (または壁としての他の文字)、発見されていない場所として別の区切り文字 (「o」など)、残りを次のように表す場合その正方形に到達するための最短経路 (「n」、「e」、「s」、および「w」を使用)。次に、ループを繰り返します。毎回、各正方形が別の正方形に広がることができるかどうかを調べます (正方形に「o」が含まれている場合)。次に、その正方形の文字列の連結バージョンを追加します。次のマスに移動する必要があり、char はそこに到達するまでにかかった移動を表します。

于 2010-03-19T17:35:36.367 に答える
0

あなたが解決しようとしている問題は、パスファインディングと呼ばれます。単純なブルート フォースから驚くべきA*まで、さまざまな方法があります。ウィキペディアには、ここに非常に優れた概要があります。

于 2010-03-19T14:36:31.263 に答える