Collision detection help

[Setharian]

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]

use a off-the-shelf physics engine, newton is good.

[Setharian]

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]

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...ght=poly+colly) that should be easy to migrate to 3D instead of 2D.

[Setharian]

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]

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]

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]

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]

With that much I think you need to go with a hardware approach. Havok uses the videocard, Ageia uses its own PPU.

[Setharian]

and do you have any idea how to program the GPU to do that?