hmmm... efficient collision?

[NexusOne]

I'm thinking of a way to create efficient collision detection in a 3d world. Would it be efficient enough if I were to create a 2d array of linked lists of references to game objects, where the each slot in the array is imagined to be a column in the 3d world, of objects with similar x and z coordinates (y being the up-vector)? Then based on where a person is in the world, they could only collide with objects in the linked list of the spot in the world they are at, or adjacent ones. That would eliminate about 99% of all game objects from collision tests. Any thoughts?

[kevglass]

This is part of how I spatially partition my current game world. It works fine but thats really to do with the type of map I'm working with. If most of your map spread is width and depth this should be enough.

Kev

[Jeff]

Another common approach is a nested tree of bounding volumes.

Games published by our own members! Check 'em out!

[princec]

All collision detection algorithms between n objects ultimately execute in ((n-1)*(n-1))/2 time. No matter which way you slice and dice the problem with clever and fiddly linked lists and octrees you will always end up doing at least ((n-1)*(n-1))/2 collision detection tests, whether it being direct collisions or classification of objects beforehand into octree nodes.

You can gradually tend towards an n log n time algorithm by using tricks like octrees but the added complexity and overhead means this only becomes viable as n grows very large.

My advice, therefore, is to go with the simplest approach you can get away with, and make sure that you can change your approach if you find that there is a bottleneck in collision detection. Brute force is perfectly acceptable for a couple of hundred objects per frame.

Cas