1
\$\begingroup\$

This question already has an answer here:

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.

\$\endgroup\$

marked as duplicate by Josh Jan 27 '14 at 21:46

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1
\$\begingroup\$

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)

enter image description here

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.

\$\endgroup\$
  • \$\begingroup\$ That makes sense. I'm going to try and take only the tiles he is touching and add them to another List<> and then loop through that instead of all the tiles on the map. Number 4 is unclear to me. Can you provide more details for that point? \$\endgroup\$ – Devin Rawlek Jan 26 '14 at 19:43
  • \$\begingroup\$ I've gotten nowhere with pulling tiles from the map list of all the tiles and into a list of tiles the sprite is touching. Could you provide an example for point two on building the list? \$\endgroup\$ – Devin Rawlek Jan 27 '14 at 4:15
  • \$\begingroup\$ @DevinRawlek I've added some extra explanation. I hope it is more clear now. \$\endgroup\$ – ThatOneGuy Jan 27 '14 at 20:25
  • 1
    \$\begingroup\$ The explanation of how to use the array did the trick! I switched my tile storage from a list to an array and I can now spawn thousands of sprites and have them collide properly. \$\endgroup\$ – Devin Rawlek Feb 1 '14 at 18:19

Not the answer you're looking for? Browse other questions tagged or ask your own question.