タワーディフェンス（TD）ゲームでは、多くの敵が1つのポイントに到達しようとします。 多くのTDゲームには、定義済みのパスまたは複数のパスがあります。 古典的なデスクトップタワーディフェンスを含む一部では、タワーを任意の場所に配置でき、敵の進路に影響を与える障害物になります。 デモを実行 し、マップをクリックして、壁を建てたり削除したりします。
これを実装する方法は？
2点間の最短経路を見つけるには、A *検索などのグラフ検索アルゴリズムがよく使用されます。 各目標に使用して、目標への道を見つけることができます。 このジャンルのゲームで使用できるさまざまなグラフ検索アルゴリズムがあります。 古典的な例を次に示します。
- 1つの開始点と1つの終了点 ：
- 最初のベストマッチで検索
- A * -ゲームで広く使用されています
- 1つの開始点とすべての終了点、またはすべての開始 点 、1つの終了点 ：
- ワイドサーチ -重みのないリブ
- ダイクストラのアルゴリズム -リブに重みを追加
- Bellman-Fordアルゴリズム -負の重みをサポート
- すべての開始点と終了点 ：
Desktop Tower Defenseのようなゲームでは、多くの敵の位置（開始点）とそれらすべての1つの終了点があります。 したがって、それらはすべての開始点と1つの終了点のカテゴリーに属します。 各敵に対してA *を実行する代わりに、アルゴリズムを1回実行すると、すべての敵のパスが計算されます。 さらに、彼はどこからでも最短経路を計算するので、敵が互いに迂回したり、新しい敵が作成されたりした場合、それらの経路はすでに計算されています。
「フィル」（FIFOのバリエーション）と呼ばれることもある幅優先の検索アルゴリズムを調べてみましょう。 グラフ検索はノードとエッジを含むすべてのグラフで機能しますが、私の例では正方形のグリッドを使用しています。 グリッドは、グラフの特殊なケースです。 各グリッドセルはグラフのノードであり、グリッドセル間の境界はグラフの端です 。 別の記事でメッシュなしのグラフを検討します。
幅優先検索は1つのノードから開始され、すべての隣接ノードを順番に通過します。 ここでの重要な概念は「境界」、つまり調査地域と未調査地域の境界です。 グラフ全体を検査するまで、境界はソースノードから外側に伸びます。
フロンティアキューは境界です：分析する必要があるグラフノード（グリッドセル）のリスト/配列。 最初は、 開始ノードという1つの要素のみが含まれています。 各ノードの訪問済みフラグにより、チェックしたかどうかを追跡できます。 最初は、 startを除くすべてのノードでFalseです。 スライダーをドラッグして、境界線の拡大を確認します。
アルゴリズムはどのように機能しますか？ 各ステップで、 フロンティアから1つの要素が取得され、 currentと呼ばれます。 次に、 nextと呼ばれる現在の近隣のそれぞれについて検索が行われます。 以前にアクセスしたことがない場合は、 フロンティアキューに追加されます。 Pythonコードのサンプルは次のとおりです。
frontier = Queue() frontier.put(start) visited = {} visited[start] = True while not frontier.empty(): current = frontier.get() for next in graph.neighbors(current): if next not in visited: frontier.put(next) visited[next] = True
コードを確認した後、 ステップバイステップで上記のアニメーションを調べてください 。 フロンティアキュー、 現在のノード、多くの次のノードに注目してください。 各段階で、境界要素が現在のノードになり、隣接ノードがマークされ、未訪問の隣接ノードがすべて境界に追加されます。 一部の隣人はすでに以前に訪問したことがあるため、国境には追加されません。
これはかなり単純なアルゴリズムであり、 人工知能を含む多くのアプリケーションに役立ちます。 私は主に3つの方法でそれを使用しています：
- 到達可能なすべてのノードをマークします。 これは、マップが完全に接続されておらず、到達可能なポイントを知りたい場合に役立ちます。 これは、 訪問済みフィールドを使用して上で行ったとおりです。
- 1つのノードから他のすべてのノードへ、またはすべてのノードから1つへの方法を見つけます 。 これは、記事の冒頭でアニメーションデモに使用した方法です。
- 1つのノードから他のすべてのノードまでの距離を測定します。 モンスターの徒歩圏内にあるものを知ることは有用です。
パスを生成する場合、各ノードから移動する方向を知る必要があります。 隣人を訪問するとき、あなたはどこから来たのかを覚えておく必要があります。 訪問したテーブルの名前をcame_fromに変更し、それを使用して前の場所を保存します。
frontier = Queue() frontier.put(start) came_from = {} came_from[start] = None while not frontier.empty(): current = frontier.get() for next in graph.neighbors(current): if next not in came_from: frontier.put(next) came_from[next] = current
それがどのように見えるか見てみましょう：
距離が必要な場合は、開始ノードで値が0のカウンターから開始し、近隣にアクセスするたびに値を増やすことができます。 訪問したテーブルの名前をdistanceに変更し、それを使用してカウンターを保存しましょう。
frontier = Queue() frontier.put(start) distance = {} distance[start] = 0 while not frontier.empty(): current = frontier.get() for next in graph.neighbors(current): if next not in distance: frontier.put(next) distance[next] = 1 + distance[current]
私たちが得たものを見てみましょう：
パスと距離の両方を計算する必要がある場合は、両方の変数を残すことができます。
したがって、これは幅優先の検索でした。 Tower Defenseゲームでは、A *を順番に使用して各敵のパスを個別に検索するのではなく、すべてのポイントから目的のポイントまでのパスを見つけるために使用しました。 モンスターの徒歩圏内にあるすべてのポイントを検索するために使用しました。 また、手続き型カードの生成にも使用しました。 Minecraftでは、スコープのクリップに使用されます 。 このアルゴリズムは知っておく価値があります。
次のステップ：
- PythonとC ++コードの実装ノートがあります。
- 1ポイントではなく1ポイントからパスを配布する必要がある場合は、パスに沿って渡すときに
came_from
ポインターを反転させます。 - 1つのポイントではなく、 複数のポイントのいずれかへのパスが必要な場合は、各エンドポイントからグラフ内のグラフへのエッジを追加のエンドノードに追加できます。 追加のノードはグリッドに表示されませんが、グラフではエンドポイントを表します。
- 早期終了：あるポイントへの/からのパスを探している場合、このポイントが見つかった直後に検索を中断できます。 これについては、 A *に関する記事で説明しています 。
- 重み付きのリブ：通過点の異なるコストを使用する必要がある場合、幅優先探索はダイクストラのアルゴリズムに変わります。 これについては、 A *に関する記事で説明しています 。
- 発見的アプローチ：検索をターゲットに向ける方法を追加すると、 幅優先検索は最初の最良一致の検索に変わります。 詳細については、 A *に関する記事をご覧ください。
- 幅優先探索から開始し、早期終了、重み付きのエッジ、およびヒューリスティックなアプローチを追加すると、A *が得られます 。 ご想像のとおり、このアルゴリズムについてはA *に関する記事で説明しています。
実装
内部状態
この記事では、visited / came_from / distanceセットとハッシュテーブルの外部状態を使用します。 また、グラフノードのデータ構造内にデータが保存される内部状態を使用することもできます。 内部データではなく外部データを使用する理由 内部データは少し高速ですが（実装ではハッシュテーブルは使用されません）、外部データは検索中にグラフデータの構造を変更しないため、「クリーン」です。 さらに、マルチスレッドまたはコルーチンを介して実装された複数の同時検索操作をサポートします。 内部
visited
フラグを持つノードの例を次に示します。
class Node: def __init__(self, name): self.visited = False self.name = name self._neighbors = [] def neighbors(self): return self._neighbors
以下にグラフの例を示します。
A = Node("A") B = Node("B") C = Node("C") D = Node("D") E = Node("E") A._neighbors = [B] B._neighbors = [A, C] C._neighbors = [D] D._neighbors = [E] E._neighbors = [] start = A
内部状態が使用される場合、アルゴリズムを繰り返すには、
visited
フラグを再度Falseに設定する必要があります。 アルゴリズムを実行する前にこれを行うことができます。
ALL_NODES = [A, B, C, D, E] frontier = Queue() frontier.put(start) for node in ALL_NODES: node.visited = False start.visited = True while not frontier.empty(): current = frontier.get() callback(current) for next in current.neighbors(): if not next.visited: next.visited = True frontier.put(next)
サンプルプログラムをダウンロードしてください 。
または、訪問したすべてのノードのリストを保持して、アルゴリズムの実行後に値を設定できます。
frontier = Queue() frontier.put(start) start.visited = True visited_nodes = [start] while not frontier.empty(): current = frontier.get() for next in current.neighbors(): if not next.visited: next.visited = True visited_nodes.append(next) frontier.put(next) for node in visited_nodes: node.visited = False
サンプルプログラムをダウンロードしてください 。
これまたはそのアプローチを選択する方法？ 実際、すべてのノードにアクセスするため、これはあまり重要ではありません。 すべてのノードにアクセスする場合、最初のアプローチは少し高速です。 ただし、 早期終了を使用する場合、すべてのノードにアクセスすることはないため、2番目のアプローチははるかに高速になります。 最初の方法は毎回すべてのノードを通過します 。 2番目の方法は、訪問したノードのみを通過します。
ノードID
（注：ほとんどの場合、この最適化は必要ありません。）ハッシュテーブルアプローチを機能させるには、ノードをハッシュする必要があります。 または、各ノードに整数の識別子を与えることができます。 その後、ビットマップを使用して
visited
を保存
visited
、通常の
int
配列を使用して
distance
と
came_from
を保存
came_from
ます。
CまたはC ++でコードを記述する場合、
distance
および
came_from
初期化せ
came_from
残すことができ
came_from
（潜在的にこれは大きな利点です！）。 ビットマップを初期化するだけで、64個の識別子を1つの
(long) int
に圧縮できます。
distance
または
came_from
の値は、ビットが設定されている場合にのみ初期化されます。 十分なスペースがある場合は、スタックにdistance / came_from配列を配置するか、各検索後に再初期化されない静的に割り当てられた配列を使用できます。 訪問したビットマップを初期化するコストとハッシュテーブルを使用するコストを慎重に比較検討してください。 各検索で訪問したノードの一部が小さい場合は、ハッシュテーブルを使用した方がよい場合があります。