これはtraP Advent Calendar2016 11日目の記事です。

1.はじめに＆概要

こんにちは、@ninjaです。

この記事では、2Dゲームの当たり判定について理論と実装(Processing)をだらだらと書いていきます。

通り抜けの防止や斜めの壁を実装できるような点と線の当たり判定を解説します。

2.環境

実装にはProcessing(ver 3.2.3)を用います。

Processing

Processingについて説明するのが面倒だったので

紹介や解説は他サイトを参照してください。

3.理論

1.基本

今回は点が移動するだけの単純なゲーム？の当たり判定を作っていきます。

さっそくですが壁となる線分から考えていきます。

線分は始点と終点を持ち、始点から見て左からのみ判定を取ります。

四角形ならば画像のように線分を持たせます。

次にプレイヤーを考えます。

プレイヤーは位置と速さを持ち、壁にぶつからない限り自由に移動することができます。

2.衝突判定

プレイヤーは毎フレームに速さだけ移動していきます。

その移動する線上に壁、つまり線分が交差しているかを調べます。

プレイヤーの移動する前の点を $p(px,py)$ 、

移動後の点を $p^{\prime }(p{x}^{\prime },p{y}^{\prime })$ 、

判定を取りたい線分の始点を $a(ax,ay)$ 、

終点を $b(bx,by)$ とおくと

直線に対して点の正負が異なればよいので、

2点を通る直線の方程式から $(ay-by)\ast (x-ax)+(ax-bx)\ast (ay-y)=0$ ・・・ $(1.1)$ この式の左辺の値の符号が異なればよいので $((ay-by)\ast (px-ax)+(ax-bx)\ast (ay-py))\ast ((ay-by)\ast (p{x}^{\prime }-ax)+(ax-bx)\ast (ay-p{y}^{\prime }))<0$ ・・・ $(1.2)$ 同様にもう一つの線分についても考え $((py-p{y}^{\prime })\ast (ax-px)+(px-p{x}^{\prime })\ast (py-ay))\ast ((py-p{y}^{\prime })\ast (bx-px)+(px-p{x}^{\prime })\ast (py-by))<0$ ・・・ $(1.3)$ 式 $(1.2)$ , $(1.3)$ を同時に満たしているとき交差しているといえます。

3.交点

線分が交差しているかまでは分かったので、次はその線分の交点を求めます。

4点からなる交点の求め方

このサイトの三角形の面積比から交点を求める方法を使います。

交差している線分、判定は一方向のものに用いるので面積は正の値をとります。 $s1=((bx-ax)\ast (py-ay)-(by-ay)\ast (px-ax))/2$ , $s2=((bx-ax)\ast (ay-p{y}^{\prime })-(by-ay)\ast (ax-p{x}^{\prime }))/2$ よって交点の座標 $(x,y)$ は $x=px+(p{x}^{\prime }-px)\ast s1/(s1+s2)$ , $y=py+(p{y}^{\prime }-py)\ast s1/(s1+s2)$

4.座標の補正

このままでは斜めの線分に向かって進むと止まってしまうので線分に沿った方向の分移動させます。 $(x,y)$ を始点に、 $(p{x}^{\prime },p{y}^{\prime })$ を終点にもつ線分の平行な成分を足し、座標 $(x^{\prime },y^{\prime })$ を得ます。 $x^{\prime }=x+(bx-ax)\ast ((p{x}^{\prime }-x)\ast (bx-ax)+(p{y}^{\prime }-y)\ast (by-ay))/({(bx-ax)}^2+{(by-ay)}^2)$ , $y^{\prime }=y+(by-ay)\ast ((p{x}^{\prime }-x)\ast (bx-ax)+(p{y}^{\prime }-y)\ast (by-ay))/({(bx-ax)}^2+{(by-ay)}^2)$

5.はみ出し防止

このまま確定させると線分を突き抜けてしまうことがあるので $(x^{\prime },y^{\prime })$ をプレイヤーの移動後の点とおいて2,3をもう一度行います。

そしてやっとプレイヤーの座標を動かして終了です。

4.実装例

