こんにちは
みにくい社長です。
今日はゲームに欠かせない技術、衝突判定について解説します。
衝突判定は一般的に、物理エンジンと呼ばれるライブラリで行われることが多いです。
有名なものでは下記の３つがあります。
- Bullet(オープンソース)
- NVIDIA PhysX(現在はオープンソース)
- Havok(有償ミドルウェア)
物理エンジンの中には衝突判定以外にも、
- 物理的な挙動の計算
- clothシミュレーション
- 破壊シミュレーション
などが含まれていますが、今回は衝突判定について取り上げます。
ゲームエンジンではユーザーが簡単に衝突判定を行うことができるようになっていますが、使い方を誤ると瞬時に処理負荷が上がってしまいます。
正しい使い方をする為に、ある程度仕組みを知っておきましょう。
形状
まず、衝突判定の形状についてです。
球体、直方体、円錐、角錐、円柱、カプセル、直線（Ray）
などがありますが、どれが処理負荷が高いかわかりますでしょうか？
3次元の計算となると、正確に衝突判定を行うには複雑な計算が必要になります。
最も処理負荷が低いのは、球体同士の判定です。
これは、
オブジェクト間の距離≦オブジェクトの半径の合計
という簡単な判定で済みます。
直方体は簡単に見えますが、３次元で回転すると判定が非常に複雑になります。
できるだけ簡単な形状を使用したい所ですが、全てのキャラクタを円で判定する訳にもいきません。
キャラクタの形状とコリジョンの形状が大きく異なる場合、地形へのめり込み等が発生してしまいます。
キャラクタによく使われる形状は、カプセルです。
カプセルでは足元が半球になっている為、ちょっとした段差が登れなくなるような問題を簡単に回避することができます。
ワールド
物理エンジンにはワールドという概念があります。
ゲームでは毎フレーム、シーン内にあるコリジョン全ての総当たり判定を行う必要があるのですが、
地面やキャラクタ同士の押し当たり判定をするためのコリジョンと、攻撃やダメージの判定を行うコリジョンは用途が異なります。
用途が異なるコリジョン同士で判定を行うのは処理時間がもったいないので、できれば避けたいところです。
その為、用途別に登録するワールドを分け、ワールド内での総当たり判定を行うようにします。
ブロードフェーズとナローフェーズ
ワールドを分けても、衝突判定の処理負荷は膨大です。
100個のオブジェクトが存在していた場合、100×99÷2＝4950回の衝突判定が必要です。
つまり、Ｏ(n2)の計算量になります。
ワールドを分けることで計算回数を減らすことができましたが、今度は概算で計算量を減らします。
- ブロードフェーズでは大まかな形状で計算
- ナローフェーズはブロードフェーズで通過した形状を正確な形状で計算
と２回のフェーズに分けて計算します。
計算回数は増えてしまうのですが、計算量は大幅に削減することができます。
では、ブロードフェーズの概算とはどのように行うのでしょうか。
ブロードフェーズでは、OBB(Oriented Bounding Box)というおおまかな形状で計算します。
OBBはオブジェクトを内包する最小限のXYZ軸に沿った直方体です。
全オブジェクトをXYZ軸に合わせることで、計算量を大きく減らすことができます。
形状にもよりますが、球体のバウンディングスフィアを使う場合もあります。
100体のオブジェクト同士の判定がブロードフェーズで10体まで絞られれば、ナローフェーズの負荷が大きく下がることになります。
レイはなぜ重い？
Rayの衝突判定は重い、という話をよく聞きます。
Rayは細いので実際に当たるオブジェクトは少なく感じますよね。
であれば、ナローフェーズの負荷が低いのでは？と思うかもしれません。
どのような時にRayを使うかを考えてみてください。
FPSの照準が敵キャラクタに当たるかどうかを判定したい時、遠くの空まで届くような長いRayの判定をすることがありますよね。
その時、OBBの大きさは全てのマップを飲み込むようなサイズになってしまいます。
これではブロードフェーズが機能せず、ナローフェーズで全ての判定を行うことになってしまいます。
そんな時はRayを何本かに分割し、手前から判定を行うことをオススメします。
そうするとOBBが小さくなり、判定を高速化することができます。
ただし分割数が多すぎると逆に負荷が上がるので、検証が必要です。
他にも8分木を使うなどの高速化の手法がありますが、今回はここまで。
では、またねー。
