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

この前、ふと「距離関数で当たり判定できるのでは?」と思い付いて実装してみました。今回は、距離関数を使った高速な当たり判定を、円と長方形の判定を例に紹介します。

サンプルの画面。マウスに付いてくる円が、中央の長方形に触れていないときは輪郭だけ、触れているときは塗りつぶされる

当たり判定の悩み

Processing などでゲームを作ると、たいてい当たり判定を実装することになります。ところが、円と長方形や、円と線分の判定は、いざ書こうとすると案外複雑な式になって、嫌な気持ちになることが多いのではないでしょうか。

そのうえ、負荷を減らすために長方形と線分で処理を分けたりして、プログラムが複雑になることもあります。

今回紹介する判定なら、これらを高速にできるうえ、形が違っても同じ書き方で済むように一般化できます。

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

実装と解説に入る前に、まず単純な例で、距離関数による当たり判定の原理を説明します。

円と円の当たり判定は、多くの人が最初に実装する判定だと思います。実は、この円と円の判定こそが、距離関数を使った判定になっています。実装は以下の通りです。

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

ここで distance は 2 つの円の中心間の距離、r1 と r2 はそれぞれの半径です。

円と円の当たり判定で行われていることは、次の 4 つです。

一方の円の中心を原点とする
2 つの円の中心間の距離を求める
2 つの半径を足す
中心間の距離が半径の和以下なら、接触していると判定する

このうち押さえておきたいのは、1 の一方の中心を原点とすることと、3 の半径を足すことです。

1 のように、どちらかの図形の中心を原点に置くと、図形自体の対称性 (線対称など) を使って、計算を効率よく進められます。

3 の処理は、「一方の円を点になるまで縮め、縮めた分だけもう一方の円を膨らませる」と読み替えられます。縮める円の半径が r1、膨らませる円の半径が r2 なら、膨らんだ円の半径は r1 + r2 です。つまり円と円の判定は、「点」と「半径が r1 + r2 の円」の判定に置き換わります。

円と円の判定の読み替え。左は半径 r1 と r2 の円が接している図で、中心間の距離 d は r1 + r2 に等しい。右は一方の円を点に縮め、もう一方を r1 だけ膨らませた図で、点が膨らんだ円の縁に乗っている

この読み替えは、丸角長方形のような複雑な形を使った判定で活躍します。

実装 (円と長方形)

大体の原理や考え方は説明し終えたので、本題に移りましょう。

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

2次元ディスタンスフィールドまとめ - Qiitaはじめに iq先生の2Dディスタンスフィールド(SDF)解説を見ましょう。3Dの方は有名なのですが、こっち見逃してました。。。もっと早く知りたかったディスタンスフィールド(距離関数)とは相手との距離を返す関数です。 glslのフラグメントシェーダーでシェイプを描く...

Qiita

まずは実装です。

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

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

ここで、halfWidth と halfHeight は長方形の幅と高さの半分、p は長方形の中心を原点としたときの円の中心の位置、radius は円の半径です。

長方形が回転しているときは、p を求めたあとで、長方形の回転と逆向きに p を回してから渡せば、同じ式で判定できます。

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

Processing で動くサンプルコード

CircleRect.pdejava

Ball ball;
Box box;

void setup() {
  size(1280, 720);
  rectMode(CENTER);
  textSize(24);
  ball = new Ball(new PVector(), 20);
  box = new Box(new PVector(width * 0.5, height * 0.5), new PVector(100, 200));
}

void draw() {
  background(16);
  ball.position.set(mouseX, mouseY);
  boolean hit = ball.hits(box);

  box.display();
  ball.display(hit);

  // 色が見分けにくくても分かるように、文字でも結果を出す
  fill(255);
  textAlign(LEFT, TOP);
  text(hit ? "HIT" : "MISS", 16, 16);
}

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

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

class Ball {
  PVector position;
  float radius;

  Ball(PVector position, float radius) {
    this.position = position;
    this.radius = radius;
  }

  // 長方形に触れているか。長方形の中心から見た位置を求めて判定に渡す
  boolean hits(Box box) {
    PVector relative = PVector.sub(position, box.position);
    return roundRectDistFunc(box.size.x * 0.5, box.size.y * 0.5, relative, radius);
  }

  // 触れていれば塗りつぶし、触れていなければ輪郭だけ
  void display(boolean hit) {
    if (hit) {
      noStroke();
      fill(255, 176, 0);
    } else {
      noFill();
      stroke(255);
      strokeWeight(3);
    }
    ellipse(position.x, position.y, radius * 2, radius * 2);
  }
}

class Box {
  PVector position;
  PVector size;

  Box(PVector position, PVector size) {
    this.position = position;
    this.size = size;
  }

  void display() {
    noStroke();
    fill(70, 130, 220);
    rect(position.x, position.y, size.x, size.y);
  }
}

判定そのものは、条件分岐も内積・外積も使わず、abs と max と length だけで書けるので、簡単だと思います。

なぜ判定ができるのか

roundRectDistFunc の中身を、上から順に見ていきます。

1. 絶対値で空間を折りたたむ

長方形は、x 軸に対しても y 軸に対しても線対称な図形です。この性質を使うために、円の位置に絶対値を取っています。

この処理は「空間を折りたたむ」操作にあたります。x 軸と y 軸で 1 回ずつ折ると、線対称な 4 つの位置が 1 か所に重なります。折り紙を 2 回折ると 4 枚が重なるのと同じです。

空間を折りたたむ図。左は長方形の中心を原点とした平面で、(x, y) (−x, y) (x, −y) (−x, −y) の 4 点が軸に対して対称に並んでいる。右は絶対値を取ったあとの平面で、4 点が x ≥ 0, y ≥ 0 の領域の 1 点 (|x|, |y|) に重なる

こうしておけば、円が長方形の上下左右どこにあっても、考えるのは x ≥ 0, y ≥ 0 の領域 (第一象限) だけで済みます。分岐を減らせるのはこのためです。この領域に残る長方形は、中心から角までの 4 分の 1 なので、必要なのは幅と高さの半分だったわけです。

2. 長方形の角を原点にする

次に halfWidth と halfHeight を引いています。これは、長方形の角が原点になるように円を動かす操作です。

引いた結果の dx と dy は、長方形の右辺と上辺から、円の中心がどれだけ離れているかを表します。正なら辺の外側、負なら辺の内側です。

3. 距離を求めて、半径を引く

最後の 1 行は難しそうに見えますが、実は、最初の円と円の判定と同じことをしています。

まず length(...) の中で、dx と dy が負のときは 0 に置き換えています (max(dx, 0.0))。dx が負というのは、円の中心が長方形の幅の範囲に収まっているということで、x 方向には長方形から離れていないからです。dy も同じです。こうして残った値だけを length に渡すと、点と点の距離の式だけで、円の中心から長方形の表面までの距離が求まります。

円の中心 p から長方形までの距離。長方形の真上にあるときは dx が負なので距離は dy、真横にあるときは dy が負なので距離は dx、斜め外にあるときは角までの距離 length(dx, dy)。長方形を半径 r だけ膨らませた輪郭は角が丸くなり、p はその弧の上にある

最後に radius を引いて、0 以下かどうかを見れば判定は完了です。これは、長方形を radius だけ膨らませた丸角長方形の中に、円の中心が入っているかどうかを調べていることになります。最初の円と円の判定で、「一方を点にして、もう一方を膨らませた」のとまったく同じ要領です。

さいごに

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

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

この記事は、Zenn に書いたものを、このサイト向けに表現と図を直して移したものです。元の記事は Zenn にあります。