5
\$\begingroup\$

Old code

"use 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.


Shash

The shash class has only 2 members.

Setup

var 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 check

shash.check();

This will check through the grid, and call the "onNeighbour" callback for each pair of neighbouring objects

function onNeighbour(object1, object2){
    // Do work with neighbours, such as collision checking.
}

Usage

// constructor
function 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: 3ms

30190 neighbours


Update

I 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
            }
        }
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Have you looked into using quad trees? jimkang.com/quadtreevis \$\endgroup\$ – OwChallie Aug 19 '17 at 23:14
  • \$\begingroup\$ Yes, I considered using quadtrees before spacial hashing, but the world is some-what homologous, and someone stated that hashing performs better in such circumstances. \$\endgroup\$ – Tobi Aug 19 '17 at 23:20
  • 1
    \$\begingroup\$ You will not get a good answer as you have given little information. Without some data for your code it is next to meaningless. What are you trying to do? Find specific shapes? How large can the shapes get, you show small, can they be large (100's of cells)? Is a shape the same if mirrored, rotated, scaled? Do the colors and circles have meaning and do they change the identity of a shape? What does the function onNeighbour do? what is a grob? I can see plenty of room for optimisation, but without more info it's just superficial code optimisation rather than algorithm optimisation. \$\endgroup\$ – Blindman67 Aug 20 '17 at 20:48
  • \$\begingroup\$ I'll edit the question. \$\endgroup\$ – Tobi Aug 21 '17 at 12:10
  • \$\begingroup\$ @Blindman67 Provided a lot more information and detail. \$\endgroup\$ – Tobi Aug 21 '17 at 12:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.