xna - Efficient Tile-based collision detection for a lot of squares?

currently I am working on my own take of a tile-based game (think Terraria, but less fantastical (I think that's a word? Sorry if it isn't)).

Anyway, I currently have collision detection working (for corner cases even!) which was a big step for me. There is something extremely gratifying about seeing a sprite not run through a block. But then I had the idea to benchmark. Bad idea.

1,000 squares, no problem. 10,000 squares, for 3 characters was kind of laggy. 100,000 squares (really huge map), for 3 characters was unplayable.

I'm having the issue where I don't want to even consider the blocks that are too far from the player, characters, items, etc., but I don't want to load those in-out of memory constantly.

Here's my algorithm so far, feel free to criticize.

foreach (Block in level)
{
    if (distance from block to player > a specified amount)
        ignore this block;
    else
    {
        get the intersection depth between the two bounding boxes
        if (depth of intersection != Zero-vector)
        {
            check y size vs x size

            resolve on smallest axis
        }
    }
}

As you will note, when the level size get's bigger, the Order of this algorithm grows by N blocks. I would like to not even consider blocks that aren't even near the player.

I'm thinking maybe use a (0,0) to (mapWidth,mapHeight) double-array of blocks instead of a list, calculating a danger-zone depending on the person's position e.g., if player's position is at (10, 20) it will look from (0, 10) to (20, 30), or so on.

Any thoughts and considerations are awesome, thank you.

Answer

Yes, you're thinking correctly. You should be using a 2D array of tiles since that allows you to index tiles by position.

Block[,] level = new Block[width, height];

And since the player can only collide with its surrounding tiles, the number of collision checks you need to do is very small. This of course depends on the size of the player. The Platformer sample does it like this:

int leftTile = (int)Math.Floor((float)characterBounds.Left / tileWidth);
int rightTile = (int)Math.Ceiling(((float)characterBounds.Right / tileWidth)) - 1;
int topTile = (int)Math.Floor((float)characterBounds.Top / tileHeight);
int bottomTile = (int)Math.Ceiling(((float)characterBounds.Bottom / tileHeight)) - 1;

for (int y = topTile; y <= bottomTile; ++y)
{

    for (int x = leftTile; x <= rightTile; ++x)
    {
        // Handle collisions with the tile level[x,y] just like you were doing!
    }
}

Check the sample if you still have any problems.