Tile Based Sprite Collision With Lots of Sprites [duplicate]

Question

I am running into lag when loading many sprites onto the screen. If I have less than 12 on the screen it runs smoothly until I add a couple more and then it bogs down.

I currently have this as my detection code;

public void Collision(Sprite sprite, Rectangle newRectangle, bool passable, bool speedRestricted, int xOffset, int yOffset)
        {// Tile boundaries
            if (sprite.Bounds.Top(newRectangle) && passable == false)
            {
                animation.Position = new Vector2(sprite.Position.X, (newRectangle.Y - sprite.Bounds.Height));
            }
            if (sprite.Bounds.Left(newRectangle) && passable == false)
            {
                animation.Position = new Vector2((newRectangle.X - sprite.Bounds.Width), sprite.Position.Y);
            }
            if (sprite.Bounds.Right(newRectangle) && passable == false)
            {
                animation.Position = new Vector2((newRectangle.X + sprite.Bounds.Width), sprite.Position.Y);
            }
            if (sprite.Bounds.Bottom(newRectangle) && passable == false)
            {
                animation.Position = new Vector2(sprite.Position.X, (newRectangle.Y + sprite.Bounds.Height));
            }
}

It is called in like this;

foreach (var tile in map.CollisionTiles)
        {
            player.Collision(player, tile.Rectangle, tile.Passable, tile.SpeedRestricted, map.Width, map.Height);

            foreach (var sprite in sprites)
            {
                sprite.Collision(sprite, tile.Rectangle, tile.Passable, tile.SpeedRestricted, map.Width, map.Height);
            }
        }

Now collision detection works perfectly so I don't have an issue there it's just when there are lots of sprites in my List<Sprite> sprites does it lag. If I remove the collision detection from the code I can load thousands of sprites onto the map.

Question: How do I limit the detection area for the sprites so it only compares the tiles around the sprite instead of all the tiles on the map for each sprite.

I have looked through the other questions and found none when it comes to multiple sprite detections for tile maps, just the main player's collision detection.

Answer 1

As you said, the problem arises because you're comparing each tile to each sprite. This leads to many unnessesary checks. You can cut down on these checks by only checking the tiles directly around the sprites.

1. Make sure your tiles are stored appropriately. In a multidimensional array, or anywhere where their positional data is stored implicitly.

2. Find the tile each of the corners of your sprite(the red rectangle) is hovering over. In the image these are [10,3], [12,3], [10,6] and [12,6].

3. Determine the range of your sprite, using the four tiles from step 2. (The yellow area)

4. Check collisions only for the tiles within the sprites range plus an extra tile on all sides. (The green area)

This way you can cut down on most collision checks, especially when your level size is large.

If your sprite is smaller than your tiles, you can get away with only determining what tile the center of your sprite is over(instead of all corners), because it can only ever collide with the 9 tiles around its center.

Finally, for further improvement, you only have to check the sprites that are moving. If a sprite is not moving, it won't be able to collide with any tiles anyway.

EDIT: Step one is important.

Store your tiles in a multidimensional Array.

When your tiles are stored in a List<tile> is is impossible to find close tiles without looping over everything (as you probably have noticed). An array makes this much easier, because it implicitly stores the locational information of whatever is in it.

Let's say you have a 10 by 10 tilegrid.

private Tile[,] TileArray = new Tile[10,10];

You create can create a multidimensional array and place the tiles in the array according to their position. you can now use the information that a tile at tileArray[5,6] will always be next to a tile at tileArray[6,6].

Combining the array and the fact that we know the tile size, finding the tiles becomes a breeze.

let's say we have a very small Sprite and we want to find the tiles it can collide with. We can start by calculating the Sprites position on the tileArray (Step 2, simplified because the sprite is small). simply by doing the following:

int XOnArray = Math.Floor(sprite.X/tile.width);
int YOnArray = Math.Floor(sprite.Y/tile.height);

This gives us the X- and Y-coördinates of the sprite on the tileArray. We know it is (for example) currently on tileArray[4,5]. We can now check for collision with all the tiles near tileArray[4,5] (as per step 4):

for(int i=XOnArray-1; i<=XOnArray+1; i++) 
{
    for(int j=YOnArray-1; j<=YOnArray+1; j++)
    {
        checkCollision()
    }
}

This decreases the collision checks per sprite from all tiles to only nine!

Again, if anything is unclear, let me know, and I'll try to explain it better.