【ゲーム数学】第四回 p5.jsで学ぶゲーム数学「円と線分の衝突判定」

JavaScript
マイケル
マイケル
みなさんこんにちは!
マイケルです!
エレキベア
エレキベア
クマ〜〜〜〜〜〜
マイケル
マイケル
今日も引き続き、ゲーム数学を進めていくよ!
今回は「円と線分の衝突判定」についてだ!
エレキベア
エレキベア
衝突判定クマ?
マイケル
マイケル
ゲームでは物体同士が衝突しているかどうかの判定処理を頻繁に行うことが多いんだ!
ゲームエンジンには、大体コライダとして標準搭載されているね!
マイケル
マイケル
今回は第三回までの間で学んできた、三角関数やベクトルの知識を使って、
円と線分、直線の衝突判定を行っていきます!
エレキベア
エレキベア
難しそうだけどやってみるクマ〜〜〜〜
スポンサーリンク

参考書籍と開発言語

マイケル
マイケル
勉強にするにあたっては前回同様、下記参考書を参考にしました!

ゲームを動かす数学・物理 R

グラフィックスプログラミング入門

マイケル
マイケル
どちらも高校数学の基礎から解説しているため、しばらく数学から離れている方でも読みやすいと思います!
エレキベア
エレキベア
一読してみるクマ
マイケル
マイケル
そしてサンプルプログラムの実装としては p5.js を使用しています!
気になった方はこちらも使用してみてくださいね!
Screenshot 2021 01 16 23 15 46

p5.js ダウンロードページ

エレキベア
エレキベア
グラフィックス特化のJavaScriptライブラリクマね

円と線分の衝突判定

マイケル
マイケル
それじゃ早速やっていこう!

考え方

マイケル
マイケル
まず、円と線分をそれぞれ 円P 線分AB として、下記のような図で考えます!
Screenshot 2021 03 13 19 49 53
エレキベア
エレキベア
見た感じ 線分PXが円と線分の最短の距離 っぽいクマね
マイケル
マイケル
その通り!
線分PXを求めて、円Pの半径より短いかどうかを判定 すれば衝突しているかどうか分かりそうだね!
マイケル
マイケル
そして線分PXは、下記のように
「線分ABと線分APのベクトルの外積」を線分ABの長さで除算
すれば求められます!
Screenshot 2021 03 13 19 50 16
エレキベア
エレキベア
なるほどクマ・・・
あえてAPの長さを残すことでPXの長さを求めるクマね

最短距離を考える

マイケル
マイケル
基本的には線分PXの長さを最短距離として考えて問題ないですが、
下記のような場合には最短距離を再設定する必要があります!


① 線分AXの長さが負の値(線分ABのベクトルと逆方向)の場合
 →線分APを最短距離として設定

Screenshot 2021 03 13 19 50 09


① 線分AXの長さが線分ABの長さより大きい(線分ABよりも先にある)場合
 →線分BPを最短距離として設定

Screenshot 2021 03 13 19 52 46
エレキベア
エレキベア
線分の場合は長さに制限があるから考慮する必要があるクマね
マイケル
マイケル
その通り!
そして線分AXの長さに関しては、先ほどと同じ考え方で、
「線分ABと線分APのベクトルの内積」を線分ABの長さで除算
することで求めることができるよ!
Screenshot 2021 03 13 19 50 22
エレキベア
エレキベア
これで判定に必要な値が揃ったクマね

実装

マイケル
マイケル
これまでの内容を実装したものが下記になります!
/**
 * 円と線分の衝突判定処理
 * (引数を円P、線分ABとして計算する)
 * @param {Circle} circleP 円P
 * @param {Line} lineAB 線分AB
 * @returns true:衝突している false:衝突していない
 */
function circleColLine(circleP, lineAB) {
  // ① 線分APのベクトルを求める
  let vecAP = lineAB.start_p.getVecPoint(circleP.p);
  let vecBP = lineAB.end_p.getVecPoint(circleP.p);

  // ② 線分ABと線分APの内積・外積を線分ABの長さで除算することで
  // 線分AX、PXの長さを求める
  let dotAX = lineAB.v.dotVec(vecAP) / lineAB.v.getLength();
  let crossPX = lineAB.v.crossVec(vecAP) / lineAB.v.getLength();
  
  // ③ 最短距離を設定
  // 基本は線分PXの長さを設定
  let distance = Math.abs(crossPX);
  if (dotAX < 0) {
    // 例外1:線分AXと逆方向に最短座標がある場合 -> 線分APの長さを設定
    distance = vecAP.getLength();
  } else if (dotAX > lineAB.v.getLength()) {
    // 例外2:線分ABよりも先に最短座標がある場合 -> 線分BPの長さを設定
    distance = vecBP.getLength();
  }
  // ④ 最短距離が円の半径より小さければ衝突と判定
  return distance < circleP.r;
}
↑円と線分の衝突判定処理
エレキベア
エレキベア
さっきの図を思い出せば意味も分かるクマね
マイケル
マイケル
参考として、クラスやベクトルの処理等は下記のように実装しています!
// 座標クラス
class Point {
  constructor (_x, _y) {
    this.x = _x;
    this.y = _y;
  }

