Draft of js spatial hash

Zone.js

/**
 * Module dependencies
 */
var Vector = require('../public/lib/vector'),
    _floor = Math.floor;



/**
 * Zone constructor
 * @param {string} name zone name.
 * @param {int} cellsize the w/h of each cell in the grid.
 * @constructor
 */
var Zone = function(name, cellsize) {
  this.name = name;
  this.grid = {};  //Grid hash
  this.ent = {};  //Raw entity list
  this.cellSize = cellsize;
};


/**
 * Gets the bucket key for a x, y pair
 * and returns the hash string
 *
 * @param {float} x x-coordinate.
 * @param {float} y y-coordinate.
 * @return {int} key.
 */
Zone.prototype._rawKey = function(x, y) {
  var cs = this.cellSize,
      a = _floor(x / cs),
      b = _floor(y / cs);

  return (b << 16) ^ a;
};


/**
 * Gets the bucket key for a x,y pair without cs lookup
 * @param {float} x xcoord.
 * @param {float} y ycoord.
 * @param {int} c cellSize of grid.
 * @return {int} key.
 */
Zone._fastKey = function(x, y, c) {
  var a = _floor(x / c),
      b = _floor(y / c);

  return (b << 16) ^ a;
};


/**
 * Adds an entity to the zone entity list
 *
 * @param {Entity} e Entity.
 * @param {function} _cb callback(err, entity.id).
 */
Zone.prototype.addEntity = function(e, _cb) {
  this.ent[e.id] = e;
  _cb(null, e.id);
};


/**
 * Returns an entity from the entity list based on its id
 *
 * @param {var} id Entity id.
 * @return {Entity} Matching entity.
 */
Zone.prototype.getEntity = function(id) {
  return this.ent[id];
};


/**
 * Deletes an entity from the entity list based on its id
 *
 * @param {var} id Entity id.
 */
Zone.prototype.delEntity = function(id) {
  delete this.ent[id];
};


/**
 * Returns entities in the same hash bucket as the given vector
 *
 * @param {Vector} vec Vector.
 * @param {function} _cb callback(error,result);.
 */
Zone.prototype.getClosest = function(vec, _cb) {
  if (!vec) _cb('No vector supplied');

  var key = this._rawKey(vec.x, vec.y);
  _cb(null, this.grid[key]);
};


/**
 * Get the keys of the buckets within range n from a given vector
 *
 * @param {Vector} vec Vector.
 * @param {float} n checking range.
 * @param {function} _cb callback(error,result).
 */
Zone.prototype.getAreaKeys = function(vec, n, _cb) {
  if (!vec || !n) _cb('No vector or distance supplied');

  var nwx = vec.x - n,
      nwy = vec.y - n,
      sex = vec.x + n,
      sey = vec.y + n,
      cs = this.cellSize,
      grid = this.grid,
      retval = [],
      rk = Zone._fastKey;

  for (var x = nwx; x <= sex; x = x + cs) {
    for (var y = nwy; y <= sey; y = y + cs) {
      var g = rk(x, y, cs);
      retval.push(g);
    }
  }

  _cb(null, retval);
};


/**
 * Gets the Id of all entities within distance n of the given vector
 *
 * @param {Vector} vec Vector.
 * @param {float} n checking range.
 * @param {function} _cb callback(err,[ids]);.
 */
Zone.prototype.getAreaIds = function(vec, n, _cb) {
  if (!vec || !n) _cb('No vector or distance supplied');
  
  //Todo: this needs to start at NW corner of zone vector is in...
  //Scary bug present
  //Get all entities within a certain area around the supplied vector
  var anwx = vec.x - n,
      anwy = vec.y - n,
      asex = vec.x + n,
      asey = vec.y + n,
      cs = this.cellSize,
      retval = [],
      grid = this.grid,
      rk = Zone._fastKey;
        

  //Step with this.cellSize in x/y, dump id of entities along the way
  for (var x = anwx; x <= asex; x = x + cs) {
    for (var y = anwy; y <= asey; y = y + cs) {     
      var g = grid[rk(x, y, cs)];      
      if(!g) continue;
      var gl = g.length;
      
      while(gl--){
        var thiseid = g[gl].id;
        if(retval.indexOf(thiseid) == -1) retval.push(thiseid);
      }                  
      
    }
  }

  _cb(null, retval);

};


/**
 * Rebuilds the grid hash
 *
 */
Zone.prototype.update = function() {
 
  delete this.grid;
  this.grid = {};
 
  var ent = this.ent,
      g = this.grid,
      cs = this.cellSize,
      atg = Zone.addToGrid;
  for (var e in ent) {
    atg(ent[e], g, cs);
  }

};


/**
 * Adds an entity to the grid hash
 *
 * @param {Entity} e Entity.
 * @param {Array} grid zone instance grid.
 * @param {int} cs grid cell size.
 */
Zone.addToGrid = function(e, grid, cs) {
  if (!e || !grid || !cs) return;

  //Data needed, entity position, checking distance
  var px = e.pos.x,
      py = e.pos.y,
      dist = e.rad,
      distdist = dist + dist;

  //Add double the objects radius to the position to form padded AABB
  //we pad because the grid is not updated every tick, and the padding
  //prevents an entity from suddenly swithing cells between updates
  co = [px - distdist, py - distdist,
    px + distdist, py - distdist,
    px - distdist, py + distdist,
    px + distdist, py + distdist],

  //cells entity needs to be in
  ec = [],

  //local ref to key function
  rk = Zone._fastKey;

  //For each corner of AABB check corners location
  //and add entity to all cells that the AABB corners are in
  //This does not allow for objects larger than cells, but then
  //again this is not needed in this implementation.
  //To allow for such objects simply iterate nw->se corner and step
  //with distdist or something smaller than cellsize and add entity
  //to each iterated location.
  for (var c = 0; c < 8; c = c + 2) {
    var key = rk(co[c], co[c + 1], cs);
    if (ec.indexOf(key) == -1) {
      ec.push(key);
      var gk = grid[key];

      gk ? gk.push(e) : grid[key] = [e];
    }
  }
};


module.exports = Zone;