Old codeuse strict;/** @constructor */function Shash(size, onNeighbour, forEach) {    this.objects = [];    this.grid = [];    this.gridSize = new vec2(0, 0);    this.size = size || new vec2(0, 0);    this.onNeighbour = onNeighbour || null;    this.forEach = forEach || null;}/** @constructor */Shash.object = function (shash, object) {    this.shash = shash;    this.object = object;    this.grid = this.gridIndex = null;};Shash.prototype.add = function (object, size) {    var ob = new Shash.object(this, object);    this.objects.push(ob);    if (this.gridSize.x < size.x) this.gridSize.x = size.x;    if (this.gridSize.y < size.y) this.gridSize.y = size.y;    return ob;}Shash.prototype.check = function () {    if (!this.onNeighbour) return;    this.grid = [];    var i = Math.ceil(this.size.x / this.gridSize.x),        J = Math.ceil(this.size.y / this.gridSize.y);    while (i--) {        this.grid[i] = [];        var j = J;        while (j--) this.grid[i][j] = [];    }    var re = this.objects.length;    while (re--) {        var grit = this.objects[re];        grit.grid = grit.shash.grid[Math.ceil(grit.object.coords.x / grit.shash.gridSize.x) - 1][Math.ceil(grit.object.coords.y / grit.shash.gridSize.y) - 1];        grit.gridIndex = grit.grid.length;        grit.grid.push(grit);    }    var i = this.grid.length;    while (i--) {        var gridx = this.grid[i],            j = gridx.length,            xr = i === this.grid.length - 1 ? 1 : 2;        while (j--) {            var gridy = gridx[j],                k = gridy.length;            while (k--) {                var grit = gridy[k],                    xl = xr;                while (xl--) {                    var xc = i + xl,                        yr = j === gridx.length - 1 ? [j - 1, j] : xl === 1 && j !== 0 ? [j - 1, j, j + 1] : [j, j + 1],                        yl = yr.length;                    while (yl--) {                        var yc = yr[yl],                            ogrid = this.grid[xc][yc],                            oi = ogrid === grit.grid ? grit.gridIndex : ogrid.length;                        while (oi--) this.onNeighbour(grit.object, ogrid[oi].object);                    }                }                if (this.forEach) this.forEach(grit.object);            }        }    }}Here's a class I made to handle my spacial hashing. I decided to separate the code from my main application, as I feel it is utility code, and is more portable.ShashThe shash class has only 2 members.Setupvar width = 1000,    height = 500,    shash = new Shash(width, height, onNeighbour);gridObject complient objects are added to the grid.shash.add(gridObject, width, height);interface gridObject{    coOrdinates coords;}interface coOrdinates {    int x;    int y;}Running checkshash.check();This will check through the grid, and call the onNeighbour callback for each pair of neighbouring objectsfunction onNeighbour(object1, object2){    // Do work with neighbours, such as collision checking.}Usage// constructorfunction rectangle(x, y, width, height){    this.coords = {        x: x || 0,        y: y || 0    };    this.width = width || 10;    this.height = height || 10    shash.add(this, this.width, this.height);}function onNeighbour(object1, object2){    console.log(NEIGHBOURS:, object1, object2);}var width = 1000,    height = 500,    shash = new Shash(width, height, onNeighbour);new rectangle(0, 0);new rectangle(5, 0);new rectangle(100, 50);shash.check();onNeighbour: NEIGHBOURS: rectangle {coords: {}, width: 10, height: 10} rectangle {coords: {}, width: 10, height: 10}This is a representation of what I - think I - am doing. I'm using this tetris-like shape to match all surrounding, when iterating through, for minimal checks. Is this effective?The blue circles are objects on the grid, the coloured grid squares are the squares being checked, for the object (blue circle). You can see how one object checks the other, but the other doesn't check it. (The orange is a result of the yellow and red checks overlapping)Each grid fits the largest object, perfectly, to minimise the area checked. This is supposed to be used for any shape, but when adding the a shape to the grid (Shash.prototype.add) the size of the shapes bounding box should be used, i.e: (10, 10) for a circle of radius 5.I was using a stripped down version of this code earlier, and had 60 fps checking 10k objects. The FPS has now halved.Are there any noticeable bottlenecks, or improvements for this code?p.s, grob means grid object.If a grid with 1000 objects on the same coordinate is checked, the onNeighbour callback will be triggered 499,500, \${n \choose 2}\$, times, as opposed to 1,000,000, \$n^2\$, times. This is a worst case scenario, where 1000 objects are simultaneously neighbouring (and colliding with) each other.In this test, I allocated 1000 10x10 squares in random positions across an area of 1000x500. This would have created a grid of 100x50 (area / maxSize). The check took 3ms, and triggered the neighbour callback ~30k times.function shape(x, y, width, height){    this.coords = {        x: x || 0,        y: y || 0    };    this.width = width || 10;    this.height = height || 10    shash.add(this, this.width, this.height);}function onNeighbour(object1, object2){    NEIGHBOURS++;}var width = 1000,    height = 500,    shash = new Shash(width, height, onNeighbour);for (var i = 1000; i--;) new shape(Math.random*width, Math.random()*height);var NEIGHBOURS = 0;console.time();shash.check();console.timeEnd();console.log(NEIGHBOURS, neighbours);default: 3ms30190 neighboursUpdateI made various changes to the code, resulting in this:use strict;/** @constructor */function Shash(width, height, onNeighbour) {    this.objects = [];    this.grid = [];    this.gridSize = { x: 1e-300, y: 1e-300 };    this.size = { x: width || 1e-300, y: height || 1e-300 };    this.onNeighbour = onNeighbour || null;}Shash.prototype.add = function (object, width, height) {    if (this.gridSize.x < width) this.gridSize.x = width;    if (this.gridSize.y < height) this.gridSize.y = height;    this.objects.push({        object: object    });}Shash.prototype._neighbour = function (object, ogrid) {    var ok = ogrid.length;    while (ok--) this.onNeighbour(object, ogrid[ok].object);}Shash.prototype.check = function () {    if (!this.onNeighbour) return;    // Clear grids    var i = Math.ceil(this.size.x / this.gridSize.x),        J = Math.ceil(this.size.y / this.gridSize.y);    this.grid = [];    while (i--) {        this.grid[i] = [];        var j = J;        while (j--) this.grid[i][j] = [];    }    // Re-assign grid objects, based on their coordinates    i = this.objects.length;    while (i--) {        var grob = this.objects[i];        grob.grid = this.grid[Math.floor(grob.object.coords.x / this.gridSize.x)][Math.floor(grob.object.coords.y / this.gridSize.y)];        grob.grid.push(grob);    }    i = this.grid.length;    while (i--) {        var gridx = this.grid[i],            iLUB = i !== this.grid.length - 1; // I: not last element        j = gridx.length;        while (j--) {            var grid = gridx[j], // Focused grid cell                k = grid.length,                jLUB = j !== gridx.length - 1, // J: not last element                jG0 = j !== 0; // J: not first element            while (k--) {                grob = grid[k]; // Focused grid object                var ok = k;                while (ok--) this.onNeighbour(grob.object, grid[ok].object); // Check same cell                if (iLUB) { // If there is space to the right                    var ogridx = this.grid[i + 1]; // Row of grids to the right of focused grid                    if (jG0) this._neighbour(grob.object, ogridx[j - 1]); // Check top-right                    this._neighbour(grob.object, ogridx[j]); // Check right                    if (jLUB) this._neighbour(grob.object, ogridx[j + 1]); // Check bottom-right                }                if (jLUB) this._neighbour(grob.object, gridx[j + 1]);  // If there is space to the below, check below            }        }    }}
Spacial hashing Library
javascript;algorithm;game;collision