当たり判定に関する考察単純な総当たりと二分探索法による高速化

これまでにゲームを作ってきましたが、オブジェクトの数が増えると当たり判定に時間がかかるのでオブジェクトの数をあまり大きくすることはありませんでした。しかし二分探索法を使えば高速化は可能です。思った以上の差となりました。

Contents

1 HTML部分
2 グローバル変数と定数
3 Bulletクラスの定義
4 ページが読み込まれたときの処理
5 更新処理
- 5.1 弾丸の生成
- 5.2 描画処理
6 当たり判定
- 6.1 愚直な総当たり法
- 6.2 二分探索法を用いた高速化

HTML部分

まずHTML部分を示します。

<!DOCTYPE html>
<html lang="ja">
<head>
<meta charset="UTF-8">
<title>当たり判定</title>
<meta name = "viewport" content = "width=device-width, initial-scale = 1.0">
<link rel="stylesheet" href="./style.css">
</head>

<body>

<div id = "container">
    <fieldset>
        <legend>当たり判定 する/しない</legend>
        <div>
          <input type="radio" id="none" name="hit-check" value="none" checked />
          <label for="none">しない</label>
        </div>
        <div>
          <input type="radio" id="naive" name="hit-check" value="naive" />
          <label for="naive">単純な総当たり</label>
        </div>
        <div>
          <input type="radio" id="bs" name="hit-check" value="bs" />
          <label for="bs">二分探索法</label>
        </div>
    </fieldset>
    <div id = "bullets-count"></div>
    <div id = "canvas-outer"></div>
</div>

<script src="./app.js"></script>

</body>
</html>

<!DOCTYPE html>

<head>

<title>当たり判定</title>

</head>

<body>

<legend>当たり判定する/しない</legend>

<div>

</div>

<div>

<label for="naive">単純な総当たり</label>

</div>

<div>

<label for="bs">二分探索法</label>

</div>

</fieldset>

</div>

</body>

</html>

style.css

body {
    background-color: black;
    color: white;
}
#container {
    width: 360px;
}

body {

background-color: black;

color: white;

}

#container {

width: 360px;

}

グローバル変数と定数

グローバル変数と定数を示します。

// canvasのサイズ
const CANVAS_WIDTH = 360;
const CANVAS_HEIGHT = 480;

// canvasの生成と追加
const $canvas = document.createElement('canvas');
const ctx = $canvas.getContext('2d');
document.getElementById('canvas-outer').appendChild($canvas);

// DOM要素

// 弾丸の総数を表示する
const $bulletsCount = document.getElementById('bullets-count');

// ラジオボタン（当たり判定のアルゴリズムを切り替える）
const $none = document.getElementById('none'); // しない
const $naive = document.getElementById('naive'); // 普通の総当たり法
const $bs = document.getElementById('bs'); // 二分探索法による高速化

let bullets = []; // 弾丸オブジェクトを格納する変数
const bulletRadius = 4; // 弾丸の半径

// canvasのサイズ

const CANVAS_WIDTH = 360;

const CANVAS_HEIGHT = 480;

// canvasの生成と追加

const $canvas = document.createElement('canvas');

const ctx = $canvas.getContext('2d');

document.getElementById('canvas-outer').appendChild($canvas);

// DOM要素

// 弾丸の総数を表示する

const $bulletsCount = document.getElementById('bullets-count');

// ラジオボタン（当たり判定のアルゴリズムを切り替える）

const $none = document.getElementById('none'); // しない

const $naive = document.getElementById('naive'); // 普通の総当たり法

const $bs = document.getElementById('bs'); // 二分探索法による高速化

let bullets = []; // 弾丸オブジェクトを格納する変数

const bulletRadius = 4; // 弾丸の半径

Bulletクラスの定義

弾丸を操作できるようにするためにBulletクラスを定義します。コンストラクタの引数は弾丸のIDと初期座標、移動速度です。当たり判定は異なるIDの弾丸同士のときだけおこないます。

