This explanation is currently available in Japanese.
ひとことで
空間を同じ大きさのセルに分け、セルの座標から計算したハッシュ値を番号にして、物体を入れ物（バケツ）に分けておく方法です。ある場所の近くにいる物体を探すときは、その場所のセルと周りのセルの入れ物だけを見ればよいので、全部の物体と距離を比べずに済みます。セルの数が無限でも、使う表の大きさは物体の数に合わせて決められるのが、ふつうの格子との違いです。
ゲームでの使いどころ
- 粒子シミュレーション：SPH や位置ベースの流体で、影響半径の中の隣の粒子を毎フレーム探す。GPU でも使われる定番。
- 群れ・群衆：ボイドや群衆の、近くの仲間を探す処理。
- 広域判定：大きさのそろった多数の物体（弾、破片、敵の群れ）の、衝突しそうな組を探す。
- 広い世界の管理：果てのないマップで、近くのチャンクや物体を座標から引く。
しくみ
- セルを決める：セルの一辺 を、探す半径（粒子の影響半径）と同じにします。物体の位置 のセルは です。
- ハッシュ：セルの座標を、表の番号へ写します。よく使われるのは、大きな素数を掛けて排他的論理和を取る方法です。
- 入れる：各物体を、そのセルのハッシュ値の入れ物に入れます。
- 探す：探す点のセルと、周りの 8 つのセル（3 次元なら 26）の入れ物の中の物体だけ、距離を比べます。セルの一辺が半径と同じなので、半径の中の物体は必ずこの 9 セルのどれかにいます。
表の大きさ が小さいと、離れたセルが同じ入れ物に入る「衝突」が起き、余計な物体を比べることになります（答えは変わりませんが遅くなります）。
数え上げソートで作る：毎フレーム作り直すときは、入れ物ごとの数を数え、累積和で置き場所を決め、物体の番号を 1 本の配列に並べます。リストを動的に作らずに済み、GPU でもそのまま使えます。
実装のポイント
- 表の大きさ：物体の数の 2 倍程度の大きさにすると、衝突が少なくなります。表の大きさを 2 のべき乗にするときは、ハッシュ値の下位ビットがよく混ざっているか確かめます。
- 同じ入れ物を 2 回見ない：周りのセルどうしが衝突して同じ入れ物になることがあるので、見た入れ物を覚えておきます。
- 物体の大きさがばらばら：大きな物体は複数のセルにまたがります。すべてのセルに登録するか、大きさごとに別のセルの大きさの表を使います。
- 並べ替えの副作用：物体の配列そのものをセル順（ハッシュ順）に並べ替えておくと、近くの物体がメモリ上でも近くなり、キャッシュの効きが良くなります（モートン符号と同じ効果）。
つまずきやすい点
- セルが大きすぎる・小さすぎる：大きすぎると 1 つのセルに物体が多く入り、比べる数が増えます。小さすぎると、調べるセルの数が増えます。探す半径と同じが基本です。
- 負の座標： は負の座標で負の整数になります。ハッシュの計算で負の数の剰余を正しく扱います。
- 物体が 1 か所に集まる：すべての物体が 1 つのセルに集まると、結局全部と比べることになります。密度の偏りが大きい場合は、木構造の方が向いています。
デモで試すこと
- 1200 個の粒子が動き回っています。黄色の枠は、探す点のセルと周りの 8 つのセルです。緑が半径の中の粒子、水色が距離を比べたが外にいた粒子です。
- 左下で、総当たりの 1200 個に対して、比べた候補がずっと少ないことを確かめてください。カーソルを動かすと、探す点が変わります。
- 「ハッシュ表の大きさ」を小さくすると、離れた場所の粒子が同じ入れ物に入り（赤）、余計な候補が増えます。
- 「セルの線を表示」で、セルの大きさが探す半径と同じであることを確かめてください。