Making a grid for collision detection in a game that wraps

Question

I'm making a 2D game which wraps (when you move off the right edge, you appear on the left, etc). The game area is square, all objects are circles (with AABB smaller than the game area, and in most cases, much smaller).

I'm dividing the game area into a grid to perform collision checks. I need to determine which cell(s) an object's AABB lives in.

Right now I have this awkward code to deal with cases when the object passes the left/right boundary... I feel like there must be a better way to write it.

gridX is x-dimension of the grid
x1 is the x-coord of the cell the object's left boundary lives in (before taking into account wrap)
x2 " " right boundary

if (x1 < 0) {
 for (let j = x1 + gridX; j < gridX; j++) someFunction(j)
 for (let j = 0; j < x2; j++) someFunction(j)
} else if (x2 >= gridX) {
 for (let j = x1; j < gridX; j++) someFunction(j)
 for (let j = 0; j < x2 - gridX; j++) someFunction(j)
} else {
 for (let j = x1; j <= x2; j++) someFunction(j)
}

someFunction would then contain the y coord version of the above and add to the grid.

Bear in mind I don't want to lose performance (as it will be run multiple times per second).

I want to write out someFunction instead of actually declaring a function so I hope there is a better way to do this - especially if I wanted to make my game 3 dimensional in future. That would be 25 pastes.

• Shuri2060: It becomes this when written out hasteb.in/apubudet.js
• Gabriel Rohweder: You say that all objects are circles. If this is true than why are you using AABB? Point/Circle collision is much faster.
• Shuri2060: @GabrielRohweder I use AABB to determine which grid cells they intersect. I think its faster (since most objects will be smaller than 1 cell)

Answer 1

Some style points first.

• Always wrap statement and loop blocks in {} eg you wrote for (let j = 0; j < x2; j++) someFunction(j) to avoid maintenance headaches use the curlies for (let j = 0; j < x2; j++) { someFunction(j) }

• Don't declare the same variable over and over. There is no advantage to locally scoping variables to code blocks unless you are writing very long functions, and you should avoid writing functions more than a page long.

• In this case j is not the best choice of variable name for the loop counter. x would be far better.

Rewriting your function with the above points

var x;
if (x1 < 0) {
 for (x = x1 + gridX; x < gridX; x++) { someFunction(x) }
 for (x = 0; x < x2; x++) { someFunction(x) }
} else if (x2 >= gridX) {
 for (x = x1; x < gridX; x++) { someFunction(x) }
 for (x = 0; x < x2 - gridX; x++) { someFunction(x) }
} else {
 for (x = x1; x <= x2; x++) { someFunction(x) }
}

The remainder operator %

"I feel like there must be a better way to write it."

You can simplify the solution by using the remainder operator %. First ensure that x1, and x2 are positive by adding the grid width (or height) Then use remainder as you loop over the items to get the wrapped coordinate.

Example replaces your function

// Assumes x1 is never less than -gridX and that x2 is always > x1
const end = x2 + gridX;
var x = x1 + gridX; 
while (x <= end) { someFunction((x++) % gridX) }

More detailed example of wrapped play-field

The example below demonstrates using remainder and has two functions that take a x,y gird coordinated and map it to an array. setGrid(x, y, val) as long as the grid coordinates are greater than gridSteps (same as your gridX) * -gridMin

const AABB = { x: 0, y: 0, w: 90, h: 90 } // values in pixels
const gridSteps = 10; // same as your gridX
const gridMin = 100; // min number of grids below origin 0,0. Used to translate 
 // coordinates to positive values
const grid = new Uint8Array(gridSteps ** 2); // grid array
function setGrid(x, y, val) { 
 x += gridSteps * gridMin; // translate to positive space
 y += gridSteps * gridMin; // translate to positive space
 const idx = (x % gridSteps) + (y % gridSteps) * gridSteps;
 grid[idx] = val;
}
// version 2
const gridMinC = gridSteps * gridMin;
function setGrid(x, y, val) { 
 const idx = ((x + gridMinC) % gridSteps) + ((y + gridMinC) % gridSteps) * gridSteps;
 grid[idx] = val;
}
 
