PDA

View Full Version : Collision detection help



Setharian
10-07-2007, 05:41 PM
I'm writing the server-side part of a MMORPG and need to solve collision detection and the requirements are very high. All collision detection is to be handled by the server, not by the client. What this means is that the collision detection algorithm must be extremly fast and efficient. I have thought of an octree approach which would contain all the vertices/faces/polygons of all the static geometry (simplified models) and terrain and then perform collision detection on a small group of polygons. However I'm not that much of a 3D game developer so I'm lacking the required math knowledge. The system should handle 8000-16000 queries per second (~4-5k players, ~200k moving objects, ~2000k static objects) at the very least without causing much lag. What would you propose?

JernejL
10-07-2007, 05:44 PM
use a off-the-shelf physics engine, newton is good.

Setharian
10-07-2007, 06:25 PM
I don't believe newton has been designed for an application of this type...on their forums I've just found 3 threads considering its usage for an MMOG of this scale and 2 of those were for client-side collision detection...plus I need just collision detection/line of sight checks, not all the goodies newton has...

jdarling
10-07-2007, 07:54 PM
Simple sphere and polygon tests such as are documented in PolyColly? For sphere the calculation should be something such as:

Collided = S1r-S2r>S1v-S2v

Where S1 and S2 are the two spheres, r is the radius of the sphere, v is the spheres vector (normalized).

