Assume a reasonably big game with a lot of players moving, not necessarily MMO style with thousands upon thousands of people, but at least more then a FPS style game where you almost never seen more then 64 players on the same server. How do you verify that the movement of the player is correct?

If we take World of Warcraft as an example, but again; it doesn't have to be this big, but it's a game every one knows and it's easy to explain and refer to. As far as I am aware player movement in these types of games are done locally on each client, the client then reports it's position at set intervals to the server which then verifies that the player is within the world bounds.

Now the problem (in my mind, at least) rises when you have a really complex world that has a lot of mountains, hills, chasms, houses, caves, etc. How does the server verify that the player is in the bounds of the world? These are the options I've come up with, and why I think the might not work.

• Using a mesh collider, is not feasible due to the amount of players (it would be to expensive on the server to keep verifying the position of the players against a mesh collider, or at least I think).
• Using simple bounding volumes makes it feel like the world would get to coarse (how would you use an AABB or Spherical collider for terrain that has valleys and mountains for example?)
• Using a navmesh, would also make the world to coarse, although less so then simple bounding volumes but how would you deal with being able to jump on and stand on a rock with a navmesh for example, if there are, literally, millions of rocks in the world. You're probably still going to need a navmesh for NPC navigation, but I feel it would be to coarse for player movement.
• Using a world heightmap, that holds the world height at some resolution, maybe every 1.0 units, this would work for open terrain but would be almost impossible to make work for houses, caves, etc.

The only feasible option (in my mind, with limited knowledge) I've come up with is to use AABB bounding volumes which contain a part of the world, and make sure the player character is completely contained in one (or more) of the AABBs at all times and then just trust the player position as long as it's inside the AABB volume.

Having worked in.. frowned upon.. situations with said game, all 3 emulators for WoW use map files to get height maps for terrains. As for inside, such as GOs etc, the GOs are spawned on the server but iirc are NOT checked against as the physical collision is calculated client side (ie, you can't walk through a wall).

EDIT: Lemme clarify that:
The servers have binary file dumps that are extracted from the clients to generated height maps. These are checked against by the server so that if a player moves below a certain threshold, or too high without having a flying mount aura, they are booted from the server. That is pretty much the only map validation done by the server. The server also processes movement (ie, if you move too fast then you are booted), but generally the collision (for Terrain and Game Objects) is done client side.

Don't make the server instance do any more work than it absolutely has to.

Having worked in.. frowned upon.. situations with said game, all 3 emulators for WoW use map files to get height maps for terrains. As for inside, such as GOs etc, the GOs are spawned on the server but iirc are NOT checked against as the physical collision is calculated client side (ie, you can't walk through a wall).

EDIT: Lemme clarify that:
The servers have binary file dumps that are extracted from the clients to generated height maps. These are checked against by the server so that if a player moves below a certain threshold, or too high without having a flying mount aura, they are booted from the server. That is pretty much the only map validation done by the server. The server also processes movement (ie, if you move too fast then you are booted), but generally the collision (for Terrain and Game Objects) is done client side.

Don't make the server instance do any more work than it absolutely has to.

Thank you very much for your answer, [s]one[/s] three follow up questions:

How do you deal with houses and buildings that you can walk in/out of in the open world (not instances), or by GOs (I assume that means GameObjects) do even houses get spawned as GOs, in this cases I understand. Are caves, like the mines in the starting area for humans, also considered GOs ?

How do you deal with dungeon instances, is there any checking here at all?

Edit: By "the server processes movements" I assume you mean that the server checks the movement (to combat speed hacks, etc.) of the players, but it doesn't process the actual input commands from the client (as an FPS server most likely would), instead the clients just send their current position, correct?

That is correct, good sir. Strictly speaking, caves and mines (and even Stormwind) are WMOs. A WMO is a World Map Object - these are hard-coded into the ADT/WDT (files that WoW uses to draw maps and map chunks). A GO is something that may or may not be interacted with, but are generally smaller than WMOs. GOs, in my opinion, were used to be placed by developers for things that could be moved around. In short, a GO is an object that can be spawned (and is maintained, by the way) by the server, but the collision is handled client side. A WMO is handled entirely by the client.
But I digress.

As for dungeon instances, they have portals (which are, if I remember correctly, GOs). When a player walks within a certain radius of these portals (The co-ordinates are stored, once again, server-side), then they are sent to the instance. The instance itself is a different map. Some instances are WMOs disguised as maps (Ragefire Chasm and Wailing Caverns come to mind). Others are fully fledged maps (Halls of Origination).
Essentially, when a player walks within or into a portal (basically collides with a GO), the client sends a packet to the server saying this, the server performs a handshake to see if the client can enter it, and then sends back to a client a message saying what map to load (which corrosponds to an ID in their internal database files).

Edit: By "the server processes movements" I assume you mean that the server checks the movement (to combat speed hacks, etc.) of the players, but it doesn't process the actual input commands from the client (as an FPS server most likely would), instead the clients just send their current position, correct?[/quote]

As far as I remember, the client sends to the server messages - basically saying "I am moving" as well as a bitmask flag for their movement type (strafe, jump). The server 1) Interpolates these and sends them to other players and 2) checks if a player moved too fast by comparing their movement speed auras to the two locations that they travelled in the interval that has passed. That is;

Client: Hey man, I started moving. (0ms)
Server: Awesome. (10ms)
Client: Hey, I'm still moving buddy. (20ms)
Server: Awesome, well, let's see.. you moved 60 yards since the last time you spoke to me 20ms ago. That's 30 yards per milisecond. Well, you shouldn't be moving faster than 8 yards per second (arbitrary, I think this is what it was), so Imma go ahead and..
Client has been kicked and banned for speed hacking.


Basically to sum up, the server interpolates movements and makes sure the player isn't doing anything he SHOULDN'T be doing.

Thank you so much for this!

One final question: So when inside a WMO or GO (stormwind, a house, a dungeon, etc.) the server does no verification of the player positions at all? So even the terrain heightmap used is discarded I assume?

Thank you so much for this!

One final question: So when inside a WMO or GO (stormwind, a house, a dungeon, etc.) the server does no verification of the player positions at all? So even the terrain heightmap used is discarded I assume?

As far as I know, the server does not check player positions when inside of a WMO or a GO (though I'm not entirely sure how resting is calculated) - this is why it is possible to noclip them, and as long as you're not seen, generally go unnoticed.

I played a game that had the user check for collisions against the ground and walls. Basically it would reset you to your last coordinate if you moved to far in too short of time.

Another way, that requires less server resources, is to have the server check the terrain map(kind of like a bump map) and test that against the players elevation. This requires less processing and memory than loading a mesh, and you can make a array of XY:Z variables to serialize and later examine with even less processing. You'd simply be able to find the corisponding X and Y value on the map and then find the Z value from there, thus not having to process an image.

If I were to make a 3D online game this is definitely how I'd do it.