Making Collision Detection more Efficient

Question

I'm working on an HTML5-canvas game, where the map is randomly generated 10px by 10px tiles which the player can then dig and build upon. The tiles are stored in an array of objects and a small map contains about 23000 tiles. My collision detection function checks the players position against all non-air tiles every run through (using requestAnimationFrame()), and it works perfectly but I feel like it's CPU intensive. Collision function is as follows (code came from an online tutorial):

function colCheck(shapeA, shapeB) {
    var vX = (shapeA.x + (shapeA.width / 2)) - (shapeB.x + (shapeB.width / 2)),
    vY = (shapeA.y + (shapeA.height / 2)) - (shapeB.y + (shapeB.height / 2)),
    hWidths = (shapeA.width / 2) + (shapeB.width / 2),
    hHeights = (shapeA.height / 2) + (shapeB.height / 2),
    colDir = null;

    // if the x and y vector are less than the half width or half height, they we must be inside the object, causing a collision
    if (Math.abs(vX) < hWidths && Math.abs(vY) < hHeights) {         
        // figures out on which side we are colliding (top, bottom, left, or right)         
        var oX = hWidths - Math.abs(vX),             
            oY = hHeights - Math.abs(vY);         
        if (oX >= oY) {
            if (vY > 0) {
                colDir = "t";
                shapeA.y += oY;
            } else {
                colDir = "b";
                shapeA.y -= oY;
            }
        } else {
            if (vX > 0) {
                colDir = "l";
                shapeA.x += oX;
            } else {
                colDir = "r";
                shapeA.x -= oX;
            }
        }
    }
    return colDir;
};

Then within my update function I run this function with the player and tiles as arguments:

for (var i = 0; i < tiles.length; i++) {
    //the tiles tag attribute determines rendering colour and how the player can interact with it ie. dirt, rock, etc. 
    //anything except "none" is solid and therefore needs collision
    if (tiles[i].tag !== "none") {
        dir = colCheck(player, tiles[i]);
        if (dir === "l"){
            player.velX = 0;
            player.jumping = false;
        } else if  (dir === "r") {
            player.velX = 0;
            player.jumping = false;
        } else if (dir === "b") {
            player.grounded = true;
            player.jumping = false;
        } else if (dir === "t") {
            player.velY *= -0.3;
        }
    }
};

So what I'm wondering is if I only check tiles within a certain distance from the player using a condition like Math.abs(tiles[i].x - player.x) < 100 and the same for y, should that make the code more efficient because it will be checking collision against fewer tiles or or is it less efficient to be checking extra parameters?

And if that's difficult to saying without testing, how do I go about finding how well my code is running?

Answer 1

but I feel like it's CPU intensive

CPU's are intended to do a lot of stuff very fast. There is math to determine the efficiency of your algorithm, and it appears that your current implementation is O(n). If you reduce the number of tiles to a constant number, you would achieve O(1), which is better, but may not be noticeable for your application. To achieve O(1), you would have to keep an index of the X closest tiles and incrementally update the index when closest tiles change. I.e. if the player moves to the right, you would modify the index so that the left most column of tiles are removed and you get a new column of tiles on the right. When checking for collisions, you would simply iterate through the fixed number of tiles in the index instead of the entire set of tiles.

...should that make the code more efficient because it will be checking collision against fewer tiles or or is it less efficient to be checking extra parameters?

The best way to answer that is with a profiler, but I expect it would improve performance especially on larger maps. This would be an O(n) solution because you still iterate over the entire tile set, and you can imagine as your tile set approaches infinity, performance would start to degrade again. Your proposed solution may be a good compromise between the O(1) solution I suggested above.

The thing you don't want to do is prematurely optimize code. It's best to optimize when you're actually experiencing performance problems, and you should do so systematically so that you get the most bang for your buck. In other words even if you did have performance problems, the collision detection may not be the source.

how do I go about finding how well my code is running?

The best way to go about optimizing code is to attach a profiler and measure which parts of your code are the most CPU intensive. When you figure out what part of your code is too slow, either figure out a solution yourself, or head over to https://codereview.stackexchange.com/ and ask a very specific about how to improve the section of code that isn't performing well and include your profiler information and the associated section of code.

Answer 2

In response to Samuel's answer suggesting I use a profiler:

With a map made up of ~23 000 tiles in an array: The original collision code was running 48% time. By changing if (tiles[i].tag !== "none") to the following the amount of time spent checking for collisions dropped to 5%.

if (tiles[i].tag !== "none" 
    && Math.abs(tiles[i].x - player.x) < 200 
    && Math.abs(tiles[i].y - player.y) < 200)

With a map made up of ~180 000 tiles: The original collision code was running 60-65% of the time and performance of the game is so low it can't be played. With the updated code the collision function is only running 0.5% of the time but performance is still low, so I would assume that even though less tiles are being checked for collision there are so many tiles that checking their position relative to the player is causing the game to run slowly.