I am making an action platform 2D game, something like Megaman. I am using XNA to make it.

I already made player physics, collisions, bullets, enemies and AIs, map editor, scrolling X Y camera (about 75% of game is finished ). As I progressed I noticed that my game would be more interesting to play if bullets would be destroyed on collision with regular(stationary) map blocks, only problem is that if I use my collision detection (each bullet with each block) sometimes it begins to lag(btw if my bullet exits the screen player can see it is removed from bullet list)

So how to improve my collision detection so that memory usage would be so high? :) ( on a map 300x300 blocks for example don't think that bigger map should be made);

            int block = 0;
            int bulet= 0;
            bool destroy_bullet = false;

            while (bulet < bullets.Count)
                while (block <  blocks.Count)
                    if (bullets[bulet].P_Bul_rec.Intersects( blocks[block].rect))
                    {//bullets and block are Lists that holds objects of bullet and block classes
                        //P_Bul_rec just  bullet rectangle  

                        destroy_bullet = true;
                if (destroy_bullet)
                { bullets.RemoveAt(bulet); destroy_bullet = false; }
                else { bulet++; }
                block = 0;
  • 2
    \$\begingroup\$ A CD check between the bullet and a tile should be O(1). If you can convert from screen position to tile location usually Tile[x / tileWidth + (y / tileHeight) * mapWidth] you can completely remove the inner while block. \$\endgroup\$ Mar 19, 2012 at 23:17
  • \$\begingroup\$ Alternately, when you move the bullet, raycast from its current location to the final location, and you won't have fast bullets teleporting through blocks. \$\endgroup\$
    – AndrewS
    Jul 29, 2014 at 22:26

2 Answers 2


Your collision detection is slow because you're checking for collisions between every bullet and every block, even if they're nowhere near one another. You should implement a space-partitioning scheme such as a quadtree. This will greatly minimize the number of potential collisions you have to detect, and should keep things at a playable speed.

Here's an article that talks specifically about using Quadrees in XNA.


I don't think a Quadtree is necessary, since you already have the blocks/map grid. Basically convert the bullet coordinates to grid coordinates (aka position divided by block size) and then check collisions only with blocks that are near it. I guess you could also check it based on velocity of the bulled (if +x/+y then check only blocks that are forward or upward of the bullet and so on).


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .