HTML5:当たり判定のアレを色々実装

　隕石ドカドカ破壊STGを作るにあたって、自機のショットと隕石の当たり判定に結構な負荷がかかる……というのか、それともJavaScriptが遅いのか、うちのPCがしょぼいせいなのか定かではないものの、とにかく重くて遅延が発生することが判明した。

　自機の発射した弾一つ一つと、画面上にある30個以上ある隕石一つ一つとの当たり判定をしていることがきっと問題なんだろうなぁということはなんとなく察していた。

「自分の周りにあるやつとだけ当たり判定を取る」

なんてことが出来ればいいんだろうけど、はてさてどうしたものかというわけで、先人の知恵をお借りする事に。

　調査の結果「モートン順序」という物の考え方をすることで解決出来そうだった。モートン順序というのは画面を4分割して

＜図A＞
０┃１
─╂─
２┃３

Z字の順に番号を振る。この０〜３の中をさらに4分割にしてまた同じように番号を振る。

＜図B＞
０┃１┃４┃５
─╂─╂─╂─
２┃３┃６┃７
─╂─╂─╂─
８┃９┃12┃13
─╂─╂─╂─╂
10┃11┃14┃15

このZ字状に振った番号は、なんとも不思議な特性を持つ。

図Bの９番を2進数にすると　1001　となるが、この4桁の数字を2桁ずつ分けると

10　と　01　になる。これは→「２　と　１」という意味になるわけだが、これは

図Aの２の位置における1番目　を意味するのだ。

図Bの14　→　1110　→　11と10　→　図Aの3の2

　で、キャラクターの座標からこの順序が計算で出せる（ここはもっとクソ難しいので割愛）ので、座標が分かればこのどの辺に居るかわかるし、順序が分かればどのへんの座標にいるかわかる。

　すごい。すごすぎる。これを思いついた人の頭は一体どうなっているのか？　まったく恐ろしいわい。まず数字を一度2進数にするとか考えな……いやでもプログラマーなら考えない事も無いか？　ビットでフラグ管理とかするし……まぁでもすごいっす！

　ちなみに図Bで０と１の間に居るキャラは１つ上の階層の図Aの０として扱うし、図Aの０と１の間に居るキャラはさらに１つ上の階層の０として扱う。つまり、もし画面上の十字の位置にキャラが寄せ集まった場合は結局全部チェックする事になるわけだが、意図的に動かさない限りそんなことはまずないかなぁと思う。

　解説のページではここでさらに線形四分木というものでモートン順序に並べた衝突リストを管理していたのだが、

・データを参照するたびに４の何乗という掛け算をやる事への抵抗感
・大量の未使用メモリを作成する（と認識した）事への忌避感
・等比数列で並べる事について私が理解出来なかった（馬鹿でスマン）

　結局私は

Array = [
[[]],
[[],[],[],[]],
[[],[],[],[],
[],[],[],[],
[],[],[],[],
[],[],[],[]]
];

こんな配列を作って、Array[階層][モートン順序]の中に隕石のオブジェクトを入れるという形で衝突リストを取り扱う事にした。

　画面上にモートン順序を表示させる関数作ったり、自機が移動するごとにモートン順序計算して画面に表示させてみたり、実装するにあたってずいぶんと段階を踏んだ。ほんとよく実装出来たなと思う。

　現在画面上ではモートン順序を表示したり、隕石に配列番号を表示させたり、表示上の負荷は増しているはずなのに、ガクガクチラチラした感じがないので、おそらく軽量化に成功している……はず？


　元々は衝突リストに隕石の配列番号を入れていたのだが、隕石の破壊によって隕石を削除すると隕石の配列番号が変わるせいでundefineな数値を参照してしまうということがわかったので、オブジェクトそのものを入れて……というか、C言語的にいうとポインタ（変数のアドレス）を入れてるっていう形になっているのかなぁ？　とにかくこうすることによって隕石を削除すると衝突リストからも自動的に削除される事になり、エラーは出なくなった。

　で、このエラーだが、前の日記で書いたChromeのデベロッパー・ツールでconsoleを表示していなかったらわからなかった。本当にこれをやる前にConsoleについて知ってて良かったと思う。気付かずにずっと色々やったあとでこれを知ったら、わけのわからんエラーが大量に吐き出されて絶望していたに違いない。