Cutting down collision detection
Author
I''ve made my first game/demo, and everything works fine, but I''m trying to optimize it a bit. A little info first: It is a space shoot-em-up, with a 16k * 16k scrolling univese which is littered with enemies that track you down and shoot you. I''m using DirectDraw 7.
My collision detection is rather brute-force right now. It checks every active bullet with every active entity out there, and at the start of the game it''s a little slow, with 1000+ enemies and lots of bullets flying.
One way I read about is partitioning the game-world, so that the bullets would check for collisions only within it''s own sector. Sounds reasonable. However, wouldn''t the speed advantage gained from the technique be lost due to every object continuously polling the world to check what sector it is in? Or is there a better way to do it?
Checking which sector the object is in should be a pretty
straight forward calculation? No? It can''t be *THAT* slow...
~~~~
Kami no Itte ga ore ni zettai naru!
straight forward calculation? No? It can''t be *THAT* slow...
~~~~
Kami no Itte ga ore ni zettai naru!
nah, assuming that your "sectors" are uniformly sized rectangles, you can get the sector coordinates by dividing the ships'' coordinates by the sector size... and remember, you will only have to do collision detection for a handful of the ships/bullets now.
Author
Yeah that is fast, but making every object, every frame check it''s coordinates and add/remove itself to different sectors is pretty slow, no?
if (my.obj.x < SectorOne.x){//Add it}// rinse-repeat
What you can do is have a list for each sector to store all
the objects in that sector. Calculating the sector
is O(1) (yes, you should use uniform rectangles or "grid"),
then as part of the world update process, each object will move
itself around the "sector lists".
~~~~
Kami no Itte ga ore ni zettai naru!
the objects in that sector. Calculating the sector
is O(1) (yes, you should use uniform rectangles or "grid"),
then as part of the world update process, each object will move
itself around the "sector lists".
~~~~
Kami no Itte ga ore ni zettai naru!
Spacial locality is a very good way to speed up collision detection. So finding a good "sector" size for your world is important.
However, remember that you can''t just check objects versus objects in the same sector. You need to check them versus objects in the same sector *AND* all surrounding sectors (like a tic-tac-toe board). Because an object might be on the border of a sector or overlapping multiple sectors at once.
Also, you don''t necessarily have to check every object versus every object each frame. It depends on if the objects are always moving. If it were me I would start by dividing up the world into apropriate sized sectors, then I would use axis-aligned bounding boxes second since they have a pretty efficient rejection case (3 floating point compares on average for 3D). Then lastly I would compare objects directly against one another if they have not been rejected yet.
-Marc
However, remember that you can''t just check objects versus objects in the same sector. You need to check them versus objects in the same sector *AND* all surrounding sectors (like a tic-tac-toe board). Because an object might be on the border of a sector or overlapping multiple sectors at once.
Also, you don''t necessarily have to check every object versus every object each frame. It depends on if the objects are always moving. If it were me I would start by dividing up the world into apropriate sized sectors, then I would use axis-aligned bounding boxes second since they have a pretty efficient rejection case (3 floating point compares on average for 3D). Then lastly I would compare objects directly against one another if they have not been rejected yet.
-Marc
I have not tried this, but wouldn''t using overlapping regions solve the need to check adjacent sqares?
Something in the topleft corner of, lets say 7, has to ''collide'' with 7,2,3 and 6.
?
---------------------------
I may be getting older, but I refuse to grow up
+----+----+----+----+| 1 | 2 | 3 | 4 || | | | |+----+----+----+----+| 5 | 6 | 7 | 8 || | | | |+----+----+----+----+| 9 | 10 | 11 | 12 || | | | |+----+----+----+----+| 13 | 14 | 15 | 16 || | | | |+----+----+----+----+ Something in the topleft corner of, lets say 7, has to ''collide'' with 7,2,3 and 6.
?
+----+----+----+----+| 1 | 2 | 3 | 4 || | ...|. | |+----+----+----+----+| 5 | .6 |. 7 | 8 || | . .|. | |+----+----+----+----+| 9 | 10 | 11 | 12 || | | | |+----+----+----+----+| 13 | 14 | 15 | 16 || | | | |+----+----+----+----+ ---------------------------
I may be getting older, but I refuse to grow up
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement