Efficient Collision detection

This is just an on-the-fly idea I had reading your post, so I really don't have any specifics, just the general idea. At first I was thinking you could do a simple distance test between objects before performing a more-intensive collision test, but that just adds to the number of tests you have to do. So then I thought, what if you could break the level up into "sections". You could store the section data in a linked list or something. The whole idea is when an object enters or leaves a section, it adds or deletes itself to/from that section list. This way when it's time to test for collisions, it checks only the objects in the same section list that it is in.

Kewl. Okay people start pointing out the flaws... I'm sure there's some in there somewhere. Is this a technique used already? It seriously just popped into my head so maybe I read it somewhere...

_________________________________________________________________

Drew Sikora
A.K.A. Gaiiden

ICQ #: 70449988
AOLIM: DarkPylat

Blade Edge Software
Staff Member, GDNet
Public Relations, Game Institute

3-time Contributing author, Game Design Methods , Charles River Media (coming April/May 2002)
Online column - Design Corner at Pixelate

Unnoficial IGDA chat! [polaris.starchat.net -> #igda]
NJ IGDA Chapter - NJ developers unite!! [Chapter Home | Chapter Forum]

quote:

---

Original post by Gaiiden
Kewl. Okay people start pointing out the flaws... I'm sure there's some in there somewhere. Is this a technique used already? It seriously just popped into my head so maybe I read it somewhere...

---

Believe it or not, that's already a common technique for both 2D and 3D. I forget the official name, but I refer to it as the bucket method, each section you described being a bucket (commonly stored as a linked list).


[edited by - Sorairo on June 14, 2002 1:11:35 AM]

Not trying to hijack the thread, but this is sort of related to collision detection.

How could you implement a line of sight, or sight radius for something in your game? For instance, you want an enemy ship to start moving toward the player or another object when one of them enters the ship''s sight radius (just a circle with the ship at the origin). Would you just have the enemy ship do a collision detection every frame and then act accordingly?

I am interested in the answer to the original post as well!

The nicest method I know is a sweep sort list. This is basically a list that keeps endpoints (start and end) of the axis aligned bounding boxes. In 3d you would have 3 of these lists, in 2d you would have 2 (so one for each axis). The endpoint list is a sorted list. Ah well, there''s good documentation and source code on this link: http://www.win.tue.nl/~gino/solid/

If your frame coherency is high, this method is extremely fast, because you only check the rectangles that are moving (and those are the only ones that are interesting)

Cheers,
Nick

quote:

---

Original post by Sorairo
Believe it or not, that''s already a common technique for both 2D and 3D. I forget the official name, but I refer to it as the bucket method, each section you described being a bucket (commonly stored as a linked list).

---

Oh I beleive it It just popped in my head so easily I knew it had to be some common technique. Glad I thought of it tho - I could use it too, heh.

quote:

---

Original post by NickWaanders
The nicest method I know is a sweep sort list. This is basically a list that keeps endpoints (start and end) of the axis aligned bounding boxes. In 3d you would have 3 of these lists, in 2d you would have 2 (so one for each axis). The endpoint list is a sorted list. Ah well, there''s good documentation and source code on this link: http://www.win.tue.nl/~gino/solid/

If your frame coherency is high, this method is extremely fast, because you only check the rectangles that are moving (and those are the only ones that are interesting)

---

This sounds a lot like an article I read in Game Programming Gems 2 on Recursive Dimensional Clustering. I found the idea to be really neat. Google it up or head down to your local bookstore to check it out if you don''t have the book (WHY do you not have this book?? )

When I coded Nebuloids
I implemented a collision stack system which was populated during the draw loop since that''s when I calculated if the object was on screen which ment I needed to check it''s size so since I had already calculated x/y start/end it was not too much more code to place the object start x/y start/end onto a stack.

I used two stacks, one for bullets and the other where the shootable objects got placed into.

Then just loop through the bullet stack against the object stack (while checking that the objects in the object stacj where still active and had not be shot past there max hits so no redundant checking on already killed objects).

The other naughty thing I did was too only place objects that where on screen onto the stacks (as the player won''t see off screen collisions anyway) which also saved time.

I must admit it was a bit of a tricky technique to get going and debugging it was a not pleasant experince and had me scratching my head for a while but once I had debugged the damn thing it is really fast!

The other method I have used is to use a 2d cell map (like good old c64 character collision) and place the bullet object references into the cells they are over and then each object checks which cells it''s over for bullet references. This method is really fast as there is no iterative factor to collsion only clear the collision cell map and populate it with bullet references, but the only problem is that it doesn''t deal with multiple bullets in the same cell area but if that is not a problem it is definately the fastest.

Well that''s my 10 cents worth, Hope it helps

:-)

