ゲームにおける経路探索アルゴリズムの深い理解

World of Warcraft などの MMOARPG ゲームをプレイしたことがあるなら、キャラクターの歩行がとても面白いことに気づくでしょう。実際の歩行体験をシミュレートするために、キャラクターは目的地に到達するまでの最短ルートを選択し、山や湖を避け、箱や森を迂回して、選択した目的地に到達します。

この一見普通の経路探索は、プログラムに実装する際には特定の経路探索アルゴリズムで解決する必要があります。最短時間で最短ルートを見つける方法は、経路探索アルゴリズムが考慮しなければならない最初の問題です。

この記事では、パスファインディングアルゴリズムがどのように進化してきたかを段階的に説明します。アルゴリズムが遭遇する問題が単純なものから効率的なものまで、また改善のプロセスもわかります。質問を念頭に置いて読むと、より早く理解できます。

この記事には主に以下の内容が含まれています。

1. 写真
2. 幅***検索、
3. ダイクストラアルゴリズム
4. 貪欲アルゴリズム
****検索アルゴリズム、
6. B*検索アルゴリズム、

1. ゲーム内のキャラクターはどうやって道を見つけるのですか?

人々が歩いている様子を見る方法:

開発者が実際にどう見ているか:

あるいはこれ:

マップの場合、開発者は特定のスキームを通じてマップをデータオブジェクトに変換する必要があります。最も一般的なのは、前述のようにマップをグリッドに分割することです。もちろん、マップを必ずしもグリッドに分割する必要はありません。ポリゴンも使用できます。ゲームによって異なります。一般的に、同じエリアのマップでは使用する頂点の数が少なくなり、パス検索アルゴリズムが高速になります。パスファインディングでよく使われるデータ構造はグラフです。以下で見てみましょう。

2. 写真

経路探索アルゴリズムについて説明する前に、まずデータ構造、つまりグラフについて理解しましょう。データ構造はアルゴリズム計算の基礎となります。優れたデータ構造はアルゴリズムを理解しやすくするだけでなく、アルゴリズムの効率も向上させます。ある意味では、グリッドもグラフの進化形ですが、グラフィックが変わったという点が異なります。グラフの概念を理解すると、経路探索アルゴリズムをより深く理解できるようになります。

グラフの基本的な定義:

グラフの正式な表現は G=(V,E) です。ここで、V は頂点の集合を表します。E と V は 2 項関係であり、エッジとして理解できます。たとえば、頂点 U から頂点 V へのエッジがある場合、E は (u,v) で表すことができます。特定の有向グラフと無向グラフは、エッジに方向があるかどうかによっても区別されます。理解を容易にするために、この記事のすべてのデータデモンストレーションはグリッドマップに基づいています。以下は、A を頂点、BCDE をサブ頂点とするいくつかの関係の配置です。各グリッドを頂点と見なすこともできます。

3. 検索アルゴリズム

グラフを検索するということは、特定の順序でグラフの頂点を 1 つずつ訪問することを意味します。マルチグラフアルゴリズムの場合、幅優先探索と深さ優先探索はどちらもグラフデータ構造にアクセスするための体系的な方法を提供するため、非常に重要です。幅優先探索アルゴリズムに焦点を当てます。

深さ優先探索

深さ優先アルゴリズムは最小パスとはほとんど関係がないので、ここでは簡単に紹介するだけにします。

深さ優先探索アルゴリズム (略して DFS) は、ツリーまたはグラフを走査または検索するために使用されるアルゴリズムです。ツリーの深さに沿ってツリーのノードをトラバースし、ツリーの枝を可能な限り深く検索します。ノード v のすべてのエッジが探索されると、検索はノード v を見つけたエッジの開始ノードに戻ります。このプロセスは、ソースノードから到達可能なすべてのノードが検出されるまで続行されます。

幅優先探索

幅優先探索アルゴリズム (略して BFS) は、幅優先探索とも呼ばれ、最短経路の最初のモデルを探索するのに非常に適したグラフ探索アルゴリズムです。この考え方に沿って、引き続き説明していきます。

BFS は、グラフ内のすべてのノードを体系的に拡張してチェックし、結果を見つけることを目的としたブラインド検索方法です。つまり、結果の可能性のある場所を考慮するのではなく、結果が見つかるまでグラフ全体を徹底的に検索します。手順は次のとおりです。

- まずルートノードをキューに入れます。
- キューから最初のノードを取得し、それがターゲットかどうかを確認します。
- ターゲットが見つかった場合、検索は終了し、結果が返されます。
- それ以外の場合は、まだチェックされていないすべての直接の子ノード (隣接ノード) をキューに追加します。
- キューが空の場合は、グラフ全体がチェックされたことを意味します。つまり、グラフ内に検索するターゲットがないことを意味します。検索を終了し、「ターゲットが見つかりません」を返します。

グリッド：

コード (js) を見てみましょう:

var フロンティア = 新しい配列();

frontier.put(開始);

var 訪問 = 新しい配列();

訪問[開始] = true;



