efficiency - Quad trees/grid based collision - putting logic into action

First of all, I've only been writing my own game logic for a short while, so I apologize if this might seem straight forward.

I've been reading a lot about quad trees and grid based collision detection. I understand the logic - basically don't check for collision unless objects are near basically. But it never is mentioned how the actually execute this.

I have a couple of possibile methods in my head but am not sure which is best

General collision test - no optimisation

for(var i:int = 0; i < objects.length; i++){
        //find object A
        var objectA = objects[i];

        for(var j:int = i + 1; j < objects.length; j++){

            //find object B
            var objectB = objects[j];

            if(objectA.collidesWith(objectB){

               //handle collision logic
              }
        }

store neighbours (method 1) But what if we want to optimise the collisions to only check objects that are near. Do we still run through all the objects, or do we create an array with near objects to check through?

var objects:Array = new Array();
    var neighbours:Array = new Array();

    for(var i:int = 0; i < objects.length; i++){
        //find object A
        var objectA = objects[i];

        for(var j:int = i + 1; j < objects.length; j++){
            //find object B
            var objectB = objects[j];


            if(objectA.isNear(objectB){

               neighbours.push(objectA, objectB);
              }
        }

    }

    //somewhere else

    for(i:int = 0; i < neighbours.length; i++){
        //only check neighbours

        for(j:int = i + 1; j < neighbours.length; j++){

            if(objectA.collidesWith(objectB){

               //handle collision logic
              }
        }

    }

loop all objects but only check neighbours for collision (method 3) The other possibillity is that we still loop through everything but check if the objects are near before testing the collision.

for(var i:int = 0; i < objects.length; i++){
        //find object A
        var objectA = objects[i];

        for(var j:int = i + 1; j < objects.length; j++){
            //find object B
            var objectB = objects[j];


            if(objectA.isNear(objectB){
               //they are near - check collision!
               if(objectA.collidesWith(objectB){

               //handle collision logic
              }
            }
        }


    }

Store objects in tile data (method 3) Using a tile based sytem allow for another option; Store the objects that are on a specific tile in the tile data itself. Check to see on which tile the object is the surrounding tiles contain any objects it could collide with:

var ObjectA;

for(var i:int = 0; i < 4; i ++){
//check 4 surrounding tiles from object A

   if(Object.currentTile + surroundingTile[i] CONTAINS collidable object){
   //check collision!

    if(objectA.collidesWith(surroundingTile.object){

    //handle collision logic
     }

}
}

I always try to look at the real world as an example. If I wanted to compare items with the same colour it would seem illogical to check every entire item even if they don't match colour (Method 2, check each item). I would probably collect the items with the same colour (objects that are near each other) and check those (method 1), instead of checking everything.

This isn't an appropiate comparison since the items in collision checking are constantly moving so the order gets mixed up. That whats confusing me.

Would it be more efficient to check each item, thus removing the strain of keep generating an array of neighbours.

Or is it more efficient to find neighbours thus not having to loop through so many objects to check the collision?

Keep changing the data on each tile seems very intensive aswell, so i'm not sure if that a good idea..

I've been thinking of a tower defense game where the tower needs to detect objects if objects are in range before it shoots at it. And it just seems silly to check all items while at some times there won't be any objects near at all.

I apologize for the long post, always having trouble explaining myself!

Answer

You need to reduce the count of actual collision checks. Yeah obvious I know. So lets elaborate on this:

Your first collision check algorithm without any optimization: how many checks will it do in one run? If n is the count of objects, this will be around n*(n-1) checks. For a lot of objects (>100) this will be horribly slow.

Your neighbor checking method will not be much faster. If your objects aren't static and move around a lot, you will need to build these neighbors list for each object everytime in your game loop. This is actually worse than the first algorithm since you're doing n*(n-1) to build the neighbour list and then check for each object if it collides with one of its neighbours.

You need to partition your game space. Lets say your game space is 400x400 pixels wide. Your can partition this into 4 sub-space each 200x200 in size and check for each object into which of the sub-spaces it belongs (one object can be inside more than one sub-space). Then you will only need to check if the objects in each subspace collides with other object in the same sub-space.

So the runtime cost will be: n for building the 4 sub-space list + (n/4)*((n-1)/4) which is a lot better than the previous runtime cost. This can be cut down further by making the sub-spaces smaller (e.g. 50x50).

So our algorithm now looks something like this:

for each (object in objects)
  check into which subspace the object belongs

for each (subspace in subspaces)
  for each (object in subspace)
    check object for collision with other objects in same subspace

This is somewhat similar to your tile data idea. But the subspaces do not need to be the same size as the tiles.

We can do one last step to optimize this further using a quadtree. Let k be the count of subspaces. To build the spaces object lists we are doing k*n checks, leading to a lot of checks if your game world gets large.

To cut this cost down we use a quadtree. A quadtree is another way to partition our game space. Instead of dividing our 400x400 space into 64 50x50 subspaces and checking for each object in which of the 64 subspaces it currently is, the game space is divide into 4 subspaces half the size of the game space (200x200), which in turn are divide into smaller subspaces (100x100), which in turn are divided again into 50x50 subspaces. This is our quadtree.

Now if we want to know into which 50x50 subspace an object belongs we check into which of the 200x200 subspaces it belongs. Then we go one level deeper in our quadtree and check against the 4 100x100 subspaces which are inside the 200x200 subspace we just found. This is repeated until we know into which 50x50 subspace the object belongs. So how many checks were now necessary? 4 for each level of the the quadtree (Remember an object can be on the edge of two subspaces). So we need 4*3 checks to assign an object to the correct 50x50 subspace. A lot better than 64 checks.

So our quadtree algorithm needs 4*3*n checks to build the subspace lists and then something like k*(n/k) checks to check the collisions of each object.