タイルで構成されるフラットマップがあるとします。 一部のタイルにはモンスターがおり、一部のタイルにはモンスターが興味を持っているあらゆる種類のものがあります。プレイヤー、武器、ポーション、弾薬など、同じ脈です。 課題は、モンスターに何にどのように行くべきかを説明することです。 パスは最適に近く、計算時間は可能な限り短くする必要があります。 最も簡単な方法の1つは、特定の目標までの距離のヒートマップを使用することです。
免責事項
私はすぐにこれがかなりよく知られた方法であることを言わなければなりません：それはゲームのAI対戦相手（例えば、 ブローグ ）に、そしてRTSボットに 、そして粒子の動きを保証するために 、そしてそのためにはるかに使用されました。 以下では、ベーグルについて説明します。つまり、世界は離散した正方形のタイルで構成され、各オブジェクトは少なくともそれらの1つにあると仮定します。[原則として、（接続された）グラフと同型の世界のトポロジでも同じことができます。 roguebasin.comのこの記事から撮影した写真
ゾンビ
ヒートマップがどのように機能するかを説明するために、可能な限り単純なモンスターであるゾンビを作成することから始めます。 彼はプレイヤーを追いかけなければならず、他の世界に気を取られず、彼が近くにいるとき、彼は混戦に突入しなければなりません。 ベーグルでは、近接攻撃と移動が1つのチームによって伝統的に行われるため、ゾンビは1つのことだけを実行するという事実によって人生が簡素化されます。つまり、プレイヤーに向かって最短方向に急ぐことです。 すべてのAIは、それぞれこの最短経路を見つけることになります。
パスを見つけるには、マップのサイズの2次元配列が必要です。各セルには、このタイルからプレーヤーまでの距離が含まれています。 プレーヤーがゼロに等しいタイルの値をみましょう。 隣接するタイルでは1に等しく、次の行では2になります。 一般に、タイルの値は、隣接するタイルの中で最も小さい値より1つ大きくなります。 通過できないタイルは無視されます。つまり、Noneまたは非常に大きな数のタイルがそこに配置されます。 次のようになります。
これで、ゾンビが各ターンで隣接するタイルの値を学習し、最小のタイルを選択して、対応する方向に進むだけで十分です。 別のゾンビがすでに立っているか、他の何かがあなたの侵入を妨げている場合、現在のものよりも大きくない値のタイルがある限り、オプションを少し悪くするなどしてください。 同様に優れたオプションがいくつかある場合-ランダムに選択します。 一般に、それですべてです。 ゾンビは自信を持ってプレーヤーの方へ移動し、ジャンルの法則に従って、地雷によって爆破され、火にさらされます。 ちなみに、これはHaxeFlixelのインタラクティブなデモです。
この方法の最初の利点は明らかです。高速です。 幅を回ってみると、最悪の場合の再計算の複雑さは、マップの領域から線形になります。 実際には、プレーヤーの動きのほとんどは、マップをまったく変更しないか（1つの場所に立っている場合）、または隣接するセルのみに影響します。 ゾンビ自身が移動の選択に費やす時間はごくわずかです。 ちなみに、2番目の利点は次のとおりです。多くのゾンビが同じカードを使用できるため、モンスターの数を増やしても、移動に費やされる時間はほとんど増えません。 画面にゾンビが1人いても1000人であっても問題ありません。ほぼ同じ方向に向けられます。
複数のアトラクタ
少し複雑な動作を示すために、ゴブリンを作成できます。 彼には人生に2つの目標があります。ゾンビのようなプレイヤーを攻撃し、金を集めることです。 したがって、カードの計算の開始時に、プレーヤーの下にゼロを置くだけでなく、少なくとも1つのコインが置かれている各タイルの下にある値を示します。 距離は、前の例と同じ方法で計算されます。 以下の図では、金の場合は-4の値が示されています。つまり、ゴブリンは10単位のexpに変わるチャンスよりも少し先に金に行く準備ができています。
明らかな問題があります：ゾンビとゴブリンの両方を1つのゲームに追加するとどうなりますか？ 動作が異なり、同じカードを使用できなくなります。 また、各タイプのAIのヒートマップを取得すると、速度の利点がすぐになくなる可能性があります。 解決策は、各タイプのアトラクタのマップを作成することです。 各AIは、関心のあるすべてのカードから値を取得し、重み付けされた量に基づいて次のステップを選択します。 「ゾンビ用カード」、「ゴブリン用カード」、「ケンタウロス用カード」よりも「プレーヤー付きカード」、「ゴールド付きカード」、「矢印付きカード」はどのように速いのですか？ 計算率がすべてです。 マップは、アトラクタが変更されたときにのみ更新する必要があります。 原則として、プレイヤーは移動するか、床から金を拾うか、モンスターを撃ちますが、同時にすべてではありません。 つまり、通常、1ターンごとに更新されるマップは1つだけであり、個々のAIカードの場合、一度にすべてを再カウントする必要があります。
AIを拡張する
ゴブリンは、ゾンビを悩ませなかった別の問題について考える必要があります。 彼は金を集めたいと考えていますが、ヒートマップは彼に彼に近づくように命令することしかできません。 幸い、人工知能は1枚のカードに限定されません。 移動方向の確認は、モンスターが現在の場所では実際には何もすることがないことを発見した後に行われます。 マップのローカル低域でのみ他のアクションの可能性をチェックすることで速度を上げることができますが、これは通常、時期尚早の最適化です。モンスターが実際に何かを行う多くのセルはローカル低域ではありません。
説明されている実装のもう1つのマイナス点は、ゾンビがプレイヤーに1 HP残っていても戦うことであり、空腹で死ぬゴブリンは金の収集を停止しません。 さて、これらの2つのクリーチャーの場合、これは通常の可能性が高いですが、実際には、モンスターは状況に応じていくつかのタイプの動作を行う必要があります。 いつものように、ここではステートマシンが役立ちます。 ヒートマップの場合の唯一の特徴は、マシンの各状態に独自のマップの重みベクトルがあることです。 重傷を負った相手は、プレイヤーから退却する可能性が高いです。つまり、対応するカードの値に負の値を掛けますが、すべての足から最も近いヒーラーまで走り、ポーションカードの値に大きな重みを与えます。 おなかがすいている人も同じように食べ物を求め、プレイヤーの目をひかないようにし、床に横たわっている弾薬を完全に無視します。
落とし穴
私は個人的に3つ見つけました。 まず、ポイントAからポイントBへのパスが複数存在する場合があります。 AIの場合、これは問題ではありません。さまざまな方法でプレイヤーに向かうモンスターは、行動の決定論で目を少し突くだけでなく、実際よりも少しスマートに見えます。 しかし、 roguebasinの記事では、同じマップを使用して、マウスで移動したり、撮影したりするときに、プレーヤーからカーソルまでのパスを表示することを提案しています。 これは非常に悪い考えです。このように画面に表示されるパスは最適かもしれませんが、キャラクターが同じポイントに行くパスと一致する必要はありません。 射撃や呪文の場合、この問題はさらに深刻です。なぜなら、カードはコーナーを歩いたりカーブに沿って移動したりすることを禁止していないからです（マップトポロジで許可されている場合）。 そして、有名なジョークの迫撃砲だけが角を曲がって撃たれるべきです。
第二に、この方法はモンスターの視野を無視します。 ゾンビは、プレーヤーを見たことがないので、存在を知らなくても、カードの半分をプレーヤーを追いかけることができます。 プレイヤーがモンスターを見ると、モンスターもそれを見ると考えられます（ステルス用に調整されます）。 次に、ヒートマップはプレーヤーの視野内でのみ更新され、その外側のタイルは通過できないタイルと同様に無視されます。 これは松葉杖ですが、残念ながら、膝の上のすべてのNPCの正直な視野は短くすることはできません。
第三に、各敵は自分で行動します。 モンスターをアトラクターとしてマップを作成することで、「パックに迷い込む」や「リーダーに従う」などの動作を指定できますが、モンスターの複雑な戦術的相互作用には、人工知能に関するより深刻な作業も必要です。
おわりに
これが、マッチやドングリから優れた人工知能を収集できる方法です。 巧妙ではありませんが、カードの重量とバランスの取れた状態マシンのバランスが取れているため、対戦相手は実際よりもずっと賢く見えます。
PS：この方法は、結局のところ、リーアルゴリズムと呼ばれています。 訂正してくれたShtucerに感謝します。