11
\$\begingroup\$

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?

\$\endgroup\$

3 Answers 3

Reset to default
6
\$\begingroup\$

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.

\$\endgroup\$
8
  • \$\begingroup\$ 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 :) \$\endgroup\$ Commented Aug 19, 2014 at 1:22
  • 3
    \$\begingroup\$ @OliverBarnwell You'll get better code reviews by not mocking up code for your question. \$\endgroup\$ Commented Aug 19, 2014 at 1:24
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Aug 19, 2014 at 1:27
  • 1
    \$\begingroup\$ @OliverBarnwell If you read the faq: On-Topic It says to keep the original code intact. \$\endgroup\$ Commented Aug 19, 2014 at 1:29
  • 2
    \$\begingroup\$ (And PS : didn't i told you, on stack overflow, that here was a better place ?? ;-) ) \$\endgroup\$ Commented Aug 19, 2014 at 1:36
8
\$\begingroup\$

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;
}
\$\endgroup\$
6
  • \$\begingroup\$ Thanks! Interesting to shift it by 0 :D I assume something like ~~ would work too :) \$\endgroup\$ Commented Aug 19, 2014 at 1:25
  • \$\begingroup\$ @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). \$\endgroup\$ Commented Aug 19, 2014 at 1:27
  • 1
    \$\begingroup\$ Why not do x /= 20; y /= 20; at the start of the function? Also ciel should be ceil. \$\endgroup\$ Commented Aug 19, 2014 at 1:53
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Aug 19, 2014 at 5:22
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Aug 19, 2014 at 6:44
5
\$\begingroup\$

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!

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.