# 2D tilemap collision method

Is this the optimal method to check for collisions in a 2d-based game? I put together a working demo of 2D collisions here (WSAD to move, orange blocks collide).

I currently use the following code to check for collisions:

function checkmove(x, y) {
if(level[Math.floor(x/20)][Math.floor(y/20)] == 1 || level[Math.ceil(x/20)][Math.floor(y/20)] == 1 || level[Math.floor(x/20)][Math.ceil(y/20)] == 1 || level[Math.ceil(x/20)][Math.ceil(y/20)] == 1) {
return false;
} else {
return true;
}
}


Update function:

function update(key) {
switch(key) {
case "W":
if(checkmove(pos.x, pos.y-2)) {
pos.y -= 2;
break;
} else {
break;
}
case "S":
if(checkmove(pos.x, pos.y+2)) {
pos.y += 2;
break;
} else {
break;
}
case "A":
if(checkmove(pos.x-2, pos.y)) {
pos.x -= 2;
break;
} else {
break;
}
case "D":
if(checkmove(pos.x+2, pos.y)) {
pos.x += 2;
break;
} else {
break;
}
default:
break;
}
}


This is called before movement is applied the the 'player'. The game is laid out as a 2D array of 1's and 0's for testing purposes.

Can I use fewer mathematical operations (less expensive for each tick) to check for a collision between the player and a '1' on my game grid?

-

Those refactoring will help :

idea is to test only upper-left point and bottom-right point, which should be ok 99.99999% of the time. (Rq : i know we could test wether the second test is in fact about the same tile, but i guess that would be slower).

function checkmove(x, y, w, h) {
var tileX, tileY, thisTile;
tileX = Math.floor(x/20) ;
tileY = Math.floor(y/20) ;
thisTile = level[tileX][tileY];
if(thisTile == 1 ) return false;
tileX = Math.floor((x+w)/20) ;
tileY = Math.floor((y+h)/20) ;
thisTile = level[tileX][tileY];
if(thisTile == 1 ) return false;
return true;
}


For your move section, there's a big issue : it is not time based. So it will run at different speed on different devices. Not good.

Define a basic game loop where you measure time. If you're interested, you can watch this fiddle i made : http://jsfiddle.net/KVDsc/

And have your game objects move by delta x = delta time * speed.

function update(key, dt) {
var dx, dy, newX, newY;
dx   = this.speedX * dt;
dy   = this.speedY * dt;
newX = pos.x;
newY = pos.y;
var kpc = 0 ;                          // key pressed count;
if      (key == "W" && ++kpc) newY-=dy;
else if (key == "S" && ++kpc) newY+=dt;
if      (key == "A" && ++kpc) newX-=dx;
else if (key == "D" && ++kpc) newX+=dx;
if( kpc && checkmove(newX, newY) ) {
pos.x = newX;
pos.y = newY;
}
}


All this should be faster. Notice that you might want to use if instead of select to enable going, say, both to the right and downward.

-
Thanks for the insight regarding testing the upper left and bottom right! I am using the delta time in my actual game. The demo was just a quick one that I mocked up for you guys :) – Oliver Barnwell Aug 19 '14 at 1:22
@OliverBarnwell You'll get better code reviews by not mocking up code for your question. – James Khoury Aug 19 '14 at 1:24
I'd have thought it would've been helpful to help describe the situation? I do admit that I should've made sure my code was more to the point. For that I apologise. – Oliver Barnwell Aug 19 '14 at 1:27
@OliverBarnwell If you read the faq: On-Topic It says to keep the original code intact. – James Khoury Aug 19 '14 at 1:29
(And PS : didn't i told you, on stack overflow, that here was a better place ?? ;-) ) – GameAlchemist Aug 19 '14 at 1:36

Before making this more efficient I'd suggest making it more readable:

in your switch statement you have break in both the true and else parts of your if statement.

if(checkmove(pos.x, pos.y-2)) {
pos.y -= 2;
break;
} else {
break;
}


It would be much easier to read if you just move the break out of the if statement.

if(checkmove(pos.x, pos.y-2)) {
pos.y -= 2;
}
break;


In another question I had suggested a bit shaving optimisation that might help here. Math.floor(number) is equivalent to number >> 0 this bit shifts the number by 0 bits and converts it to an integer.

Math.floor(x/20)


becomes

(x / 20) >> 0


similarly adding almost 1 (+ 1 - Number.EPSILON) and then flooring will give you the ceiling. (number + 1 - Number.EPSILON) >> 0

The checkmove() function calculates this multiple times on the one line. I'd rewrite it to calculate once.

function checkmove(x, y) {
var floorX = (x/20) >> 0;
var floorY = (y/20) >> 0;
var ceilX = ((x/20) + 1 - Number.EPSILON) >> 0;
var ceilY = ((y/20) + 1 - Number.EPSILON) >> 0;

return level[floorX][floorY] == 1 ||
level[ceilX][floorY] == 1 ||
level[floorX][ceilY] == 1 ||
level[ceilX][ceilY] == 1;
}

-
Thanks! Interesting to shift it by 0 :D I assume something like ~~ would work too :) – Oliver Barnwell Aug 19 '14 at 1:25
@OliverBarnwell I hadn't thought of that. Might be worth a try but I'd guess thats two operations where as bit shifting is one (I think I will test out that theory sometime). – James Khoury Aug 19 '14 at 1:27
Why not do x /= 20; y /= 20; at the start of the function? Also ciel should be ceil. – mjolka Aug 19 '14 at 1:53
x /= 20; y /= 20; would only save you one inexpensive operation. Not that it would hurt either. 6 one way, half a dozen the other way. – James Khoury Aug 19 '14 at 5:22
The way you're calculating the ceiling won't work. For example, Math.ceil(25 / 20) is 2, but ((25 / 20) + 0.5) >> 0 is 1. – mjolka Aug 19 '14 at 6:44

This line:

if(level[Math.floor(x/20)][Math.floor(y/20)] == 1 || level[Math.ceil(x/20)][Math.floor(y/20)] == 1 || level[Math.floor(x/20)][Math.ceil(y/20)] == 1 || level[Math.ceil(x/20)][Math.ceil(y/20)] == 1) {


is really long and makes your code difficult to read. You can refactor this to something much easier on the eyes:

if(level[Math.floor(x/20)][Math.floor(y/20)] == 1 ||
level[Math.ceil(x/20)][Math.floor(y/20)] == 1 ||
level[Math.floor(x/20)][Math.ceil(y/20)] == 1 ||
level[Math.ceil(x/20)][Math.ceil(y/20)] == 1) {


I'm sure there's a way to simplify these checks, but I will leave that to someone more experienced to comment on.

if(checkmove(pos.x, pos.y-2)) {
pos.y -= 2;


The reader is left to wonder what the significance of 2 is here. You should define it in a variable so we explicitly know what it means. It is important to make your code self documenting so that it is easier to understand.

if(checkmove(pos.x, pos.y-2)) {
pos.y -= 2;
break;
} else {
break;
}


There has to be a cleaner way to implement input than if/else statements and breaks inside of a switch statement, but I do not know Javascript well enough to write the code for you. You should be using an onbuttonpressed event in the browser to call the function if I am not mistaken.

Also I did take a quick look at the full game that you linked to. I encourage you to post more of that code for review!

-