フロンティアの長さが0を超える場合

    現在の = frontier.get();

     //周囲の頂点を見つける for(next in graph.neighbors(current)){

        var notInVisited = visits.indexOf(next)==-1;

        // 訪問されていない if(notInVisited) {

            frontier.put(次へ);

            訪問[次] = true;

          }

       }
}

上記から、幅の検索は開始頂点から始まり、その子ノードを訪問し (グリッドでは周囲のノードを訪問します)、ターゲットが見つかるまでこのプロセスを継続的にループすることがわかります。このアルゴリズムは従来のロジックに沿っており、すべての頂点を列挙します。しかし、この方法には明らかな欠点もあります。

欠陥：

1. 効率が低く、時間の計算量は T(n) = O(n^2) です。
2. 各頂点間に重みがないため、優先順位を定義できず、最適なルートを見つけることができません。たとえば、水に遭遇した場合、その周りを歩く必要がありますが、これは幅のアルゴリズムに含めることはできません。

この問題を解決するにはどうすればいいでしょうか?ダイクストラのアルゴリズムを見てみましょう。

4. ダイクストラアルゴリズム

幅優先探索アルゴリズムは、開始頂点から目標頂点までの経路計画問題を解決しますが、エッジに重み (距離など) がなく、経路を推定して最適なソリューションを比較できないため、最適かつ最も適切なアルゴリズムではありません。なぜ重みがそれほど重要なのでしょうか? 実際の環境では、2 つの頂点間のルートは必ずしも直線ではないからです。目的地に到達するには、森林、湖、山などの障害物を迂回する必要があり、これらはすべて直接通過するのではなく迂回する必要があります。

たとえば、幅優先アルゴリズムを使用すると、次の状況では障害物 (緑の部分) を直接通過しますが、これは明らかに望ましい結果ではありません。

問題点を解決する:

グラフ内のある頂点から別の頂点までの最短かつ最小の重みのパスを見つけることは、非常に重要な改良プロセスです。選択されたパスのコストを追跡するために頂点間の各エッジに重みを追加し、ある場所への新しいパスが以前の最適パスよりも優れている場合は、それを新しいルートに追加します。

ダイクストラアルゴリズムは、幅優先アルゴリズムに基づいた改良版です。最短パスツリーに最短エッジを追加し、貪欲アルゴリズムを使用して計算を行い、最終的に最良の結果を生成します。具体的な手順は次のとおりです。

1. 各頂点には推定コスト（開始点から現在の頂点までの距離）が含まれており、各辺には重み v があります。最初は、開始頂点の推定コストのみが 0 で、他の頂点の推定値 d はすべて無限大です。
2. コスト値が最小の頂点Aを探し、パスキューに入れる
3. Aの直接の子頂点をループし、子頂点の現在のコスト値を取得してcurrent_costという名前を付け、新しいパスnew_costを計算します。new_cost = 親ノードAのコスト+v（親ノードから現在のノードへのエッジの重み）、new_cost < current_costの場合、現在の頂点のコスト = new_cost
4. 頂点にアクセスできなくなるまで、2 と 3 を繰り返します。

次の例を見てみましょう。

コード (js) を見てみましょう:

var フロンティア = 新しい PriorityQueue();

frontier.put(開始);

パス = 新しい配列();

//各頂点パスは cost_so_far = new Array() を消費します。



パス[開始] = 0;

これまでのコスト[開始] = 0



フロンティアの長さが0を超える場合

   現在の = frontier.get();


   現在の値 == 目標値の場合:

      壊す

       //周囲のノードを検索 for(next in graph.neighbors(current)){

        var notInVisited = visits.indexOf(next)==-1;

        var new_cost = cost_so_far[現在] + graph.cost(現在、次);

           //訪問されていないか、パスが近い if(notInVisited || new_cost < cost_so_far[next]) {

            これまでのコスト[次] = 新しいコスト;

            優先度 = 新しいコスト;

            frontier.put(次、優先度);

            パス[次] = 現在のパス;

          }

       }

}

ダイクストラアルゴリズムは幅優先探索よりも賢く、cost_so_far に基づいて長いルートやアクセスできないエリアを回避できますが、それでも盲目的に探索する傾向があることがわかります。マップでよくある状況は、ターゲットと開始点の間のパスを見つけることであり、これには一定の方向性があります。上の図からわかるように、ダイクストラアルゴリズムは、開始点から子ノードまですべての方向に拡散します。

欠点:

1. 実行時間の計算量は、T(n) = O(V^2) です。ここで、V は頂点の数です。あまり効率的ではない
2. ターゲット検索は方向性がない

盲目的に検索せずに検索の問題を解決するにはどうすればよいでしょうか?貪欲最良優先探索アルゴリズムを見てみましょう。

5. 貪欲な***最初の検索

私はダイクストラのアルゴリズムの根本的な欠陥を発見しました。それは、検索が盲目であるということです。ここでは、この問題点にのみ焦点を当て、貪欲な優先探索を使用して解決します。どうすれば解決できるでしょうか?概念を少し変更する必要があります。ダイクストラアルゴリズムでは、優先キューは開始頂点に対する各頂点の推定値を使用してソートします。貪欲な最初の検索では、

