空間ハッシュは、データベース、物理エンジンおよびグラフィックエンジン、パーティクルシミュレーション、および一般に迅速に何かを見つける必要がある場所で使用される単純な手法です。 要するに、一番下の行は、オブジェクトのあるスペースをセルに分割し、オブジェクトをその中に入れるということです。 次に、値で検索する代わりに、ハッシュですばやく検索します。
複数のオブジェクトがあり、それらの間に衝突があるかどうかを調べる必要があるとします。 最も簡単な解決策は、各オブジェクトから他のすべてのオブジェクトまでの距離を計算することです。 ただし、このアプローチでは、必要な計算の数が非常に速くなります。 1ダースのオブジェクトが100回のチェックを行う必要がある場合、100個のオブジェクトにはすでに何万ものチェックがあります。 これは、アルゴリズムの悪名高い2次の複雑さです。
以下では、疑わしいことにC＃に非常によく似た擬似コードが使用されますが、これは単なる幻想です。 このコードは記事の最後にあります。
// foreach (var obj in objects) { if (Distance(this.position, obj.position) < t) { // } }
グリッドを使用してスペースを壊すと、状況を改善できます。 その後、各オブジェクトはいくつかのグリッドセルに分類され、隣接するセルを見つけてその充実度を確認するのは非常に簡単です。 たとえば、2つのオブジェクトが少なくとも1つのセルで分離されている場合、それらが衝突しなかったことを確認できます。
グリッドはすでに良好ですが、グリッドの更新に問題があります。 セル内の座標の絶え間ないふるい分けは、2次元ではうまく機能しますが、3次元ではすでに減速し始めています。 さらに一歩進んで、ハッシュを使用して多次元検索スペースを1次元に減らすことができます。 ハッシュを使用すると、セルをより速く埋めて検索することができます。 これはどのように機能しますか？
ハッシュとは、大量のデータを固定データに変換するプロセスで、ソースデータにわずかな違いがあるため、固定データに大きな違いが生じます。 これは本質的に非可逆圧縮です。 各セルに識別子を割り当てることができます。オブジェクトの座標を圧縮し、画像との類似性を描き、解像度を下げると、目的のセルの座標が自動的に取得されます。 この方法ですべてのセルを埋めると、任意の座標の近くにあるオブジェクトを簡単に取得できます。 座標をハッシュし、オブジェクトを含むセルの識別子を取得します。
固定サイズの2次元グリッドの場合、ハッシュ関数はどのように見えるでしょうか？ たとえば、次のとおりです。
hashId = (Math.Floor(position.x / ellSize)) + (Math.Floor(position.y / ellSize)) * width;
x座標をセルサイズで除算し、小数部分を切り取り、y座標で同じことを行い、グリッドの幅を乗算します。 次の図のように、1次元配列になります。
実際、以前と同じグリッドを使用していますが、計算が簡素化されているため、検索は高速になっています。 確かに、非常に遠いオブジェクトの座標ハッシュが近いオブジェクトの座標ハッシュと一致する可能性がある場合、衝突の出現により単純化されます。 したがって、適切な分布と許容される衝突頻度を備えたハッシュ関数を選択することが重要です。 詳細については、ウィキペディアをご覧ください。 実際に3次元の空間ハッシュを実装する方法を紹介したいと思います。
ハッシュについて少し追加
2 * 3.14または2 * 3.1415926535897932384626433832795028841971を計算するのに速いのは何ですか？ もちろん、最初の。 精度の低い結果が得られますが、誰が気にしますか？ 同様に、ハッシュ付き。 私たちは計算を単純化し、精度を失いますが、高い確率で私たちに合った結果が得られます。 これがハッシュチップであり、その強さの源です。
最も重要なことから始めましょう-三次元座標のハッシュ関数。 Nvidia Webサイトの非常に波乱に富んだ記事では 、次のオプションを提供しています。
GLuint hash = ((GLuint)(pos.x / CELLSIZE) << XSHIFT) | ((GLuint)(pos.y / CELLSIZE) << YSHIFT) | ((GLuint)(pos.z / CELLSIZE) << ZSHIFT);
各軸の座標を取得し、セルのサイズで除算し、ビットシフトを適用して、結果をそれらの間でORします。 この記事の著者は、シフトのサイズを指定していません。さらに、ビット計算は完全に「最小」ではありません。 この出版物では、少し簡単に説明されている機能があります。 コードに変換すると、次のようになります。
hash = (Floor(pos.x / cellSize) * 73856093) ^ (Floor(pos.y / cellSize) * 19349663) ^ (Floor(pos.z / cellSize) * 83492791);
各軸のセル座標を見つけ、大きな素数とXORを掛けます。 正直なところ、それほど簡単ではありませんが、少なくとも未知のシフトはありません。
空間ハッシュを使用するには、オブジェクトをセルに保存するコンテナとオブジェクトのセル番号を保存するコンテナの2つが便利です。 ハッシュテーブルは、メインコンテナ、辞書、ハッシュマップ、またはお気に入りの言語で呼び出されるものとして最も速く機能します。 そのうちの1つでは、保存されたオブジェクトをハッシュキーで取得し、もう1つではセル番号をオブジェクトキーで取得します。 これら2つのコンテナを一緒に使用すると、隣人をすばやく見つけてセルの充実度を確認できます。
private Dictionary<int, List<T>> dict; private Dictionary<T, int> objects;
これらのコンテナの操作はどのように見えますか？ 2つのパラメーターを使用してオブジェクトを挿入します：座標とオブジェクト自体。
public void Insert(Vector3 vector, T obj) { var key = Key(vector); if (dict.ContainsKey(key)) { dict[key].Add(obj); } else { dict[key] = new List<T> { obj }; } objects[obj] = key; }
座標をハッシュし、ディクショナリでキーを確認し、オブジェクトをキーで押し込み、キーをオブジェクトで押し込みます。 座標を更新する必要がある場合、古いセルからオブジェクトを削除し、新しいセルに挿入します。
public void UpdatePosition(Vector3 vector, T obj) { if (objects.ContainsKey(obj)) { dict[objects[obj]].Remove(obj); } Insert(vector, obj); }
一度に更新されるオブジェクトが多すぎる場合、すべての辞書をクリアして、毎回それらを再入力する方が簡単です。
public void Clear() { var keys = dict.Keys.ToArray(); for (var i = 0; i < keys.Length; i++) dict[keys[i]].Clear(); objects.Clear(); }
それだけです。完全なクラスコードを以下に示します。 UnityエンジンのVector3を使用しますが、コードはXNAまたは別のフレームワークに簡単に適合できます。 ハッシュの機能は特定の「高速丸め」を使用するため、その作業を保証することはできません。
SpatialHash.cs
using System.Linq; using UnityEngine; using System.Collections.Generic; public class SpatialHash<T> { private Dictionary<int, List<T>> dict; private Dictionary<T, int> objects; private int cellSize; public SpatialHash(int cellSize) { this.cellSize = cellSize; dict = new Dictionary<int, List<T>>(); objects = new Dictionary<T, int>(); } public void Insert(Vector3 vector, T obj) { var key = Key(vector); if (dict.ContainsKey(key)) { dict[key].Add(obj); } else { dict[key] = new List<T> { obj }; } objects[obj] = key; } public void UpdatePosition(Vector3 vector, T obj) { if (objects.ContainsKey(obj)) { dict[objects[obj]].Remove(obj); } Insert(vector, obj); } public List<T> QueryPosition(Vector3 vector) { var key = Key(vector); return dict.ContainsKey(key) ? dict[key] : new List<T>(); } public bool ContainsKey(Vector3 vector) { return dict.ContainsKey(Key(vector)); } public void Clear() { var keys = dict.Keys.ToArray(); for (var i = 0; i < keys.Length; i++) dict[keys[i]].Clear(); objects.Clear(); } public void Reset() { dict.Clear(); objects.Clear(); } private const int BIG_ENOUGH_INT = 16 * 1024; private const double BIG_ENOUGH_FLOOR = BIG_ENOUGH_INT + 0.0000; private static int FastFloor(float f) { return (int)(f + BIG_ENOUGH_FLOOR) - BIG_ENOUGH_INT; } private int Key(Vector3 v) { return ((FastFloor(vx / cellSize) * 73856093) ^ (FastFloor(vy / cellSize) * 19349663) ^ (FastFloor(vz / cellSize) * 83492791)); } }
インタラクティブデモでは、このリンクに従って 、ハッシュスペースがどのように分散されているかを確認してください。 黄色のボールの座標はタイマーによってハッシュされ、その後、球内のランダムなポイントに移動します。 黄色の立方体は、同じセルに入る座標を示します。 青いキーは、作成済みのキーを示しているため、メモリがいっぱいになるプロセスを見ることができます。 マウスを回転させることができます。
GitHubのソース | Unity Web Playerの所有者向けのオンラインバージョン
興味深い関連リンク
http://www.cs.ucf.edu/~jmesit/publications/scsc%202005.pdf
http://www.beosil.com/download/CollisionDetectionHashing_VMV03.pdf
http://http.developer.nvidia.com/GPUGems3/gpugems3_ch32.html