衝突判定
The instants of collision are calculated with high precision, and the physical bodies never actually interpenetrate. We call this a priori because we calculate the instants of collision before we update the configuration of the physical bodies.
The main benefits of the a posteriori methods are as follows. In this case, the collision detection algorithm need not be aware of the myriad of physical variables; a simple list of physical bodies is fed to the algorithm, and the program returns a list of intersecting bodies. The collision detection algorithm doesn't need to understand friction, elastic collisions, or worse, nonelastic collisions and deformable bodies.
ヒットボックス(hitbox)とは、ビデオゲームにおいてリアルタイムの衝突判定のために一般的に使用される「見えない四角」であり、バウンディングボックスの一種である。3Dモデル(3Dゲームの場合)やスプライト(2Dゲームの場合)などの可視オブジェクトと同じ場所にアタッチされることが多く、2Dゲームでは長方形、3Dゲームでは直方体の形をしている。円形または球形をしている場合もよくあるが、それでもほとんどの場合は「ボックス」と呼ばれる(海外でも)。可動オブジェクトでは、モーション中の精度を確保するために、可動する各パーツにヒットボックスがアタッチされているのが一般的である。
ヒットボックスは、キャラクターと敵の打撃や弾丸との衝突判定を取る場合など、「一方向」の衝突を検出するために使用される。衝突によってフィードバックが発生する場合、例えば壁にぶつかった際にフィードバックによって反発が起き、すぐ次のフレームでは壁から引き離される、と言うような場合は、ヒットボックスの位置が絶えず変化することになり、ヒットボックスの位置の管理がとても面倒になるので、ヒットボックス方式を使うのは適していない。
特に3D空間で衝突判定を取る場合において、上記の方式では管理が面倒になる場合は「軸並行境界ボックス方式(Axis Aligned Bounding Box, AABB方式)」を使う。
ヒットボックス方式の「基本的な方法」ではオブジェクトのバウンディングボックス(境界ボックス)の左上の点をオブジェクト自体の座標とみなし、そこから右下までの長さを取るのが一般的なのに対して、AABB方式ではヒットボックスの中心座標をオブジェクト自体の座標とみなし、そこからxyz軸方向に±何mの広がりがある、という表し方をする。ヒットボックスの中心を(x,y,z), 双方向への広がりの大きさを(rx,ry,rz)とすると、このヒットボックスは x方向については x-rx ~ x+rx, y方向には y-ry ~ y+ry, z方向には z-rz ~ z+rz の範囲を占める。軸並行境界ボックス方式を用いてふたつのヒットボックスA・Bについて衝突判定を行うには、以下のようになる。
Alternative algorithms are grouped under the spatial partitioning umbrella, which includes octrees, binary space partitioning (or BSP trees) and other, similar approaches. If one splits space into a number of simple cells, and if two objects can be shown not to be in the same cell, then they need not be checked for intersection. Since BSP trees can be precomputed, that approach is well suited to handling walls and fixed obstacles in games. These algorithms are generally older than the algorithms described above.
2Dゲームにおいて、ピクセル単位で衝突判定を取る方式。スプライト画像をベースとする衝突判定の方式なのでimage-based collision detectionともいう。1980年代頃までの8bit機ではスプライトの表示位置ごとの衝突判定を取ることしかできなかったが(当時のスプライトの大きさは基本的に8x8であったため、8ドット単位の衝突判定になった)、この方式を用いることで、1ドット単位の衝突判定が可能になる。
MSX2(1985年発売)の「スプライトモード2」ではハードウェアの支援が得られることがウリの一つであった。ハードウェアの支援が得られないハードにおいてソフトウェアベースでピクセルパーフェクトを実現する方式がいくつかあるが、現代においてこれをソフトウェアで実装するには、基本的には複数のヒットボックスを組み合わせて衝突判定を取る方式が用いられる。そもそも現代の2Dゲームエンジンでは8bit機時代のようなスプライト機能をソフトウェア上で擬似的に実装しているだけであるので、現代のハードウェアの性能をもってすれば、ソフトウェアベースでピクセルパーフェクトを実装することは特に困難ではない。