  // 引数の位置へ向かうベクトルを求める
  getVecPoint(p) {
    return new Vec(p.x - this.x, p.y - this.y);
  }
}

// ベクトルクラス
class Vec {
  constructor (_x, _y) {
    this.x = _x;
    this.y = _y;
  }

  // ベクトル同士の内積を求める
  dotVec(v) {
    return this.x * v.x + this.y * v.y;
  }

  // ベクトル同士の外積を求める
  crossVec(v) {
    return this.x * v.y - this.y * v.x;
  }

  // ベクトルの長さを求める
  getLength() {
    return Math.sqrt(this.x*this.x + this.y*this.y);
  }
}

// 線分クラス
class Line {
  constructor (_start_p, _end_p) {
    this.start_p = _start_p;
    this.end_p = _end_p;
    // ベクトルを設定
    this.v = new Vec(
      this.end_p.x - this.start_p.x,
      this.end_p.y - this.start_p.y
    );
  }
}

// 円クラス
class Circle {
  constructor (_p, _r) {
    this.p = _p;
    this.r = _r;
  }
}
↑位置やベクトル等のクラス
マイケル
マイケル
上記ソースコードよりシミュレータを作ってみたので、
是非触って挙動を確かめてみてください!

See the Pen
0313_01_COLISON
by masarito617 (@masarito617)
on CodePen.

↑円と線分の衝突判定(※ドラッグで線分の長さを変更可)

マイケル
マイケル
下記のように、衝突判定を行えていることがわかります!
Screenshot 2021 03 13 21 31 35
Screenshot 2021 03 13 21 31 44
エレキベア
エレキベア
やったクマ〜〜〜〜〜〜!!

円と直線の衝突判定

マイケル
マイケル
そしておまけになりますが、円と直線の衝突判定処理 についても紹介します!

考え方

マイケル
マイケル
考え方は基本的に円と線分の衝突判定と同じですが、
直線のため終点がありません。
マイケル
マイケル
そのため下記のように、直線の任意の位置と方向ベクトルで衝突判定を行うことになります!
Screenshot 2021 03 13 22 30 06
エレキベア
エレキベア
これも線分PXが円と線分の最短の距離 っぽいクマね
マイケル
マイケル
その通り!
そして線分PXは下記のように
直線Aの正規化されたベクトルと線分APのベクトルの外積
から求めることができます!
Screenshot 2021 03 13 22 30 10
エレキベア
エレキベア
さっきよりもだいぶシンプルクマね

実装

マイケル
マイケル
そして実装したコードは下記になります!
/**
 * 円と直線の衝突判定処理
 * (引数を円P、直線Aとして計算する)
 * @param {Circle} circleP 円P
 * @param {StraightLine} lineA 直線A
 * @returns true:衝突している false:衝突していない
 */
 function circleColStraightLine(circleP, lineA) {
  // ① 線分APのベクトルを求める
  let vecAP = lineA.start_p.getVecPoint(circleP.p);

  // ② 直線Aの正規化ベクトルを求める
  let vecALength = lineA.v.getLength();
  // ベクトルの長さが0の場合、線分APの長さで衝突判定
  if (vecALength == 0) {
    return vecAP.getLength() < circleP.r;
  }
  let nomVecA = new Vec(lineA.v.x / vecALength, lineA.v.y / vecALength);

  // ③ 正規化ベクトルA*線分APの外積で、PXの長さを求める
  let crossPX = nomVecA.crossVec(vecAP);
  
  // ④ 最短距離が円の半径より小さければ衝突と判定
  return Math.abs(crossPX) < circleP.r;
}
↑円と直線の衝突判定
// 直線クラス
 class StraightLine {
  constructor (_start_p, _v) {
    this.start_p = _start_p;
    this.v = _v;
  }
}
↑直線クラス

マイケル
マイケル
こちらもシミュレータを作ったので触ってみてください!

See the Pen
0313_02_COLISION
by masarito617 (@masarito617)
on CodePen.

↑円と直線の衝突判定(※ドラッグで直線の方向を変更可)

マイケル
マイケル
下記のように衝突判定が行えていることが分かります!
Screenshot 2021 03 13 22 07 51
Screenshot 2021 03 13 22 08 01
エレキベア
エレキベア
線分との衝突よりもシンプルにできたクマね

おわりに

マイケル
マイケル
というわけで今回は「円と線分(直線)の衝突判定」についてでした!
どうだったかな?
エレキベア
エレキベア
式だけ見るとややこしいクマが、図を描いてみると理解できたクマ〜〜〜
マイケル
マイケル
衝突判定は少しややこしいものが多いけど、
引き出しにもなるので少しずつ覚えていこうと思う!
エレキベア
エレキベア
クマもがんばるかもしれないクマ〜〜〜
マイケル
マイケル
それでは今日はこの辺で!
アデュー!!!
エレキベア
エレキベア
クマ〜〜〜〜〜〜〜〜

【ゲーム数学】第四回 p5.jsで学ぶゲーム数学「円と線分の衝突判定」 〜完〜

コメント