quote:

---

Original post by Arion
I was wondering if collision checks could be cut down by dividing the screen into quads and when a sprite changes position, it reports which quad it is in. The problem here is the sprite can be in all four quads if it is in the center of the screen. Hmm, that''s a problem.

---

you could make the ''check'' sequence a state machine,
and it''ll stick with whatever was reported last.
ie) guy is in the center of the screen, and it
reports 1,2,3,4 it''ll report it back as quad 4.
if that''s a problem with the actual collision detection
(ie, only colliding in quad 4 but not the other three)
you could do something like this:

test for occupancy in quad1
run collision detection routines for quad1

test for occupancy in quad2
run collision detection routines for quad2

test for occupancy in quad3
run collision detection routines for quad3

test for occupancy in quad4
run collision detection routines for quad4

-eldee
;another space monkey;
[ Forced Evolution Studios ]

1. divide your world up into a grid. (say, 256x256 blocks)
2. have each grid block store a reference to objects in it
3. if an object is in multiple grid blocks, just add them to all of ''em, like normal
4. when an object moves, find out which grid block(s) its in, and only collision detect against other objects in that grid

optimization -- set a flag when an object collides, so incase it is check again (and obviously the same collision is detected), that it will only handle the collision once

I have impemented something like what NickWaanders describes. Each world update (20 times per second) it sorts the lower and upper bound of each object in a parallel-linked list with elements linked according to x position, y position and Z position, although It could probably be shrunk to two dimensions easily enough. Each box has a lower element (MinX, MinY, MinZ) and an upper element (MaxX, MaxY, MaxZ).

Then for each box, only check the list elements between the lower element and the upper element on either the x axis, y axis or z axis. Its best to choose the axis that has fewest elements between lower and upper, so it maintains a count and simply goes with the axis where there are fewest elements between the lower and upper. Well its fairly complicated, but it works. Even in a stress-test with 1600 entities roaming around it didn't do too badly at all.

If you'd like the classes I wrote for doing this, send me an e-mail. I'd post it all here, but it's too big.

Value of good ideas: 10 cents per dozen.
Implementation of the good ideas: Priceless.
The Battlezone Launch Pad

[edited by - BS-er on June 15, 2002 10:52:34 PM]

quote:

---

Original post by Rocket05

1. divide your world up into a grid. (say, 256x256 blocks)
2. have each grid block store a reference to objects in it
3. if an object is in multiple grid blocks, just add them to all of ''em, like normal
4. when an object moves, find out which grid block(s) its in, and only collision detect against other objects in that grid

optimization -- set a flag when an object collides, so incase it is check again (and obviously the same collision is detected), that it will only handle the collision once

---

Can''t you people read past the first post?? Or did you just want to distill mine?

And that sounds cool BS-er. If you don''t mind, I''d like to have a look - gaiiden@gamedev.net

I implemented the sections thing in my game as well. It works quite nicely

***********************
          

Chaoslab... I don't think its such a great idea to ignore collisions just coz they're not in the player's field of view... what this effectively means is that if you're not looking, enemies could just charge straight through the wall (and each other) and bite yer head off!

Collision detection needs to be performed for every dynamic object in order to maintain a consistent game world... you naughty monkey.

[edit] - damn typos

[edited by - Bad Monkey on June 15, 2002 12:59:28 AM]

Bad Monkey: Absolutely. It''s silly not to check collisions if you can''t see an object. If you turn around everything in the world might fall through it!

Try an Octree. Check out my tutorial here: www.CodeFortress.com

Also, I had a talk with the guy who did the collision detection for Neverwinter Nights (I believe) and he says that multiple bounding volume checks is all you need. Use spheres to represent all your objects (it''s not fast, it''s FREAKIN fast).

I implemented just this in my asteroids clone and I was getting an avg of about 70fps with 40 asteroids tested againsted 10 bodys (planets and sun) and all the bullets in the world (about 60 spheres). So 60 * 40 * 10 = 24000 checks. I dropped about 4 frames I think then when I didn''t have it on. Not too shabby. So what you could actually do is create 4 or 8 or 16 or whatever numbers of world spheres and any objects that pass their border is included in the lower subset check. Similar to the grid theory someone mentioned a little while ago, but more like an Octree. It''s a hack but it could work.


"Love all, trust a few. Do wrong to none." - Shakespeare

Dirge - Aurelio Reis
www.CodeFortress.com

Yes god forbid, if you look up, you would suddenly find yourself falling into a bottomless pit

~Vendayan