衝突判定
ビデオゲームにおいては、非常に限られた計算機時間をいくつかのタスクに分割する必要がある。ゲームではこのようなリソースの制限に加え、かなり原始的な衝突検出アルゴリズムを使用せざるをえないという制限があったにもかかわらず、ゲームのプログラマーは、一応はプレイヤーの信頼に足るプログラムを作り上げて来た。
2Dのゲームの時代においては、処理するオブジェクトの数が非常に限られていたため、すべてのオブジェクトの衝突判定を行うことはそれほど問題ではなかった。2Dのゲームでは、ハードウェアにピクセル単位の衝突判定が実装されている場合もあり、その場合はハードウェアが画面上のスプライト同士の間で重複するピクセルを検出して報告してくれるので、ソフトの開発者としても効率的で楽だった。もしハードの支援が無かった場合でも、画面にタイルパターンを並べ、BGのタイルパターンと自機のスプライトが重なったかどうかをチェックするだけで十分な衝突判定が可能であった。ペアワイズ法を使った衝突判定のチェックにおいては、「ヒットボックス」と呼ばれる長方形の境界(円形の場合もある)が使用され、これで十分に正確な衝突判定が行えると考えられて来た。
3Dのゲームにおける衝突判定は、「空間をいくつかの区画に分割して刈り込む」という空間分割法か、もしくは「3Dのオブジェクトをいくつかの球に分割してペアワイズチェックを行う」という方法を長い間使用していた。
Each box is represented by the product of three intervals (i.e., a box would be I 1 × I 2 × I 3 = [ a 1 , b 1 ] × [ a 2 , b 2 ] × [ a 3 , b 3 ] {\displaystyle I_{1}\times I_{2}\times I_{3}=[a_{1},b_{1}]\times [a_{2},b_{2}]\times [a_{3},b_{3}]} ). A common algorithm for collision detection of bounding boxes is sweep and prune. We observe that two such boxes, I 1 × I 2 × I 3 {\displaystyle I_{1}\times I_{2}\times I_{3}} and J 1 × J 2 × J 3 {\displaystyle J_{1}\times J_{2}\times J_{3}} intersect if, and only if, I 1 {\displaystyle I_{1}} intersects J 1 {\displaystyle J_{1}} , I 2 {\displaystyle I_{2}} intersects J 2 {\displaystyle J_{2}} and I 3 {\displaystyle I_{3}} intersects J 3 {\displaystyle J_{3}} .