IT用語集 › プログラミング › 空間ハッシュ
空間を一様なグリッドに刻み、各セルの座標をハッシュしてハッシュテーブルに入れることで、同じセルか隣のセルにある物体同士だけを判定対象にする手法。
衝突判定のブロードフェーズとしてはオクツリーと同じ役割を担うが、木の代わりにフラットなハッシュテーブルを使う。挿入が O(1) で軽く、何より、ワールドの大きさをあらかじめ決める必要がない。使われているセルにだけエントリができるため、疎な世界や果てのない世界でも、空のセルにメモリを浪費しない。
物体の大きさがほぼ揃っているときに最も効き、セルを物体に合わせて調整できる。大きさがばらつくと1つの物体が多数のセルにまたがり、利点が薄れる。Teschner らが2003年に変形体向けの最適化版を示し、この方法は SPH などのパーティクル・流体シミュレーションや、ボイドの近傍検索にも現れる。