Allegro.cc - Online Community

Allegro.cc Forums » The Depot » Grid based collision detection demo

This thread is locked; no one can reply to it. rss feed Print
Grid based collision detection demo
Frank Drebin
Member #2,987
December 2002
avatar

Hi guys,

when I noticed that my game slows down horribly with increasing number of objects, I decided to use a grid to divide the screen into different cells to reduced the number of collision checks.
To investigate the effect of the grid size and the number of object on FPS I wrote a small demo that might be worth to share here. Take a look if you are interested (source code included).

{"name":"612070","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/f\/f\/ff6ef97f78399d7cee06809d3d4da7f5.png","w":959,"h":539,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/f\/f\/ff6ef97f78399d7cee06809d3d4da7f5"}612070

Controls:
LEFT MOUSE BUTTON: Add object
KEY_UP: Increase grid size
KEY_DOWN: Decrease grid size
T: Toggle statistics

Edgar Reynaldo
Major Reynaldo
May 2007
avatar

I got to around 750 objects and then the 1x1 and 2x2 grids started stalling. Switched it up to 16, and it ran fine again. Amazing work.

Why not use a quad tree though? Do you prefer a grid to a sub dividing terrain?

I think a grid works fine though. ;) Nice job.

{"name":"612073","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/1\/9\/19f66a7fe30d41284f048ef36052dd73.png","w":962,"h":573,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/1\/9\/19f66a7fe30d41284f048ef36052dd73"}612073

Frank Drebin
Member #2,987
December 2002
avatar

Thanks!

Of course a quad tree would be even better but I am lazy ;)
Also using a grid renders the game from unplayable (0 FPS) to smoothly running (100 FPS) so that's enough for the time being :)

Edgar Reynaldo
Major Reynaldo
May 2007
avatar

Niunio
Member #1,975
March 2002
avatar

Nice work.

If simple grid works, just use it. Quad tree will increase memory a little. Quad tree will help with the objects that are "bewteen tiles", though.

-----------------
Current projects: Allegro.pas | MinGRo

Frank Drebin
Member #2,987
December 2002
avatar

Frank, how do you handle multi-grid cell occupants?

An object can be in up to 4 cells. Each corner of the object is checked in which cell it is in:

int i=0;
while ((i<MAX_OBJECTS) && (objects[i].active()))
{
   int c1=get_index(objects[i].get_x(),objects[i].get_y());
   int c2=get_index(objects[i].get_x()+4,objects[i].get_y());
   int c3=get_index(objects[i].get_x(),objects[i].get_y()+4);
   int c4=get_index(objects[i].get_x()+4,objects[i].get_y()+4);
   cells[c1].add_object(i);
   cells[c2].add_object(i);
   cells[c3].add_object(i);
   cells[c4].add_object(i);
    i++;
}

Edgar Reynaldo
Major Reynaldo
May 2007
avatar

Frank Drebin
Member #2,987
December 2002
avatar

I assume you're removing duplicates?

Of course! Feel free to take a look at the source code...

Go to: