Uniform Grid

/*

____ _

/ ___|| | _____ | | | | _ | __ | | _____ _

\___ \| |/ \ \ /\ / / || |/ ` |/ ` |/ \| |/ / \ '_ \

___) | | (_) \ V V /| | (| | (_| | (_) | < __/ | | |

|____/|_|\___/ \_/\_/ |_| |_|\__,_|\__,_|\___/|_|\_\___|_| |_| */

let canvas = document.getElementById("partitionedCanvas");

let context = canvas.getContext("2d");

let canvasWidth = canvas.width = 500;

let canvasHeight = canvas.height = 300;

let Entity = function(aabb) {

this.id = 0;

this.isColliding = false;

this.aabb = aabb;

};

let AABB = function(x,y,half,halfHeight) {

this.pos = { x: x, y: y};

this.half = { x: half, y: halfHeight || half };

};

// Uniform Spatial Partitioning Grid

// built using examples by Andrew Petersen and Liam Brummitt

let SpatialGrid = function(gridWidth,gridHeight,bucketSize) {

let spatialGrid = {};

let _bucketSize = bucketSize || 100;

// A spatial grid is composed of regions, buckets, and pairs.

spatialGrid.buckets = {}; // {"column,row":[entities]}

spatialGrid.pairs = []; // [{"entityA:entityB":[pair]}]

// gets row and column in grid from x and y Cartesian coordinates of bounding box

let _getRegion = function(aabb) {

let startCol = parseInt((aabb.pos.y - aabb.half.y) / _bucketSize);

let endCol = parseInt((aabb.pos.y + aabb.half.y) / _bucketSize);

let startRow = parseInt((aabb.pos.x - aabb.half.x) / _bucketSize);

let endRow = parseInt((aabb.pos.x + aabb.half.x) / _bucketSize);

let regions = [];

let i = 0;

// for each row and column the entity overlaps create a region

for (let y = startCol; y <= endCol; y++) {

for (let x = startRow; x <= endRow; x++) {

// regions are used as keys for buckets

regions[i] = {

id: x + "," + y,

row: x,

column: y

};

i++;

}

}

return regions;

};

// A bucket is a region key and an array value. It's a hash for buffering.

// creates buckets["columnX,columnY"][entities]

let _createBuckets = function(entities) {

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

let regions = _getRegion(entities[i].aabb);

for (let j = 0; j < regions.length; j++) {

if (spatialGrid.buckets[regions[j].id] === undefined) {

// create bucket and add entity to it

spatialGrid.buckets[regions[j].id] = [];

spatialGrid.buckets[regions[j].id].push(entities[i]);

} else {

// add entity to existing bucket

spatialGrid.buckets[regions[j].id].push(entities[i]);

}

}

}

};

// A pair of entities in a bucket that could potentially collide.

// creates pairs[[entityA,entityB]],[entityA,entityB]] etc.

let _createPairs = function(bucket) {

// skip a bucket that contains only one entity

if (bucket.length > 1) {

// create unique pairs (unordered)

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

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

let pair = [bucket[i],bucket[j]];

spatialGrid.pairs.push(pair);

}

}

}

};

// aabb vs aabb collision detection

let _intersectAABB = function(aabbA,aabbB) {

let dx = aabbA.pos.x - aabbB.pos.x;

let dy = aabbA.pos.y - aabbB.pos.y;

let adx = dx < 0 ? -dx : dx;

let ady = dy < 0 ? -dy : dy;

let px = (aabbA.half.x + aabbB.half.x) - adx;

let py = (aabbA.half.y + aabbB.half.y) - ady;

// no collision

if (px <= 0 || py <= 0) {

return false;

}

// collision

return true;

};

// resets entity collision flags and clears grid

spatialGrid.clear = function(entities) {

// reset collision flags

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

entities[i].isColliding = false;

}

// clear all buckets and pairs

spatialGrid.buckets = {};

spatialGrid.pairs = [];

};

// creates buckets

spatialGrid.update = function(entities) {

_createBuckets(entities);

};

// Creates potential collision pairs from buckets.

spatialGrid.queryForCollisionPairs = function() {

for (let key in spatialGrid.buckets) {

let bucket = spatialGrid.buckets[key];

_createPairs(bucket);

}

};

// Simple narrow phase aabb vs aabb collision detection against each pair.

spatialGrid.collision = function() {

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

// test for collision against each pair

let pair = spatialGrid.pairs[i];

let entityA = pair[0];

let entityB = pair[1];

let aabbA = entityA.aabb;

let aabbB = entityB.aabb;

// narrow phase collision test

let isColliding = _intersectAABB(aabbA,aabbB);

// we reset these flags in the clear method

if (isColliding) {

entityA.isColliding = true;

entityB.isColliding = true;

}

}

};

// render buckets and entity's bounding boxes

spatialGrid.render = function(ctx,entities) {

// set background to black

ctx.fillStyle = "black";

ctx.fillRect(0,0,canvasWidth,canvasHeight);

// render each occupied grid square i.e. bucket

ctx.fillStyle = "grey";

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

let entity = entities[i];

let region = _getRegion(entity.aabb);

for (let j = 0; j < region.length; j++) {

let row = region[j].row;

let column = region[j].column;

ctx.fillRect(row*_bucketSize,column*_bucketSize,_bucketSize,_bucketSize);

}

}

// render each bucket as a stroke

let gridWidth = canvasWidth/_bucketSize;

let gridLength = (canvasWidth/_bucketSize) * (canvasHeight/_bucketSize);

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

let y = parseInt(i/gridWidth);

let x = i%gridWidth;

ctx.strokeStyle = "lightgrey";

ctx.strokeRect(x*_bucketSize,y*_bucketSize,_bucketSize,_bucketSize);

}

// render entity's bounding boxes

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

let entity = entities[i];

if (entity.isColliding) {

ctx.fillStyle = "red";

} else {

ctx.fillStyle = "white";

}

ctx.fillRect(entity.aabb.pos.x-entity.aabb.half.x,

entity.aabb.pos.y-entity.aabb.half.y,

entity.aabb.half.x*2,

entity.aabb.half.y*2);

}

};

// This grid is destroyed and rebuilt with everey step.

return spatialGrid;

};

let bucketSize = 100;

// You could factory these entities out with unique ids.

let aabb1 = new AABB(45,105,25);

let entity1 = new Entity(aabb1);

entity1.id = 1;

let aabb2 = new AABB(105,35,25);

let entity2 = new Entity(aabb2);

entity2.id = 2;

let aabb3 = new AABB(25,135,25);

let entity3 = new Entity(aabb3);

entity3.id = 3;

let aabb4 = new AABB(160,45,25);

let entity4 = new Entity(aabb4);

entity3.id = 4;

// add entities to array below

let entities = [entity1,entity2,entity3,entity4];

// create an instance of a grid

let grid = SpatialGrid(canvasWidth,canvasHeight,bucketSize);

grid.clear(entities);

grid.update(entities);

grid.queryForCollisionPairs();

grid.collision();

grid.render(context,entities);