function rand_range(a, b) {

      return Math.random() * (b - a) + a;

    }

​

function sat(x) {

      return Math.min(Math.max(x, 0.0), 1.0);

    }

class SpacialHashGrid{

  constructor(bounds, dimensions){

    this._bounds = bounds;

    this._dimensions = dimensions;

    this._cells = new Map();

  }

  NewClient(position, dimensions){

    const client = {

      position: position,

      dimensions: dimensions,

      indices: null,

    };

    this._Insert(client);

    return client;

  }

  _Insert(client){

    const [x, y] = client.position;

    const [w, h] = client.dimensions;

    const i1 = this._GetCellIndex([x - w / 2, y - h / 2]);

    const i2 = this._GetCellIndex([x + w / 2, y + h / 2]);

    client.indices = [i1, i2];

    for (let x= i1[0], xn=i2[0]; x <= xn; ++x){

      for (let y= i1[1], yn = i2[1]; y <= yn; ++y){

        const k = this._Key(x, y);

        // lazy initialization

        if (!(k in this._cells)) {

          this._cell[k] = new Set();

        }

        this._cells[k].add(client);

      }

    } 

  }

  _Key(x,y){

    return x + '.' + y;

  }

  _GetCellIndex(position){

    const x = sat((position[0] - this._bounds[0]) /

          (this._bounds[1][0] - this._bounds[0][0]));

    const y = sat((position[1] - this._bounds[1]) /

          (this._bounds[1][1] - this._bounds[0][1]));

    const xIndex = Math.floor(x * (this._dimensions[0] -1));

    const yIndex = Math.floor(y * (this._dimensions[0] -1));

    return [xIndex, yIndex];

  }

  FindNear(position, bounds){

    const [x, y] = position;

    const [w, h] = bounds;

    const i1 = this._GetCellIndex([x - w / 2, y - h / 2]);

    const i2 = this._GetCellIndex([x + w / 2, y + h / 2]);

    const clients = [];

    for (let x= i1[0], xn=i2[0]; x <= xn; ++x){

      for (let y= i1[1], yn = i2[1]; y <= yn; ++y){

        const k = this._Key(x, y);

        if (k in this._cells){

          // another lazy thing :(

          for (let v of this._cells[k]) {

            clients.push(v);

          }

        }

      }

    }

    return clients;

  }

  UpdateClient(client){

    this.RemoveClient(client);

    this._Insert(client);

  }

  RemoveClient(client){

    const [i1, i2] = client.indices;

    for (let x= i1[0], xn=i2[0]; x <= xn; ++x){

      for (let y= i1[1], yn = i2[1]; y <= yn; ++y){

        const k = this._Key(x, y);

        this._cells[k].delete(client);

      }

    }

  }

}

​

​

const _NUM_CLIENTS = 100000;

const _ITERATIONS = 1000;

​

const bounds = [[0, 0,],[400,400]];

const dimensions = [50, 50];

const grid = new SpacialHashGrid(bounds, dimensions);

​

const clients = [];

const queryPositions = [];

const queryBounds = [15,15];

​

function setup() {

  createCanvas(400, 400);

  for (let i = 0; i < _NUM_CLIENTS; i++){

      const client = grid.NewClient(

      [

        rand_range(bounds[0][0], bounds[1][0]),

        rand_range(bounds[0][1], bounds[1][1])

      ],[15,15]

      );

      clients.push(client);

  }

  for (let i = 0; i < _ITERATIONS; i++){

    const p = [

      rand_range(bounds[0][0], bounds[1][0]),

      rand_range(bounds[0][1], bounds[1][1])

    ];

    queryPositions.push(p);

  }

}

​

​

function drawClients(the_clients){

  for (let i = 0; i < the_clients.length; i++){

    client = the_clients[i];

    [x,y] = client.position;

      console.log('drawing ') + the_clients.length;

    console.log("Clients: " + the_clients.length + " "+x+ " " + y);

    ellipse(x,y, 10,10);

​

}

  }

​

function _TestGrid(){

  console.log("Clients: "+clients.length)

  console.log("SPATIAL GRID FAST?");

  let startTime = performance.now();

  for (let i = 0; i < _ITERATIONS; i++){

    var the_clients = grid.FindNear(queryPositions[i], queryBounds);

    console.log("found " + the_clients.length + " clients")

    //drawClients(the_clients);

  }

  let totalTime = performance.now() - startTime;

  console.log('Time: ' + totalTime + 'ms');

  console.log('--------------------------');

}

​

​

function draw() {

  background(220);

  _TestGrid();

  noLoop();

}

​

​

​