処理を減らすための数学２

おはようございます。本日の当番、プログラマーのK.Yです。

今回も前回に引き続き処理軽減の参考になりそうなお話です。

前回の内容は【いちばん近いオブジェクトを探す】処理でした。
今回はというと、やはりオブジェクトを探す処理です。

ただ、今回は距離ではなく【特定の範囲内にいるオブジェクトを探す】です。

例えばこんな感じです。

このように、例えばプレイヤーの視野範囲内にいるオブジェクトを
探すような感じの処理を考えてみます。

やり方のひとつとしては以下のような方法があります。

プレイヤーの座標を　 ( px py )
オブジェクトの座標を ( ox oy )
としたとき

（１）それぞれの値を引く
　　　x1 = px - ox
　　　y1 = py - oy

（２）アークタンジェント関数にその値を放り込む
　　　求めたい角度 = atan2( x1, y1 )

存在するオブジェクトの数分この処理を行う事でそれぞれの角度が取得できます。
そして、その中でプレイヤーの視野角よりも小さいものが
探すべきオブジェクトになります。

手順としては（１）と（２）だけしかありませんし、
これでいいじゃないの？と思うかも知れません。
しかし、ここで安心してはいけません。
なぜなら（２）の処理がなかなかの重たさだからです。
それも毎フレーム全オブジェクトに対してこの処理を行うとなると
結構な負荷になってしまいます。

　
というわけで、もっと処理を軽くできないかという事で
以下のような方法をとってみます。

やり方としましては条件に合わないオブジェクトを対象から外していくやり方です。

○プレイヤーの後ろにいるオブジェクトを対象から外す

　この図でいうところの赤色の領域にいるオブジェクトは
　プレイヤーの後ろになります。
　調べる方法としましては、それぞれのＸ座標を比べるだけです。
　これで、プレイヤーよりもＸ座標が小さかったら
　後ろにいるオブジェクトになります。
　オブジェクトがまんべんなくエリアに存在している場合、
　これだけで約半分が対象から外れます。

ここからは仕様にもよりますが以下の方法で対象から外す事ができます。

○例えばプレイヤーの視野角が４５度の時

　黄色の領域にいるオブジェクトはプレイヤーの前方にいますが
　視野範囲の外側にいます。
　この黄色の領域にいるかを調べるために
　上で求めた x1 と y1 の絶対値を比べます。
　その結果 |x1| < |y1| となっていれば
　黄色の領域にいるオブジェクトになります。
　これで、さらに半分ほど対象から外れました。

というか、これで残ったオブジェクトが
プレイヤーの視野範囲内にいるオブジェクトになります。

○じゃあ、３０度の時はどうするの？

　基本的には４５度の時と考え方は同じですが、ひと手間必要です。
　tan30 = 0.57735026918962576450914878050196
　ですので、これを定数にでもして持っておきます。
　こんな感じで
　#define TAN_30 (0.57735026918962576450914878050196)
　そして
　|x1 * TAN_30| < |y1|
　となるオブジェクトを対象から外したら
　残りは視野範囲内にいるオブジェクトになります。

　
最初の例ではアークタンジェントのように三角関数を使って処理しましたが、
仕様によってはそのような関数を使わなくても同じような結果を得る事ができます。

このように【角度を扱うための数学の知識は、
三角関数を使わなくても処理できる場面を発見できる】という事もあったりします。

今回の例は２Ｄですし角度も４５度や３０度という分かりやすいものでしたが、
３Ｄ空間上やその他の角度でも仕様によっては同じように対応が可能な場所は
色々とあると思います。

そんな場所を発見し、変更を加え、
処理軽減をどんどんと実装していければと思います。

・・・というわけで、あいかわらずプログラムとにらめっこ中。