download, contribute or fork this project here!
Continuing from our last post, We were just ready to create our grid “buckets”!
Buckets are small rectangles forming the grid; objects corresponding to each bucket location will be saved (a reference to them) in that bucket.
To create buckets (and our grid) we need to divide the size of our target canvas (it can be our stage size or a virtual stage) to create smaller rectangles, then we will need just to check each object against other objects only in the same bucket or neighbor buckets which will dramatically reduce the required number of iterations. but it’s important to decide about the bucket sizes according to our needs (number of objects, desired distance to check…) and since variables affecting or decision here aren’t constant, it’s better to make it flexible so we can decide about the bucket size later! we will start with defining a float variable that will dictate desired size of our bucket to the class, if it’s not defined when calling the class it can be created automatically according to number of objects and requested distance check etc. but for now … let’s keep simple!
Also, we would want (I imagine at this point) two methods:
1. obj.set() –> Objects will declare their position to class and get referenced in corresponding buckets.
2. obj.get() –> which will return an array of references in all the neighbors in the requested distance.
Here to check the functionality of our Spatial hash grid class I’ll use a simple class I wrote before, which just generates bunch of random point objects on the stage, so we can put our class under some definable load, the Points class is simple (and anyway not the subject of this topic, but let me know if you want know more about it!):
So! here is the structure of our HashGrid class:
Here we just declared the class and bunch of variables and methods we know we’re gonna need.
There is also a displayGrid() function that will just draw our grid for us on the display so it’d be easier to understand and to debug.
But we have defined another class inside the HashGrid class as well (a nested class) near the end of this code snippet, Buckets class. that’s because in Java you should define the array type in declaration time and since our array will keep reference to Objects and there is not such a primitive called “Object” you need to define the object to be able to declare an array of that kine of objects, so we create a nested class called buckets to keep our bucket arrays and an array of our buckets in it!
Also you may notice that I hard coded another object type in my HashGrid class (The Points) which is not the best practice since we want to be able to use this class everywhere with no modifications, but for now and to keep it as simple as possible we are gonna leave it like that, but later on (in another post hopefully if I could) we will make it more abstract by using an interface or some other techniques.
Now we need to create an array of buckets, create an array in each bucket (to keep our object references) and populate our set() and get() functions:
Now our HashGrid class is all functional! awesome! but there is a few things still we need to do, some of them are relatively easy to implement, like adding the functionality to be able to define the desired distance to check (checking neighbors as well as the bucket itself) and also the Interface, we are gonna work on these later-on (hopefully!) in another post. But now to test our class we can create a new processing file (tab) and put this code on it:
Yep! it works! you can download, contribute or fork the whole project here at Github: