How to fetch only the sprites in the player's range of motion for collision testing? (2D, axis aligned sprites)

Question

I am working on a 2D sprite game for educational purposes. (In case you want to know, it uses WebGl and Javascript) I've implemented movement using the Euler method (and delta time) to keep things simple. Now I'm trying to tackle collisions.

The way I wrote things, my game only has rectangular sprites (axis aligned, never rotated) of various/variable sizes.

So I need to figure out what I hit and which side of the target sprite I hit (and I'm probably going to use these intersection tests). The old fashioned method seems to be to use tile based grids, to target only a few tiles at a time, but that sounds silly and impractical for my game. (Splitting the whole level into blocks, having each sprite's bounding box fit multiple blocks I might abide. But if the sprites change size and move around, you have to keep changing which tiles they belong to, every frame, it doesn't sound right.) In Flash you can test collision under one point, but it's not efficient to iterate through all the elements on stage each frame. (hence why people use the tile method).

Bottom line is, I'm trying to figure out how to test only the elements within the player's range of motion. (I know how to get the range of motion, I have a good idea of how to write a collisionCheck(playerSprite, targetSprite) function. But how do I know which sprites are currently in the player's vicinity to fetch only them?)

Please discuss. Cheers!

Answer 1

There are a few things you can do. I would recommend you try them in turn and see if your performance is acceptable. You can also re-use the simpler method in the advanced method.

1. Generate a quick check to see if a sprite is close enough to the player and check the player against each sprite. This distance check could be something like:
   • Pythagorean theorem
   • Pythagorean theorem sans square root (checking against the square of your min distance)
   • See if their X tile location is +/- n spaces and their Y tile location is +/- n spaces
2. Use QuadTrees to limit the number of sprites you need to check against the player. There is a balance here between keeping the minimum quad size low and keeping the traversal short. Play around with it before deciding you want to try something more complex.

Also make sure your collisionCheck method has a quick abort. Just do a real quick bounding box overlap test and see if there is a collision and if it's worth finding the exact point of impact.

Answer 2

To check which sprites are in the vicinity, you can just use the distance formula.

distance = sqrt( (x1-x2)^2 + (y1-y2)^2 );

But if you want to check collision for only the sprites in the vicinity, then its not a good choice. Anyways, you'd have to calculate the distance for all the sprites; instead you can check collision itself.

To check the side from where your player has collided, its better you have a function as

checkCollision(playerBound, targetBound, playerVelocity)

We won't check if a collision has occurred. Instead, we will check if it is about to occur it the player makes its next move.

Lets have a playerBound to the player, the rectangle that determines the player position and size. Similarly for targetBound

playerVelocity would be velocity vector of the player per time span (method call).

We can have a function that checks if a rectangle collides with another

bool checkXCollision(bound1, bound2)
{
    if((bound1.left <= bound2.right && bound1.left >= bound2.left) || (bound1.right <= bound2.right && bound1.right >= bound2.left)) //Check for x-axis
        return true; //Collision is there
    return false;
}    
bool checkYCollision(bound1, bound2)
{
    if((bound1.bottom <= bound2.top && bound1.bottom >= bound2.bottom) || (bound1.top <= bound2.top && bound1.top >= bound2.bottom)) //Check for y-axis
        return true; //Collision is there
    return false;
}  
bool checkCollision(bound1, bound2)
{
    if(checkXCollision(bound1, bound2) && checkYCollision(bound1, bound2))
        return true;
    return false;
}

Notation for top, bottom, left and right

     top   __________
          |          |
          |          |
          |          |
          |     o    |
          |          |
          |          |
  bottom  |__________|
          left       right

Case 1: Colliding at y-axis

       __________
      |          |
      |          |
      |          |
      |          |
      |          |\   _________
      |          | \ |         |
      |__________|  \|         |
                     |         |
                     |_________|

If after one more step, they collide, then collision has occured from the left.

Case 2: Colliding at x-axis

       __________
      |          |
      |          |
      |          |
      |          |
      |          |
      |          |
      |__________|
               \
               _\______
              |        |
              |        |
              |        |
              |________|

If after one more step, they collide, then collision has occured from the top.

Case 3: Not colliding at any axis

       __________
      |          |
      |          |
      |          |
      |          |
      |          |
      |          |
      |__________|
               \
                \   ________
                 \ |        |
                  \|        |
                   |        |
                   |________|

But after making one step they will collide, so we are not sure whether its from left or right.

Direction checkCollision(playerBound, targetBound, playerVelocity)
{
    bool xCollided = false;
    bool yCollided = false;
    bool isCollided = false;
    if(checkXCollision(playerBound, targetBound))
        xCollided = true;
    else if(checkYCollision(playerBound, targetBound))
        yCollided = true;

    playerBound.x += playerVelocity.x;
    playerBound.y += playerVelocity.y;
    if(checkCollision(playerBound, targetBound))
        isCollided = true;

    if(isCollided)
    {
        if(xCollided)  //Case 1
            //Collision has occured either from left or right depending on playerVelocity.x
        else if(yCollided)  //Case 2
            //Collision has occured either from top or bottom depending on playerVelocity.y
    }
}

For case 3, we can increment the position of the player by small amount unless it collides at exactly 1 axis. Of if still it collides at both axis, we can say that their corners (not sides) are collided.

Alternatively, we can compare the slope of the line made by o-p and the velocity vector. From there, we can know whether its going more towards x or y.

       __________
      |          |
      |          |
      |          |
      |          |
      |     o____|__
      |     |    |  |
      |_____|____p  |
            |       |
            |_______|