|
Grid based collision detection demo |
Frank Drebin
Member #2,987
December 2002
|
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. {"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"} Controls: |
Edgar Reynaldo
Major Reynaldo
May 2007
|
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"} My Website! | EAGLE GUI Library Demos | My Deviant Art Gallery | Spiraloid Preview | A4 FontMaker | Skyline! (Missile Defense) Eagle and Allegro 5 binaries | Older Allegro 4 and 5 binaries | Allegro 5 compile guide |
Frank Drebin
Member #2,987
December 2002
|
Thanks! Of course a quad tree would be even better but I am lazy |
Edgar Reynaldo
Major Reynaldo
May 2007
|
Frank, how do you handle multi-grid cell occupants? My Website! | EAGLE GUI Library Demos | My Deviant Art Gallery | Spiraloid Preview | A4 FontMaker | Skyline! (Missile Defense) Eagle and Allegro 5 binaries | Older Allegro 4 and 5 binaries | Allegro 5 compile guide |
Niunio
Member #1,975
March 2002
|
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. ----------------- |
Frank Drebin
Member #2,987
December 2002
|
Edgar Reynaldo said: 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
|
I assume you're removing duplicates? Anyway, nice implementation. I may have to My Website! | EAGLE GUI Library Demos | My Deviant Art Gallery | Spiraloid Preview | A4 FontMaker | Skyline! (Missile Defense) Eagle and Allegro 5 binaries | Older Allegro 4 and 5 binaries | Allegro 5 compile guide |
Frank Drebin
Member #2,987
December 2002
|
Edgar Reynaldo said: I assume you're removing duplicates? Of course! Feel free to take a look at the source code... |
|