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"}
Controls:
LEFT MOUSE BUTTON: Add object
KEY_UP: Increase grid size
KEY_DOWN: Decrease grid size
T: Toggle statistics
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"}
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
Frank, how do you handle multi-grid cell occupants?
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, 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++; }
I assume you're removing duplicates?
Anyway, nice implementation. I may have to steal write one myself
I assume you're removing duplicates?
Of course! Feel free to take a look at the source code...