class Bullet {
    constructor(id, x, y, vx, vy){
        this.ID = id;
        this.X = x; // 弾丸の座標
        this.Y = y;
        this.VX = vx; // 弾丸の移動速度
        this.VY = vy;
        this.Hitting = false; // 弾丸は他の弾丸の接触している
        this.IsDead = false; // 弾丸はcanvasの外に出ていった
    }
    Draw() {
        ctx.beginPath();
        ctx.arc(this.X, this.Y, bulletRadius, 0, Math.PI * 2);
        if(!this.Hitting)
            ctx.strokeStyle = '#0ff';
        else
            ctx.strokeStyle = '#f00'; // 弾丸は他の弾丸の接触しているときは色を変える
        ctx.stroke();
    }
    Move(){
        this.X += this.VX;
        this.Y += this.VY;
        if(this.X < -10 || this.X > CANVAS_WIDTH + 10 || this.Y < -10 || this.Y > CANVAS_HEIGHT + 10)
            this.IsDead = true; // 移動処理後の弾丸の座標がcanvasの外であれば死亡フラグをセット
    }
}

class Bullet {

constructor(id, x, y, vx, vy){

this.ID = id;

this.X = x; // 弾丸の座標

this.Y = y;

this.VX = vx; // 弾丸の移動速度

this.VY = vy;

this.Hitting = false; // 弾丸は他の弾丸の接触している

this.IsDead = false; // 弾丸はcanvasの外に出ていった

}

Draw() {

ctx.beginPath();

ctx.arc(this.X, this.Y, bulletRadius, 0, Math.PI * 2);

if(!this.Hitting)

ctx.strokeStyle = '#0ff';

else

ctx.strokeStyle = '#f00'; // 弾丸は他の弾丸の接触しているときは色を変える

ctx.stroke();

}

Move(){

this.X += this.VX;

this.Y += this.VY;

if(this.X < -10 || this.X > CANVAS_WIDTH + 10 || this.Y < -10 || this.Y > CANVAS_HEIGHT + 10)

this.IsDead = true; // 移動処理後の弾丸の座標がcanvasの外であれば死亡フラグをセット

}

ページが読み込まれたときの処理

window.onload = () => {
    $canvas.width = CANVAS_WIDTH;
    $canvas.height = CANVAS_HEIGHT;

    // モニターのリフレッシュレートによらず1秒間60更新とする
    const INTERVAL = 1000 / 60;
    let nextUpdateTime = new Date().getTime() + INTERVAL;
    frameProc();

    function frameProc(){
        const curTime = new Date().getTime();
        if(nextUpdateTime < curTime){
            nextUpdateTime +=  INTERVAL;
            update();
        }
        requestAnimationFrame(() => frameProc());
    }
};

window.onload = () => {

$canvas.width = CANVAS_WIDTH;

$canvas.height = CANVAS_HEIGHT;

// モニターのリフレッシュレートによらず1秒間60更新とする

const INTERVAL = 1000 / 60;

let nextUpdateTime = new Date().getTime() + INTERVAL;

frameProc();

function frameProc(){

const curTime = new Date().getTime();

if(nextUpdateTime < curTime){

nextUpdateTime += INTERVAL;

update();

}

requestAnimationFrame(() => frameProc());

}

};

更新処理

弾丸を移動させ、当たり判定をしたあと描画処理をおこないます。また更新回数が24の倍数であれば新しい弾丸を生成して全方向に飛ばします。

let updateCount = 0; // 更新回数

function update(){
    updateCount++;

    if(updateCount % 24 == 0)
        createBullets();
    bullets.forEach(_ => _.Move());
    bullets = bullets.filter(_ => !_.IsDead);

    bullets.forEach(_ => _.Hitting = false);
    if($naive.checked) // 当たり判定（ここが本日の肝）
        judge1();
    else if($bs.checked)
        judge2();

    draw();
}

let updateCount = 0; // 更新回数

function update(){

updateCount++;

if(updateCount % 24 == 0)

createBullets();

bullets.forEach(_ => _.Move());

bullets = bullets.filter(_ => !_.IsDead);

bullets.forEach(_ => _.Hitting = false);

if($naive.checked) // 当たり判定（ここが本日の肝）

judge1();

else if($bs.checked)

judge2();

draw();

}

弾丸の生成

弾丸を生成する処理を示します。10方向に初速を与えて放射状に飛ぶようにしています。

function createBullets(){
    const speed = 1;
    const xs = [0.2, 0.2, 0.2, 0.4,  0.4,  0.6, 0.6, 0.6, 0.8, 0.8, ];
    const ys = [0.1, 0.5, 0.9, 0.35, 0.65, 0.1, 0.5, 0.9, 0.35, 0.65, ];

    for(let i = 0; i < xs.length; i++)
        createBullets0(i, CANVAS_WIDTH * xs[i], CANVAS_HEIGHT * ys[i]);

    function createBullets0(id, x, y){
        for(let i = 0; i < 32; i++){
            let angle = Math.PI / 16 * i;
            bullets.push(new Bullet(id, x, y, speed * Math.cos(angle), speed * Math.sin(angle)));
        }
    }
}

function createBullets(){

const speed = 1;

const xs = [0.2, 0.2, 0.2, 0.4, 0.4, 0.6, 0.6, 0.6, 0.8, 0.8, ];

const ys = [0.1, 0.5, 0.9, 0.35, 0.65, 0.1, 0.5, 0.9, 0.35, 0.65, ];

for(let i = 0; i < xs.length; i++)

createBullets0(i, CANVAS_WIDTH * xs[i], CANVAS_HEIGHT * ys[i]);

function createBullets0(id, x, y){

for(let i = 0; i < 32; i++){

let angle = Math.PI / 16 * i;

bullets.push(new Bullet(id, x, y, speed * Math.cos(angle), speed * Math.sin(angle)));

}

描画処理

描画処理を示します。canvas全体を黒で塗りつぶし弾丸を描画します。また弾丸の総数を表示させます。

function draw(){
    ctx.fillStyle = '#000';
    ctx.fillRect(0, 0, CANVAS_WIDTH, CANVAS_HEIGHT);

    bullets.forEach(_ => _.Draw());

    $bulletsCount.innerHTML = `弾丸数：${bullets.length}`
}

function draw(){

ctx.fillStyle = '#000';

ctx.fillRect(0, 0, CANVAS_WIDTH, CANVAS_HEIGHT);

bullets.forEach(_ => _.Draw());

$bulletsCount.innerHTML = `弾丸数：${bullets.length}`

}

当たり判定

本日のメインコンテンツの当たり判定です。

愚直な総当たり法

最初に愚直なやり方を示します。これは a < b < bullets.length を満たすすべての a と b について総当たりをしています。弾丸数が1000個だと499,500回、2000個だと1,999,000回の比較が必要です。当たり判定のありなしを切り替えると極端に動作速度が落ちることに気が付きます。

function judge1(){
    for(let a = 0; a < bullets.length; a++){
        for(let b = a + 1; b < bullets.length; b++){
            const bulletA = bullets[a];
            const bulletB = bullets[b];
            if(bulletA.ID == bulletB.ID)
                continue;
            hitCheck(bulletA, bulletB);
        }
    }
}

// 弾丸AとBが接触しているならHittingフラグをtrueにする
function hitCheck(bulletA, bulletB){
    const d2 = Math.pow(bulletA.X - bulletB.X, 2) + Math.pow(bulletA.Y - bulletB.Y, 2);
    if(Math.sqrt(d2) < bulletRadius * 2){
        bulletA.Hitting = true;
        bulletB.Hitting = true;
    }
}

function judge1(){

for(let a = 0; a < bullets.length; a++){

for(let b = a + 1; b < bullets.length; b++){

const bulletA = bullets[a];

const bulletB = bullets[b];

if(bulletA.ID == bulletB.ID)

continue;

hitCheck(bulletA, bulletB);

}

// 弾丸AとBが接触しているならHittingフラグをtrueにする

function hitCheck(bulletA, bulletB){

const d2 = Math.pow(bulletA.X - bulletB.X, 2) + Math.pow(bulletA.Y - bulletB.Y, 2);

if(Math.sqrt(d2) < bulletRadius * 2){

bulletA.Hitting = true;

bulletB.Hitting = true;

}

二分探索法を用いた高速化

高速化するにはどうすればよいでしょうか？

まず弾丸のX座標で配列をソートします。ソートすることでX座標が離れすぎているものを判定対象から外すことができます。弾丸Aと接しているのであれば、少なくともX座標が（弾丸AのX座標±弾丸の半径の範囲内）であるという条件を満たしているはずです。

そこで弾丸オブジェクトの配列のなかからそれを満たす区間を探します。そしてこの区間のなかだけを調べます。そうすることで無駄な処理をする必要がなくなるので高速化を実現することができるのです。

配列のなかから値がtarget以上である最小のindexを返す関数を示します。

配列を昇順でソートしているので添字の最小値よりも1小さいのであればその要素はtargetよりも明らかに小さいです。また添字の最大値よりも1大きいのであればその要素はtargetよりも明らかに大きいとみなします（そもそも配列の範囲外ではあるのだが・・・）。

そこで最初は変数 ng を -1、ok を arr.length で初期化しておきます。そしてこの中間の整数 mid を取ります。そして arr[mid] と target を比較します。この大小関係によってokとngの値を変更します。この処理を ok – ng == 1 になるまで繰り返せば配列内の値がtarget以上である部分とそうでない部分の境界線がわかります。このときのokの値が配列内の要素の値がtarget以上である最小のindexの値です。

function lowerBound(arr, target){
    let ng = -1;
    let ok = arr.length;

    while(ok - ng > 1){
        const mid = Math.floor((ok + ng) / 2);
        if(arr[mid] >= target)
            ok = mid;
        else
            ng = mid;
    }
    return ok;
}

function lowerBound(arr, target){

let ng = -1;

let ok = arr.length;

while(ok - ng > 1){

const mid = Math.floor((ok + ng) / 2);

if(arr[mid] >= target)

ok = mid;

else

ng = mid;

}

return ok;

}

改良された当たり判定の処理を示します。

bulletsをX座標でソートし、そのX座標を配列に変換したものを上記のlowerBound関数に渡します。この処理を target = bulletA.X – bulletRadius と target = bulletA.X + bulletRadius + 1 でおこなうことでbulletAとの当たり判定が必要な配列の区間がわかります。ラジオボタンで当たり判定のアルゴリズムを切り替えてみると両者の差は歴然といえます。

動作確認はこちらから

function judge2(){
    bullets.sort((a, b) => a.X - b.X);

    const xs = [];
    bullets.forEach(_ => xs.push(_.X));

    for(let a=0; a<bullets.length; a++){
        const bulletA = bullets[a];
        const start = lowerBound(xs, bulletA.X - bulletRadius);
        const end = lowerBound(xs, bulletA.X + bulletRadius + 1);

        for(let b = start; b<end; b++){
            const bulletB = bullets[b];
            if(bulletA.ID == bulletB.ID)
                continue;
            hitCheck(bulletA, bulletB);
        }
    }
}

function judge2(){

bullets.sort((a, b) => a.X - b.X);

const xs = [];

bullets.forEach(_ => xs.push(_.X));

for(let a=0; a<bullets.length; a++){

const bulletA = bullets[a];

const start = lowerBound(xs, bulletA.X - bulletRadius);

const end = lowerBound(xs, bulletA.X + bulletRadius + 1);

for(let b = start; b<end; b++){

const bulletB = bullets[b];

if(bulletA.ID == bulletB.ID)

continue;

hitCheck(bulletA, bulletB);

}

当たり判定に関する考察単純な総当たりと二分探索法による高速化

HTML部分

グローバル変数と定数

Bulletクラスの定義

ページが読み込まれたときの処理

更新処理

弾丸の生成

描画処理

当たり判定

愚直な総当たり法

二分探索法を用いた高速化

鳩でも分かるC#管理人からのお願い

コメントについて

管理人のモチベーションアップのために

コメントをどうぞ