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

2024/01/05に公開
この前、ふと「距離関数で当たり判定できるのでは?」と思い付き実装してみたので、今回は距離関数を用いた高速な当たり判定を、円と矩形の判定を例に挙げて紹介します。


 当たり判定の悩みProcessingなどを使ってゲームを作る時はたいてい当たり判定を実装することになると思うのですが、円と矩形や円と線分の当たり判定をいざ実装しようとすると案外複雑な計算式を実装することになり、嫌な気持ちになることが多いのではないでしょうか。

そのうえ、負荷を減らすために矩形と線分で分岐処理を行い、プログラムが複雑になってしまうこともあると思います。
今回紹介する判定では、これらの判定を高速化するとともに一般化して実装することができます。

 距離関数による当たり判定実装とその解説に移る前に、まずは単純な例で距離関数による当たり判定の原理を説明します。
多くの人は人生で最初に円と円の当たり判定を実装すると思うのですが、実はこの円と円の判定こそが距離関数を用いた判定になっています。

実装は以下の通りです。
boolean circleCollision(float distance, float r1, float r2) {
  return distance <= r1 + r2;
}
ここでdistanceは円と円の中心の距離、r1、r2はそれぞれの半径を表します。
円と円の当たり判定において行われていることは以下の通りです。
一方の円の中心を原点とする
円と円の距離を求める
円と円の半径を足す
半径の和より円と円の距離が近ければ接触していると判定する
この一連の処理において特筆すべき点は、1番で一方の中心を原点としている点と3番の円と円の半径を足すという点です。

まず1番のように適当に適当な図形の中心を原点に設定することで、図形自体の対称性(線対称など)を利用して効率的な計算を行うことができます。

次に3番の処理についてですが、この処理は「一方の円の半径を縮め、もう一方の円の半径を同じだけ膨らませる」と解釈することができます。このような処理は、各丸長方形などの複雑な形状を用いた判定を行う際に活躍します。

 実装(円と矩形)大体の原理や考え方は説明し終えたので、本題に移りましょう。
当たり判定を実装するにあたって、こちらのサイトを参考にしました。
まずは実装を紹介します。
float length(float x, float y) {
  return sqrt(x * x + y * y);
}

boolean roundRectDistFunc(float width, float height, PVector p, float radius) {
  float dx = abs(p.x) - width;
  float dy = abs(p.y) - height;
  return length(max(dx, 0.0), max(dy, 0.0)) - radius <= 0;
}
ここで、widthとheightはそれぞれ長方形の幅と高さの半分で、pは長方形の中心を原点としたときの円の相対位置、radiusは円の半径です。
もし回転した長方形を扱いたいのであれば、相対位置を求めた後に円の中心の相対位置とともに回転を戻せば判定することができます。
冒頭の画像のサンプルコードも載せておきますが、結構長いので折りたたんでおきます。
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 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);
  }
}
判定自体は分岐や内積/外積を使うわけではないので簡単だと思います。

 なぜ判定ができるのか長方形と円の判定では、長方形がx軸とy軸に関して線対称な図形であることを活用します。

まず、円の相対位置に対して絶対値をとっている処理を不思議に思うかもしれませんが、この処理では「空間を折りたたむ」という操作を行っています。

なぜこのような操作が可能かというと、x軸とy軸に関して絶対値をとることにより、線対称な4つの点を同一視できるからです。より分かりやすく例えるならば、絶対値をとる操作が折り紙を折る操作に対応していて、2回折り紙を折ると4つの部分が1つの部分に重なるということを表しています。

なぜこのような操作を行うかというと、距離関数による評価を第一象限のみで完結させ、分岐処理を削減するためです。だから幅と高さの半分が必要だったんですね。
次にwidthとheightを引いている部分では、長方形の頂点を原点として扱うために円を移動させています。
最後の処理は一見難しそうに見えるものの、実は最初の円と円の当たり判定と同じことをしています。

まずlength(...)の部分では負の相対座標を0と同一視することで、なんと点と点の距離の式だけで長方形の表面から点までの距離を求めています。最後にradiusを引くことで、最初の円と円の判定と同じ要領で交差判定を完了させます。

 さいごに今回は距離関数を用いた当たり判定の一例として長方形と円を取り上げましたが、やろうと思えば線分と線分の判定やカプセル同士の判定、さらには長方形同士の判定もできるのではないかと思います。

なので、皆さんも「こんな判定があったよ」というものがあればぜひ記事を書くなりしてこの界隈を盛り上げてください。
当たり判定の悩み

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

実装(円と矩形)

なぜ判定ができるのか

さいごに

Discussion
