Improving collision detection efficiency

Moderator
Posts: 365
Joined: 2002.04
Post: #1
My little game engine has a very simple sphere-based collision detection system. However, although it's simple, it can get pretty slow when there are a lot of objects around, so I'm looking for ways of making it more efficient.

It works like this.... I have three lists of objects which exist in a big wraparound continuum:
  • Normal objects (which can collide with one another)
  • Bullets (which can only collide with normal objects)
  • Special effects (which don't require collision detection)

For the normal object list, I check every item in the list against every other item once only. I then check every item in the normal list against every item in the bullet list (bullets can't hit each other so this is a simpler process). Everything in the special effects list gets ignored.

The real number crunching comes from testing the normal object list. As I add more objects, it gets to be more and more intensive, up to the point where I spend more time doing collision detection than drawing the graphics.

My question is: are there any good ways of reducing the number of collisions that need to be processed?

Neil Carter
Nether - Mac games and comic art
Quote this message in a reply
Member
Posts: 164
Joined: 2002.04
Post: #2
octtrees or some similar structure.
Quote this message in a reply
ededed
Unregistered
 
Post: #3
octtrees or some similar structure??????????????????
WHAT?

You could check if the bounding boxes of the spheres intersect then check if the spheres intersect only if the boundiung boxes do.

Fast sphere collision detection:

Sphere a, b;

if ((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) + (a.z-b.z)*(a.z-b.z) < (a.rad+b.rad)*(a.rad+b.rad)) return YES;
return NO;
Quote this message in a reply
Member
Posts: 164
Joined: 2002.04
Post: #4
I think the bounding box thing would actually make it go slower... from my experience if you divide the world into sections then you only have to collide the objects in one section with those in the same section, or on the border. This gets rid of a lot of pointless tests.
Quote this message in a reply
ededed
Unregistered
 
Post: #5
That is a good way too. It is faster to detect for bounding box collisions then sphere collisions but it still might not be fast enough.

What I meant was that if you have two sphere instead of checking if they intersect you check if there bounding boxes intersect and if they do then check if they intersect. This works because checking for bouunding box collisions is very fast and pythagoras's hyp formulae is really slow on a computer because of all the squareing
Quote this message in a reply
Luminary
Posts: 5,143
Joined: 2002.04
Post: #6
Sphere-sphere collision detection is much faster than axis-aligned bounding box collision detection. You only have to do one if statement rather than 6, and the math is not really that much worse. You don't have to take the square root for a sphere-sphere collision, you can compare the squares.

If you want to reduce your load, really the only way to go is (like David said), some kind of tree structure to cut out large numbers of collisions. The easiest such structure to program is a quadtree (for 2D collisions), or an octtree (for 3D).
Quote this message in a reply
Moderator
Posts: 365
Joined: 2002.04
Post: #7
Thanks for the suggestions, guys.

I'm already using a pretty efficient sphere-sphere collision detection routine (the same as OneSadCookie mentioned). To reduce the number of individual tests, I think I'm going to go for dividing space into 2D cuboids because my gameplay is primarily 2D. I suspect I might be able to get away without quadtrees because I've just managed to add more efficiency elsewhere, but I'll keep it in mind anyway.

I need to sit down and actually read some octtree/quadtree source before I know what I'm talking about in any case!

Cheers!

Neil Carter
Nether - Mac games and comic art
Quote this message in a reply
ededed
Unregistered
 
Post: #8
... What are octree's? Similar to BSP's?
Quote this message in a reply
Moderator
Posts: 365
Joined: 2002.04
Post: #9
Quote:Originally posted by ededed
... What are octree's? Similar to BSP's?

As I understand it, you treat space as a cube and divide it into eight smaller cubes. You then subdivide each new cube into up to eight even smaller cubes and so on. This forms a tree structure that you can quickly traverse looking for objects. I believe the idea is that you only need to consider cubes of space that actually have something in them.

If someone with a bigger brain than me would like to elucidate, please do! Wink

Neil Carter
Nether - Mac games and comic art
Quote this message in a reply
Jens
Unregistered
 
Post: #10
It's really quite easy. If you have a quadtree, it is essentialy a bounding box/rectangle divided into four new quadtrees and so on until you reach the required depth. Each of your objects should (if they are inside world space) belong to one or more leaf in the quadtree.

When you check for intersections, you check against the bounding box/rectangle of each node, and only continue checking at a deeper level if you get an intersection. Eventually you'll end up in a leaf containing one or more game objects. You now check against each of those as you have done before.

Of course, if you know which leaves your object belongs to, you can check against the objects in those leaves directly and skip the traversion.
Quote this message in a reply
iollmann
Unregistered
 
Post: #11
Another approach is to keep your object list sorted according to some axis. X-axis would be a nice example. Assuming your objects dont move that quickly, the list should stay reasonably sorted from frame to frame, so the re-sorting cost will be roughly proportional to N.

If you have a sorted list then collision checking is a simple exercise in starting with the first element and checking collisions with the next and later elements until you find an element in the list that is too far away to collide in the X dimension. You can safely stop checking there, and start with the next element in the list.

You probably will do a few more checks this way than for oct-trees, but on the nice side, you may spend less time bouncing around in memory, depending on how you store your list, and you wont have any empty nodes to traverse before you find an occupied one or complicated logic to figure out what nodes to check, depending on how sparse your oct-tree is defined.
Quote this message in a reply
Sta7ic
Unregistered
 
Post: #12
Octrees and quadtrees are data structures that are eight- and four-branch/leaf/child trees. That's the short version.

A linked list, including queues and stacks (but NOT arrays), refers to an object that points to another object of its kind, typically a "next" reference.
A binary tree has two "next" references, left and right, and can be used to quickly or almost automatically sort objects as they are processed.
A quadtree divides an area up into smaller, similar areas through use of four "next" references -- {q1, q2, q3, q4} -- and is more common with geometry than logical problems.
An octree contains eight "next" references, and is used for volumes. One cube can be divided into the upper/front/left or lower/back/right sections -- {ufl, ufr, ubl, ubr, lfl, lfr, lbl, lfr} respectively -- to sort spacial (3D) objects into smaller areas.

The practical use for quad and octrees is that by making more areas with fewer objects, neighboring-object checks (which require object^2 function calls) go much faster. Even after considering the cost of needing to suddenly sort all the objects, which can (should?) be done as they're handled.

I hope this helps, or at least makes sense.
-Sta7ic Matt
Quote this message in a reply
Sage
Posts: 1,482
Joined: 2002.09
Post: #13
Quote:Originally posted by Sta7ic
...and can be used to quickly or almost automatically sort objects as they are processed...
-Sta7ic Matt


I'm familiar with the idea of binary trees, but I've never really been sure what you use them for, and how do they automatically sort themselves. Don't you need to do a lot more bounding box checks for this to work?

I'm having the same problem with processing 2d objects in Metal. Doing bounding box checks is slow, using the circles makes it a little faster, but still slow.

I was going to try using a rectangular array where you would plot the links of the objects into the array, as you plot objects you would check for collisions with the links in the surrounding six boxes. The array's resolution would have to be high enough to prevent two objects in the same element. Unfortunately, this would take alot of ram, and probably be just as slow. I haven't thought much about it yet.

Anyway, I'm more interested in learning methods than implementing them in programing right now, because I'm trying to learn obj-c and/or waiting for Metal v2 to come out.

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Quote this message in a reply
Sta7ic
Unregistered
 
Post: #14
Using binary (greater/lesser) sorting techniques, you can attach extra nodes fairly quickly (compared to sorting arrays), but the best way to get this is to try it.
Make a program with a class that has a value, lessThan reference, and greaterThan reference. Have it generate some 40 numbers, sort them with a tree, and trace out how it all goes together on paper or in your head.

Unfortunately, I'm only familiar with the theory for attaching this into games. There are a couple section on using them in Game Programming Gems and some problems that can occur with them, but...

(quick, someone that's done this, bail me out?)

-Sta7ic Matt
Quote this message in a reply
Member
Posts: 304
Joined: 2002.04
Post: #15
how many objects are we talking about here? sphere - sphere collisions is an awfully fast test - are you sure that that is where your problem is?

BSP / Octrees are good for testing (whether for collision or occlusion) against static geometry. But not good with moving objects against other moving objects - which is what it sounds like you are doing.
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  Suggestion on improving retention in FREEMIUM game Mega Bee influx 0 2,163 Oct 23, 2012 05:47 AM
Last Post: influx
  Collision Detection Rant kodex 5 4,091 Apr 12, 2005 05:48 AM
Last Post: kodex