問題点を解決する:

各頂点をターゲット頂点までの距離でソートします。 1つは開始頂点からの距離でソートされ、もう1つはターゲット頂点からの距離でソートされます（ターゲットからの距離でソートされます）。

どちらが速いですか?次の図を見てみましょう (左が幅優先、右が貪欲優先)。

上の図から、右側のアルゴリズム (貪欲な最優先検索) の方が左側よりも高速に検索していることがはっきりとわかります。そのパスは最適でも最短でもありませんが、障害物が最も少ない場合は十分に高速です。これは、完全な検索ではなく目標に基づいて検索する貪欲アルゴリズムの利点です。

アルゴリズムを見てみましょう (js):

フロンティア = 新しい PriorityQueue();

フロンティア.put(開始, 0)

came_from = 新しい配列();

came_from[開始] = 0;



フロンティアの長さが0を超える場合

    現在の = frontier.get()



   現在の値 == 目標値の場合:

      壊す



       for(graph.neighbors(current) の次の){

           var notInVisited = visits.indexOf(next)==-1;

           // 訪問されていない if(notInVisited) {

            //ゴールまでの距離が近いほど、優先度が高くなります。priority = heuristic(goal, next);

             frontier.put(次、優先度);

             came_from[次] = 現在のもの;

          }

       }

}



関数ヒューリスティック(a, b){

    //ターゲットからの距離 return abs(ax - bx) + abs(ay - by)

}

欠点:

1. この道は最短の道ではなく、より良い道にしかならない

最短経路を確保しながら、できるだけ少ない頂点を検索するにはどうすればよいでしょうか? A* アルゴリズムを見てみましょう。

6. A*アルゴリズム

上記のアルゴリズムの進化により、最短経路と最小の検索頂点数を求める 2 つのソリューション、ダイクストラアルゴリズムと貪欲な 1 次探索が徐々に見つかりました。では、両方のアルゴリズムの利点を活用して、経路探索アルゴリズムを高速かつ効率的にすることは可能でしょうか?

答えはイエスです。A* アルゴリズムはまさにそれを行います。ダイクストラアルゴリズムの cost_so_far を利用し、各辺の長さに重みを設定し、各頂点から開始頂点までの距離を継続的に計算して最短経路を取得します。また、目標に向かって継続的に移動する貪欲な 1 次検索アルゴリズムの利点を活用し、各頂点からターゲット頂点までの距離を継続的に計算して、検索キューが目標に継続的に近づくように誘導します。これにより、検索する頂点の数が少なくなり、効率的な経路検索が維持されます。

問題点を解決する:

A* アルゴリズムの優先キューソート方法は、F 値に基づいています。
F = コスト (頂点から開始頂点までの距離) + ヒューリスティック (頂点からターゲット頂点までの距離)

アルゴリズムを見てみましょう (js):

var フロンティア = 新しい PriorityQueue();

frontier.put(開始);

パス = 新しい配列();

cost_so_far = 新しい配列();

パス[開始] = 0;

これまでのコスト[開始] = 0

フロンティアの長さが0を超える場合

    現在の = frontier.get()

   現在の値 == 目標値の場合:

      壊す

       for(graph.neighbors(current) の次の){

           var notInVisited = visits.indexOf(next)==-1;

           var new_cost = cost_so_far[現在] + graph.cost(現在、次);

           // 訪問されておらず、パスが近い if(notInVisited || new_cost < cost_so_far[next]) {

              これまでのコスト[次] = 新しいコスト

              //キューの優先度 = new_cost (頂点から開始頂点までの距離) + ヒューリスティック (頂点からターゲット頂点までの距離)

            優先度 = 新しいコスト + ヒューリスティック(目標、次)

            frontier.put(次、優先度)

            パス[次] = 現在

          }

       }

}

関数ヒューリスティック(a, b){

    //ターゲットからの距離 return abs(ax - bx) + abs(ay - by)

}

以下は、ダイクストラアルゴリズム、貪欲アルゴリズム、A* アルゴリズムの経路探索レーダーダイアグラムです。番号の付いたグリッドが検索されています。3 つの効率を比較できます。

7. B*アルゴリズム

B* アルゴリズムは A* アルゴリズムよりも効率的なアルゴリズムです。ゲーム内のモンスターの自動経路探索に適しています。その効率は A* アルゴリズムをはるかに上回ります。テストの結果、その効率は通常の A* アルゴリズムの数十倍から数百倍です。 B* アルゴリズムを紹介するつもりはありません。Google で検索してください。

上記のアルゴリズムの継続的な進化を通じて、各アルゴリズムの限界と、拡張された新しいアルゴリズムで出現する解決策がわかります。これにより、理解が促進されることを願っています。

<<: 見逃せない 7 つのディープニューラルネットワーク可視化ツール

>>: 人工知能オンライン機能システムのデータアクセス技術