適当に書いていたら200行を余裕で越えてしまったので部分部分を抜粋していきます。
コード全文は下記リンクにて

class Point{
float x, y;

Point(float nx, float ny){
x = nx;
y = ny;
}
}

class Line{
Point p1, p2;
Point pv, vv;
float l;

Line(Point np1, Point np2){
p1 = np1;
p2 = np2;
l = sqrt((p2.x - p1.x) * (p2.x - p1.x) + (p2.y - p1.y) * (p2.y - p1.y));
pv = new Point((p2.x - p1.x)/l, (p2.y - p1.y)/l);
vv = new Point(-pv.y, pv.x);
}
Line(float x1, float y1, float x2, float y2){
this(new Point(x1, y1), new Point(x2, y2));
}

void draw(){
stroke(0, 0, 0);
strokeWeight(1);
drawLine(this);
}

Point delta(){
return subPoint(p2, p1);
}

Line clone(){
return new Line(p1.x, p1.y, p2.x, p2.y);
}
}

点と線分のクラスです。

デフォルトで参照渡しだったのでコピーできる関数を持たせています。

boolean isIntersected(Line l1, Line l2) {
if (l1.p1.x == l1.p2.x && l2.p1.x == l2.p2.x && l1.p1.x == l2.p1.x) {
return false;
}
if (l1.p1.y == l1.p2.y && l2.p1.y == l2.p2.y && l1.p1.y == l2.p1.y) {
return false;
}
float a = (l2.p1.x - l2.p2.x) * (l1.p1.y - l2.p1.y) + (l2.p1.y - l2.p2.y) * (l2.p1.x - l1.p1.x);
float b = (l2.p1.x - l2.p2.x) * (l1.p2.y - l2.p1.y) + (l2.p1.y - l2.p2.y) * (l2.p1.x - l1.p2.x);
float c = (l1.p1.x - l1.p2.x) * (l2.p1.y - l1.p1.y) + (l1.p1.y - l1.p2.y) * (l1.p1.x - l2.p1.x);
float d = (l1.p1.x - l1.p2.x) * (l2.p2.y - l1.p1.y) + (l1.p1.y - l1.p2.y) * (l1.p1.x - l2.p2.x);
return c * d <= 0 && a * b <= 0;
}

衝突判定用の関数です。

今回は端点でも判定をとるため平行なときは除外し、等号も含めるようにしています。

Line foldLine(Line l1, Line l2) {
Line ans = l1.clone();
float s1 = ((l2.p2.x - l2.p1.x) * (l1.p1.y - l2.p1.y) - (l2.p2.y - l2.p1.y) * (l1.p1.x - l2.p1.x));
float s2 = ((l2.p2.x - l2.p1.x) * (l2.p1.y - l1.p2.y) - (l2.p2.y - l2.p1.y) * (l2.p1.x - l1.p2.x));
ans.p2.x = l1.p1.x + (l1.p2.x - l1.p1.x) * s1 / (s1 + s2);
ans.p2.y = l1.p1.y + (l1.p2.y - l1.p1.y) * s1 / (s1 + s2);
ans.p2 = subPoint(ans.p2, l2.vv);
return ans;
}

Line bendLine(Line l1, Line l2){
Line remain = l1.clone();
Line ans = foldLine(l1, l2);
ans.p2 = addPoint(ans.p2, product(l2.pv, innerProduct(remain, l2.pv)));
return ans;
}

はみ出し防止用の関数と補正有りの関数です。

補正有りは途中まで同じなのでfoldLineを関数内で呼んでいます。

また、桁落ちで線分を貫通するのを防ぐため、線分の法線方向の単位ベクトルを引くことで押し出しています。

実際の動き

コード全文は[こちら](https://github.com/n-inja/AdventCalendar)(github)

5.参考にさせていただいたサイト

マルペケつくろーどっとコム

Visual Basic Library

もっと簡単に - 線分交差判定 -

Neo Transilvania

2Dゲームの当たり判定をガチで作りこむ

画像処理ソリューション

4点からなる交点の求め方

明日はleoさんとponyaさんの2人です。お楽しみに！