ゲームなどのコンテンツにおいて、「当たり判定」から逃れることはできません。オブジェクトとオブジェクトが衝突したかどうかという判定は、インタラクティブコンテンツにおいて最も重要な部分になるからです。

当たり判定の実装自体は難しくありません。ですが、素朴な実装ですと、対象となるオブジェクトが大量である場合に、十分なパフォーマンスが出ません。これはオブジェクトの多い、現代的なゲームでしたり、弾幕シューティングなどを作るときに大きな障害となります。

この記事では、大量のオブジェクトの当たり判定を処理する、効率的な方法について紹介します。

まずは素朴に実装してみる

当たり判定の処理を語るには、ある程度ゲームの骨組みのようなものが必要になってきます。もちろんクラスなどを使わないベタ書きでもよいのですが、大変読みにくくなってしまいます。ですので、今回は、まず簡易的なゲームエンジンのようなものを作って、その上で当たり判定の処理を実装していきます。

また、当たり判定に関しましても、最初は最も簡単な方法での当たり判定を組み、そのあとで変更を加えていくという流れになります。

すこし長めの記事になりますので、気合いを入れて、心の準備ができたら次に読み進んでくださいませ。

当たり判定の作成

まずはコリジョン（当たり判定）のクラスを作成していきます。ベースとなるColliderクラスと、今回使用するRectangleColliderを実装します。

今回は簡単のためRectangleCollider（矩形当たり判定）のみを使用するので、もし他の形状の当たり判定が必要なら、適宜追加してください。

// 当たり判定の基底クラス。

// このクラスを直接は使わない。

class Collider {

constructor(type, x, y) {

this._type = type;

this.x = x;

this.y = y;

}

get type() { return this._type; }

}

// 矩形（四角形）の当たり判定。

// 今回はこれだけを使う。

class RectangleCollider extends Collider {

constructor(x, y, width, height) {

super('rectangle', x, y);

this.width = width;

this.height = height;

}

// 位置の平行移動。

// ローカル空間からグローバル空間への変換に使う。

translate(dx, dy) {

return new RectangleCollider(this.x + dx, this.y + dy, this.width, this.height);

}

// 各種getter。

// なくてもいいが、あったほうが楽。

get top() { return this.y; }

get bottom() { return this.y + this.height; }

get left() { return this.x; }

get right() { return this.x + this.width; }

}

コードを見れば大体わかると思いますが、一応いくつか解説しておきます。

Colliderクラスはtypeを持ちます。typeは’point’や’rectangle’、’circle’などの文字列です。これによって当たり判定を取る際に形状を振り分けます。今回は’rectangle’のみなので、typeの値に特に意味はありません。

RectangleColliderクラスは具体的な実装です。これは矩形（四角形）の当たり判定を表し、実際にプログラム中で使用します。少し気になるのがtranslate（平行移動）メソッドですね。これは、今回当たり判定の位置はオブジェクトからの「相対位置」で表すので、本当に当たり判定を取る際は、相対的なローカル座標ではなく、グローバルな「絶対位置」を取得する必要があります。そのときに平行移動させる必要があるので、これを用意しています。

特に難しいところはないと思うので、次に行きましょう。

ゲームキャラクターの作成

次にゲームキャラクターを作成します。これをActor（役者）と名付けましょう。Actorはx,yの座標と、当たり判定を持ちます。これを先ほどのRectangleColliderの下に追加します。新しいコードはどんどん下に追加していきます。

// Actor（役者）クラス。

// これを継承したオブジェクトが

// 実際のゲームオブジェクトとなる。

