Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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?

share|improve this question

3 Answers 3

up vote 6 down vote accepted

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.

share|improve this answer
    
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 at 1:22
3  
@OliverBarnwell You'll get better code reviews by not mocking up code for your question. –  James Khoury Aug 19 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 at 1:27
1  
@OliverBarnwell If you read the faq: On-Topic It says to keep the original code intact. –  James Khoury Aug 19 at 1:29
2  
(And PS : didn't i told you, on stack overflow, that here was a better place ?? ;-) ) –  GameAlchemist Aug 19 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;
}
share|improve this answer
    
Thanks! Interesting to shift it by 0 :D I assume something like ~~ would work too :) –  Oliver Barnwell Aug 19 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 at 1:27
1  
Why not do x /= 20; y /= 20; at the start of the function? Also ciel should be ceil. –  mjolka Aug 19 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 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 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!

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.