特定のターゲットを攻撃できる有効な動きのリストから有効な位置を与えることができるアルゴリズム名または実装を探しています。
私は 2D タイル マップと、特定の数の移動と範囲内で敵を攻撃できるヒーローを持っています。マップ上の障害物により、ヒーローの移動エリアは変化し、穴が開く可能性があります。
この質問では、この移動エリアと攻撃エリアを組み合わせて、ヒーローがゲーム ボード上で発揮する「脅威」範囲の合計を取得する方法を学びました。この場合、2 体の敵が脅威範囲内にあり、攻撃することができます。
かかる一般化されたアルゴリズムの名前または情報を探しています:
そして、特定のターゲットを攻撃できるオレンジ色の領域内のすべてのセルを返します。敵は独自の脅威エリアを発揮するため、必ずしも最も近い正方形が必要というわけではありません。可能な動きを調べて、ヒーローが攻撃のために移動する脅威が最も少ないものを選択します.
HERO の到達可能なタイルのセットは既知です。これらの各タイルの周りには脅威エリアがあり、これは (凸型?) 多角形 (菱形?) のようなもので、敵の位置は別の凸型多角形 (この場合は正方形) と考えることができます。一般的なケースでは、これらのポリゴンが交差するかどうかをテストしたいと思いますよね?
残念ながら、この一般的な問題は予想以上に難しいようです。
問題にいくつかの特別な特性があることがわかった場合は、幸運が訪れるかもしれません。HERO の脅威領域が常に凸状である場合、ダイヤモンドの境界を使用して内側/外側テストを実行できます (CGAL のbounded_side_2テストに似たもの) 。
アプローチが十分でないとわかった場合は、次のことができます。ボードの「攻撃可能な位置」のセットを事前に生成します。各セルは、HERO が攻撃できる他のセルのセットを知っています。これは時間と空間のトレードオフであり、大きなメモリの制約や動く障害物がなければ、うまく機能するはずです。
問題を解決できると思う方法は次のとおりです。
1) ヒーローの脅威を見つける (移動 + 攻撃マス)
脅威エリア内の各ターゲットに対して、以下を実行します。
2) 有効な動きの各マスについて、特定のターゲットまでのマンハッタン距離を計算します
3) (距離 <= 攻撃範囲) AND 正方形が有効な移動内にある場合、ヒーローはその正方形からターゲットを攻撃できます
私の特定のケースでは、近接ヒーローが周囲の 8 つの正方形すべてを攻撃できるようにする (コネクティ 8) ため、チェスのキングのように振る舞い、マンハッタン距離の代わりにチェブシェフ距離を計算します。
