Collision Detection Optimization For A Large Number of Objects
Author
I need to seriously optimize my collision detection code, and would like some advice to go about this. Heres my basic game set up so far.
Almost all objects can collided with other objects, And I have one giant list of all these objects at any given time. Thus Whenever I check collision, i go through the list checking one object with each other object, then selecting the next object, and repeating, and so on.
Problem is, this is incredibly slow for the amount of objects I plan to have. It works fine for say ~50 or so objects, but when running upwards of 500 or so (how many I plan on having on any given map) It gets insanely slow fps.
Im using basic circular bounding collision (no sqrt functions though) to test collision initially. Is there any way to reduce the unnescessary checking of every object with every objcet every frame?
I thinking octree or something to that effect, but anyone else have other ideas / suggestions?
Thx
-Vulcan
Yeah quadtree can be a good solution, or octree depending of your engine.
You can use scene graphs too.
In all cases, the purpose is to have a hierarchical representation of your world, in order to quickly reject lots of objects in the same time.
You can use scene graphs too.
In all cases, the purpose is to have a hierarchical representation of your world, in order to quickly reject lots of objects in the same time.
Quadtrees and Octrees are often times not fast enought when you have SOOO many objects. If you can just wait a month or two, I can write an article on my new culling/collision algorithm that''s most likely much faster than quad and octrees for large worlds with lots of objects in fairly-outdoor scenes (such as gta3-type worlds or large terrain-like worlds). Portal engines will probly be faster for indoor scenes however. And I think occlusion algs should work very nicely with this new one although i can''t test it out to be sure. The only downfall to it is that it takes up slightly more space than a quad and octree does but that shouldn''t make too much of a difference on computers nowadays.
But if you can''t wait that long, go with the quad and octree approach because they will probly yield the best results now.
And this isn''t the place to post it I know, but can anyone tell me the following answers, nothing more:
1.) Can i get the algorithm copyrighted or arn''t ideas copyrightable. But bresenham got his in his name, right?
2.) Where should I submit the article if i wrote one? Obviously gamedev.net but do I need to submit it to a place somewhere to get recognition?
---
My Site-My Tetris Clone w/Source
Come join us on IRC in #directxdev @ irc.afternet.org
But if you can''t wait that long, go with the quad and octree approach because they will probly yield the best results now.
And this isn''t the place to post it I know, but can anyone tell me the following answers, nothing more:
1.) Can i get the algorithm copyrighted or arn''t ideas copyrightable. But bresenham got his in his name, right?
2.) Where should I submit the article if i wrote one? Obviously gamedev.net but do I need to submit it to a place somewhere to get recognition?
---
My Site-My Tetris Clone w/Source
Come join us on IRC in #directxdev @ irc.afternet.org
I''ve just solved this problem recently. I''ve got over 8000 units running around and colliding with a framerate of 66 per second.
I''ve got a two dimensional array of pointers. In my case, the dimensions are 64x64. These pointers point to a linked list. My units themselves ARE the linked list. Each unit contains the pointer to the next in the list. A single object only needs to check for collisions in its list and the surrounding lists.
As a comparison between my method and the "straight-forward" method, I''ll show the number of collisions tested...
With 8192 units, 67,108,864 collisions would have to be tested. Even with my P4 1.4GHz, this is unworkable.
Now, with the units divided up into a two-dimensional 64x64 array (4096 areas) there is only an average of 2 units per area (or linked list). If a unit checks its areas and the surrounding areas, that is a total of 9 linked lists it must traverse (this can be optimized). So on average, a unit checks 18 collisions for a total of 147,456 collision tests per frame. With the type of collision test you are using, this would be very practical.
- Jay
"I have head-explody!!!" - NNY
Get Tranced!
I''ve got a two dimensional array of pointers. In my case, the dimensions are 64x64. These pointers point to a linked list. My units themselves ARE the linked list. Each unit contains the pointer to the next in the list. A single object only needs to check for collisions in its list and the surrounding lists.
As a comparison between my method and the "straight-forward" method, I''ll show the number of collisions tested...
With 8192 units, 67,108,864 collisions would have to be tested. Even with my P4 1.4GHz, this is unworkable.
Now, with the units divided up into a two-dimensional 64x64 array (4096 areas) there is only an average of 2 units per area (or linked list). If a unit checks its areas and the surrounding areas, that is a total of 9 linked lists it must traverse (this can be optimized). So on average, a unit checks 18 collisions for a total of 147,456 collision tests per frame. With the type of collision test you are using, this would be very practical.
- Jay
"I have head-explody!!!" - NNY
Get Tranced!
I apologize if I repost something that someone already has said, but here's how I would do it. Have a grid (2 dimentional array) of arrays to pointers. So I guess in effect, this would actually be a 3D array, but that isn't so important. Anyway, each square in this grid would be an array because it would have to point to all of the objects that are within it's bounds. So you would have to be careful and set the number high enough so that you would never run over memory if you happen to have too many objects in one square.
Then what you can do is have an update function where first all of the pointers in the array are set to null. After that, go through each item, and since the grid size will be uniform, each item will put a pointer of itself on this grid of arrays wherever it happens to be positioned. Then each item will only have to check for collisions for all of the items in the box it is in, as well as for the surrounding 8 boxes, if the item happens to be on the border of one of the grids.
To be a little more specific, let's say that your map is 100 units by 100 units. You could make each square in the grid 10 by 10. That way, say an object is positoined at x = 54 and y = 23, it would be in grid [5][2]. Then it would check against all of the pointers in 5,2, and the surrounding 8 boxes.
I guess thiws would only work with 2D, but if your game is 3D, you could modify it so that you have a 3 dimentional grid.
Assuming an even distribution of items, each item would only have to check 9 out of 100 grids. And if you want, you could make more grids, finding out the optimum number of sections for your code to run smoother.
--Vic--
edit: it seems like my solution is somewhat similar to the answer above me. However, I'm not quite understanding the purpose of having a linked list, but maybe it's above my head
[edited by - Roof Top Pew Wee on August 29, 2002 1:40:54 PM]
Then what you can do is have an update function where first all of the pointers in the array are set to null. After that, go through each item, and since the grid size will be uniform, each item will put a pointer of itself on this grid of arrays wherever it happens to be positioned. Then each item will only have to check for collisions for all of the items in the box it is in, as well as for the surrounding 8 boxes, if the item happens to be on the border of one of the grids.
To be a little more specific, let's say that your map is 100 units by 100 units. You could make each square in the grid 10 by 10. That way, say an object is positoined at x = 54 and y = 23, it would be in grid [5][2]. Then it would check against all of the pointers in 5,2, and the surrounding 8 boxes.
I guess thiws would only work with 2D, but if your game is 3D, you could modify it so that you have a 3 dimentional grid.
Assuming an even distribution of items, each item would only have to check 9 out of 100 grids. And if you want, you could make more grids, finding out the optimum number of sections for your code to run smoother.
--Vic--
edit: it seems like my solution is somewhat similar to the answer above me. However, I'm not quite understanding the purpose of having a linked list, but maybe it's above my head
[edited by - Roof Top Pew Wee on August 29, 2002 1:40:54 PM]
each square in this grid would be an array because it would have to point to all of the objects that are within it's bounds. So you would have to be careful and set the number high enough so that you would never run over memory if you happen to have too many objects in one square.
the linked list is used instead of an array so that size of the list is dynamic so you don't need to predefine a size.
[edited by - necromancer_df on August 29, 2002 9:08:53 PM]
the linked list is used instead of an array so that size of the list is dynamic so you don't need to predefine a size.
[edited by - necromancer_df on August 29, 2002 9:08:53 PM]
Here''s yet another one:
In my game I have 3 linked lists, one for the x-plane, y-plane and z-plane.
Every object has 2 vector classes representing an axis-aligned bounding box: {Low.x, Low.y, Low.z} and {High.x, High.y, High.z}.
Each vector instance belongs to all 3 linked lists (linkage built into the class). Each list is sorted every update according to x, y and z order. This sorting is cheap because the orientation of all objects never varies much at each individual update. If all objects are sitting still then there is no sorting at all, just N checks.
With these ordered lists, you just check all vectors between an object''s low vector and its high vector in all 3 dimensions. My code also keeps the count of vectors between each low vector and high vector, so that you always do the check in the list with the fewest vectors between the low and high vector. And if by good chance there are no in-between vectors in any one dimension, there is no collision.
For each collision (meaning there is overlap in all 3 dimensions) I then perform a more stringent check.
It seems to exhibit from N to NlogN performance generally, and there is no dimensional limit which is why I like it.
This could equally apply in 2 dimensions.
Value of good ideas: 10 cents per dozen.
Implementation of the good ideas: Priceless.
Proxima Rebellion - A 3D action sim with a hint of strategy
In my game I have 3 linked lists, one for the x-plane, y-plane and z-plane.
Every object has 2 vector classes representing an axis-aligned bounding box: {Low.x, Low.y, Low.z} and {High.x, High.y, High.z}.
Each vector instance belongs to all 3 linked lists (linkage built into the class). Each list is sorted every update according to x, y and z order. This sorting is cheap because the orientation of all objects never varies much at each individual update. If all objects are sitting still then there is no sorting at all, just N checks.
With these ordered lists, you just check all vectors between an object''s low vector and its high vector in all 3 dimensions. My code also keeps the count of vectors between each low vector and high vector, so that you always do the check in the list with the fewest vectors between the low and high vector. And if by good chance there are no in-between vectors in any one dimension, there is no collision.
For each collision (meaning there is overlap in all 3 dimensions) I then perform a more stringent check.
It seems to exhibit from N to NlogN performance generally, and there is no dimensional limit which is why I like it.
This could equally apply in 2 dimensions.
Value of good ideas: 10 cents per dozen.
Implementation of the good ideas: Priceless.
Proxima Rebellion - A 3D action sim with a hint of strategy
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
