A Simple Spatial Hashing (HashGrid) for processing-1

Spatial HashGrid projected on a sphere
Image Source: Wikimedia.

While working on bunch of sketches to create visuals for one of my documents, I was thinking to implement it with a simple Spatial Hash grid, but since performance wasn’t that important in that particular project, I just did it the simple way (checking every node against all the others in each iteration which means —> n² checks / frame (90K check for 300 prticle points for example!)) and it worked just fine! but strangely enaugh it was bothering me that I didn’t do it the right way! and since I’m gonna to reuse the code in another projects for sure and since I’ll need to implement this technique anyway sooner or later in one of my “things”! I tried to give it a try and do it the “right way”.
I started by just thinking and trying to analyze the way I’d imagine it works, I wanted something simple and minimal, so I did bunch of sketches on paper like these one (which probably make sense just to myself!):

Spatial hash first sketches
primitive sketches on paper to define spatial grid I wanted to have to myself!

The concept behind spatial grids is simple: you keep track of each target object by keeping a reference to that object in the grid bucket beneath it (in a 2D scenario (which is expandable to a 3D one respectivly easy)), so each bucket is an array of references to objects located on that bucket’s position (on the grid), of course it can be further developed I think to a more efficient algorithm combining a quad-tree system for scenarios where objects are placed mostly not evenly on the grid ( buckets will have a limit size (let’s say 3) and then (if there is more than 3 objects located there) they’ll divide to 4 buckets…), but we don’t need that here since my objects will be scattered on space by a random perlin noise algorithm (almost evenly placed on enough large spaces). Doing a bit of research I found out some interesting libraries which would do the job just fine, like HashGrid class in giCentre Utiles library:

hashGrid = new HashGrid(width,height,10);

But first of all, I wanted it to be simple and just do a few things that I need it to do and secondly (and more important for me) I wanted to do it myself so I’d understand it and I’d be able to use the technique whenever and wherever (let’s say in my simple JS Canvas game) I wanted to, and all in all it looked like easy to implement! (surly enough, just to do the basic and probably not in the best way possible?!) So anyway I started to write the class:
(Ah btw, unfortunately, their source code is not available to public! (just a broken link on their Google repo site) and I didn’t find any other essay to do this on internet so I was (or am) pretty much on myself to figure it out! wish me luck!)

class HashGrid{
// It is just a simple class declaration so far!
 HashGrid(/*defined vars*/){
// constructor
 }
}

To keep reference to objects there is ArrayList class/ interface available in JAVA (and Processing) which is very convenient since it resizes dynamically according to the number of objects in it, but is slower than a simple array of objects, so it’d be better if we can have simple arrays but then we should think about a mechanism to add AND remove (There is a confusion for me though since in Java these methods doesn’t exist! but apparently they exist in Processing (as it explain in the reference page: Decreases an array by one element and returns the shortened array. (Also look at this snippet))) (EDIT: I further investigated this issue and found out that (as I guessed) the append and shorten methodes in processing are pretty ineficient and actually just create a new array, with one member more or less and copy the old one to it, and don’t respect Java specs, all in all, seems better to avoid them (after all we can do the same thing if we need and keep the code more reusable in another Java envirenment)) items manually to and from the array (which happens automatically using ArrayList) but due to Java Array limitations the length of Array can not be changed, … since our concern is performance here (that’s why we want to create a hashGrid in the first place!) we should obviously go with standard arrays. (I’ll make this decision later on, be cause although Arrays are faster but: 1.we need to allocate a considerable amount of memory to them either we use that space or not, and 2. it may bring more and in-neccesary complexity to the process when we need to itterate each bucket array to get references to objects… (EDIT: it turned out that it wasn’t that complicated! so I used simple Arrays finally, Although I guess other implementations, including the GiCentre Utiles, are using arrayLists, so I guess my methode should be a lot faster than other ones specially when the number of elements is higher) ), let’s go and start by creating out buckets:

. . .
TO BE CONTINUED IN THE NEXT POST!

2 thoughts on “A Simple Spatial Hashing (HashGrid) for processing-1”

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>