5：当たり判定を最適化する
当たり判定を最適化する
（2019.2.03執筆）
今回は、当たり判定部分の最適化に挑戦したいと思います。コアとなるゲームエンジン部分（engine.js）のカスタマイズ、 初期状態では矩形（まっすぐの長方形）のみ取り扱ってましたが（計算処理が早いらしい）、他にも円や線などを取り扱えたら良いですね（処理が複雑になるか？）、まぁゆくゆく拡張できればいいかな。って下準備程度に改良。それと当たり判定の最適化について。人間が分かりやすい記述のままだと、ゲームの処理速度が動作に支障をきたすくらい大変なようです。より効率的に当たり判定をとれるよう、古都さんのコラムを見ながら実装していきたいと思います。とてもむずかしい（o _ o。） こぴぺで何とか。理解しながら、動けば御の字でしょうか。
当たり判定を効率的に取る...以下のコラムについて実践してみます。。
参考 ⇒ JavaScriptで大量のオブジェクトの当たり判定を効率的にとる（sbfl.net）
Colliderクラスの実装
当たり判定は、これまで全てRectangleクラスに任せていました。Rectangleクラスは、画像の切り抜き、そしてhitAreaの当たり判定で使用していましたが、hitAreaで当たり判定を取るのは専用のColliderクラスにします、役割を切り分けます。engine.js ⇒ 最初の方に追加
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;
}
get top() { return this.y; }
get bottom() { return this.y + this.height; }
get left() { return this.x; }
get right() { return this.x + this.width; }
}
一方で最初から入ってた普通のRectangleクラスの設定から、当たり判定の式を削除します。
class Rectangle {
constructor(x, y, width, height) {//左上開始位置（x座標、y座標）と、大きさ（幅、高さ）を持つ矩形オブジェクトの定義 当たり判定なし
this.x = x;
this.y = y;
this.width = width;
this.height = height;
}
}
当たり判定の総まとめクラスを用意することで、すんなり解決しました。
同じく、engine.jsに追記します。
Colliderクラス群の下くらいに記述すると分かりやすいかな？
engine.jsに追記 ⇒ CollisionDetectorクラス
class CollisionDetector {
detectCollision(actor1, actor2) {
const c1 = actor1.hitArea;
const c2 = actor2.hitArea;
if(c1.type == 'rectangle' && c2.type=='rectangle') { //両方矩形なら、矩形同士の衝突判定式を
return this.deRectRect(c1, c2);
}
return false;
}
deRectRect(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); //両方の条件が一致すれば接触判定
}
}
ここで作ったCollisionDetectorを通じることで、矩形同士だけでなく、円と円、円と矩形、線、点、楕円、といった異なるオブジェクト同士の当たり判定を実装できるようになるでしょう（計算式が面倒になるかもしれんが）
さて、各シーンクラスに使われる当たり判定を、CollisionDetectorクラスを通じて任せることができれば、一通りの基礎ができあがることになります。
engine.js ⇒ Sceneクラスの追記と修正
class Scene extends EventDispatcher {//Actorをまとめあげる舞台の役割、シーンの定義
constructor(name, backgroundColor, renderingTarget) {
super();
this.name = name;
this.backgroundColor = backgroundColor;
this.actors = [];
this.renderingTarget = renderingTarget;
this._detector = new CollisionDetector(); //⇒ここを追加
this._destroyedActors = [];
}
_hitTest() {//当たり判定を処理する
const length = this.actors.length;
for(let i=0; i < length - 1; i++) {
for(let j=i+1; j < length; j++) {
const obj1 = this.actors[i];
const obj2 = this.actors[j];
const hit = this._detector.detectCollision(obj1, obj2); //⇒ ここを修正
if(hit) {
obj1.dispatchEvent('hit', new GameEvent(obj2));
obj2.dispatchEvent('hit', new GameEvent(obj1));
}
}
}
}
これでSceneクラスの修正はOKかな。
後はdanmaku.jsの各Actorに割り当てたhitAreaのクラスをnew RectangleColliderに書き換えましょう。
danmaku.js ⇒ hitArea部分の修正
class Player extends SpriteActor {
constructor(x, y) {
const sprite = new Sprite(assets.get('player'), new Rectangle(32, 96, 32, 32));
const hitArea = new RectangleCollider(6, 4, 20, 28); //⇒ここを修正
super(x, y, sprite, hitArea);
class PlayerAction extends Actor {
constructor(x, y, dir) {
const hitArea = new RectangleCollider(0, 0, 32, 32); //⇒ここを修正
super(x, y, hitArea, ['playerAction']);
class NPC extends SpriteActor {
constructor(x, y) {
const sprite = new Sprite(assets.get('npc1'), new Rectangle(32, 0, 32, 32));
const hitArea = new RectangleCollider(0, 0, 32, 32); //⇒ここを修正
super(x, y, sprite, hitArea, ['npc']);
class TextLabel extends Actor {
constructor(x, y, text, color, size) {
if (color===undefined) color="#555";
if (size===undefined) size = 16;
const hitArea = new RectangleCollider(-1, -1, 0, 0);
super(x, y, hitArea);
class MessageWindow extends Actor {
constructor(messages, color, size) {
if (color===undefined) color="#555";
if (size===undefined) size = 16;
const hitArea = new RectangleCollider(-1, -1, 0, 0);
super(0, 0, hitArea);
これで一通りの流れが繋がりました。ゲームが動くかどうか確かめます。
⇒ デモを確認してみましょう。
無事に動きました。CollisionDetectorによる当たり判定が無事に動いてます。ぱちぱち＝
では、当たり判定の形状クラスを拡張してみる。円を描きますか。
CircleColliderクラスと当たり判定の実装
当たり判定に、矩形だけでなく円も扱えるようにします。まず円形の当たり判定としてCircleColliderクラスを定義してみましょう。
engine.js ⇒ CircleColliderクラスの定義
class CircleCollider extends Collider { //当たり判定を円形で使うクラス
constructor(x, y, radius) { //中心点（x,y）の座標と、半径radiusを持つ円の定義
super('circle', x, y);
this.radius = radius;
}
}
では次、CollisionDetectorに円形同士の当たり判定式を取り入れてみます。
engine.js ⇒ CollisionDetectorクラスに追記
class CollisionDetector {
detectCollision(actor1, actor2) {
const c1 = actor1.hitArea;
const c2 = actor2.hitArea;
if(c1.type == 'rectangle' && c2.type=='rectangle') { //矩形なら、矩形同士の衝突判定式を
return this.deRectRect(c1, c2);
}
if(c1.type == 'circle' && c2.type=='circle') { //円なら、円同士の衝突判定式を
return this.deCircleCircle(c1, c2);
}
return false;
}
deRectRect(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); //両方で接触判定
}
deCircleCircle(circle1, circle2) { //円同士の衝突判定式、中心と中心の距離、xの差、yの差を用いた三平方の定理で求める
const dx = circle1.x - circle2.x; //水平方向の距離
const dy = circle1.y - circle2.y; //鉛直方向の距離
const dr = circle1.radius + circle2.radius; //斜辺の長さ = 半径の和
return ( dr*dr > dx*dx + dy*dy ); //斜辺の累乗 > 水平距離の累乗 + 垂直距離の累乗 なら、接触判定trueで返す
}
}
⇒ 円同士の当たり判定を行うには
試しに、hitAreaに使用するクラスを、先ほど作ったCircleColliderに変更してみます。
danmaku.js ⇒ hitArea部分を円形に
class Player extends SpriteActor {
constructor(x, y) {
const sprite = new Sprite(assets.get('player'), new Rectangle(32, 96, 32, 32));
const hitArea = new CircleCollider(16, 16, 16); //⇒ここを変更
super(x, y, sprite, hitArea);
class PlayerAction extends Actor {
constructor(x, y, dir) {
const hitArea = new CircleCollider(16, 16, 16); //⇒ここを変更
super(x, y, hitArea, ['playerAction']);
this._dir = dir;
}
render(target) {//オーバーライドしたrenderメソッドで、アクション範囲を可視化してみる
const context = target.getContext('2d');
const rect = this.hitArea;
context.fillStyle = "rgba(255,255,255,0.7)"; //半透明の白で塗りつぶす
context.arc(rect.x, rect.y, rect.radius, 0, Math.PI*2, false); //⇒ここを円の描画に変更
context.fill();
}
update(gameInfo, input) {
this.destroy();
}
}
class NPC extends SpriteActor {
constructor(x, y) {
const sprite = new Sprite(assets.get('npc1'), new Rectangle(32, 0, 32, 32));
const hitArea = new CircleCollider(16, 16, 16); //⇒ここを変更
super(x, y, sprite, hitArea, ['npc']);
⇒ 円形の当たり判定をデモで確認。
おっと＿？！ 円の当たり判定は無事にできてるので良しとします。
しかし円の描画が初期化されないぞ？？ どういうことだ。。。？ 調べてみた。
⇒ JS初心者がCanvasを使っていたらぶち当たった壁
なるほど、円の描画のときは最初に、context.beginPath();だ。
class PlayerAction extends Actor {
constructor(x, y, dir) {
const hitArea = new CircleCollider(16, 16, 16); //⇒ここを変更
super(x, y, hitArea, ['playerAction']);
this._dir = dir;
}
render(target) {//オーバーライドしたrenderメソッドで、アクション範囲を可視化してみる
const context = target.getContext('2d');
const rect = this.hitArea;
context.beginPath(); //⇒ 忘れないように
context.fillStyle = "rgba(255,255,255,0.7)"; //半透明の白で塗りつぶす
context.arc(rect.x, rect.y, rect.radius, 0, Math.PI*2, false); //⇒ここを円の描画に変更
context.fill();
}
update(gameInfo, input) {
this.destroy();
}
}
では次に、円形と矩形の当たり判定を実装してみましょう。
円形＆矩形の当たり判定を実装する
ちょっと大変ですが、CollisionDetectorクラスに円形＆矩形の当たり判定を実装してみます。参考 ⇒ 円と長方形の当たり判定
engine.js ⇒ CollisionDetectorクラスの修正
class CollisionDetector {
detectCollision(actor1, actor2) {
const c1 = actor1.hitArea;
const c2 = actor2.hitArea;
if(c1.type == 'rectangle' && c2.type=='rectangle') { //矩形なら、矩形同士の衝突判定式を
return this.deRectRect(c1, c2);
}
if(c1.type == 'circle' && c2.type=='circle') { //円なら、円同士の衝突判定式を
return this.deCircleCircle(c1, c2);
}
if(c1.type == 'rectangle' && c2.type=='circle') { //矩形と円同士の衝突判定式を
return this.deRectCircle(c1, c2);
}
if(c1.type == 'circle' && c2.type=='rectangle') { //円と矩形同士の衝突判定式を
return this.deRectCircle(c2, c1);
}
return false;
}
deRectRect(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); //両方の条件が一致すれば接触判定
}
deCircleCircle(circle1, circle2) { //円同士の衝突判定式、中心と中心の距離、xの差、yの差を用いた三平方の定理で求める
const dx = circle1.x - circle2.x; //水平方向の距離
const dy = circle1.y - circle2.y; //鉛直方向の距離
const dr = circle1.radius + circle2.radius; //斜辺の長さ = 半径の和
return ( dr*dr > dx*dx + dy*dy ); //斜辺の累乗 > 水平距離の累乗 + 垂直距離の累乗 なら、接触判定trueで返す
}
deRectCircle(rect, circle) { //矩形と円の衝突判定式
const topRC = rect.top - circle.radius; //y軸トップの境界（矩形のトップに、円の半径分を足す）
const bottomRC = rect.bottom + circle.radius; //y軸ボトムの境界（矩形のボトムに、円の半径分を足す）
const leftRC = rect.left - circle.radius; //x軸左の境界（矩形の左端から、円の半径分を足す）
const rightRC = rect.right + circle.radius; //x軸右の境界（矩形の右端に、円の半径分を足す）
if (topRC < circle.y && bottomRC > circle.y && rect.left < circle.x && rect.right > circle.x) {return true;} //矩形の上下境界の間に円の中心点yが重なり、かつ矩形のx軸間に中心点xがあるなら接触
if (rect.top < circle.y && rect.bottom > circle.y && leftRC < circle.x && rightRC > circle.x) {return true;} //矩形の左右境界の間に円の中心点xが重なり、かつ矩形のy軸間に中心点yがあるなら接触
const topRC2 = Math.pow( rect.top - circle.y ,2); //三平方の定理に使う top
const bottomRC2 = Math.pow( rect.bottom - circle.y ,2); //三平方の定理に使う bottom
const leftRC2 = Math.pow( rect.left - circle.x ,2); //三平方の定理に使う left
const rightRC2 = Math.pow( rect.right - circle.x ,2); //三平方の定理に使う right
const radius2 = circle.radius * circle.radius; //円の半径の累乗
if ( topRC2 + leftRC2 < radius2 || bottomRC2 + leftRC2 < radius2 || topRC2 + rightRC2 < radius2 || bottomRC2 + rightRC2 < radius2 ) {return true;} //矩形の四隅の点と、円との衝突判定
else {return false;} //３つとも判定が無ければ当たってない。
}
}
⇒ ここまでのデモを確認してみる。
無事に矩形と円形の衝突判定が実装できました。
次に当たり判定の高速処理に挑戦するための、計測器を付けましょう。
処理スピードを可視化する
古都さんのコードを参考に、前もって処理スピードを測る機能を記述しておきます。danmaku.js の最後の方に追加 ⇒ スピードメーターの実装
const timeCounter = document.createElement('div'); //⇒ ここを追加
assets.addImage('sprite', 'sprite.png');
assets.addImage('player', 'chara_player.png');
assets.addImage('npc1', 'chara_npc1.png');
assets.loadAll().then((a) => {
const game = new DanamkuStgGame();
document.body.appendChild(game.screenCanvas);
document.body.appendChild(timeCounter); //⇒ ここを追加
game.start();
});
engine.js に追記 ⇒ _loop(timestamp)内
_loop(timestamp) {
const start = performance.now(); //⇒ ここを追加
const elapsedSec = (timestamp - this._prevTimestamp) / 1000;
const accuracy = 0.9; // あまり厳密にするとフレームが飛ばされることがあるので
const frameTime = 1 / this.maxFps * accuracy; // 精度を落とす
if(elapsedSec <= frameTime) {
requestAnimationFrame(this._loop.bind(this));
return;
}
this._prevTimestamp = timestamp;
this.currentFps = 1 / elapsedSec;
const screenRectangle = new Rectangle(0, 0, this.width, this.height);
const info = new GameInformation(this.title, screenRectangle,
this.maxFps, this.currentFps);
const input = this._inputReceiver.getInput();
this.currentScene.update(info, input);
const end = performance.now(); //⇒ ここを追加
const timeStr = (end - start).toPrecision(4); //⇒ ここを追加
timeCounter.innerText = `${timeStr}ms`; //⇒ ここを追加
requestAnimationFrame(this._loop.bind(this));
}
開発環境に便利ですね.｡.:*･
矩形アクターをバラまいてみる
このままだと計測しづらいので、アクターを増やしてみましょう。danmaku.js ⇒ 矩形アクタークラスの作成
class RectangleActor extends Actor {
constructor(x, y, width, height) {
const hitArea = new RectangleCollider(0, 0, width, height);
super(x, y, hitArea, ['spirit']);
this.width = width;
this.height = height;
this._color = null;
this._vx = Math.random() * 10 - 5;
this._vy = Math.random() * 10 - 5;
this.addEventListener('hit', (e) => this._color = 'rgba(0, 255, 0, 0.9)' );
}
update(gameInfo, input) {
this._color = 'rgb(0, 0, 0)';
this.x += this._vx;
this.y += this._vy;
if(this.x < 0 || this.x > gameInfo.screenRectangle.width) { this._vx = -this._vx; }
if(this.y < 0 || this.y > gameInfo.screenRectangle.height) { this._vy = -this._vy; }
}
render(target) {
const context = target.getContext('2d');
context.fillStyle = this._color;
context.fillRect(this.x, this.y, this.width, this.height);
}
}
矩形アクタークラスをメインシーンに追加
class DanmakuStgMainScene extends Scene {
constructor(renderingTarget) {
super('メイン', 'black', renderingTarget);
const npc = new NPC(150, 100);
const player = new Player(150, 200);
this.add(npc);
this.add(player);
// ~~
//ここから追加
const actors = 100;
for(let i=0; i < actors; i++) {
const x = Math.random() * 512;
const y = Math.random() * 384;
const rect = new RectangleActor(x, y, 10, 10);
this.add(rect);
}//ここまで
}
}
驚いた、なかなか綺麗ですね。
今度はアクターを円形に変更してみましょう。
円形アクターをバラまいてみる
円形アクタークラスを作成して、先ほどのメインシーン追加分を置き換えます。danmaku.js ⇒ 円形アクタークラスの作成
class CircleActor extends Actor {
constructor(x, y, radius) {
const hitArea = new CircleCollider(radius, radius, radius);
super(x, y, hitArea, ['spirit']);
this.radius = radius;
this._color = null;
this._vx = Math.random() * 10 - 5;
this._vy = Math.random() * 10 - 5;
this.addEventListener('hit', (e) => this._color = 'rgba(0, 255, 0, 0.9)' );
}
update(gameInfo, input) {
this._color = 'rgb(0, 0, 0)';
this.x += this._vx;
this.y += this._vy;
if(this.x < 0 || this.x > gameInfo.screenRectangle.width) { this._vx = -this._vx; }
if(this.y < 0 || this.y > gameInfo.screenRectangle.height) { this._vy = -this._vy; }
}
render(target) {
const context = target.getContext('2d');
context.fillStyle = this._color;
context.beginPath();
const rect = this.hitArea;
context.arc(rect.x, rect.y, rect.radius, 0, Math.PI*2, false);
context.fill();
}
}
円形アクタークラスをメインシーンに追加
class DanmakuStgMainScene extends Scene {
constructor(renderingTarget) {
super('メイン', 'black', renderingTarget);
const npc = new NPC(150, 100);
const player = new Player(150, 200);
this.add(npc);
this.add(player);
// ~~
//ここから追加
const actors = 100;
for(let i=0; i < actors; i++) {
const x = Math.random() * 512;
const y = Math.random() * 384;
const circle = new CircleActor(x, y, 5);
this.add(circle);
}//ここまで
}
}
円形を組み込むと、判定処理にかかる時間が倍になってる感じでしょうか。
じゃあ今度は、飾りのアクターを矩形５０個，円形５０個に振り分けてみます。
矩形と円形のアクタークラスをメインシーンに追加
class DanmakuStgMainScene extends Scene {
constructor(renderingTarget) {
super('メイン', 'black', renderingTarget);
const npc = new NPC(150, 100);
const player = new Player(150, 200);
this.add(npc);
this.add(player);
// ~~
//ここから追加
const actorsR = 50;
for(let i=0; i < actorsR; i++) {
const x = Math.random() * 512;
const y = Math.random() * 384;
const rect = new RectangleActor(x, y, 10, 10);
this.add(rect);
}
const actorsC = 50;
for(let i=0; i < actorsC; i++) {
const x = Math.random() * 512;
const y = Math.random() * 384;
const circle = new CircleActor(x, y, 5);
this.add(circle);
}//ここまで
}
}
同じアクター数の場合、円形より矩形の比率が多くなるほど、処理時間が軽減されるようですね。 つまり、基本的には矩形アクターで衝突判定するほうが負担は少ない、ということで。体感しました。
それではとうとう本題です。
当たり判定の最適化に、四分木と呼ばれるものを導入してみます。
4分木空間分割による当たり判定の効率化
私にはコードの記述がさっぱりわかりません。できることは、既存コードを組み込んで調整するくらいです。 詳しい解説は、古都さんのコラムや、こちらのサイトを読んだほうが良いと思う。⇒ JavaScriptで大量のオブジェクトの当たり判定を効率的にとる（sbfl.net）
⇒ 4分木空間分割を最適化する！（理屈編）
実装してみた後のサンプルコードはあとがきに載せます(' '*)
めちゃ長い。先にデモのリンクを貼るか。。。
⇒ 四分木実装後のデモを確認してみる。
さて、結果としては一見「？良くなったのかな？」です。 それぞれのアクター数を増やして比べるほど、なるほど若干早くなったというのが分かります！ ただ各アクターサイズを大きくするほど、どうも振り分けコストが無駄になるようで、パフォーマンスが低下した。
色々数値をいじると、四分木にする強みが何処なのか見えてくるような気がします。
四分岐による当たり判定の特徴
体感できたのは、空間のサイズに対して、各アクターが小さくなるほど四分木の恩恵が増える。（逆に各アクターサイズの比が大きくなるほど四分木の効果は微妙になる。） アクターの数が多くなるほど、四分岐の効果が反映されやすくなる。といった感じでした。もっと広大なマップになって、相対的なアクターのサイズ比が小さくなった場合に、四分木の当たり判定が威力を発揮するかもしれません。
またこの事から、各シーンのマップサイズに応じて、空間分割レベルを調整してあげるといいかもしれません。(試してません） ひとまず中断、また必要に応じたタイミングで詰めていきます。
古都さんのアドバイスより
古都さんに確認していただいて、以下のアドバイスを頂きました。四分木の速度の問題ですが、高速にするための前処理の時間もゼロではないので、前処理だけでそこそこ時間を食います。 これをオーバーヘッドと言います。今回だと空間へのオブジェクトの振り分けとかですね。
当たり判定の場合はオブジェクト数が少ないとオーバーヘッドの方が大きくなる可能性があります。 また、今回は形状による分岐も入ったので、そのあたりも影響しているのでしょう。
四分木による当たり判定の特徴として、「高速になる」というよりも「遅くなりにくい」というのがあります。 処理の無駄（オーバーヘッド）は多いかもしれないですが、1000個とか2000個の当たり判定になっても速度の低下は極めてゆるやかになります。 一方で数が少ないとシンプルな当たり判定に負ける……という現象が起こります。
なるほど、四分木は判定の高速化ではなく「遅くなりにくくする！」処置だったのですね。
それから形状による分岐も影響してるかもとの事。今回は矩形と円形だけの判定でした。
修正前はpointクラスみたいとかも入れて６種類くらい形状の振り分けをしてました。此処で時間を食ってたのかも？？ 使うアクターの形状を想定して、よく使う順番に判定式を置いて行くと良いのかも。と勝手に考えました。
それからマップに配置する地形や背景オブジェクト同士は、絶対に衝突しないことが分かっています。
ColliderクラスにisObj=true ? true:false;な感じの判定も加えてみよう。
Colliderクラスの改良
class Collider { //当たり判定に使うクラスの元
constructor(type, x, y, isObj = false) {
this._type = type;
this.x = x;
this.y = y;
this.isObj = isObj; //背景オブジェクト同士の判定に利用
}
get type() { return this._type; }
}
当たり判定式の順番を考えた
class CollisionDetector {
detectCollision(actor1, actor2) {
const c1 = actor1;
const c2 = actor2;
if(c1.isObj == true && c2.isObj == true) { return false; } //背景オブジェ同士なら接触しない
if(c1.type == 'rectangle' && c2.type=='rectangle') { return this.deRectRect(c1, c2); } //矩形なら、矩形同士の衝突判定式を
if(c1.type == 'rectangle' && c2.type=='circle') { return this.deRectCircle(c1, c2); } //矩形と円同士の衝突判定式を
if(c1.type == 'circle' && c2.type=='rectangle') { return this.deRectCircle(c2, c1); } //円と矩形同士の衝突判定式を
if(c1.type == 'circle' && c2.type=='circle') { return this.deCircleCircle(c1, c2); } //円なら、円同士の衝突判定式を
return false;
}
矩形の判定式を優先して先に置いた。。。あ、もうアレですね。 最近のPCは処理速度がとても早いので、今は気にしないで大丈夫とのこと。
毎秒60fpsで動いてるフレーム、快適に動く上限が毎フレーム15とか16msくらいの判定でギリギリ。現状は1〜5msくらいで動いてるので、まだまだ余裕あります。
次回、「６：線分の当たり判定」につづきますよ。
⇒ JavaScriptでゲーム作り「５：当たり判定を最適化する」
すぺしゃるさんくす
https://sbfl.net/古都さん
JavaScriptで作る弾幕STGの基礎（フレームワーク）を使わせていただいてます。感謝！
ぴぽやさんもありがとう、キャラチップをお借りしています。
今回の差分は、主にengine.jsのカスタマイズです。
danmaku.js分まで載せると長くなるので、それは本文中で拾ってください。
engine.js修正後の全体ソースコード
'use strict';
class Collider { //当たり判定に使うクラスの元
constructor(type, x, y, isObj = false) {
this._type = type;
this.x = x;
this.y = y;
this.isObj = isObj; //背景オブジェクト同士の判定に利用
}
get type() { return this._type; }
}
class RectangleCollider extends Collider { //当たり判定を四角形で使うクラス
constructor(x, y, width, height, isObj) {
super('rectangle', x, y, isObj);
this.width = width;
this.height = height;
}
get top() { return this.y; }
get bottom() { return this.y + this.height; }
get left() { return this.x; }
get right() { return this.x + this.width; }
}
class CircleCollider extends Collider { //当たり判定を円形で使うクラス
constructor(x, y, radius, isObj) { //中心点（x,y）の座標と、半径radiusを持つ円の定義
super('circle', x, y, isObj);
this.radius = radius;
}
get top() { return this.y - this.radius; }
get bottom() { return this.y + this.radius; }
get left() { return this.x - this.radius; }
get right() { return this.x + this.radius; }
}
class CollisionDetector {
detectCollision(actor1, actor2) {
const c1 = actor1;
const c2 = actor2;
if(c1.isObj && c2.isObj) { return false; } //背景オブジェ同士なら接触しない
if(c1.type == 'rectangle' && c2.type=='rectangle') { return this.deRectRect(c1, c2); } //矩形なら、矩形同士の衝突判定式を
if(c1.type == 'rectangle' && c2.type=='circle') { return this.deRectCircle(c1, c2); } //矩形と円同士の衝突判定式を
if(c1.type == 'circle' && c2.type=='rectangle') { return this.deRectCircle(c2, c1); } //円と矩形同士の衝突判定式を
if(c1.type == 'circle' && c2.type=='circle') { return this.deCircleCircle(c1, c2); } //円なら、円同士の衝突判定式を
return false;
}
deRectRect(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); //両方の条件が一致すれば接触判定
}
deCircleCircle(circle1, circle2) { //円同士の衝突判定式、中心と中心の距離、xの差、yの差を用いた三平方の定理で求める
const dx = circle1.x - circle2.x; //水平方向の距離
const dy = circle1.y - circle2.y; //鉛直方向の距離
const dr = circle1.radius + circle2.radius; //斜辺の長さ = 半径の和
return ( dr*dr > dx*dx + dy*dy ); //斜辺の累乗 > 水平距離の累乗 + 垂直距離の累乗 なら、接触判定trueで返す
}
deRectCircle(rect, circle) { //矩形と円の衝突判定式
const topRC = rect.top - circle.radius; //y軸トップの境界（矩形のトップに、円の半径分を足す）
const bottomRC = rect.bottom + circle.radius; //y軸ボトムの境界（矩形のボトムに、円の半径分を足す）
const leftRC = rect.left - circle.radius; //x軸左の境界（矩形の左端から、円の半径分を足す）
const rightRC = rect.right + circle.radius; //x軸右の境界（矩形の右端に、円の半径分を足す）
if (topRC < circle.y && bottomRC > circle.y && rect.left < circle.x && rect.right > circle.x) {return true;} //矩形の上下境界の間に円の中心点yが重なり、かつ矩形のx軸間に中心点xがあるなら接触
if (rect.top < circle.y && rect.bottom > circle.y && leftRC < circle.x && rightRC > circle.x) {return true;} //矩形の左右境界の間に円の中心点xが重なり、かつ矩形のy軸間に中心点yがあるなら接触
const topRC2 = Math.pow( rect.top - circle.y ,2); //三平方の定理に使う top
const bottomRC2 = Math.pow( rect.bottom - circle.y ,2); //三平方の定理に使う bottom
const leftRC2 = Math.pow( rect.left - circle.x ,2); //三平方の定理に使う left
const rightRC2 = Math.pow( rect.right - circle.x ,2); //三平方の定理に使う right
const radius2 = circle.radius * circle.radius; //円の半径の累乗
if ( topRC2 + leftRC2 < radius2 || bottomRC2 + leftRC2 < radius2 || topRC2 + rightRC2 < radius2 || bottomRC2 + rightRC2 < radius2 ) {return true;} //矩形の四隅の点と、円との衝突判定
else {return false;} //３つとも判定が無ければ当たってない。
}
}
//四分岐による空間分割、当たり判定に使うクラス
class LinearQuadTreeSpace {
constructor(width, height, level) {
this._width = width;
this._height = height;
this.data = [null];
this._currentLevel = 0;
while(this._currentLevel < level) {
this._expand();
}
}
clear() {
this.data.fill(null);
}
_addNode(node, level, index) {
const offset = ((Math.pow(4, level)) - 1) / 3;
const linearIndex = offset + index;
while(this.data.length <= linearIndex) {
this._expandData();
}
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);
}
addActor(actor) {
const collider = actor.hitArea;
const leftTopMorton = this._calc2DMortonNumber(collider.left, collider.top);
const rightBottomMorton = this._calc2DMortonNumber(collider.right, collider.bottom);
if(leftTopMorton === -1 && rightBottomMorton === -1) {
return;
}
if(leftTopMorton === rightBottomMorton) {
this._addNode(actor, this._currentLevel, leftTopMorton);
return;
}
const level = this._calcLevel(leftTopMorton, rightBottomMorton);
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 = ((Math.pow(4, (nextLevel+1))) - 1) / 3;
while(this.data.length < length) {
this.data.push(null);
}
this._currentLevel++;
}
_separateBit32(n) {
n = (n|(n<<8)) & 0x00ff00ff;
n = (n|(n<<4)) & 0x0f0f0f0f;
n = (n|(n<<2)) & 0x33333333;
return (n|(n<<1)) & 0x55555555;
}
_calc2DMortonNumber(x, y) {
if(x < 0 || y < 0) { return -1; }
if(x > this._width || y > this._height) { return -1; }
const xCell = Math.floor(x / (this._width / (Math.pow(2, this._currentLevel))));
const yCell = Math.floor(y / (this._height / (Math.pow(2, this._currentLevel))));
return (this._separateBit32(xCell) | (this._separateBit32(yCell)<<1));
}
_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 Rectangle {
constructor(x, y, width, height) {//左上開始位置（x座標、y座標）と、大きさ（幅、高さ）を持つ矩形オブジェクトの定義 当たり判定なし
this.x = x;
this.y = y;
this.width = width;
this.height = height;
}
}
class Sprite {//Rectangleに画像を当てはめる。画像と、画像のどの部分を使うか？の定義）
constructor(image, rectangle) {
this.image = image;
this.rectangle = rectangle;
}
}
class AssetLoader {//画像などを読み込むための箱、このクラスで画像ファイルを管理する
constructor() {
this._promises = [];
this._assets = new Map();
}
addImage(name, url) {
const img = new Image();
img.src = url;
const promise = new Promise((resolve, reject) =>//画像を完全に読み込んだ後に動作させるための記述
img.addEventListener('load', (e) => {
this._assets.set(name, img);
resolve(img);
}));
this._promises.push(promise);
}
loadAll() { return Promise.all(this._promises).then((p) => this._assets); }
get(name) { return this._assets.get(name); }
}
const assets = new AssetLoader();//画像ファイル管理棚のaseetsを作成...asetts[key].get(名前)で取り出せる
class EventDispatcher {//独自クラスでイベントを使うのに、仕組みを自作する
constructor() {
this._eventListeners = {};
}
addEventListener(type, callback) {//addEventListener(type, callback)でコールバック関数を登録
if(this._eventListeners[type] == undefined) {
this._eventListeners[type] = []; //追加イベントが見つからない場合、空の配列を用意
}
this._eventListeners[type].push(callback);
}
dispatchEvent(type, event) {//dispatchEvent(type, event)でコールバック関数（イベント）を実行する仕組みを記述
const listeners = this._eventListeners[type];
if(listeners != undefined) listeners.forEach((callback) => callback(event));
}
}
/*EventDispatcherの仕事は、コールバック関数を登録することと、
イベントが起こったときにコールバック関数を実行すること
余裕があればremoveEventListenerも実装するといいでしょう。
*/
class GameEvent {//EventDIspatcherから発火させるイベント用の定義？
constructor(target) {
this.target = target;
}
}
class Actor extends EventDispatcher {//EventDispatcherイベント発生関数を持つActorクラスの定義
constructor(x, y, hitArea, tags = []) {
super();
this.hitArea = hitArea;
this._hitAreaOffsetX = hitArea.x;
this._hitAreaOffsetY = hitArea.y;
this.tags = tags;
this.x = x;
this.y = y;
}
update(gameInfo, input) {}//動く仕組みを作る
render(target) {}//...線画処理
hasTag(tagName) {//タグは当たり判定などのときに使います
return this.tags.includes(tagName);
}
spawnActor(actor) {//他のActorを発生させるときに使用
this.dispatchEvent('spawnactor', new GameEvent(actor));
}
destroy() {//自身を破壊する、しかし関数で自身を消すことはできないので、イベントだけ発生させてより上位のクラスに実際の処理を任せる
this.dispatchEvent('destroy', new GameEvent(this));
}
get x() { return this._x; }//x座標を読み込む関数
set x(value) {//x座標にvalueを代入する関数
this._x = value;
this.hitArea.x = value + this._hitAreaOffsetX;
}
get y() { return this._y; }//y座標を読み込む関数
set y(value) {//y座標にvalueを代入する関数
this._y = value;
this.hitArea.y = value + this._hitAreaOffsetY;
}
}
class SpriteActor extends Actor {//画像を当てはめたActor
constructor(x, y, sprite, hitArea, tags=[]) {
super(x, y, hitArea, tags);
this.sprite = sprite;//画像
this.width = sprite.rectangle.width;//画像の幅
this.height = sprite.rectangle.height;//画像の高さ
}
render(target) {//オーバーライドしたrenderメソッドでは、canvasのdrawImageメソッドを使って自身を描画
const context = target.getContext('2d');
const rect = this.sprite.rectangle;
context.drawImage(this.sprite.image,
rect.x, rect.y,
rect.width, rect.height,
this.x, this.y,
rect.width, rect.height);
}
isOutOfBounds(boundRect) {//isOutOfBoundsメソッドはRectangleオブジェクトの外であるかどうかを判定
const actorLeft = this.x;
const actorRight = this.x + this.width;
const actorTop = this.y;
const actorBottom = this.y + this.height;
const horizontal = (actorRight < boundRect.x || actorLeft > boundRect.width);
const vertical = (actorBottom < boundRect.y || actorTop > boundRect.height);
return (horizontal || vertical);
}
}
class Input {//キー入力を保持するだけのクラス
constructor(keyMap, prevKeyMap) {
this.keyMap = keyMap;
this.prevKeyMap = prevKeyMap;
}
_getKeyFromMap(keyName, map) {
if(map.has(keyName)) {
return map.get(keyName);
} else {
return false;
}
}
_getPrevKey(keyName) {
return this._getKeyFromMap(keyName, this.prevKeyMap);
}
getKey(keyName) {
return this._getKeyFromMap(keyName, this.keyMap);
}
getKeyDown(keyName) {
const prevDown = this._getPrevKey(keyName);
const currentDown = this.getKey(keyName);
return (!prevDown && currentDown);
}
getKeyUp(keyName) {
const prevDown = this._getPrevKey(keyName);
const currentDown = this.getKey(keyName);
return (prevDown && !currentDown);
}
}
/*このクラスのオブジェクトがActorのupdateメソッドに渡されます。
やっていることは前回のキー入力と現在のキー入力を保持しているだけです。押下しているかどうかを判定をするgetKeyメソッド、キーを押し込んだかどうかを判定するgetKeyDownメソッド、キーを放したかどうかを判定するgetKeyUpメソッドがあります。
*/
class InputReceiver {//実際にキー入力を検知してInputクラスを生成するクラス
constructor() {
this._keyMap = new Map();
this._prevKeyMap = new Map();
addEventListener('keydown', (ke) => this._keyMap.set(ke.key, true));
addEventListener('keyup', (ke) => this._keyMap.set(ke.key, false));
}
getInput() {
const keyMap = new Map(this._keyMap);
const prevKeyMap = new Map(this._prevKeyMap);
this._prevKeyMap = new Map(this._keyMap);
return new Input(keyMap, prevKeyMap);
}
}
/*
ブラウザ上でキーを押すと、keydownイベント、keyupイベントが発生するのでそれを受け取って記録します。
getInputメソッドが呼び出されると、前回の入力と現在の入力を使って、Inputオブジェクトを作ります。
*/
class Scene extends EventDispatcher {//Actorをまとめあげる舞台の役割、シーンの定義
constructor(name, backgroundColor, renderingTarget) {
super();
this.name = name;
this.backgroundColor = backgroundColor;
this.actors = [];
this.renderingTarget = renderingTarget;
this._qTree = new LinearQuadTreeSpace(512, 384, 3);
this._detector = new CollisionDetector();
this._destroyedActors = [];
}
add(actor) {//Actorたちを保持する（追加・削除）
this.actors.push(actor);
actor.addEventListener('spawnactor', (e) => this.add(e.target));//spawnactorイベントが発生した場合はシーンにActorを追加
actor.addEventListener('destroy', (e) => this._addDestroyedActor(e.target));//destroyイベントが発生した場合はそのActorを削除
}
remove(actor) {
const index = this.actors.indexOf(actor);
this.actors.splice(index, 1);
}
changeScene(newScene) {//Sceneを変更します。ですがScene自身がSceneを変更することはできないので、Actorのときと同じようにイベントだけ発生させて、実際の処理は他のクラスに任せます
const event = new GameEvent(newScene);
this.dispatchEvent('changescene', event);
}
update(gameInfo, input) {//updateメソッドではシーンに登録されているActor全てを更新し、当たり判定を行い、描画します。描画の前に一度画面全体をクリアするのを忘れないで下さい。
this._updateAll(gameInfo, input);//Actorたちの動きを更新する
this._qTree.clear();
this.actors.forEach((a) => {
this._qTree.addActor(a);
});
this._hitTest();//当たり判定を処理する
this._disposeDestroyedActors();//死んだ役者リスト
this._clearScreen(gameInfo);//シーンの初期化、描画の前に一度画面全体をクリアする
this._renderAll();//再描画
}
_updateAll(gameInfo, input) {//Actorたちの動きを更新する
this.actors.forEach((actor) => actor.update(gameInfo, input));
}
_hitTest(currentIndex = 0, objList = []) {
const currentCell = this._qTree.data[currentIndex];
this._hitTestInCell(currentCell, objList);
let hasChildren = false;
for(let i = 0; i < 4; i++) {
const nextIndex = currentIndex * 4 + 1 + i;
const hasChildCell = (nextIndex < this._qTree.data.length) && (this._qTree.data[nextIndex] !== null);
hasChildren = hasChildren || hasChildCell;
if(hasChildCell) {
objList.push(...currentCell);
this._hitTest(nextIndex, objList);
}
}
if(hasChildren) {
const popNum = currentCell.length;
for(let i = 0; i < popNum; i++) { objList.pop(); }
}
}
_hitTestInCell(cell, objList) {
const length = cell.length;
const cellColliderCahce = new Array(length);
if(length > 0) { cellColliderCahce[0] = cell[0].hitArea; }
for(let i=0; i < length - 1; i++) {
const obj1 = cell[i];
const collider1 = cellColliderCahce[i];
for(let j=i+1; j < length; j++) {
const obj2 = cell[j];
let collider2;
if(i === 0) {
collider2 = obj2.hitArea;
cellColliderCahce[j] = collider2;
} else {
collider2 = cellColliderCahce[j];
}
const hit = this._detector.detectCollision(collider1, collider2);
if(hit) {
obj1.dispatchEvent('hit', new GameEvent(obj2));
obj2.dispatchEvent('hit', new GameEvent(obj1));
}
}
}
const objLength = objList.length;
const cellLength = cell.length;
for(let i=0; i obj.render(this.renderingTarget));
}
_addDestroyedActor(actor) {//死んだ役者リストに追加
this._destroyedActors.push(actor);
}
_disposeDestroyedActors() {//役者を消す
this._destroyedActors.forEach((actor) => this.remove(actor));//死んだ役者を消す
this._destroyedActors = [];//消した死んだ役者リストを空にする
}
}
class GameInformation {//ActorやSceneのupdateに渡すゲーム情報クラスを作りましょう。
constructor(title, screenRectangle, maxFps, currentFps) {
this.title = title;
this.screenRectangle = screenRectangle;
this.maxFps = maxFps;
this.currentFps = currentFps;
}
}
class Game {//いよいよ総まとめです！Gameクラスを作りましょう。Gameクラスはメインループを持ちます
constructor(title, width, height, maxFps) {
this.title = title;
this.width = width;
this.height = height;
this.maxFps = maxFps;
this.currentFps = 0;
this.screenCanvas = document.createElement('canvas');
this.screenCanvas.height = height;
this.screenCanvas.width = width;
this._inputReceiver = new InputReceiver();
this._prevTimestamp = 0;
console.log(`${title}が初期化されました。`);
}
changeScene(newScene) {
this.currentScene = newScene;
this.currentScene.addEventListener('changescene', (e) => this.changeScene(e.target));
console.log(`シーンが${newScene.name}に切り替わりました。`);
}
start() {
requestAnimationFrame(this._loop.bind(this));
}
_loop(timestamp) {
const start = performance.now();
const elapsedSec = (timestamp - this._prevTimestamp) / 1000;
const accuracy = 0.9; // あまり厳密にするとフレームが飛ばされることがあるので
const frameTime = 1 / this.maxFps * accuracy; // 精度を落とす
if(elapsedSec <= frameTime) {
requestAnimationFrame(this._loop.bind(this));
return;
}
this._prevTimestamp = timestamp;
this.currentFps = 1 / elapsedSec;
const screenRectangle = new Rectangle(0, 0, this.width, this.height);
const info = new GameInformation(this.title, screenRectangle,
this.maxFps, this.currentFps);
const input = this._inputReceiver.getInput();
this.currentScene.update(info, input);
const end = performance.now();
const timeStr = (end - start).toPrecision(4);
timeCounter.innerText = `${timeStr}ms`;
requestAnimationFrame(this._loop.bind(this));
}
}
/*
Gameクラスのループが始まるとSceneのupdateメソッドが呼びだされます。そしてSceneは各Actorのupdateを呼び出し……という仕組みでゲーム全体が動きます。
メインループにはrequestAnimationFrameを利用しています。これは次のフレームの描画タイミングのとき1回だけコールバック関数を呼び出してくれるものです。1回だけなので毎回呼び出さないといけません。
コールバック関数をbindしているのは、実行箇所によってthisが変わってしま うためです。これはJavaScript特有の問題です。
*/