Friday, February 12, 2010

A Spatial Hash class in C#.

Now that I'm writing more C# than Python... I've ported some of my more useful classes for use with Unity3D and C#. This is a rather useful class, the Spatial Hash. It is used for creating an index of spatial data (3D things in space) and allowing fast queries to be run against the index. The original Python version is over here. This new class is used in much the same way.

Effectively, you can use this class to ask, "I'm at this position, what other objects are near me?".

using UnityEngine;
using System.Collections;

public class SpatialHash
{
private Hashtable idx;
private int cellSize;

public SpatialHash(int cellSize) {
this.cellSize = cellSize;
this.idx = new Hashtable();
}

public int Count {
get { return idx.Count; }
}

public ICollection Cells {
get { return idx.Keys; }
}

public void Insert(Vector3 v, object obj) {
ArrayList cell;
foreach(string key in Keys(v)) {
if(idx.Contains(key))
cell = (ArrayList)idx[key];
else {
cell = new ArrayList();
idx.Add(key, cell);
}
if(!cell.Contains(obj))
cell.Add(obj);
}
}

public ArrayList Query(Vector3 v) {
string key = Key(v);
if(idx.Contains(key))
return (ArrayList)idx[key];
return new ArrayList();
}

private ArrayList Keys(Vector3 v) {
int o = cellSize / 2;
ArrayList keys = new ArrayList();
keys.Add(Key(new Vector3(v.x-o, v.y-0, v.z-o)));
keys.Add(Key(new Vector3(v.x-o, v.y-0, v.z-0)));
keys.Add(Key(new Vector3(v.x-o, v.y-0, v.z+o)));
keys.Add(Key(new Vector3(v.x-0, v.y-0, v.z-o)));
keys.Add(Key(new Vector3(v.x-0, v.y-0, v.z-0)));
keys.Add(Key(new Vector3(v.x-0, v.y-0, v.z+o)));
keys.Add(Key(new Vector3(v.x+o, v.y-0, v.z-o)));
keys.Add(Key(new Vector3(v.x+o, v.y-0, v.z-o)));
keys.Add(Key(new Vector3(v.x+o, v.y-0, v.z-0)));
keys.Add(Key(new Vector3(v.x-o, v.y-o, v.z-o)));
keys.Add(Key(new Vector3(v.x-o, v.y-o, v.z-0)));
keys.Add(Key(new Vector3(v.x-o, v.y-o, v.z+o)));
keys.Add(Key(new Vector3(v.x-0, v.y-o, v.z-o)));
keys.Add(Key(new Vector3(v.x-0, v.y-o, v.z-0)));
keys.Add(Key(new Vector3(v.x-0, v.y-o, v.z+o)));
keys.Add(Key(new Vector3(v.x+o, v.y-o, v.z-o)));
keys.Add(Key(new Vector3(v.x+o, v.y-o, v.z-o)));
keys.Add(Key(new Vector3(v.x+o, v.y-o, v.z-0)));
keys.Add(Key(new Vector3(v.x-o, v.y+o, v.z-o)));
keys.Add(Key(new Vector3(v.x-o, v.y+o, v.z-0)));
keys.Add(Key(new Vector3(v.x-o, v.y+o, v.z+o)));
keys.Add(Key(new Vector3(v.x-0, v.y+o, v.z-o)));
keys.Add(Key(new Vector3(v.x-0, v.y+o, v.z-0)));
keys.Add(Key(new Vector3(v.x-0, v.y+o, v.z+o)));
keys.Add(Key(new Vector3(v.x+o, v.y+o, v.z-o)));
keys.Add(Key(new Vector3(v.x+o, v.y+o, v.z-o)));
keys.Add(Key(new Vector3(v.x+o, v.y+o, v.z-0)));
return keys;
}

private string Key(Vector3 v) {
int x = (int)Mathf.Floor(v.x/cellSize)*cellSize;
int y = (int)Mathf.Floor(v.y/cellSize)*cellSize;
int z = (int)Mathf.Floor(v.z/cellSize)*cellSize;
return x.ToString() + ":" + y.ToString() + ":" + z.ToString();
}

}

2 comments:

LogicalError said...

You might be interested in the following paper:
http://www.beosil.com/download/CollisionDetectionHashing_VMV03.pdf
It contains a hash function which uses an integer instead of a string, which would be much much faster.

Also, I'm wondering why you don't use any of the generics collections? Those are way more efficient than ArrayList and HashTable..
You could use List and Dictionary instead.

Simon Wittber said...

Thanks for the link, I'll be sure to check it out.

I'm not using Generics as they are not currently supported on Unity iPhone.

Popular Posts