360度アクションゲームでの敵の探索

質問

スターオーシャンなど、戦闘でキャラクターが自在に敵の正面や背後に移動できるようなアクションゲームで、自分の移動するキャラクターから見て、どの敵が一番近いかを調べるには、やっぱり敵ごとの位置情報を調べて、自分の位置と比較していくしかないんでしょうか。

また、たとえば、30vs30のような多数対多数で、それぞれすべてのキャラクター達が一番近い敵を調べるようなゲームでは、どのようなアルゴリズムが使われているのでしょうか？

どなたかご教授ください。

回答No.2

sha-girl · ベストアンサー

自分の位置を原点、対象の位置(x,y,z)とすると
距離はsqrt(x^2 + y^2 + z^2)となりますが
距離を比較するだけならsqrtは不要でx^2+y^2+z^2で比較できます。

>30vs30のような多数対多数それぞれすべてのキャラクター達が一番近い敵を調べる
この計算量は30C2 = 435回にすぎないのでこの場合普通にCPUで計算したので問題ないと思います。

これが例えば毎フレーム30000個のオブジェクトの各距離判定を行うとかであれば
マルチコアを使って計算を分散させるか、最近ではCUDA等があるので
それらを使ってGPGPUを使うと高速に計算出来るでしょう。
(GPGPUはDirectX11から標準サポートされるそうです)

お礼

お礼が遅くなって申し訳ありません。

自分は今DirectXを使っていないので、GPGPUの機能を使うことは出来ないのですが、そもそも計算回数が少ないんですね。
今までsprtを使って計算していたのですが、これを省いただけでも速度が向上しました。
あちがとうございました。

回答No.1

yama1718

律儀に計算するなら三角関数で計算するのでしょうけど、
簡略化するなら単純に縦軸と横軸の差の合計を距離とする方法もあります。
これは戦略ゲームなどのマス目状のマップで、同距離のエリアがひし形状に広がっていきます。
かなり大雑把ですけど、これで大まかに並べておけば計算が効率化できます。
また、正確な距離が不要なら三角関数も計算済みのテーブルを使って高速化する方法もあります。
今ではＣＰＵの処理能力が高いので、律儀に計算しても充分速いのでしょうけど。

お礼

お礼が遅くなって申し訳ありません。

自分のマシンだと、ちょっと速度が気になったので質問してみたのですが、ほかのマシンだと問題ないんですかね。
いろんな方法を試してみます。
ありがとうございました。