requestAnimationFrame(update);
const scaleMouse = 0.05; // scales mouse to add movement
const inset = 3, inset2 = inset * 2;
var w = 1, h = 1;
const gridImg = createImage(w, h);
const ctx = canvas.getContext("2d");
const mouse = {x : 0, y : 0};
document.addEventListener("mousemove", mouseEvents);
function fillGrid(AABB, gridSteps, col = "#9998") { // Draw wrapped collision boxes
 var x, y, xs = w / gridSteps, ys = h / gridSteps;
 const yStart = AABB.y / ys | 0, yEnd = (AABB.y + AABB.h) / ys | 0;
 const xStart = AABB.x / xs | 0, xEnd = (AABB.x + AABB.w) / xs | 0;
 ctx.fillStyle = col;
 ctx.beginPath();
 for (y = yStart; y <= yEnd; y += 1) {
 const yy = y % gridSteps;
 for (x = xStart; x <= xEnd; x += 1) {
 const xx = x % gridSteps;
 ctx.rect(xx * xs + inset, yy * ys + inset, xs - inset2, ys - inset2); 
 }
 }
 ctx.fill();
}
function drawBox(AABB, col = "#000") { // draws AABB box wrapped
 ctx.strokeStyle = col;
 ctx.lineWidth = 2;
 const x = AABB.x % w;
 const y = AABB.y % h;
 ctx.strokeRect(x, y, AABB.w, AABB.h);
 var corner = 0;
 if (x + AABB.w > w) {
 ctx.strokeRect(x- w, y, AABB.w, AABB.h);
 corner ++;
 } 
 if (y + AABB.h > h) {
 ctx.strokeRect(x, y - h, AABB.w, AABB.h);
 corner ++;
 }
 if (corner === 2) { ctx.strokeRect(x - w, y - h, AABB.w, AABB.h) }
}
function update() {
 if (w !== (innerWidth / 2 | 0) || h !== innerHeight) {
 w = gridImg.width = canvas.width = innerWidth / 2 | 0;
 h = gridImg.height = canvas.height = innerHeight;
 drawGridLines(gridImg.ctx, gridSteps);
 }
 ctx.globalCompositeOperation = "copy"; // copy transparent pixels to destination 
 ctx.drawImage(gridImg, 0, 0);
 ctx.globalCompositeOperation = "source-over"; // default comp mode 
 
 //Use mouse dist from center to scale speed of AABB
 AABB.x = (AABB.x + (mouse.x - w / 2) * scaleMouse + w) % w;
 AABB.y = (AABB.y + (mouse.y - h / 2) * scaleMouse + h) % h;
 fillGrid(AABB, gridSteps);
 drawBox(AABB);
 requestAnimationFrame(update);
}
function mouseEvents(e){
 const bounds = canvas.getBoundingClientRect();
 mouse.x = e.pageX - bounds.left - scrollX;
 mouse.y = e.pageY - bounds.top - scrollY;
}
function createImage(width, height) {
 const img = document.createElement("canvas");
 img.width = width, img.height = height;
 img.ctx = img.getContext("2d");
 return img;
}
function drawGridLines(ctx, gridSteps, col = "red") {
 var i, xs = w / gridSteps, ys = h / gridSteps;
 ctx.lineWidth = 2;
 ctx.strokeStyle = col;
 ctx.beginPath();
 for (i = 0; i <= gridSteps; i ++) {
 ctx.moveTo(0, i * ys);
 ctx.lineTo(w, i * ys);
 ctx.moveTo(i * xs, 0);
 ctx.lineTo(i * xs, h);
 }
 ctx.stroke();
}

canvas { position : absolute; top : 0px; left : 0px; cursor: crosshair;}

<canvas id="canvas"></canvas>

Last point

"especially if I wanted to make my game 3 dimensional in future."

You would never use a 3D grid for collisions as their size can grow very quickly, a 1024 cube would require a minimum or 1Gig of RAM. What you want are Quad Trees or even Octrees and the many variations, as they provide fast data structures for all sorts of spacial related problems 2D, 3D, and more :D

Collision grids are great for lowres 2D and limited 3D uses but you will need to consider alternatives when resolutions grow.

• Shuri2060: I avoided using the % operator as I was under the impression it performs division (slow)? And then for the last point - the same problem surely exists with quad/octrees if you have a game that wraps?
• Blindman67: @Shuri2060 JavaScript has internal Number formats. Default double (64bit float) fastest is signed int32. You can force a number to be a int32 in a variety of ways. Apply a bitwise operator. x |= 0 (OR zero). CPU instruction sets do not generally have an (int) modulo instruction however dividing op DIV a remainder is stored in a register (x86/64). For the fastest modulo use a grid that is power of two, 2, 4, 8, 16, 32, etc .. and bitwise mask (AND &) the coordinate. eg grid = 256; mask = grid - 1; x &= mask very fast and result same as x %= grid if 0 <= x < 2**31