8

私の質問がかなり漠然としているように思えますが、それをより適切に表現する方法が思いつかないので、私がやろうとしていることを説明することから始めます.

私は現在、マップを与えられたプロジェクトに取り組んでおり、マップ内をナビゲートできる「Critter」をコーディングしています。クリッターには他にもさまざまな機能がありますが、それらは現在の質問には関係ありません。プログラム全体とソリューションは C# で記述されています。

クリッターの速度を制御し、現在の X および Y 位置を返すことでマップ上の現在の位置を取得できます。また、クリッターをブロックする地形と衝突したときの方向を設定することもできます。

私が抱えている唯一の問題は、地図を賢くナビゲートする方法が思いつかないことです。これまでのところ、生き物が地形に衝突したときにどの方向を向いているかに基づいて作成してきましたが、これは決してマップ内を移動する良い方法ではありません!

私はゲーム プログラマーではなく、これはソフトウェアの割り当てのためなので、AI の手法についてはまったくわかりません。

マップと生き物がどのように見えるかの画像へのリンクは次のとおりです。

地図と生き物の画像

完全な解決策を提供してくれる人を探しているわけではありません。マップ ナビゲーションの一般的な方向性を推し進めるだけです。

4

4 に答える 4

6

あなたが持っている環境に関する唯一の知識があなたの生き物の位置とその速度である場合、あなたができる最善の方法は壁追従アルゴリズムだと思います. 環境内で他のいくつかのものを検出できる場合は、さらに多くのオプションがあります。

より一般的なアルゴリズムの種類のいくつかは...

ポテンシャル フィールドとは、すべての障害物や壁には「反発力」があり、すべての目標には「引き寄せ力」があることを意味します。力の強さは、オブジェクトからの距離とオブジェクトの「重大度」に基づいています。(溶岩の穴はでこぼこの道よりもはるかに厳しいものです) 力場を構築した後、単純なアルゴリズムは、最小の抵抗の経路をたどることに要約されます。より良いバージョンでは、極小値と極大値を検出し、それらのウェルを回避できます。

    Critter
    -----\    /-------\
          \  /         \ 
           \/           \
   Local Minima Trap     \
                          \
                           \
                             Goal
于 2010-05-01T23:46:46.430 に答える
3

検索

A*経路探索アルゴリズムを見てみましょう。これは基本的に、このようなものに対する標準的なアプローチです。

ゲームのパスファインディングに関する Amit Patel の記事には、A* とアルゴリズムの一般的なバリアントのかなり良い紹介があります。

C# の実装はこちらとこちらにあります

ダイナミック A*

探索する地形が事前にわかっているわけではなく、エージェントがその環境を探索するときに発見されるとしましょう。エージェントが未知の障害物に遭遇した場合、エージェントの地形マップを更新してから A* を再実行して、障害物を迂回する目標への新しいパスを見つけることができます。

実行可能な解決策ではありますが、新しい障害を見つけるたびに計画アルゴリズムをゼロから再実行すると、かなりの量の冗長な計算が発生します。たとえば、障害物を回避した場合、障害物を発見する前に計画していたルートが、ゴールへの最も効率的なルートである可能性があります。A* を再実行するだけで、前のパスのこのセクションを再計算する必要があります。

これは、 Dynamic A* (D*)を使用することで回避できます。以前に計算された経路を追跡するため、エージェントが新しい障害物を見つけた場合、システムは障害物の周囲の領域で新しい経路を計算するだけで済みます。その後、既存のパスを再利用できます。

于 2010-05-01T23:33:00.767 に答える
0

私は目標指向のアプローチを使用します。あなたの質問は、目標はマップを探索して障害物を回避することであると述べているので、それが私たちの目標です。しかし、マップ全体を探索するにはどうすればよいでしょうか。私たちは未知のものを探求します。

最初から、未踏のエリアは 1 つだけです。それは、あなたがいる広場です。マップの残りの部分は未踏としてマークされています。未踏の場所を選択し、それを探索することを目標にします。しかし、どうやってそこに着くのですか？サブゴールを作成して、その隣の場所を探索します。そして、どのようにそれを行うのですか - その隣の正方形を探索し、元の目標が一連の探索に分解されるまで、現在の正方形から開始して目的の正方形に移動します。

障害物にぶつかり、マップの機能を発見すると、サブゴールの一部を変更する必要がある場合があります。たとえば、壁にぶつかったとき、その広場を探索するサブゴールをスクラブする必要があり、別のルートを見つけるための新しい計画を作成します。これはバックトラッキングと呼ばれます。

これで基本的に高レベルの説明は終わりです。それが役立つことを願っています！

于 2010-05-01T23:32:36.910 に答える