衝突判定
現実を厳密にシミュレートしようとするようなタイプのシミュレーションゲームはともかくとして、ゲームで物理的に正確な衝突判定を行うことはまれである。そもそも、たとえゲームで正確な衝突判定を目指したところで、必ずしもすべての場合において正確な衝突判定のチェックが行えるわけでもない。
ゲームは実際の物理を模倣する必要がないため、衝突判定の確実性はそれほど問題ではない。ほとんどすべてのゲームは事後衝突検出を使用しており、もし衝突が検知された場合は非常に単純なルールを使用して解決される。たとえば、キャラクターが壁にめり込んだことが検知された場合、キャラクターは単に壁にめり込んでいなかった最後の場所まで戻される、と言う処理を行うゲームもある。一部のゲームでは、キャラクターが壁にめり込むまでに移動できる距離を計算し、壁にめり込まない距離までしか移動できないようにする、という処理を行う。
ゲームでフィールドとの衝突判定を行う場合、基本的にはキャラクターを「点」で近似するだけで十分である。この場合、バイナリ空間分割木は、「点」がフィールド内にめり込んだ状態であるか、それともそうでないかをチェックするための実行可能で効率的でシンプルなアルゴリズムを提供する。キャラクター同士の衝突、もしくは敵弾や当たるとダメージを受ける物との衝突判定はまた別の手法を用いて行われる。
↑ “Components of the Amiga: The MC68000 and the Amiga Custom Chips”. 2018年7月17日時点のオリジナルよりアーカイブ。2018年7月17日閲覧。 “Additionally, you can use system hardware to detect collisions between objects and have your program react to such collisions.”
↑ “Hitbox”. Valve Developer Community. Valve. 2011年9月18日閲覧。
↑ 特開平7-230559「衝突判定処理システムおよびこれを用いた画像処理装置」。ちなみにこのセガの特許はゲーム業界では非常に重要な特許であったようで、セガがゲーム機から撤退する前には競合機においてこれを回避するかのような特許が出願されている他、セガがサードパーティになった後は例えば任天堂株式会社の特開2017-217334「ゲーム装置、ゲーム制御方法およびゲームプログラム」(Wii Uの特許)などでも引用されている。なお1994年に出願したものであり、2014年に失効している。
↑ ビデオゲームの語り部たち 第2部:「バーチャファイター」のプロトタイプに込められた石井精一氏の人生
↑ 特開平10-165648「当たり判定装置,及びコンピュータプログラムを記録した媒体」
↑ 特開平11-328445「衝突判定装置および方法、および衝突判定方法を記録した媒体」。おそらくは競合機セガサターンを展開する前記のセガの特許を回避するためである
( A x − A r x ≤ B x + B r x ) ∧ ( B x − B r x ≤ A x + A r x ) {\displaystyle (A_{x}-A_{rx}\leq B_{x}+B_{rx})\land (B_{x}-B_{rx}\leq A_{x}+A_{rx})} ∧ ( A y − A r y ≤ B y + B r y ) ∧ ( B y − B r y ≤ A y + A r y ) {\displaystyle \land (A_{y}-A_{ry}\leq B_{y}+B_{ry})\land (B_{y}-B_{ry}\leq A_{y}+A_{ry})} ∧ ( A z − A r z ≤ B z + B r z ) ∧ ( B z − B r z ≤ A z + A r z ) {\displaystyle \land (A_{z}-A_{rz}\leq B_{z}+B_{rz})\land (B_{z}-B_{rz}\leq A_{z}+A_{rz})}
AABBは大雑把な衝突判定や可視判定で使われることがある。
AABB方式は2Dの衝突判定を取る場合でも使われることがある。特に四角いヒットボックスと円形のヒットボックスの衝突判定を取る時は、四角いヒットボックスの座標をAABB方式で管理した方が楽である。
Once we've selected a pair of physical bodies for further investigation, we need to check for collisions more carefully. However, in many applications, individual objects (if they are not too deformable) are described by a set of smaller primitives, mainly triangles. So now, we have two sets of triangles, S = S 1 , S 2 , ... , S n {\displaystyle S={S_{1},S_{2},\dots ,S_{n}}} and T = T 1 , T 2 , ... , T n {\displaystyle T={T_{1},T_{2},\dots ,T_{n}}} (for simplicity, we will assume that each set has the same number of triangles.)
The obvious thing to do is to check all triangles S j {\displaystyle S_{j}} against all triangles T k {\displaystyle T_{k}} for collisions, but this involves n 2 {\displaystyle n^{2}} comparisons, which is highly inefficient.
複雑な形状のポリゴンモデルの衝突判定を行うとき、ポリゴンモデルを「複数の球の組み合わせ」とみなし、それぞれの球において衝突判定を行うことでオブジェクト同士の衝突判定を行うことができる。セガの初代『バーチャファイター』(1993年)で初めて実装された手法。現在はポリゴンのキャラクター同士の衝突判定を取る際の基本的な手法であるが、これが初めて実装された1993年当時は衝撃的であったとのこと(『バーチャファイター』以前のゲームは、各キャラクターの姿勢や動作の一つ一つについてヒットボックスを個別に実装していたため、メモリを食う上にキャラクターの見た目と衝突判定が一致していなかった)。