quote:

---

Original post by Max_Payne
Collision detection has to be performed on the server side for the game to be reliable, and this does not mean no collision detection on the client side, it just means the server has the final say on everything. Exploits, especially in large scale MMO games, should be avoided.

---

In an ideal world, yes, all collision detection would be performed on the server rather than the client because you can''t be certain that the client hasn''t been nobbled to allow the player to walk through walls.

Also in an ideal world, all scene rendering would be performed by the server and the screen buffer sent to the client, because you can''t be certain that the client renderer hasn''t been nobbled to see through walls.

Obviously the latter isn''t currently possible due to limits on processing speed of the server and bandwidth to the clients. However, the former is also not feasible - you might be nearly there on processing speed, but certainly not bandwidth. Imagine 100,000 players in your favourite MMOG. Say the server is processing movement and collision for each of those players at 30 fps. Imagine the server needs to send a 128 byte packet back to each client (collision response data, position, rotation, packet header, etc) - that''s 3840 bytes per client per second, and overall the server would be pumping out over 360 Mb per second. That''s the type of bandwidth I''m looking forward to, along with my flying car.

MMOGs work because the servers only send out a little information periodically (may be several seconds between updates) to each client, and the client fills in the gaps. This does, however, mean the client needs to do it''s own collision detection, and is susceptible to tampering. There may be some higher level cheat checking running on the server - eg. player #337 has moved from area A to area B in 3 seconds, and it should have taken 30 seconds if they''d run through the gateway, not through the wall - but as for server side collision detection, I''d say nooooooo.

Almost all physics engine are determinstic these days. Given the same inital condition and lock step update cycles they will produce the same results. Why would you need to send all collision contact information to the client. At most you would send inital condition and resync if the client diverged too much from the server. A MMORPG isnt a fast action game, it doesnt need to update anymore than 5x a sec. Doing physics on the client and server is fesible. Most MMORPG break up their worlds so a server runs about 1-2k players, so its not impossible for a server with 2k players and doing physics and using the above mentioned update scheme to work. I would say a bandwidth rate of more like 1 k - 800 bytes / players would be more likely. At those ranges and given the 10$/month fees, bandwidth cost are less than incoming revenue.

Well Good Luck!

-ddn

Physics, even Havok, is never 100% deterministic. This is because FPUs on different CPUs operate subtly and slightly differently. You can never rely on deterministic physics.

With a proper hierarchial collision detection system using bounding volumes/OBB-trees/etc nowhere near this number of polys would have to be tested.

Server-side collision detection is doable and, IMHO, necessary (for anti-exploit) reasons.

As regards players exploiting mobs being subjected to collision with characters, this would be solved by a decent AI and logic that detects people blocking the route to the target (and affects a change of target because of this).

quote:

---

Original post by Megahertz
In any event, its the collision with the world that worries me. Just to throw some more numbers out, say each node in your octree has 500 polygons in it, 500 polys * 600 mobs, thats 300,000 polygons that are going to have to be tested to as potential colliders, then you still have to find the collision and resolve it. That's going to take a serious chunk of time.

---

[edited by - Golroc on January 10, 2004 12:14:35 PM]

quote:

---

Original post by Golroc
With a proper hierarchial collision detection system using bound volumes/OBB-trees/etc nowhere near this number of polys would have to be tested.

Server-side collision detection is doable and, IMHO, necessary (for anti-exploit) reasons.

---

Well said, Golroc. I know for a FACT that AC1 uses server side collision detection (from an interview question answered by one of the deveopers some time ago, although unfortunately I can''t find the link at the moment, rats). And that technology is what, 5 years old? So it can be done (and has).

This subject really caught my attention a week ago since Im intrested in MMO development and how to stop cheating. I did some tests using ODE (http://opende.sourceforge.net/ode.html) a physics engine that is open source. I decided to go with a few of the suggestions in this topic, notably:

- Skip moveable vs moveable
- Use hierarchal spatial structure
- Use simple collision proxies

Some words about these conditions. Hierarchal spatial structure is already implemented in ODE (dQuadTreeSpaceCreate) which is nice. Only simple collsion is needed since we are just concerned with preventing cheating on server side. On client side you can use a more subtle scheme to improve visual appearance because you only need to consider your own collisions and immediate surrounding area. I can email the source for this test suite if anyone is intrested. You must have a compiled ODE lib and include files to compile it.


The tests
=========

A) Generate a virtual forest approximated by 10000 capped cylinders (faster than regular I think) all using same Z value. Forest dimensions are 10000x10000 meters.Then perform 1000 collision detections between a simple sphere representing a player character and the virtual forest. This test simulates the case where players are walking around in an "open" (not dense) forest. No collisions were detected (same player pos).

B) Generate a virtual dungeon approximated by 10000 boxes all using same Z value. Dungeon dimensions are 100x100 meters. Then perform 1000 collision detections between a simple sphere representing a player character and the dungeon. This simulates players in a more collision prone environment. During this test several (7) collisions were detected for each simulation.


Results
=======

These were tested both with the quad approach and the brute force to show the difference between using an hierarchal spatial structure and not. Precalc is the time to setup quadtree and other internal structures ONCE in the beginning, that would be when you load your level. Tests were executed in Release mode on a PIII 866 MHz machine. All values in milliseconds.

Test type         precalc time    Collision detection time------------------------------------------------------------A) brute force            16ms                      2797msA) Quad tree            3078ms                        16msB) brute force            15ms                      2797msB) Quad tree            3141ms                        31ms

Conclusion
==========

(For brute force the tests are almost identical since mostly the "trees" bounding boxes are used during quick rejection)
Well, these test are not advanced enough to prove anything but they sure hint at the possibility to use server side collision detection even in an MMORPG for example. About the bandwidth issue, I dont really see how this affects how much data is transferred over the network. The server will most likely send and receieve player positions all the time anyway. This collision detection only resets a player to his latest valid position in case a collision is detected. Also see posts by Max_Payne and RonHiler explaining this. Sweep tests or at least a few "inbetween" tests have to be done if player is moving fast for this to work.

(Edited to clarify results section)
(Edited again when I found the source tag Yihaaa)

[edited by - Borundin on January 8, 2004 3:30:02 PM]

[edited by - Borundin on January 8, 2004 3:53:05 PM]

Borundin,

What do the spaces between 16 and 2797 mean, is there supposed to be a comma there or a period, or is the space separation of a column? and why is the quad tree equivelent nearly opposite; 3078 and 16?

Testtype Precalc Collisions
----------------------------------------------
A) brute force 16 2797
A) Quad tree 3078 16

B) brute force 15 2797
B) Quad tree 3141 31

Just a little clarification would be nice, thanks.

For brute force there is no precalculation cost, so its pretty low, proably just mememory allocation overhead.

-ddn

Oops sorry. Wrote the post in notepad and then pasted into browser and away with all the fixed size characters which made my results almost unreadable, bahh =(
Will try to edit post to make it more easy to read...

You could exploit the untapped processing power of the client and implement a feature where the client would do collision detection for all the players it can see, and if it notices somebody where they shouldn''t be it automatically ''snitches'' on that player to the server, which will then perform a full collisions check on that player.