2Dゲームの当たり判定

当たり判定領域の例。
プレイヤーの判定領域はゲームによって点、円、矩形など異なる形を取る。
ゲームでは様々な形状の敵機、弾丸、障害物との衝突判定を行う必要がある。

本項では敵機・弾丸・障害物などの衝突判定をする際に使うアルゴリズムを紹介する。
まずは最も簡単な、「点と円」「点と矩形」の当たり判定について解説し、
さらに複雑な図形や、移動する物体を想定した当たり判定へと拡張していく。
・点と円
・点と矩形
・点と多角形（各頂点の角度が180未満の場合限定）
・点と任意の多角形
・線分と線分
・線分と円

点と円の当たり判定

点の座標（x1,y1）と、円の中心座標（x2,y2）、円の半径rが与えられているとする。
この場合、点の座標と円の中心座標との距離Rを求め、Rが半径r以下の場合に当たりとなる。
ピタゴラスの定理より、
R² ＝ (x2-x1)² + (y2-y1)²
となるので、
(x2-x1)² + (y2-y1)² ≦ r²
が成り立つ場合に当たりとすれば良い。

点と矩形の当たり判定

点の座標（x1,y1）と、矩形の左上（left,top）右下(right,bottom)が与えられているとする。
座標は画面左上を原点(0,0)とし、画面右下へ進むにつれて正の値を取るものとする。
この場合、
left≦x≦right かつ top≦y1≦bottom
が成り立つ場合に当たりとすれば良い。

点と多角形（各頂点の角度が180未満の場合限定）の当たり判定

点の座標（x1,y1）と、多角形の頂点座標A(ax,ay),B(bx,by),C(cx,cy)が得られているものとする。
本項では最も単純なケースとして、三角形ABCを例に挙げるが、四角形以上の多角形でも計算方法は同じである。
（ただし、四角形以上の多角形では、各頂点の角度が180以上になってはいけない）
まず、各頂点を一周するようにベクトルAB,BC,CAを求める。
AB=(bx-ax,by-ay)
BC=(cx-bx,cy-by)
AB=(ax-cx,ay-cy)
次に、各頂点から点(x1,y1)へのベクトルを求める。
AO=(x1-ax,y1-ay)
BO=(x1-bx,y1-by)
CO=(x1-cx,y1-cy)
ベクトル同士の左右判定は外積のZ軸成分を用いる。
(本項ではZ軸成分を記すために「|z」と記述する)
AB×AO|z=(bx-ax)*(y1-ay)-(by-ay)*(x1-ax)……�@
BC×BO|z=(cx-bx)*(y1-by)-(cy-by)*(x1-bx)……�A
CA×CO|z=(ax-cx)*(y1-cy)-(ay-cy)*(x1-cx)……�B
�@�A�B式の符号がすべて＋または、すべて−ならば、
点は多角形の内部に有るため、当たりとなる。
外積Z軸成分の符号はベクトル同士の右回り・左回りを示すためである。

※外積の説明をしだすとキリが無いので、かなり省略して解説する。
3次元ベクトル同士の外積(x1,y1,z1)×(x2,y2,z2)は
(y1*z2-z1*y2 , z1*x2-x1*z2 , x1*y2-y1*x2)
で計算できる。
ここで、2次元ベクトル同士の場合、z1=z2=0なので、外積Z軸成分以外は0となる。
外積Z軸成分の符号は右回り・左回りを示し、絶対値は2つのベクトルが成す平行四辺形の面積を示す。

線分と線分の当たり判定

線分AB点の頂点座標(ax,ay),(bx,by)、線分CDの頂点座標(cx,cy),(dx,dy)が有るとする。
この2本の線分が交差している場合を当たりと判定する。
次の2項目を同時に満たす場合のみ、線分は交差していることになる。
・ベクトルABに対して、ベクトルACとベクトルADは左右逆の向きに存在する。……条件1
・ベクトルCDに対して、ベクトルCAとベクトルCBは左右逆の向きに存在する。……条件2
AB=(bx-ax,by-ay)
CD=(dx-cx,dy-cy)
AC=(cx-ax,cy-ay)
AD=(dx-ax,dy-ay)
CA=(ax-cx,ay-cy)
CB=(bx-cx,by-cy)
上記のように各ベクトルは書き下すことができる。
ベクトル同士の左右判定は、外積のZ軸成分(前章を参照)を用いる。
符号の異なる数同士をかけると負の数になるため、条件1,2は下記のように変換できる。
( AB×AC|z )*( AB×AD|z ) ＜ 0 ……条件1
( CD×CA|z )*( CD×CB|z ) ＜ 0 ……条件2
さらに書き下すと、下記のようになる。
((bx-ax)*(cy-ay)-(by-ay)*(cx-ax))*((bx-ax)*(dy-ay)-(by-ay)*(dx-ax)) ＜ 0 ……条件1
((dx-cx)*(ay-cy)-(dy-cy)*(ax-cx))*((dx-cx)*(by-cy)-(dy-cy)*(bx-cx)) ＜ 0 ……条件2
この条件を同時に満たす場合に、線分ABと線分CDは交差し、当たりとなる。

線分と円の当たり判定

線分AB点の頂点座標(ax,ay),(bx,by)、半径rの円Oの中心座標(ox,oy)が有るとする。
AB=(bx-ax,by-ay)
OA=(ax-ox,ay-oy)
円Oから、ベクトルABに垂直で長さrのベクトルOPを求める。
OPは線分向きと逆向きの二通り得られるが、仮に片方を採用する。
OP=r*sqrt((ay-by)²+(bx-ax)²)(ay-by,bx-ax)
次に、ベクトルOPとベクトルOAの成す角が鈍角ならば、OPの向きがプラスマイナス逆なので、
OP=-r*sqrt((ay-by)²+(bx-ax)²)(ay-by,bx-ax)
とする。
ここまでで得られた線分OPと、線分ABが交差している場合を当たりと判定する。
( AP×AB|z )*( AO×AB|z ) ＜ 0 ……条件1
( OP×OA|z )*( OP×OB|z ) ＜ 0 ……条件2
この条件1,2を同時に満たす場合に、線分ABと円Oは交わり、当たりとなる。

また、線分の交差は無くとも、線分ABの頂点のうち、一方でも円Oに含まれる場合は当たりとなる。
すなわち、
(ax-ox)² + (ay-oy)² ≦ r²……条件3
(bx-ox)² + (by-oy)² ≦ r²……条件4
この条件3,4のいずれかを満たす場合も、当たり有りとなる。