class Actor {

constructor(option = {collider: null}) {

this.x = 0;

this.y = 0;

this._collider = option.collider;

}

// フレームごとに状態を更新するためのメソッド。

// ここでは実装せず、子クラス側で実装する。

update(info) {}

// グラフィックをレンダリングするメソッド。

// 子クラス側で実装する。

// canvasのコンテキストを受け取る。

render(context) { }

// 他のオブジェクトに衝突したときのメソッド。

// 子クラス側で実装する。

// 本来はメソッドにするよりも、もう少し回りくどい方法を

// 取るべきだが、ここでは簡単のためこうしている。

hit(other) {}

get collider() { return this._collider; }

// 今回、当たり判定はActorからの相対位置で

// 配置するので、実際の当たり判定時には

// グローバルな位置を取得する必要がある。

// そのためのgetter。

get globalCollider() {

return this._collider.translate(this.x, this.y)

}

Actorクラスは、他にもいくつかのメソッドを持ちます。

まずupdate()メソッドですが、これは毎フレーム状態が更新されるときに呼び出されるメソッドとなります。オブジェクトの移動などの処理はここに書きます。引数でいくつかの情報を受け取り、それをメソッド内で活用することも可能です。

次にrender()メソッドです。これは描画を行うメソッドです。canvasのcontextが引数として渡されるので、それに対して命令を送ることで描画を実現します。

最後にhit()メソッドです。これは他のオブジェクトと衝突したときに呼び出されるメソッドです。本来、イベントなどを用いてもう少し回りくどい方法で実現するべきなのですが、今回は簡単のため単なるメソッドとしました。

また、globalColliderというgetterも持ちます。これは先ほど述べた通り、当たり判定はActorに対して相対位置で配置されるので、他のActorと衝突判定をするためには、グローバルな絶対位置を取得するための手段が必須です。そのためのgetterです。

さて、次はこのActorクラスを使って、ゲームキャラクターを実装します。キャラクターと言っても、今回は単純にしたいので、単なる四角形を作ります。

// 今回使用する具体的なオブジェクト。

// 単純な四角形のActor。

class RectangleActor extends Actor {

constructor(x, y, width, height) {

// 当たり判定はActorからの相対位置なので、

// Actorと当たり判定が同じ位置の場合、xとyは0。

const collider = new RectangleCollider(0, 0, width, height);

super({collider});

this.x = x;

this.y = y;

this.width = width;

this.height = height;

this._color = 'rgb(0, 0, 0)';

// 移動速度。ランダム。

this._vx = Math.random() * 10 - 5;

this._vy = Math.random() * 10 - 5;

}

// 更新メソッド。

update(info) {

this._color = 'rgb(0, 0, 0)';

// 速度分だけ移動する。

this.x += this._vx;

this.y += this._vy;

// 画面から外れたら、速度を反転する。

if(this.x < 0 || this.x > info.world.width) {

this._vx = -this._vx;

}

if(this.y < 0 || this.y > info.world.height) {

this._vy = -this._vy;

}

// 描画メソッド。

render(context) {

context.fillStyle = this._color;

context.fillRect(this.x, this.y, this.width, this.height);

}

// 衝突メソッド

hit(other) {

this._color = 'rgb(255, 0, 0)';

}

単純と言えどそこそこの長さになりました。この四角形、RectangleActorは動き回る四角形で、ランダムな速度で移動します。また、画面の端に到達すると反転します。当たり判定は自身の形と同じ四角形です。

衝突の際には自身の色を赤色に変えます。これで衝突したことがわかりやすくなります。

当たり判定検出器を作る

次に当たり判定の検出器を作りましょう。2つのActorを受け取り、結果をbooleanで返します。

// 当たり判定の検出器。

class CollisionDetector {

// 当たり判定を検出する。

detectCollision(actor1, actor2) {

const c1 = actor1.globalCollider;

const c2 = actor2.globalCollider;

if(c1.type == 'rectangle' && c2.type=='rectangle') {

return this.detectRectangleCollision(c1, c2);

}

return false;

}

// 矩形同士の当たり判定を検出する。

detectRectangleCollision(rect1, rect2) {

const horizontal = (rect2.left < rect1.right) && (rect1.left < rect2.right);

const vertical = (rect2.top < rect1.bottom) && (rect1.top < rect2.bottom);

return (horizontal && vertical);

}

detectCollision()メソッドの仕事は、両Actorのコリジョンの絶対座標を取得し、それらの間の当たり判定を行うことです。

今回は矩形同士のみで当たり判定を取ります。矩形の当たり判定については、詳しいことはここでは説明いたしません。詳しい解説は、「矩形　当たり判定」「四角形　当たり判定」などで検索すれば出てくるでしょう。

Actorを配置する世界を作る

最後にActorを配置するための世界（World）を作ります。Worldは各Actorの管理や、実際の当たり判定を取る作業などを行います。

// Actorが配置される世界。

class World {

constructor(width, height) {

this._width = width;

this._height = height;

// 配置されているActor一覧。

this._actors = [];

this._detector = new CollisionDetector();

}

// 世界にActorを配置する。

addActor(actor) {

this._actors.push(actor);

}

// 更新メソッド。Actorのupdateとは別。

update() {

const info = {

world: {

width: this._width,

height: this._height

}

};

// 各Actorをupdateする。

this._actors.forEach((a) => {

a.update(info);

});

// 各Actorの当たり判定を取る。

this._hitTest();

}

// 当たり判定を取る。

// 全てのパターンの総当たり。

_hitTest() {

const length = this._actors.length;

for(let i=0; i<length-1; i++) {

for(let j=i+1; j<length; j++) {

const a1 = this._actors[i];

const a2 = this._actors[j];

const hit = this._detector.detectCollision(a1, a2)

if(hit) {

a1.hit(a2);

a2.hit(a1);

}

// レンダリング。

render(context) {

this._actors.forEach((a) => {

a.render(context);

});

}

細かい説明はコードを見ればわかると思うので、今回は特に_hitTest()メソッドについて説明します。

_hitTest()メソッドで実装されている当たり判定は、最も素朴な設計です。Worldに登録されているすべてのActorに対して、他のActor全てとの当たり判定を取ります。当たり判定の検出自体は先ほどのCollisionDetectorに任せるので、Worldの仕事は「どのActorとどのActorを組み合わせて判定するか」という作業になります。

実際に動かしてみる

ここまでできたら、次は実際に動かしてみましょう。Worldを作りActorを配置、その後canvasを追加して、そこにレンダリングするだけです。

// Worldを作る。サイズは500x500ぐらいで。

const worldSize = 500;

const world = new World(worldSize, worldSize);

// Wolrd内にRectangleActorをランダム配置。

const actors = 1000;

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

const x = Math.random() * worldSize;

const y = Math.random() * worldSize;

const rect = new RectangleActor(x, y, 10, 10);

world.addActor(rect);

}

// canvasの設置。

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

canvas.width = worldSize;

canvas.height = worldSize;

const context = canvas.getContext('2d');

document.body.appendChild(canvas);

// 時間表示の設置。

const timeCounter = document.createElement('div');

document.body.appendChild(timeCounter);

// メインループ。

function loop(timestamp) {

// update()にかかる時間を測る。

const start = performance.now();

world.update();

const end = performance.now();

const timeStr = (end - start).toPrecision(4);

timeCounter.innerText = `${timeStr}ms`;

// 一度まっさらにしてからレンダリング。

context.clearRect(0, 0, worldSize, worldSize);

world.render(context);

// 次のフレームを要求する。

requestAnimationFrame((timestamp) => loop(timestamp));

}

// アニメーションを開始する。

requestAnimationFrame((timestamp) => loop(timestamp));

加えて今回は当たり判定にかかった時間も計測して表示しておきます。performance.now()について詳しくはJavaScriptで任意の処理にかかる時間を計測するをご覧ください。

実行してみる

ここまでできたら、実際に実行してみましょう。

見ての通り、大量のオブジェクトの当たり判定には、とても時間がかかります。この例ですと42msかかっていますが、ゲームなどを作る際には約17ms（1/60秒）以内に納めないといけないので、大幅に超えてしまっています。

ここまでのコードまとめ

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

// 当たり判定の基底クラス。

// このクラスを直接は使わない。

class Collider {

constructor(type, x, y) {

this._type = type;

this.x = x;

this.y = y;

}

get type() { return this._type; }

}

// 矩形（四角形）の当たり判定。

// 今回はこれだけを使う。

class RectangleCollider extends Collider {

constructor(x, y, width, height) {

super('rectangle', x, y);

this.width = width;

this.height = height;

}

// 位置の平行移動。

// ローカル空間からグローバル空間への変換に使う。

translate(dx, dy) {

return new RectangleCollider(this.x + dx, this.y + dy, this.width, this.height);

}

// 各種getter。

// なくてもいいが、あったほうが楽。

get top() { return this.y; }

get bottom() { return this.y + this.height; }

get left() { return this.x; }

get right() { return this.x + this.width; }

}

// Actor（役者）クラス。

// これを継承したオブジェクトが

// 実際のゲームオブジェクトとなる。

class Actor {

constructor(option = {collider: null}) {

this.x = 0;

this.y = 0;

this._collider = option.collider;

}

// フレームごとに状態を更新するためのメソッド。

// ここでは実装せず、子クラス側で実装する。

update(info) {}

// グラフィックをレンダリングするメソッド。

// 子クラス側で実装する。

// canvasのコンテキストを受け取る。

render(context) { }

// 他のオブジェクトに衝突したときのメソッド。

// 子クラス側で実装する。

// 本来はメソッドにするよりも、もう少し回りくどい方法を

// 取るべきだが、ここでは簡単のためこうしている。

hit(other) {}

get collider() { return this._collider; }

// 今回、当たり判定はActorからの相対位置で

// 配置するので、実際の当たり判定時には

// グローバルな位置を取得する必要がある。

// そのためのgetter。

get globalCollider() {

return this._collider.translate(this.x, this.y)

}

// 今回使用する具体的なオブジェクト。

// 単純な四角形のActor。

class RectangleActor extends Actor {

constructor(x, y, width, height) {

// 当たり判定はActorからの相対位置なので、

// Actorと当たり判定が同じ位置の場合、xとyは0。

const collider = new RectangleCollider(0, 0, width, height);

super({collider});

this.x = x;

this.y = y;

this.width = width;

this.height = height;

this._color = 'rgb(0, 0, 0)';

// 移動速度。ランダム。

this._vx = Math.random() * 10 - 5;

this._vy = Math.random() * 10 - 5;

}

// 更新メソッド。

update(info) {

this._color = 'rgb(0, 0, 0)';

// 速度分だけ移動する。

this.x += this._vx;

this.y += this._vy;

// 画面から外れたら、速度を反転する。

if(this.x < 0 || this.x > info.world.width) {

this._vx = -this._vx;

}

if(this.y < 0 || this.y > info.world.height) {

this._vy = -this._vy;

}

// 描画メソッド。

render(context) {

context.fillStyle = this._color;

context.fillRect(this.x, this.y, this.width, this.height);

}

// 衝突メソッド

hit(other) {

this._color = 'rgb(255, 0, 0)';

}

// 当たり判定の検出器。

class CollisionDetector {

// 当たり判定を検出する。

detectCollision(actor1, actor2) {

const c1 = actor1.globalCollider;

const c2 = actor2.globalCollider;

if(c1.type == 'rectangle' && c2.type=='rectangle') {

return this.detectRectangleCollision(c1, c2);

}

return false;

}

// 矩形同士の当たり判定を検出する。

detectRectangleCollision(rect1, rect2) {

const horizontal = (rect2.left < rect1.right) && (rect1.left < rect2.right);

const vertical = (rect2.top < rect1.bottom) && (rect1.top < rect2.bottom);

return (horizontal && vertical);

}

// Actorが配置される世界。

class World {

constructor(width, height) {

this._width = width;

this._height = height;

// 配置されているActor一覧。

this._actors = [];

this._detector = new CollisionDetector();

}

// 世界にActorを配置する。

addActor(actor) {

this._actors.push(actor);

}

// 更新メソッド。Actorのupdateとは別。

update() {

const info = {

world: {

width: this._width,

height: this._height

}

};

// 各Actorをupdateする。

this._actors.forEach((a) => {

a.update(info);

});

// 各Actorの当たり判定を取る。

this._hitTest();

}

// 当たり判定を取る。

// 全てのパターンの総当たり。

_hitTest() {

const length = this._actors.length;

for(let i=0; i<length-1; i++) {

for(let j=i+1; j<length; j++) {

const a1 = this._actors[i];

const a2 = this._actors[j];

const hit = this._detector.detectCollision(a1, a2)

if(hit) {

a1.hit(a2);

a2.hit(a1);

}

// レンダリング。

render(context) {

this._actors.forEach((a) => {

a.render(context);

});

}

// Worldを作る。サイズは500x500ぐらいで。

const worldSize = 500;

const world = new World(worldSize, worldSize);

// Wolrd内にRectangleActorをランダム配置。

const actors = 1000;

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

const x = Math.random() * worldSize;

const y = Math.random() * worldSize;

const rect = new RectangleActor(x, y, 10, 10);

world.addActor(rect);

}

// canvasの設置。

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

canvas.width = worldSize;

canvas.height = worldSize;

const context = canvas.getContext('2d');

document.body.appendChild(canvas);

// 時間表示の設置。

const timeCounter = document.createElement('div');

document.body.appendChild(timeCounter);

// メインループ。

function loop(timestamp) {

// update()にかかる時間を測る。

const start = performance.now();

world.update();

const end = performance.now();

const timeStr = (end - start).toPrecision(4);

timeCounter.innerText = `${timeStr}ms`;

// 一度まっさらにしてからレンダリング。

context.clearRect(0, 0, worldSize, worldSize);

world.render(context);

// 次のフレームを要求する。

requestAnimationFrame((timestamp) => loop(timestamp));

}

// アニメーションを開始する。

requestAnimationFrame((timestamp) => loop(timestamp));

工夫して当たり判定を取る

当たり判定は非常に重い処理になりますので、実際に使う際には、実用的なパフォーマンスがでるように工夫しなければなりません。

実はその工夫については、私が説明しなくても、IKD様による以下のページで詳しい説明がなされています。

非常に詳しく書かれていて、私ができることはもう残っていないようにも思えます。ですがこれらのページではC++を用いられていて、JavaScriptな私たちは、実装に落とし込むのに非常に手間がかかってしまいます。

なので、この記事では上記のページの内容を軽くまとめつつ、JavaScriptではどのように実装すればいいのかについて説明したいと思います。

空間を分割する

オブジェクトが同じ空間に存在している以上、「総当たり」から逃れることはできません。なぜなら、同じ空間にいるのなら衝突する可能性があるからです。

では逆に考えてみましょう。オブジェクトが違う空間に存在すれば、総当たりの必要性がなくなります。つまり、空間を分割して、それぞれが違う空間に所属するようにすればいいのです。

最も有名な分割方法は、四分木による分割です。空間を4つに分割し、その分割された空間をさらに4分割し……ということを繰り返します。四分木については既知のものとしますので、わからない人は各自調べてください。

この図で、青四角がオブジェクトです。

例えば左上のオブジェクトと、左下の2つのオブジェクトを見てみましょう。左上のオブジェクトは左上の空間に存在し、左下の2つは左下の空間に存在します。所属する空間が別なので、これらは衝突する可能性はありません。

さらに左下の2つについては、さらに細かく分割された、別々の空間にいます。これら2つも互いに衝突する可能性はないので、当たり判定を取る必要はありません。

ここで問題児は右にいるオブジェクトです。これは一番大きな分割をまたいでいるので、他のオブジェクトと衝突の可能性があります。これに関しては仕方ないので、全てのオブジェクトと当たり判定を取ります。

という風に、空間を分割すると当たり判定を取るべきオブジェクトというのは、どんどん減らしていけます。一部減らせないものもありましたが、それは我慢してください。

この分割はオブジェクトの数が増えてくると、劇的に効果を発揮します。

四分木のコスト

空間を四分木で分割して、オブジェクトを突っ込んで、当たり判定を減らして、はい終わり……というわけにはいかないのが世の中の難しいところです。

当然の話ではあるのですが、この四分木の操作にもコストがかかります。オブジェクトを適切に四分木へ登録するコストが非常に大きいのです。下手をすると「四分木の導入で減らせるコスト」よりも「四分木の導入で増えるコスト」の方が大きくなります。これでは全く意味がありません。

四分木を導入すれば高速に当たり判定を取れるが、四分木自体の操作は遅い。この板挟みを解決していかなければなりません。

モートン順序

「つまり、もし四分木の操作コストを軽減する魔法のような技術があれば……」と考えるでしょう。実はあります。あるんです。魔法のような技術が。

それには、前準備として、空間への番号の振り方を工夫する必要があります。こんな風に振ります：

まず、四分木のルートとなる分割されていない空間、これは普通に0番を振ります。次に4分割された空間ですが、0、1、2、3、とZ字状に番号を振っていきます。これもいいでしょう。

さて次です。4分割された空間を4分割した、16分割された空間ですが、図をよく見てください。左上の空間にZ字に番号を振ります。次に右上の空間にZ字に番号を振ります。次は左下、右下、という風にZ字に番号を振っていきます。より細かく分割した場合もこれを繰り返します。

これをモートン順序と言います。実に不思議な番号の振り方です。ですが、こうすることによりいくつかの利点があるのです。

モートン順序は上位空間の情報を持つ

モートン順序の番号は、上位空間の情報を内包しています。何を言っているかわけがわからないと思うので、実際に見てみましょう。

まず16分割された空間の、9番に着目します。

9番最上位空間はもちろん分割されていない空間の「0番」です。そして9番はその中の「2番」の中に存在します。そして9番自体は2番の中の「1番（青い文字）」になります。「0」「2」「1」という並び、ちょっとの間覚えておいてください。

ここで唐突に「9」を2進数で表現してみます。「9」は2進数で「001001」です。さらにこの2進数を2bitごとに区切ります。「00 | 10 | 01」です。2bitごとに区切ったそれぞれの2進数を10進数に直すと、それぞれ「0」「2」「1」です。おやおやどこかで見たことのあるような並び。

そうです。モートン順序は自身の上位空間の情報をすべて持っているのです。これはどれだけ分割が深くなっても同じです。ひとつの番号から、その上位の空間の番号まで、簡単に導き出すことができるのです。

そしてそれぞれの2進数から、位置の情報まで取り出すことができます。たとえば「2」＝「10」ですが、この2進数の1の位はX軸、10の位はY軸を表しています。1の位の「0」は「左側にある」で、10の位の「1」は「下にある」です。実際に4分割された空間の2番を見ると、左下にあります。

このようにして、モートン順序で番号を振ることで、ただの番号から様々な情報を取り出すことができます。

位置からモートン番号を割り出す

番号から位置がわかる、つまり番号は位置情報の組み合わせで構成されている。ならば位置から番号を導き出すこともできる、そう考えてもよいでしょう。

まず簡単のため、空間全体の大きさを100×100としましょう。このとき、16分割された空間の、それぞれの小空間の一辺あたりの長さは、100/(2^2)です。これは簡単ですね。

次に点の座標が与えられたとします。具体例のほうがいいでしょうから、適当に(27, 74)とでもしておきましょうか。この点の座標を一辺あたりの長さで割ると、どの位置にあるのかが出てきます。割ってみると(1.08, 2.96)ですね。今回欲しいのは小空間の位置なので、小数点切り捨てで(1, 2)となります。

(1, 2)が表すのは、「左から1番目、上から2番目（※0番目から数える）」となります。図を見ながら左から0、1……上から0、1、2…と数えてみると、9番が出てきますね。さて、今回は図を見て数えましたが、実際には(1, 2)からこの「9」を算出する必要があります。どうしましょう。

ここで(1, 2)を2進数にしてみます。(01, 10)ですね。x軸y軸それぞれ1bit目同士と、2bit目同士を組み合わせて新しい2進数を作ります。すると……

なんとびっくり。「1001」となって「9」が出てきました。そうです、モートン番号は位置の情報から構成されているので、逆に位置さえわかれば番号を算出することもできるのです。

大きさのあるオブジェクトの番号算出

点の位置から番号を算出することができました。これは大きな進歩です。ですが、私たちにはまだ課題があります。

私たちが実際に扱うオブジェクトは、大きさ（幅・高さ）を持ちます。点の時とは違い、このオブジェクトがどの空間に含まれるのか算出するのは、少し工夫が必要になります。

まず、青色のオブジェクトの左上の点の番号を求めます。これはさっきやった計算で出てきます。次に右下の点の番号も求めます。すると「4」「7」が出てきます。

次にこれらを2進数にしてXORをとって、「0100 XOR 0111」なので「0011」となります。

そして、このXORの結果を2bitずつ右シフトしていきます。この右シフトを「捨てられたビットが0でなくなるまで」繰り返します。今回は1回シフトすれば「11」が捨てられるので、そこで終了です。

このシフト回数が重要になってきます。「0以外が捨てられるまで繰り返したシフトの回数」分だけ、上に遡ります。今回は「1回」なので、「16分割された空間」から「1階層」上がって、「4分割された空間」に所属することになります。

これで所属する空間の階層がわかりました。そしてモートン番号は上位空間の情報も持ちます。「4」か「7」から上位空間の情報を取り出して「1」を得れば、終わりです。

線形四分木

そろそろ実装に移りたいところですが、もうひとつお話があります。今度は四分木自体のお話です。

四分木はその名の通りツリーで、データ構造としてもツリーを採用するのが普通です。ですが、ツリーにしてしまうとアクセスが遅くなってしまいます。

そこで、四分木を線形（配列）として表してしまえば、高速にアクセスできてしまうのではないか、というアイデアがあります。

四分木というとこんな感じですが、これを

こうします。

こうすると簡単に要素にアクセスできます。さて、ここで面倒なのが「階層Lのn番目は、線形四分木の何番目か」の算出ですが、これは等比級数の和を使って簡単に求めることができます。等比級数の和より、階層Lの0番目は、

(4^L – 1)/(4 – 1) = (4^L – 1)/3

です。これにnを足せば、線形四分木の何番目に入れればいいかが出てきます。

ここまでを実装する

いろいろと長い話をしてきましたが、要は以下の通りです：

空間を分割してモートン順序で番号を振る
モートン番号は空間の情報を含んでいる
空間の情報からモートン番号を算出することもできる
（おまけ）線形四分木にすると扱いが楽

これを一旦実装してみましょう。

ソースファイルの一番上か、Worldの上あたりにクラスLinearQuadTreeSpaceを追加します。これは線形四分木空間を表すクラスで、モートン番号の計算も行います。

ここで言葉を整理しておきましょうか。これからは、空間の階層のことをレベル、分割された各小空間のことをセルと呼びます。

LinearQuadTreeSpaceに必要な機能は、以下の通りです：

オブジェクトのコリジョンから左上と右下のモートン番号を算出する
コリジョンの左上と右下のモートン番号から所属するレベルを算出する
モートン番号とレベルから所属するセルを算出する
レベルとセル番号からオブジェクトを四分木に追加する
四分木をクリア（リセット）する

また、各セルの値は配列とします。同じセルに複数のオブジェクトが入ることもありますので。配列の代わりにLinkedListを採用してもいいですが、最近のJavaScript実行エンジンは賢いので、配列でもリストでも実行速度はそんなに変わらないと思います。

これを実装してみましょう。だいたい以下のような感じになると思います：

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

// 線形四分木空間。

// 空間階層のことをレベル、

// 各小空間のことをセルと呼ぶことにする。

class LinearQuadTreeSpace {

constructor(width, height, level) {

this._width = width;

this._height = height;

this.data = [null];

this._currentLevel = 0;

// 入力レベルまでdataを伸長する。

while(this._currentLevel < level) {

this._expand();

}

// dataをクリアする。

clear() {

this.data.fill(null);

}

// 要素をdataに追加する。

// 必要なのは、要素と、レベルと、レベル内での番号。

_addNode(node, level, index) {

// オフセットは(4^L - 1)/3で求まる。

// それにindexを足せば線形四分木上での位置が出る。

const offset = ((4 ** level) - 1) / 3;

const linearIndex = offset + index;

// もしdataの長さが足りないなら拡張する。

while(this.data.length <= linearIndex) {

this._expandData();

}

// セルの初期値はnullとする。

// しかし上の階層がnullのままだと面倒が発生する。

// なので要素を追加する前に親やその先祖すべてを

// 空配列で初期化する。

let parentCellIndex = linearIndex;

while(this.data[parentCellIndex] === null) {

this.data[parentCellIndex] = [];

parentCellIndex = Math.floor((parentCellIndex - 1) / 4);

if(parentCellIndex >= this.data.length) {

break;

}

// セルに要素を追加する。

const cell = this.data[linearIndex];

cell.push(node);

}

// Actorを線形四分木に追加する。

// Actorのコリジョンからモートン番号を計算し、

// 適切なセルに割り当てる。

addActor(actor) {

const collider = actor.globalCollider;

// モートン番号の計算。

const leftTopMorton = this._calc2DMortonNumber(collider.left, collider.top);

const rightBottomMorton = this._calc2DMortonNumber(collider.right, collider.bottom);

// 左上も右下も-1（画面外）であるならば、

// レベル0として扱う。

// なおこの処理には気をつける必要があり、

// 画面外に大量のオブジェクトがあるとレベル0に

// オブジェクトが大量配置され、当たり判定に大幅な処理時間がかかる。

// 実用の際にはここをうまく書き換えて、あまり負担のかからない

// 処理に置き換えるといい。

if(leftTopMorton === -1 && rightBottomMorton === -1) {

this._addNode(actor, 0, 0);

return;

}

// 左上と右下が同じ番号に所属していたら、

// それはひとつのセルに収まっているということなので、

// 特に計算もせずそのまま現在のレベルのセルに入れる。

if(leftTopMorton === rightBottomMorton) {

this._addNode(actor, this._currentLevel, leftTopMorton);

return;

}

// 左上と右下が異なる番号（＝境界をまたいでいる）の場合、

// 所属するレベルを計算する。

const level = this._calcLevel(leftTopMorton, rightBottomMorton);

// そのレベルでの所属する番号を計算する。

// モートン番号の代表値として大きい方を採用する。

// これは片方が-1の場合、-1でない方を採用したいため。

const larger = Math.max(leftTopMorton, rightBottomMorton);

const cellNumber = this._calcCell(larger, level);

// 線形四分木に追加する。

this._addNode(actor, level, cellNumber);

}

// 線形四分木の長さを伸ばす。

_expand() {

const nextLevel = this._currentLevel + 1;

const length = ((4 ** (nextLevel+1)) - 1) / 3;

while(this.data.length < length) {

this.data.push(null);

}

this._currentLevel++;

}

// 16bitの数値を1bit飛ばしの32bitにする。

// JavaScriptの数値は52bitあるので、

// 余裕があれば26bitまで拡張しても良い。

_separateBit32(n) {

n = (n|(n<<8)) & 0x00ff00ff;

n = (n|(n<<4)) & 0x0f0f0f0f;

n = (n|(n<<2)) & 0x33333333;

return (n|(n<<1)) & 0x55555555;

}

// x, y座標からモートン番号を算出する。

_calc2DMortonNumber(x, y) {

// 空間の外の場合-1を返す。

if(x < 0 || y < 0) {

return -1;

}

if(x > this._width || y > this._height) {

return -1;

}

// 空間の中の位置を求める。

const xCell = Math.floor(x / (this._width / (2 ** this._currentLevel)));

const yCell = Math.floor(y / (this._height / (2 ** this._currentLevel)));

// x位置とy位置をそれぞれ1bit飛ばしの数にし、

// それらをあわせてひとつの数にする。

// これがモートン番号となる。

return (this._separateBit32(xCell) | (this._separateBit32(yCell)<<1));

}

// オブジェクトの所属レベルを算出する。

// XORを取った数を2bitずつ右シフトして、

// 0でない数が捨てられたときのシフト回数を採用する。

_calcLevel(leftTopMorton, rightBottomMorton) {

const xorMorton = leftTopMorton ^ rightBottomMorton;

let level = this._currentLevel - 1;

let attachedLevel = this._currentLevel;

for(let i = 0; level >= 0; i++) {

const flag = (xorMorton >> (i * 2)) & 0x3;

if(flag > 0) {

attachedLevel = level;

}

level--;

}

return attachedLevel;

}

// 階層を求めるときにシフトした数だけ右シフトすれば

// 空間の位置がわかる。

_calcCell(morton, level) {

const shift = ((this._currentLevel - level) * 2);

return morton >> shift;

}

長いですね！ですが今まで説明してきた通りの内容なので、そんなに難しくはないはずです。

今までの説明になかったのは、空間外にオブジェクトが存在する場合です。これは、今回はモートン番号「-1」を返すようにして、完全に外に出ていたらレベル0として扱う、という処理にしておきました。ただ、これはこれで問題もあるので、実際に使う際にはよく考えていろいろ工夫してください。完全に外に出ていたら線形四分木には追加しない（当たり判定を取らない）、というのもありだと思います。

それとセルの最初の値はnullとしておきました。これはあとあと使うので、nullにしておいてください。初期値を空配列にしてもいいのですが、一部処理がちょっと面倒になるので。

線形四分木の巡り方

あとは上位空間から下位空間へ向けて当たり判定を取っていくだけですが、ここにもある程度の工夫が必要です。

最も単純な方法だと、まずレベル0のオブジェクトについて、下位空間を辿って当たり判定を取ります。次にレベル1のオブジェクトについて下位空間を辿って……となります。しかし、これをやっていると、なんどもなんども四分木を辿らないといけず、非常に時間がかかります。

そこでスタックを導入して1回巡るだけで全ての当たり判定を取れるようにしたいと思います。このスタックを「衝突オブジェクトリスト」とします。

まずそのレベル0のオブジェクトについて、セル内で総当たりで当たり判定を取ります。次に衝突オブジェクトリスト内のオブジェクトと、総当たりで当たり判定を取ります。ただし最初は衝突オブジェクトリストは空なので、特に何もしません。これが終わったらレベル0のセルのオブジェクトを衝突オブジェクトリストにpushします。

次に下位（レベル1）のひとつのセルに移動して、同じことをします。つまり、レベル1の、同じセル内にいるオブジェクト同士で当たり判定を取ります。そして衝突オブジェクトリスト内のオブジェクトと当たり判定を取ります。次にセルが下位セルを持つなら、今のセルのオブジェクトを衝突オブジェクトリストにpushして下位のひとつのセルに移動します。下位セルを持たないならば、何もせず上位セルへ戻ります。

これを繰り返し、下るべき下位セルが存在しなくなったら、衝突オブジェクトリストから、追加したオブジェクトの個数分だけpopします。

これを実行すると、1回木を巡っただけで処理が完了します。

線形四分木を使った当たり判定を実装する

あとはWorldクラスを書き換えるだけです。コンストラクタ、update()、_hitTest()あたりをいじります。

_hitTest()は、先ほど説明した通りの再帰メソッドにします。

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

// Actorが配置される世界。

class World {

constructor(width, height) {

this._width = width;

this._height = height;

// 配置されているActor一覧。

this._actors = [];

// 線形四分木空間。

// とりあえずレベル3ぐらいで。

this._qTree = new LinearQuadTreeSpace(width, height, 3);

this._detector = new CollisionDetector();

}

// 世界にActorを配置する。

addActor(actor) {

this._actors.push(actor);

}

// 更新メソッド。Actorのupdateとは別。

update() {

const info = {

world: {

width: this._width,

height: this._height

}

};

// 各Actorをupdateする。

this._actors.forEach((a) => {

a.update(info);

});

// 線形四分木をクリアする。

this._qTree.clear();

// 各Actorを四分木に登録する。

this._actors.forEach((a) => {

this._qTree.addActor(a);

});

// 各Actorの当たり判定を取る。

this._hitTest();

}

// 当たり判定。

_hitTest(currentIndex = 0, objList = []) {

const currentCell = this._qTree.data[currentIndex];

// 現在のセルの中と、衝突オブジェクトリストとで

// 当たり判定を取る。

this._hitTestInCell(currentCell, objList);

// 次に下位セルを持つか調べる。

// 下位セルは最大4個なので、i=0から3の決め打ちで良い。

let hasChildren = false;

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

const nextIndex = (currentIndex === 0) ? i + 1 : currentIndex * 4 + i;

// 下位セルがあったら、

const hasChildCell = (nextIndex < this._qTree.data.length) && (this._qTree.data[nextIndex] !== null);

hasChildren = hasChildren || hasChildCell;

if(hasChildCell) {

// 衝突オブジェクトリストにpushして、

objList.push(...currentCell);

// 下位セルで当たり判定を取る。再帰。

this._hitTest(nextIndex, objList);

}

// 終わったら追加したオブジェクトをpopする。

if(hasChildren) {

const popNum = currentCell.length;

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

objList.pop();

}

// セルの中の当たり判定を取る。

// 衝突オブジェクトリストとも取る。

_hitTestInCell(cell, objList) {

// セルの中。総当たり。

const length = cell.length;

for(let i=0; i < length - 1; i++) {

const obj1 = cell[i];

for(let j=i+1; j < length; j++) {

const obj2 = cell[j];

const hit = this._detector.detectCollision(obj1, obj2);

if(hit) {

obj1.hit(obj2);

obj2.hit(obj1);

}

// 衝突オブジェクトリストと。

const objLength = objList.length;

const cellLength = cell.length;

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

const obj = objList[i];

for(let j=0; j<cellLength; j++) {

const cellObj = cell[j];

const hit = this._detector.detectCollision(obj, cellObj);

if(hit) {

obj.hit(cellObj);

cellObj.hit(obj);

}

// レンダリング。

render(context) {

this._actors.forEach((a) => {

a.render(context);

});

}

できました！

実行してみる

では実行してみましょう。

だいたい1000個で22msです。総当たりのときは42msだったので、20msの短縮になりました。四分木を導入することで、著しく性能が向上していることがわかります。

ここまでのコード

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

367

368

369

370

371

372

373

374

375

376

377

378

379

380

381

382

383

384

385

386

387

388

389

390

391

392

393

394

395

396

397

398

399

400

401

402

403

404

405

406

407

408

409

410

411

412

413

414

415

416

417

418

419

420

421

422

423

424

425

426

427

428

429

430

431

432

433

434

435

436

437

438

439

440

441

442

443

444

445

446

447

448

449

450

451

452

453

454

455

456

457

458

459

460

461

462

463

464

465

466

467

468

469

470

471

472

473

474

475

476

477

478

479

480

// 線形四分木空間。

// 空間階層のことをレベル、

// 各小空間のことをセルと呼ぶことにする。

class LinearQuadTreeSpace {

constructor(width, height, level) {

this._width = width;

this._height = height;

this.data = [null];

this._currentLevel = 0;

// 入力レベルまでdataを伸長する。

while(this._currentLevel < level) {

this._expand();

}

// dataをクリアする。

clear() {

this.data.fill(null);

}

// 要素をdataに追加する。

// 必要なのは、要素と、レベルと、レベル内での番号。

_addNode(node, level, index) {

// オフセットは(4^L - 1)/3で求まる。

// それにindexを足せば線形四分木上での位置が出る。

const offset = ((4 ** level) - 1) / 3;

const linearIndex = offset + index;

// もしdataの長さが足りないなら拡張する。

while(this.data.length <= linearIndex) {

this._expandData();

}

// セルの初期値はnullとする。

// しかし上の階層がnullのままだと面倒が発生する。

// なので要素を追加する前に親やその先祖すべてを

// 空配列で初期化する。

let parentCellIndex = linearIndex;

while(this.data[parentCellIndex] === null) {

this.data[parentCellIndex] = [];

parentCellIndex = Math.floor((parentCellIndex - 1) / 4);

if(parentCellIndex >= this.data.length) {

break;

}

// セルに要素を追加する。

const cell = this.data[linearIndex];

cell.push(node);

}

// Actorを線形四分木に追加する。

// Actorのコリジョンからモートン番号を計算し、

// 適切なセルに割り当てる。

addActor(actor) {

const collider = actor.globalCollider;

// モートン番号の計算。

const leftTopMorton = this._calc2DMortonNumber(collider.left, collider.top);

const rightBottomMorton = this._calc2DMortonNumber(collider.right, collider.bottom);

// 左上も右下も-1（画面外）であるならば、

// レベル0として扱う。

// なおこの処理には気をつける必要があり、

// 画面外に大量のオブジェクトがあるとレベル0に

// オブジェクトが大量配置され、当たり判定に大幅な処理時間がかかる。

// 実用の際にはここをうまく書き換えて、あまり負担のかからない

// 処理に置き換えるといい。

if(leftTopMorton === -1 && rightBottomMorton === -1) {

this._addNode(actor, 0, 0);

return;

}

// 左上と右下が同じ番号に所属していたら、

// それはひとつのセルに収まっているということなので、

// 特に計算もせずそのまま現在のレベルのセルに入れる。

if(leftTopMorton === rightBottomMorton) {

this._addNode(actor, this._currentLevel, leftTopMorton);

return;

}

// 左上と右下が異なる番号（＝境界をまたいでいる）の場合、

// 所属するレベルを計算する。

const level = this._calcLevel(leftTopMorton, rightBottomMorton);

// そのレベルでの所属する番号を計算する。

// モートン番号の代表値として大きい方を採用する。

// これは片方が-1の場合、-1でない方を採用したいため。

const larger = Math.max(leftTopMorton, rightBottomMorton);

const cellNumber = this._calcCell(larger, level);

// 線形四分木に追加する。

this._addNode(actor, level, cellNumber);

}

// 線形四分木の長さを伸ばす。

_expand() {

const nextLevel = this._currentLevel + 1;

const length = ((4 ** (nextLevel+1)) - 1) / 3;

while(this.data.length < length) {

this.data.push(null);

}

this._currentLevel++;

}

// 16bitの数値を1bit飛ばしの32bitにする。

// JavaScriptの数値は52bitあるので、

// 余裕があれば26bitまで拡張しても良い。

_separateBit32(n) {

n = (n|(n<<8)) & 0x00ff00ff;

n = (n|(n<<4)) & 0x0f0f0f0f;

n = (n|(n<<2)) & 0x33333333;

return (n|(n<<1)) & 0x55555555;

}

// x, y座標からモートン番号を算出する。

_calc2DMortonNumber(x, y) {

// 空間の外の場合-1を返す。

if(x < 0 || y < 0) {

return -1;

}

if(x > this._width || y > this._height) {

return -1;

}

// 空間の中の位置を求める。

const xCell = Math.floor(x / (this._width / (2 ** this._currentLevel)));

const yCell = Math.floor(y / (this._height / (2 ** this._currentLevel)));

// x位置とy位置をそれぞれ1bit飛ばしの数にし、

// それらをあわせてひとつの数にする。

// これがモートン番号となる。

return (this._separateBit32(xCell) | (this._separateBit32(yCell)<<1));

}

// オブジェクトの所属レベルを算出する。

// XORを取った数を2bitずつ右シフトして、

// 0でない数が捨てられたときのシフト回数を採用する。

_calcLevel(leftTopMorton, rightBottomMorton) {

const xorMorton = leftTopMorton ^ rightBottomMorton;

let level = this._currentLevel - 1;

let attachedLevel = this._currentLevel;

for(let i = 0; level >= 0; i++) {

const flag = (xorMorton >> (i * 2)) & 0x3;

if(flag > 0) {

attachedLevel = level;

}

level--;

}

return attachedLevel;

}

// 階層を求めるときにシフトした数だけ右シフトすれば

// 空間の位置がわかる。

_calcCell(morton, level) {

const shift = ((this._currentLevel - level) * 2);

return morton >> shift;

}

// 当たり判定の基底クラス。

// このクラスを直接は使わない。

class Collider {

constructor(type, x, y) {

this._type = type;

this.x = x;

this.y = y;

}

get type() { return this._type; }

}

// 矩形（四角形）の当たり判定。

// 今回はこれだけを使う。

class RectangleCollider extends Collider {

constructor(x, y, width, height) {

super('rectangle', x, y);

this.width = width;

this.height = height;

}

// 位置の平行移動。

// ローカル空間からグローバル空間への変換に使う。

translate(dx, dy) {

return new RectangleCollider(this.x + dx, this.y + dy, this.width, this.height);

}

// 各種getter。

// なくてもいいが、あったほうが楽。

get top() { return this.y; }

get bottom() { return this.y + this.height; }

get left() { return this.x; }

get right() { return this.x + this.width; }

}

// Actor（役者）クラス。

// これを継承したオブジェクトが

// 実際のゲームオブジェクトとなる。

class Actor {

constructor(option = {collider: null}) {

this.x = 0;

this.y = 0;

this._collider= option.collider;

}

// フレームごとに状態を更新するためのメソッド。

// ここでは実装せず、子クラス側で実装する。

update(info) {}

// グラフィックをレンダリングするメソッド。

// 子クラス側で実装する。

// canvasのコンテキストを受け取る。

render(context) { }

// 他のオブジェクトに衝突したときのメソッド。

// 子クラス側で実装する。

// 本来はメソッドにするよりも、もう少し回りくどい方法を

// 取るべきだが、ここでは簡単のためこうしている。

hit(other) {}

get collider() { return this._collider; }

// 今回、当たり判定はActorからの相対位置で

// 配置するので、実際の当たり判定時には

// グローバルな位置を取得する必要がある。

// そのためのgetter。

get globalCollider() {

return this._collider.translate(this.x, this.y)

}

// 今回使用する具体的なオブジェクト。

// 単純な四角形のActor。

class RectangleActor extends Actor {

constructor(x, y, width, height) {

// 当たり判定はActorからの相対位置なので、

// Actorと当たり判定が同じ位置の場合、xとyは0。

const collider = new RectangleCollider(0, 0, width, height);

super({collider});

this.x = x;

this.y = y;

this.width = width;

this.height = height;

this._color = 'rgb(0, 0, 0)';

// 移動速度。ランダム。

this._vx = Math.random() * 10 - 5;

this._vy = Math.random() * 10 - 5;

}

// 更新メソッド。

update(info) {

this._color = 'rgb(0, 0, 0)';

// 速度分だけ移動する。

this.x += this._vx;

this.y += this._vy;

// 画面から外れたら、速度を反転する。

if(this.x < 0 || this.x > info.world.width) {

this._vx = -this._vx;

}

if(this.y < 0 || this.y > info.world.height) {

this._vy = -this._vy;

}

// 描画メソッド。

render(context) {

context.fillStyle = this._color;

context.fillRect(this.x, this.y, this.width, this.height);

}

// 衝突メソッド

hit(other) {

this._color = 'rgb(255, 0, 0)';

}

// 当たり判定の検出器。

class CollisionDetector {

// 当たり判定を検出する。

detectCollision(actor1, actor2) {

const c1 = actor1.globalCollider;

const c2 = actor2.globalCollider;

if(c1.type == 'rectangle' && c2.type=='rectangle') {

return this.detectRectangleCollision(c1, c2);

}

return false;

}

// 矩形同士の当たり判定を検出する。

detectRectangleCollision(rect1, rect2) {

const horizontal = (rect2.left < rect1.right) && (rect1.left < rect2.right);

const vertical = (rect2.top < rect1.bottom) && (rect1.top < rect2.bottom);

return (horizontal && vertical);

}

// Actorが配置される世界。

class World {

constructor(width, height) {

this._width = width;

this._height = height;

// 配置されているActor一覧。

this._actors = [];

// 線形四分木空間。

// とりあえずレベル3ぐらいで。

this._qTree = new LinearQuadTreeSpace(width, height, 3);

this._detector = new CollisionDetector();

}

// 世界にActorを配置する。

addActor(actor) {

this._actors.push(actor);

}

// 更新メソッド。Actorのupdateとは別。

update() {

const info = {

world: {

width: this._width,

height: this._height

}

};

// 各Actorをupdateする。

this._actors.forEach((a) => {

a.update(info);

});

// 線形四分木をクリアする。

this._qTree.clear();

// 各Actorを四分木に登録する。

this._actors.forEach((a) => {

this._qTree.addActor(a);

});

// 各Actorの当たり判定を取る。

this._hitTest();

}

// 当たり判定。

_hitTest(currentIndex = 0, objList = []) {

const currentCell = this._qTree.data[currentIndex];

// 現在のセルの中と、衝突オブジェクトリストとで

// 当たり判定を取る。

this._hitTestInCell(currentCell, objList);

// 次に下位セルを持つか調べる。

// 下位セルは最大4個なので、i=0から3の決め打ちで良い。

let hasChildren = false;

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

const nextIndex = (currentIndex === 0) ? i + 1 : currentIndex * 4 + i;

// 下位セルがあったら、

const hasChildCell = (nextIndex < this._qTree.data.length) && (this._qTree.data[nextIndex] !== null);

hasChildren = hasChildren || hasChildCell;

if(hasChildCell) {

// 衝突オブジェクトリストにpushして、

objList.push(...currentCell);

// 下位セルで当たり判定を取る。再帰。

this._hitTest(nextIndex, objList);

}

// 終わったら追加したオブジェクトをpopする。

if(hasChildren) {

const popNum = currentCell.length;

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

objList.pop();

}

// セルの中の当たり判定を取る。

// 衝突オブジェクトリストとも取る。

_hitTestInCell(cell, objList) {

// セルの中。総当たり。

const length = cell.length;

for(let i=0; i < length - 1; i++) {

const obj1 = cell[i];

for(let j=i+1; j < length; j++) {

const obj2 = cell[j];

const hit = this._detector.detectCollision(obj1, obj2);

if(hit) {

obj1.hit(obj2);

obj2.hit(obj1);

}

// 衝突オブジェクトリストと。

const objLength = objList.length;

const cellLength = cell.length;

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

const obj = objList[i];

for(let j=0; j<cellLength; j++) {

const cellObj = cell[j];

const hit = this._detector.detectCollision(obj, cellObj);

if(hit) {

obj.hit(cellObj);

cellObj.hit(obj);

}

// レンダリング。

render(context) {

this._actors.forEach((a) => {

a.render(context);

});

}

// Worldを作る。サイズは500x500ぐらいで。

const worldSize = 500;

const world = new World(worldSize, worldSize);

// Wolrd内にRectangleActorをランダム配置。

const actors = 1000;

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

const x = Math.random() * worldSize;

const y = Math.random() * worldSize;

const rect = new RectangleActor(x, y, 10, 10);

world.addActor(rect);

}

// canvasの設置。

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

canvas.width = worldSize;

canvas.height = worldSize;

const context = canvas.getContext('2d');

document.body.appendChild(canvas);

// 時間表示の設置。

const timeCounter = document.createElement('div');

document.body.appendChild(timeCounter);

// メインループ。

function loop(timestamp) {

// update()にかかる時間を測る。

const start = performance.now();

world.update();

const end = performance.now();

const timeStr = (end - start).toPrecision(4);

timeCounter.innerText = `${timeStr}ms`;

// 一度まっさらにしてからレンダリング。

context.clearRect(0, 0, worldSize, worldSize);

world.render(context);

// 次のフレームを要求する。

requestAnimationFrame((timestamp) => loop(timestamp));

}

// アニメーションを開始する。

requestAnimationFrame((timestamp) => loop(timestamp));

まとめ

当たり判定の最も素朴な実装は、総当たりでした。ですが、それではあまり速度が出ないということで、四分木を導入しました。しかし四分木の操作にもコストがかかります。できるだけ操作コストをゼロに近づけて、四分木のメリットだけを享受することを目標に最適化を進めました。

「モートン順序」を導入すれば、四分木の操作をできるだけ軽くできるということがわかりました。また、四分木を線形にすることで、簡単にアクセスできるようにしました。最後に、四分木の巡り方を工夫することで、巡る距離を最小に抑えました。

これらの最適化の結果、オブジェクト1000個の当たり判定において、20msもの短縮が実現できました。まだ細かい最適化の余地はあるものの、素晴らしい結果です。

最後に（バグ等を見つけたら）

一応頑張ってバグのチェックはしたつもりですが、これだけ複雑になると何かしら漏れがあるかもしれません。バグを見つけた場合は一人で悩まず、@kfurumiyaに相談してください。たぶん解決はしませんが、一緒に頭をかかえるぐらいならできると思います。

まずは素朴に実装してみる

当たり判定の作成

ゲームキャラクターの作成

当たり判定検出器を作る

Actorを配置する世界を作る

実際に動かしてみる

実行してみる

ここまでのコードまとめ

工夫して当たり判定を取る

空間を分割する

四分木のコスト

モートン順序

モートン順序は上位空間の情報を持つ

位置からモートン番号を割り出す

大きさのあるオブジェクトの番号算出

線形四分木

ここまでを実装する

線形四分木の巡り方

線形四分木を使った当たり判定を実装する

実行してみる

ここまでのコード

まとめ

最後に（バグ等を見つけたら）

関連

JavaScriptで気楽に始めるオブジェクト指向プログラミング

Web Workersを用いてJavaScriptをマルチスレッド化する

JavaScriptの関数で何ができるのか、もう一度考える

まずは素朴に実装してみる

当たり判定の作成

ゲームキャラクターの作成

当たり判定検出器を作る

Actorを配置する世界を作る

実際に動かしてみる

実行してみる

ここまでのコードまとめ

工夫して当たり判定を取る

空間を分割する

四分木のコスト

モートン順序

モートン順序は上位空間の情報を持つ

位置からモートン番号を割り出す

大きさのあるオブジェクトの番号算出

線形四分木

ここまでを実装する

線形四分木の巡り方

線形四分木を使った当たり判定を実装する

実行してみる

ここまでのコード

まとめ

最後に（バグ等を見つけたら）

共有:

関連

JavaScriptで気楽に始めるオブジェクト指向プログラミング

Web Workersを用いてJavaScriptをマルチスレッド化する

JavaScriptの関数で何ができるのか、もう一度考える