Zenn
💥

距離関数で高速な当たり判定を実装する

2024/01/05に公開
math
#
gamedev
Processing
tech

この前、ふと「距離関数で当たり判定できるのでは?」と思い付き先行事例を探してみたものの、意外とそのような事例は少なかったので、今回は距離関数を用いた高速な当たり判定を紹介します。
サンプルの画像

当たり判定の悩み

Processingなどを使ってゲームを作る時、避けて通れないのが当たり判定。

当たり判定のうち、まだ円と円のような簡単な判定であれば苦戦はしないものの、円と線分や円と矩形のような複雑な判定式が必要な当たり判定を実装するとなると、なかなか実装やデバッグが難しくなります。

しかも、大量の当たり判定を捌く必要があるゲームでは条件分岐などによるボトルネックができてしまいます。

そこで今回紹介するのが、距離関数による当たり判定です。

距離関数による当たり判定

今回実装するのは円と矩形(又はOBB)の当たり判定ですが、実は先ほどの内容の中にもう一つ、一般的には距離関数によって当たり判定が実装されているものが存在します。

それは、円と円の当たり判定です。

距離関数を理解するうえで円と円は最も簡単な例なので、実装を見てみましょう。

boolean circleCollision(float distance,float r1,float r2){
  return distance<=r1+r2;
}

この実装におけるdistanceは円と円の中心の距離、r1、r2はそれぞれの半径を表します。

つまりは、「2つの円の距離が2つの円の半径の合計より小さい場合、当たっている」ということです。

こうして見ると、非常に簡単ですね。

ここで、少し数学の知識を思い出しましょう。
不等式では等式と同じように移項することができます。
これを先ほどのコードで行ってみると、

boolean circleCollision(float distance,float r1,float r2){
  return distance-(r1+r2)<=0;
}

となります。

ここで、circleCollision()という関数はただの当たり判定であるだけでなく、円同士が当たっているときはdistance-(r1+r2)が0以下になるという性質を兼ね備えています。

このことから、「任意の図形に対応した距離関数に対して、内部の点に対する距離が負となるように調整すれば、当たり判定を距離関数によって記述できる」
と考えられます。

なので、多角形やアステロイド、さらにはフラクタルのような複雑な図形でも距離関数が存在すれば、内部の点に対する距離が負となるよう調整することで当たり判定に利用することができると考えられます。

実装(円と矩形)

今回は、円と矩形の当たり判定を距離関数で実装します。

当たり判定を実装するにあたって、こちらのサイトを参考にしました。

Processingで実装するとこうなります。

float length(float x,float y){
  return sqrt(x*x+y*y);
}

boolean roundRectDistFunc(PVector p,float x,float y, float radius) {
  float dx=abs(p.x)-x;
  float dy=abs(p.y)-y;
  return min(max(dx, dy), 0.0) + length(max(dx,0.0),max(dy,0.0))- radius<=0;
}

冒頭の画像のサンプルコードも載せておきますが、結構長いので折りたたんでおきます。

Processingで実際に動かせるサンプルコード
Circle circle;
Rectangle rectangle;

float distance;
float overlap;

void setup(){
  size(1280,720);
  circle=new Circle(new PVector(0,0),20);
  rectangle=new Rectangle(new PVector(width*0.5,height*0.5),new PVector(100,200));
  rectMode(CENTER);
  noStroke();
}

void draw(){
  background(0);
  circle.position.set(mouseX,mouseY);
  circle.collision(rectangle);
  circle.display();
  rectangle.display();
}

float length(float x,float y){
  return sqrt(x*x+y*y);
}

boolean roundRectDistFunc(PVector p,float x,float y, float radius) {
  float dx=abs(p.x)-x;
  float dy=abs(p.y)-y;
  return min(max(dx, dy), 0.0) + length(max(dx,0.0),max(dy,0.0))- radius<=0;
}

class Circle{
  PVector position;
  float radius;
  
  boolean hit=false;
  
  Circle(PVector position,float radius){
    this.position=position;
    this.radius=radius;
  }
  
  void display(){
    if(hit)fill(255,0,0,128);
      else fill(0,255,0,128);
    circle(position.x,position.y,radius*2);
  }
  
  void collision(Rectangle r){
    PVector dist=position.copy().sub(r.position);
    hit=roundRectDistFunc(dist,r.size.x*0.5,r.size.y*0.5,radius);
  }
}

class Rectangle{
  PVector position;
  PVector size;
  
  Rectangle(PVector position,PVector size){
    this.position=position;
    this.size=size;
  }
  
  void display(){
    fill(0,128,255,128);
    rect(position.x,position.y,size.x,size.y);
  }
}

判定自体は分岐や内積/外積を使うわけではないので簡単ですね。

使い方

roundRectDistFunc([円の、長方形を原点とした相対位置],[長方形の半分の幅],[長方形の半分の高さ],[円の半径]);

ちなみに、長方形の幅か高さのどちらかを0にすると線分と円の当たり判定ができます。
あと、回転した長方形と円の判定は、相対座標を回転させたら出来ます。

なぜ判定ができるのか

この説明をするためにはまず、今回の判定の形状を分解する必要があります。
分解するとこの画像のようになります。
判定の形
どこかでこんな配色を見たような...

まあそれはそれとして、今回の判定は大まかに

  1. 中心の青い長方形の部分
  2. 長方形の外部から一定の幅を埋める赤い部分

の2つに分けられます。

そして、今回の判定で最も重要なのが1番目の青い長方形の部分です。

長方形の部分の判定のみを取り出した関数を見てみましょう。(length()の定義は除いています)

boolean roundRectDistFunc(PVector p,float x,float y) {
  //[1]
  float dx=abs(p.x)-x;
  float dy=abs(p.y)-y;
  //[2]
  return min(max(dx, dy), 0.0) 
  //[3]
  + length(max(dx,0.0),max(dy,0.0))<=0;
}

元のコードからradius、つまり半径を除いただけです。
ここでの処理を順を追って見てみましょう。

  1. pとの距離を求める。abs()が付いているのは中心で判定を折り返すため。
    このときとある座標軸に対して交差している場合、その座標軸での距離は負の値になる。
  2. pとの距離が全ての軸で負の場合、最も表面に近い距離を返す。
    それ以外の場合は0を返す。
  3. 長方形の表面との最短距離を返す。
    これにより表面との距離が0以外の場合を除外する。

これで今回のコードの解説はほぼ終わりです。
引数に半分の大きさを代入するのは、absによる折り返しの影響だったんですね。

最後に赤い部分の判定を解説すると、

  1. 長方形からradiusの分だけ判定を膨らませる

以上、解説は終わりです。

さいごに

今回は距離関数を用いた当たり判定の一例として長方形と円を取り上げましたが、やろうと思えば線分と線分の判定やカプセル同士の判定、さらには長方形同士の判定もできるのではないかと思います。
なので、皆さんも「こんな判定があったよ」というものがあればぜひ記事を書くなりしてこの界隈を盛り上げてください。

Discussion