Tile Engine Collision Optimization

Question

Alright, so today I decided to try to further optimize my collision detection code for my tile engine.

This is what I did:

Circle class checks if there are points within range. If there are, then check for collision between player and tile.

Code:

        int tileWidth = 128;
        int tileHeight = 128;

        int[,] Layer3 = { 1, 1, 1, etc... };

        int tileMapWidth = Layer3.GetLength(1);
        int tileMapHeight = Layer3.GetLength(0);

        Rectangle tile, tile2;

        for (int x = 0; x < tileMapWidth; x++)
        {
            for (int y = 0; y < tileMapHeight; y++)
            {
                int wallIndex = Layer3[y, x];

                if (wallIndex == 1) //Full-sized Tile Collision (128 x 128)
                {
                    if (collisionCircle.Contains(new Vector2(x * tileWidth + (tileWidth / 2) + (int)Player.camera.Position.X,
                                                             y * tileHeight + (tileHeight / 2) + (int)Player.camera.Position.Y))) //+ tile / 2 is for centering the point
                    {
                        tile = new Rectangle(x * tileWidth + (int)Player.camera.Position.X, y * tileHeight + (int)Player.camera.Position.Y, tileWidth, tileHeight);
                        Collide(tile);
                    }
                }
            }
        }

This would check throughout layer3 if there is a "1". If there is, assign rectangle and check for collision if point is inside collision radius.

Also, I checked this code(with a draw method), and I know it's working properly, at least the behavior.

I added in about 120,000(32 x 3888) tiles to try to make it lag, and before the code, it lagged a little bit. But after I added in the code, it lagged even more so.

I thought that since it would only check for collision between tiles(points) that are within the radius it wouldn't even remotely lag, but that's not the case...

Any help/ideas on how to optimize this would be great.

Thanks a lot, Shyy

EDIT:

Cirlce.Contains() code:

    public bool Contains(Vector2 Point)
    {
        return ((Point - position).Length() <= radius);
    }

I used a circle because I've heard it's faster than using a rectangle.

try to pretest with rectangle, not circle especially if your circle test is using sqrt instead of comparing the squared distances — LearnCocos2D
@Cocos, thanks for replying. I posted my Circle.Contains() code above. I'm only using a circle because I've heard it's faster than using a rectangle. — Shyy Guy
Where did you hear that? It's only about equivalent in terms of performance if you compare the squared lengths but since you're using Length() this means square root is used which makes it slower. See answer from @OSborn. — LearnCocos2D
Alright, I changed the code in the circle class to the one Osborn recommended. It now is a little bit better on performance. I added in more tiles to check (now at 153,000), and it's running at around 30-40 FPS (guessing on that number, since I don't have a proper FPS on screen). So it's not the near flawless performance I thought I could get(thinking of Million Tile Engine), though I suppose a 400 x 400 map is pretty huge, and that's about 160,000 tiles assuming I'd cover the whole map with collision tiles, which wouldn't happen. That's good enough. Thanks for the help, everyone. — Shyy Guy
Wouldn't it make a lot more sense to limit collision detection to just the visible tiles plus maybe an extended area that's close to the visible area? — LearnCocos2D

OSborn OSborn · Accepted Answer · 2014-09-29T20:00:16

Another possible optimization is instead of return ((Point - position).Length() <= radius); use return ((Point - position).LengthSquared() <= radius * radius);

This is faster because Vector2.Length() has to perform a costly square root operation. Vector2.LengthSquared() does not have to perform that slow operation. The radius has to be multiplied by itself to account for the length from the vector being squared.

It sounds like you're trying to determine what tiles you don't need to use for collision with the player. Another optimization you could do is that if a tile at (X=5,Y=5) is above and to the left of the player, then you don't need to check a tile at (X=4,Y=4). Similarly if (X=5,Y=5) is below and to the right, (X=6,Y=6) is guaranteed to be too far as well. Try to determine when you've passed the player and no longer need to check collisions.

Tile Engine Collision Optimization

2 Answers