2

テキストベースのゲームの AI を書いていますが、問題は、壁の最も薄い部分を判断する方法に行き詰まっていることです。たとえば、次は 2D マップを表します。ここで、'^' は、'*' 文字で表される壁を通り抜けて 'X' とマークされた場所に到達したいキャラクターです。

------------------
|  X *           |
|*****           |
|****            |
|***             |
|**      ^       |
|                |
|                |
|                |
------------------

私はこれについて数日間続けて考えていましたが、アイデアがなくなりました. * アルゴリズムを使用してみましたが、壁のキャラクターを通過しようとすると、g コストが非常に高くなります。残念ながら、アルゴリズムは、壁を通り抜けてパスを検索しないことを決定します。

エージェントは、一度に 1 スペースずつ、斜めには移動できず、左右上下にのみ移動できます。

上記の例では、壁を通る最短経路は 1 つです。これは、1 つの「*」文字を通過するだけでよいためです。

いくつかの簡単なアイデアが必要です:)

4

4 に答える 4

2

加重グラフにして、すべての「壁」にとてつもなく大きな重みを付けるだけです。

整数をオーバーフローしないように注意してください。

于 2013-05-31T15:43:22.463 に答える
1

任意の数の動きが常に壁を通過するよりも安価であると仮定すると(つまり、10000000000 の壁を通過しない移動は、1 つの壁を通過する移動よりも安価です) (そうでなければ、コストを適切に設定するとうまくいきます)、任意のアルゴリズムの特殊なケースを見ることができます。マップ全体を実質的に検索する必要はないと思いますので...

  • ソースから徹底的な A* を行い、壁で停止し、各位置での最短経路を記録します。
  • 壁の横にある探索された位置ごとに、壁を通り抜けます。次に、それらすべてを組み合わせた A* (該当する場合) を実行し、再び壁で停止します。
  • 壁の隣にあるこれらの新しい探索位置のそれぞれについて、壁を通り抜けて A* を続けます。
  • などなど…ターゲットが見つかるまで。

既に探索された位置をスキップします - 新しい経路は、常にそこにある経路よりも長くなければなりません。

BFS の代わりに A* を実行したい唯一の理由は、これにより、ターゲットを含むエリアに到達した直後の探索が少なくて済むからです。これがより効率的かどうかは、マップによって異なります。

シントが言ったように、スタートが常に広いオープン エリアであり、フィニッシュが狭いエリアである場合、この検索を逆にする方が効率的です。しかし、これは実際に当てはまるかどうかを知っている場合にのみ当てはまります。それを検出することは効率的である可能性は低く、一度検出すると、ほとんどの作業はすでに完了しており、両方が適度なサイズの領域にある場合は失われてしまいます.

例：

X** |
**  |
**  |
** ^|

初期 BFS:

X**3
**32
**21
**10

壁を通り抜けて BFS (壁を通り抜ける以外に行き場がないため、BFS は発生しません):
(無視できるものは でマークされています%)

X*4%
*4%%
*3%%
*2%%

壁に足を踏み入れて BFS (BFS をターゲットに):

65%%
5%%%
4%%%
3%%%
于 2013-05-31T12:02:38.837 に答える
1

ダイクストラを使用します。

あなたが扱っているのはテキスト ベースのゲームなので、1000 x 1000 文字を超えるマップについて話しているとは考えにくいと思います。O(n*logn)これにより、非常に低コストで、非常にシンプルでわかりやすいコードで、保証された最良の回答が得られます。

基本的に、各検索状態は 2 つのことを追跡する必要があります:これまでにいくつの壁を通り抜けたか、および通常の空きスペースはいくつありますか。これは、たとえば、各壁を通過するコストが 2^16 であると仮定することにより、検索とマークマトリックスの両方で単一の整数にエンコードできます。したがって、ダイクストラの自然な順序付けにより、壁が最も少ないパスが最初に試行され、壁を通過した後、同じ数の壁を通過せずに既に到達したパスを繰り返さないことが保証されます。

基本的に、32 ビット整数を仮定すると、5 つの空きスペースと 3 つの壁を通過した状態は次のようになります 0000000000000011 0000000000000101。マップが非常に巨大で、迷路のようで、何トンもの壁がある場合、壁が少ない場合などは、この表現を微調整して、各情報に使用するビット数を増減したり、より快適に感じる場合はより長い整数を使用したりすることもできます。この特定のエンコード例は、65,000 を超える空きスペースを歩く必要がある最短パスが存在する場合、「オーバーフロー」します。

2 つではなく 1 つの整数を使用する主な利点 (壁/空きスペース) はint mark[MAXN][MAXM];、検索を追跡するために単一の単純なマトリックスを使用できることです。壁を通り抜けて特定の正方形に到達した場合5、無用な状態の伝播を防ぐために、4 つ、3 つ、またはそれ以下の壁で到達できたかどうかを確認する必要はありません。この情報は自動的に整数に埋め込まれます。の量をより高いビットに保存する限り、walls「壁のコスト」が高くてもパスを繰り返すことはありません。

これは C++ で完全に実装されたアルゴリズムです。上記のアイデアを視覚化して理解するための疑似コードと考えてください :)

int rx[4] = {1,0,-1,0};
int ry[4] = {0,1,0,-1};
int text[height][width]; // your map
int mark[height][width]; //set every position to "infinite" cost
int parent[height][width]; //to recover the final path

priority_queue<int64_t, vector<int64_t>, greater<int64_t> > q;
int64_t state = (initial_y<<16) + initial_x;
q.push(state);
while(!q.empty()){
    state = q.top(); q.pop();
    int x = state & 0xFF;
    int y = (state>>16) & 0xFF;
    int cost = state>>32;
    if(cost > mark[x][y]) continue;
    if(text[x][y] == 'X') break;
    for(int i = 0; i < 4; ++i){
        int xx = x+rx[i];
        int yy = y+ry[i];
        if(xx > -1 && xx < width && yy > -1 && yy < height){
            int newcost = cost;
            if(text[yy][xx] == ' ') newcost += 1;
            else newcost += 1<<16;
            if(newcost < mark[yy][xx]){
                mark[yy][xx] = newcost;
                parent[yy][xx] = i; //you know which direction you came from
                q.push( ((int64_t)newcost << 32) + (y<<16) + x);
            }
        }
    }
}
// The number of walls in the final answer:
// walls = state>>48;
// steps = (state>>32) & 0xFF; // (non walls)
// you can recover the exact path traversing back using the information in parent[][]
于 2013-05-31T15:32:14.800 に答える