Archived

This topic is now archived and is closed to further replies.

Laroche

Cutting down collision detection

Recommended Posts

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?

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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!

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
I have not tried this, but wouldn''t using overlapping regions solve the need to check adjacent sqares?

+----+----+----+----+
| 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 |
| | | | |
+----+----+----+----+
By overlaying a 2nd grid of the same size with a half square offset every point falls into 2 gridslots. And collisions can be resolved within the 2 slots exclusively. Overhead (colliding twice with the same object) has to be captured somehow, but it is not too common as the slots only overlap on 1/7 of their area in 2D and 1/15 in 3D



---------------------------
I may be getting older, but I refuse to grow up

Share this post


Link to post
Share on other sites