#### Archived

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

# Cutting down collision detection

This topic is 5697 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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 on other sites
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!

##### 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 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 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 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 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