Object Collision With Spatial Hashing

Object Collision With Spatial Hashing

I ran across a great article today by Christer Bystrom that talks of the difference between Quadtree's and Spatial Hashing at implementation and subsequently alludes at the performance implications. I've made a more appropriate demo (in my opinion,) than the confusing code in the spatial hashing implementation on the page to make it more simple to see and understand. I thought that it was worth taking a look at. In my code example I do not show his spatial mapping library. You'll have to use this link to gain access to that. I merely show how I implemented the library. In order to run my demo, you need just reference the easel library which can be included with import {easel} from 'ion-cloud'; after npm install ion-cloud --save to your project.

The highlighted boxes indicate those which have just collided or were forced to overlap due to compression of space allowance (ie, no room for the square to go.) The Spatial Hashing algorithm was created by Christer Bystrom.

import {easel} from 'ion-cloud';  
import {SpatialHash} from './ChristerBystromSpatialHash';

let config = {numberOfObjects: 400,sizePowerOfTwo: 3},  
    myObjects = createObjects(),
    myTree = new SpatialHash(config.sizePowerOfTwo);

function createObjects(){  
  let result = [];

  for(let i=0;i<config.numberOfObjects;i++){
    result.push({
      id: i,
      last: null,
      x: r(10, v.w), //random decimal between lb,ub
      y: r(10, v.h), //random decimal between lb,ub
      width: r(10,20,true), //random number
      height: r(10,20,true), //random number
      vx: r(-1,1), //random decimal between lb,ub
      vy: r(-1,1), //random decimal between lb,ub
      check: false
    });
  } //end for
  return result;
} //end createObjects()

function drawObjects(node){  
  let objects = node.retrieve();

  for(let i=0,obj;i<objects.length;i++){
    obj = objects[i];
    if(obj.check){
      ctx.strokeStyle = 'rgba(255,255,255,0.9)';
    }else{
      ctx.strokeStyle = 'rgba(255,255,255,0.2)';
    } //end if
    ctx.strokeRect(obj.x,obj.y,obj.width,obj.height);
  } //end for
} //end drawObjects()

(function main(){
  let returnObjects = [];

  myTree.clear(); //reset the tree
  for(let i=0;i<myObjects.length;i++){
    returnObjects=[];
    myObjects[i].x+=myObjects[i].vx;
    myObjects[i].y+=myObjects[i].vy;
    myObjects[i].check=false;
    if(myObjects[i].x>v.w) myObjects[i].x=0;
    if(myObjects[i].x<0) myObjects[i].x=v.w;
    if(myObjects[i].y>v.h) myObjects[i].y=0;
    if(myObjects[i].y<0) myObjects[i].y=v.h;
    myTree.insert(myObjects[i]);
    returnObjects = myTree.retrieve({
      x: myObjects[i].x,
      y: myObjects[i].y,
      width: myObjects[i].width,
      height: myObjects[i].height
    });
    for(let j=0;j<returnObjects.length;j++){

      // Make sure we filter out ourself
      if(returnObjects[j].id!==myObjects[i].id){
        let o1=returnObjects[j],
            o2=myObjects[i];

        if(o1.idle||o2.idle) continue;
        o1.check=true;o2.check=true; //highlight objects

        // if we already highlighted this from the other
        // object then stop now
        if(o1.last===o2.id||o2.last===o1.id) continue;
        if(o1.vx>0&&o2.vx>0||o1.vx<0&&o2.vx<0){
          [o1.vy,o2.vy]=[o2.vy,o1.vy];
        }else if(o1.vy>0&&o2.vy>0||o1.vy<0&&o2.vy<0){
          [o1.vx,o2.vx]=[o2.vx,o1.vx];
        }else{
          [o1.vx,o2.vx]=[o2.vx,o1.vx];
          [o1.vy,o2.vy]=[o2.vy,o1.vy];
        } //end if
        o1.last=o2.id;o2.last=o1.id;
      } //end if
    } //end for
  } //end for
  drawObjects(myTree);
  requestAnimationFrame(main);
})();

About Nathaniel Inman

I'm a gamer, graphic designer, musician and software engineer. C++ and Javascript are my favorite two programming languages for which I develop exclusively in vim, tmux and zsh on Arch Linux.

Kansas City, Missouri http://www.theoestudio.com