Better performance of 2D collision detection than simply checking each pair of objects

I need my 2D collision detection algorithm to be scalable, but I fear it is not. My algorithm does this:

1. Created a LinkedList of the sprite objects (which includes all of their data)

   开发者_StackOverflow社区

   private LinkedList<Sprite> collisionSpritesList = new LinkedList<Sprite>();

2. The main game loop then adds all sprites to the LinkedList:

   public void GameUpdate() { collisionSpritesList.add(avatar); collisionSpritesList.add(enemy1); collisionSpritesList.add(enemy2); }

3. Then the collisionCheck() method called; it cycles through all of the pair's of entities in the list looking for a collision. Then the LinkedList is completely erased. This is because the entities need to be updated with their new locations.

public boolean checkCollision() {

for(int i = 0; i < collisionSpritesList.size(); i++)
{


for(int j = 0; j < collisionSpritesList.size(); j++)
 {
if(i != j)
 {
     if(collisionSpritesList.get(i).getRectangle().intersects(collisionSpritesList.get(j).getRectangle()))
     {
        Point p = gridMap.getRandomWalkableLocation();
        collisionSpritesList.get(j).setLocation(p.x * gridMap.getCellSize(), p.y * gridMap.getCellSize());
        collisionSpritesList.clear();
        return true;
     }
  }

} }

  collisionSpritesList.clear();
    return false;
}

My question is how efficient is this way of checking a collision? Should it be done in a different way? If so what methods are there that are scalable?

I would consider using a QuadTree to subdivide your space and then only check for collisions in sprites that are in the same "buckets" or space.

If you can partition your sprites in a data structure that takes into account their position then you can limit the number of collision tests you need to perform.

One data structure that is used is called a quad tree. The following limk describes how to use collision detection in combination with a quadtree:

http://lab.polygonal.de/2007/09/09/quadtree-demonstration/

Keep a sorted list (sorted by one of the axes) and resort it each cycle with a bubble sort this will scale to O(n*x) with x the average amount of movement each cycle.

and then use a sweep algorithm which has O(n*k) with k the average overlap on the sort axis

(the list is sorted by minX here)

for(int i = 0; i < collisionSpritesList.size(); i++)
{
  for(int j = i+1; j < collisionSpritesList.size(); j++)
   {
     if(collisionSpritesList.get(j).getRectangle().minX()>collisionSpritesList.get(i).getRectangle().maxX())
         break;//breakout inner for when no overlap on x-axis possible

     if(collisionSpritesList.get(i).getRectangle().intersects(collisionSpritesList.get(j).getRectangle()))
      {
        Point p = gridMap.getRandomWalkableLocation();
        collisionSpritesList.get(j).setLocation(p.x * gridMap.getCellSize(), p.y * gridMap.getCellSize());
        return true;
      }
  }
}