空間ハッシュ

ひとことで

空間を同じ大きさのセルに分け、セルの座標から計算したハッシュ値を番号にして、物体を入れ物（バケツ）に分けておく方法です。ある場所の近くにいる物体を探すときは、その場所のセルと周りのセルの入れ物だけを見ればよいので、全部の物体と距離を比べずに済みます。セルの数が無限でも、使う表の大きさは物体の数に合わせて決められるのが、ふつうの格子との違いです。

ゲームでの使いどころ

• 粒子シミュレーション：SPH や位置ベースの流体で、影響半径の中の隣の粒子を毎フレーム探す。GPU でも使われる定番。
• 群れ・群衆：ボイドや群衆の、近くの仲間を探す処理。
• 広域判定：大きさのそろった多数の物体（弾、破片、敵の群れ）の、衝突しそうな組を探す。
• 広い世界の管理：果てのないマップで、近くのチャンクや物体を座標から引く。

しくみ

1. セルを決める：セルの一辺 $h$ を、探す半径（粒子の影響半径）と同じにします。物体の位置 $(x, y)$ のセルは $(\lfloor x/h \rfloor, \lfloor y/h \rfloor)$ です。
2. ハッシュ：セルの座標を、表の番号へ写します。よく使われるのは、大きな素数を掛けて排他的論理和を取る方法です。

3. 入れる：各物体を、そのセルのハッシュ値の入れ物に入れます。
4. 探す：探す点のセルと、周りの 8 つのセル（3 次元なら 26）の入れ物の中の物体だけ、距離を比べます。セルの一辺が半径と同じなので、半径の中の物体は必ずこの 9 セルのどれかにいます。

表の大きさ $T$ が小さいと、離れたセルが同じ入れ物に入る「衝突」が起き、余計な物体を比べることになります（答えは変わりませんが遅くなります）。

数え上げソートで作る：毎フレーム作り直すときは、入れ物ごとの数を数え、累積和で置き場所を決め、物体の番号を 1 本の配列に並べます。リストを動的に作らずに済み、GPU でもそのまま使えます。

実装のポイント

• 表の大きさ：物体の数の 2 倍程度の大きさにすると、衝突が少なくなります。表の大きさを 2 のべき乗にするときは、ハッシュ値の下位ビットがよく混ざっているか確かめます。
• 同じ入れ物を 2 回見ない：周りのセルどうしが衝突して同じ入れ物になることがあるので、見た入れ物を覚えておきます。
• 物体の大きさがばらばら：大きな物体は複数のセルにまたがります。すべてのセルに登録するか、大きさごとに別のセルの大きさの表を使います。
• 並べ替えの副作用：物体の配列そのものをセル順（ハッシュ順）に並べ替えておくと、近くの物体がメモリ上でも近くなり、キャッシュの効きが良くなります（モートン符号と同じ効果）。

つまずきやすい点

• セルが大きすぎる・小さすぎる：大きすぎると 1 つのセルに物体が多く入り、比べる数が増えます。小さすぎると、調べるセルの数が増えます。探す半径と同じが基本です。
• 負の座標：$\lfloor x/h \rfloor$ は負の座標で負の整数になります。ハッシュの計算で負の数の剰余を正しく扱います。
• 物体が 1 か所に集まる：すべての物体が 1 つのセルに集まると、結局全部と比べることになります。密度の偏りが大きい場合は、木構造の方が向いています。

デモで試すこと

1. 1200 個の粒子が動き回っています。黄色の枠は、探す点のセルと周りの 8 つのセルです。緑が半径の中の粒子、水色が距離を比べたが外にいた粒子です。
2. 左下で、総当たりの 1200 個に対して、比べた候補がずっと少ないことを確かめてください。カーソルを動かすと、探す点が変わります。
3. 「ハッシュ表の大きさ」を小さくすると、離れた場所の粒子が同じ入れ物に入り（赤）、余計な候補が増えます。
4. 「セルの線を表示」で、セルの大きさが探す半径と同じであることを確かめてください。