Most efficient way to check collision

Question

For example, I have a player and a map, to check player collision with some block we need to check entire map tiles, but the bigger the map, the slower the framerate. What's most efficient way to check collision?

Answer 1

For maps with square tiles you don't actually need to check against every tile, instead you can perform a simple calculation that will give you the tile the player is currently on.

Xtile = (Player.X - Map.X) / Map.Tile.Width

You then do the same for the y and get the tile that the player is on.

Now if your player position is on the upper left hand you more than likely want to perform actions on all the tiles the player is currently over. To do that you would have to choose one of two options; If the players width is constant then you can simply iterate the couple tiles that are part of the square the player would represent.

For example if your tile width is the same as your player width, and same for the height then you could calculate the Xtile and Ytile, then also perform actions on the (Xtile + 1, Ytile), (Xtile, Ytile + 1) and the (Xtile + 1, Ytile + 1)

On the other hand if your player has a variable width(or you want to use the same technique for all possible characters of various sizes) then you calculate the Xtile and Ytile and use loops to iterate on all things inside the rectangle.

For example your Xtile was calculated to be 3, your Ytile was calculated to be 4, your character is 3 tiles wide and 5 tiles high Then you could:

for(int i = Xtile; i <= (Xtile + Character.WidthInTiles); i++){
    for(int p = Ytile; o <= (Ytile + Character.HeightInTiles); o++){
        CurrentTile = Map[i][o];
        //Perform actions on CurrentTile here
    }
}

Edit: forgot to mention regular AABB collisions and speed; As a side note for your regular collisions you shouldn't be checking if there is a collision but rather if a collision is impossible.

By that I mean that you should be checking if PlayerX + PlayerWidth is less than the ObjectX, because that means that its too far off the right and so you don't need to check the rest of the possibilities which is faster.

The final version with all four sides checked looks like this:

if((Object1X + Object1Width) < Object2X || Object1X > (Object2X + Object2Width) || (Object1Y + Object1Height) < Object2Y || Object1Y > (Object2Y + Object2Height)){
    //There is a collision detected between Object1 and Object2
}