Sign in to follow this  
brainydexter

Which broadphase collision tech should I use ?

Recommended Posts

brainydexter    158
I am making this 3D First person shooter based game. It would have quake / unreal type levels, but I am focused on getting the gameplay done first. As of now, I have a bunch of players moving around and shooting bullets at each other. I am trying to figure out which broadphase collision technique to use, given my game-context. I spent some time reading about different things that I can use and came across these three broad categories: Grids / Oct-trees / BSP (kd trees). What I can't decide is, which one of these should I use ? The thought that goes on in my head about Oct-trees/BSP is, since the players are constantly moving and firing bullets at each other, it would be quite expensive to update the trees each frame, thus I think they will not be a good choice. I understand they are good for static geometries or levels since its an initial cost and the geometry doesn't change as much. Can someone here please help me reason out what would be a good approach to adopt. Thanks

Share this post


Link to post
Share on other sites
rewolfer    120
You're right about oct-trees. They are good for object-world collisions, where the world is static but for moving geometry it's costly. You may want to look into a Sweep-And-Prune (aka Sort And Sweep) method for moving geometry. This has some bad worst case issues with regards to clustering, but there are work-arounds that can improve performance a lot. I recommend giving it a look.

Share this post


Link to post
Share on other sites
Eric_Brown    127
Sweep and prune is definitely a good way to go for moving objects.

Note: sweep and prune maintains a persistent list of potentially colliding objects. This is a slightly different paradigm from tree based approaches, where you might query a single object against the entire tree. This paradigm shift might not bode well if you are trying to insert sweep and prune into an existing collision system.

Share this post


Link to post
Share on other sites
oliii    2196
Yeah, I'm not a big fan of sweep and prune when it comes to standard collision queries (what objects are in the path of a ray, what objects are near a spherical area, what objects are near a rectangular area, what object inside a conic section, ect...). Stuff that is actually quite useful for virtual environments.

However, it's good at detecting collision pairs.

Share this post


Link to post
Share on other sites
brainydexter    158
Well, I don't have a existing system in-place for handling collision as of now, so I can go eitherways and if required implement Sweep and Prune.

Actually, I did implement sweep and prune once and got it to work. The problem that I felt was, I could not understand how could I get to work effectively with dynamic objects. When the objects move, the intervals due to there bounding volume changes and then I have to repeat the whole process of sorting them intervals to get intersecting pairs. If I have to do the whole thing again and again every frame, I think its going to be very slow.

What do you guys think about that ?

Share this post


Link to post
Share on other sites
Eric_Brown    127
The thing is, sweep and prune takes advantage of spatial coherency. You've got to resort the boundary points, but chances are, you only need to flip the order of the boundary point with the neighboring boundary point. Thus a simple linear search is all that is needed.

In an oct-tree, the resort may require recursing an entirely different branch of the tree, especially for objects in the "middle".

I've contemplated using a bisection search on the sweep and prune boundary lists, in order to do "one-shot" collision querying. I've also seen an efficient ray-casting implementation for sweep and prune. So I think there are ways to merge the two paradigms.

It's just if you were already performing single object collision queries and ray-casts, and you try to plop sweep and prune into the middle of all that, you've got some tweaking to do. It's better to design the collision system to use sweep and prune from the ground up.

[EDIT: resort = re-sort!]

Share this post


Link to post
Share on other sites
brainydexter    158
Quote:
Original post by Eric_Brown
The thing is, sweep and prune takes advantage of spatial coherency. You've got to resort the boundary points, but chances are, you only need to flip the order of the boundary point with the neighboring boundary point. Thus a simple linear search is all that is needed.

Since bullets would be traveling fast, do you think they would still satisfy the property of spatial coherency ?
See this is where I got lost earlier as well. The part where you talk about "flipping the order of the boundary point with the neighboring boundary point". How does this work out ? How can we just flip a boundary point with a neighbour's boundary point ?

Quote:
Original post by Eric_Brown
It's just if you were already performing single object collision queries and ray-casts, and you try to plop sweep and prune into the middle of all that, you've got some tweaking to do. It's better to design the collision system to use sweep and prune from the ground up.

[EDIT: resort = re-sort!]


I am writing things from ground up, so I hope this works out well.

[Edited by - brainydexter on March 18, 2010 3:16:38 PM]

Share this post


Link to post
Share on other sites
Eric_Brown    127
Good point about bullets.

You probably don't want to represent the bullets explicitly in the sweep and prune lists. Like I said before, I've seen a ray cast algorithm that works with sweep and prune. You could treat the bullet as a ray. The slower moving objects would be fine using sweep and prune. This kind of sucks, though, since you have to introduce a special case to handle bullets.

Share this post


Link to post
Share on other sites
brainydexter    158
Heh, well I think I am back to square one. Because the main actors in the game are:
- Players
- Fired Bullets
- Weapons (before they are picked up, i.e. placed in world => static )
- World level geometry

I was thinking of dealing with world level geometry later on (& probably use BSP), so that leaves me with other three.

If not sweep and prune, then which one should I use ?

Alternatively, this is what I was thinking:
- for each GameObject's Bounding sphere, calculate its min and max extents.
- For minPt and maxPt, calculate a hash value, that represents a bucket
- Each bucket is mapped to a list of GameObjects (using the idea of hashmap)
- At the end of given frame iteration, for each of the keys, the corresponding value i.e. list of gameObjects are potentially colliding

What do you guys think about this ?

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this