2D tilemap collision method

Question

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?

Answer 1

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.

• Oliver Barnwell: 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 :)
• James Khoury: @OliverBarnwell You'll get better code reviews by not mocking up code for your question.
• Oliver Barnwell: 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.
• James Khoury: @OliverBarnwell If you read the faq: On-Topic It says to keep the original code intact.
• GameAlchemist: (And PS : didn't i told you, on stack overflow, that here was a better place ?? ;-) )

Answer 2

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;
}

• Oliver Barnwell: Thanks! Interesting to shift it by 0 :D I assume something like ~~ would work too :)
• James Khoury: @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).
• mjolka: Why not do x /= 20; y /= 20; at the start of the function? Also ciel should be ceil.
• James Khoury: 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.
• mjolka: 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.

Answer 3

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!