As for polygon collision, search the forums, there is a port of PolyColly that I posted up (in http://www.pascalgamedevelopment.com/viewtopic.php?t=4174&highlight=poly+colly) that should be easy to migrate to 3D instead of 2D.

Setharian
10-07-2007, 08:21 PM
thx for intersection tests....I'm also searching advices on efficient implementation of structures and algorithms...my primary concern is for the collision queries to be extremly fast so quickly enumerating possible colidees and reducing the set of checked polygons are the most important things....

Huehnerschaender
11-07-2007, 11:11 AM
I don't believe that modern RPG like world of warcraft do collision detection on the server side... what if you have lags? What if connection breaks? Your characters would just run through walls...

I guess there is always the need for client side collision detection, not only to make the collision calculations of 5000 games (clients) to be done on a single computer. That makes no sense in my eyes...

Setharian
11-07-2007, 11:31 AM
client does collision detection for the controlled player but nothing else...the rest - creatures, NPCs, etc.- is handled by the server and that's the majority of work...world of wacraft does this in the same way, one cannot trust the client to respond with correct data when the server asks it something so the best approach is to not to ask it anything at all....

jdarling
11-07-2007, 12:07 PM
Most MMO's use a combination of server and client side testing. Where the client uses its collisions locally, but the server "double checks" the clients movement. If the client is allowing invalid movement then the server corrects this by adjusting the clients position within the world.

As far as how to do this the fastest way possible, an in memory table or list containing most of the possible collisions and using quick lookups is the fastest way to go about this. The basic idea is build a list of all "blocks" and collision vectors that affect them, then test the position against the known blocks. If no match is found then its likely that you don't have a collision. Now you can move to local collision by testing immediate neighbors, if none found then no collision has occurred.

Its also good to do predictive collision detection when you have processor time. Thus calculate any collisions along a given path in the time you have alloted. If you find one, then you store it some place (in your memory block if its static, or in your local chances if its with something like another player).

Remember, just because things move doesn't mean that they are not static when doing collision detection. A perfect example would be a gear in a grain mill. While the gear rotates (thus moving the teeth) the pattern is very fixed and can easily be stored. The collision vectors in your list need to be generic (if your within N of me then we are considered equal).

One other note, most MMO's push local collisions off to the client completely. The server doesn't really care if you "run over" another player, this isn't a game threat. If you run through a wall is another story.

Final note, 2D collision is faster then 3D. Using a 2D collision system that is double checked with by its 3D counterpart may be better then actually using a 3D all of the time.

NecroDOME
12-07-2007, 08:50 AM
With that much I think you need to go with a hardware approach. Havok uses the videocard, Ageia uses its own PPU.

Setharian
12-07-2007, 12:07 PM
and do you have any idea how to program the GPU to do that?

NecroDOME
12-07-2007, 12:15 PM
You should use shaders. No idea how that works, but the got it working with havok. But GPU is only for simple physics. You can calculate +10.000, but al in a simple way. It you really want to have a large scale I suggest to take a look at agiea physics engine. They also make the hardware. And if ist only server-side, the only one needing a physics card is the server. (they cost around $250 I think)

Setharian
12-07-2007, 01:09 PM
I'll look at both the shader approach (if it is actually useable) and also at Ageia PhysX engine....but more tips are welcome still ;)

NecroDOME
12-07-2007, 01:19 PM
You could also "share" physics, let multiple computers do the calculations...

however, here's a demo movie from havok using nVidia card for physics:
http://video.google.com/videoplay?docid=2350042502418485801&q=havok+physics&total=84&start=0&num=100&so=0&type=search&plindex=1

Mirage
12-07-2007, 09:49 PM
Setharian, before you start investigating a cluster-based/additional hardware approaches, I propose you to make sure that a single server can't perform the task. I think it can.
To speed-up the calculations you can use an early sphere-sphere test, as well as a kind of space partition (I suggest BSP for static, non-heightmap-based landscape/level).

NecroDOME
13-07-2007, 08:15 AM
200.000 moving objects can be calculated on the CPU, but it would be VERY slow. Newton as already trouble with 200-300 moving and colliding objects. And then I'm talking about 1 room. If you want to test where the object is, what it collides with etc, you can't preform that on today's default desktop pc's. even with a quad core you still have not enough power. Thats why Havok uses the video card and Agiea uses its own hardware.

However you could give it a try, but I'm sure its slow.

Setharian
13-07-2007, 11:37 AM
maybe cluster-based approach won't be needed....the great advantage is that one doesn't have to consider collision of 2 moving objects in detail (simplified bounding volumes like spheres/elipsoids are used for this purpose), only moving object <--> static object checks are needed to be more precise because usually the decoration (and terrain) cannot be encapsulated in a simple bounding volume for a reliable collision detection....object management works on an octree principle to quickly perform enumeration/addition/removal and I was thinking to extend it to contain static geoemtry as well....every individual "geometry object" would contain an AABB and an internal BSP tree of all the polys contained within it....also models used by the server are simplifications of those used by the client (usually have only 10-15% of polys of the original model)....because all of the geometry is static, AABBs and BSP trees can be precomputed....do you guys think there is any "hidden" problem in this approach?

JernejL
13-07-2007, 02:27 PM
New newton release is slowly closing release, and it runs off GPU with support for multiple cpu cores, so it runs pretty fast:

http://www.newtondynamics.com/forum/viewtopic.php?t=3164&postdays=0&postorder=asc&start=75

see videos posted there on bottom of that page.

savage
13-07-2007, 05:31 PM
maybe cluster-based approach won't be needed....the great advantage is that one doesn't have to consider collision of 2 moving objects in detail (simplified bounding volumes like spheres/elipsoids are used for this purpose), only moving object <--> static object checks are needed to be more precise because usually the decoration (and terrain) cannot be encapsulated in a simple bounding volume for a reliable collision detection....object management works on an octree principle to quickly perform enumeration/addition/removal and I was thinking to extend it to contain static geoemtry as well....every individual "geometry object" would contain an AABB and an internal BSP tree of all the polys contained within it....also models used by the server are simplifications of those used by the client (usually have only 10-15% of polys of the original model)....because all of the geometry is static, AABBs and BSP trees can be precomputed....do you guys think there is any "hidden" problem in this approach?

wow that's hard to read! Made me realise how much I take white space for granted.

Setharian
13-07-2007, 07:37 PM
New newton release is slowly closing release, and it runs off GPU with support for multiple cpu cores, so it runs pretty fast:

http://www.newtondynamics.com/forum/viewtopic.php?t=3164&postdays=0&postorder=asc&start=75

see videos posted there on bottom of that page.
Newton is great overall but I fear it is "too precise" for our needs, I think it takes into consideration a lot of factors which is kinda of an overhead when they are constant. I'll do some further research on this.


wow that's hard to read! Made me realise how much I take white space for granted.
I will try to add white space next time I'll write a long post. :)