   server-side collition detection
  asked this on "math and physics" branch but no answerit's quite general question: how to implement server-side collision detection for NPC movement and PC movement verification, for MMORGP.Possible options: to implement it from scratch or to use some physic engine, e.g. Bullet, ODE or PhysX. Server is running on Linux.In case of implementing it from scratch: what is typical approach? multi-layer heighmap (terrain can have caves or multistory buildings)? In case of physics engine: is it efficient solution for large worlds (even if it is zoned for server cluster)? isn't it more reasonable to implement something well tuned for only collision detection when typical physics engine provides much wider functionality?thanks in advance for sharing your opinion   
  The problem with server-side collision detection is that movement at client-side is horribly delayed, especially with mmo games. If you've looked at some collision detection library samples before, you notice that >1000 entities runs reasonably well (maybe 10fps) for a server, so I'd go with that.But if I were you I'd first solve the problem with delay. Keep in mind that beauty is in the eye of the beholder if you're trying to find a solution.Michel   ;  tnx for answer but I'm not sure I got your message about delays, pls elaboratethere's small info about physics engine usage on server-side, and so I'm worrying about performance. did you mean 1000 NPCs (entities)? requirements are: one server should handle  several thousands PCs and not specified number of NPCs. PCs movement verification is not required to be done on every move so can be significantly optimized. Nevertheless "1000 entities" watermark is not amazing since it's not the single server task.   ;  I've not implemented anything like this myself, but i did read this article a while back, it may help you out.http://gafferongames.com/game-physics/networked-physics/   ;  thank, Marvin, I've read it carefully including all comments! :)there's one but major problem: Glenn Fiedler speaks about FPS game, and what is more important, seems it speaks about not MMO game. E.g. I don't see why client should send movement commands instead of position updates, can anybody explain this? I'm based on the idea that both server and client do simulation, server does just collisions when client does full-scope simulation. So sending pos updates to the server allows server to "trust" client and just occasionally check for cheating so releasing some server power.And Glenn Fiedler doesn't say anything about what is better: to use available 3rd-party physics engine or to implement handmade server-side collision detection.;  Use an exiting collision engine. Implementing your own doesn't make sense, unless you have very specific requirements not served by the crop of existing engines. (For example, our engine does whole-Earth simulation, which the game engines can't do).If you implement your own, you need a spatial index for broad-phase (loose octree, hash grid, sweep-and-prune, or similar). Then you may need a mid-phase index for triangles (if colliding triangle meshes). Finally, you need the narrow-face pairwise collision checking functions that tell you whether there's actual collision, and if so, what the contact points/depths/normals are, to build a contact manifold to use for simulation.There's obviously a lot more to it than that :-) If you're interested in collision detection in general, I recommend Christer Ericsson's book Real-time Collision Detection.;  in terms of multilayered heightmaps, the basis is a 2D regular heightmap, with holes in it (for cave / building entrances and such), the caves and buildings would be space partitioned (BSP tree, Bounding Volume hierarchy, ect...), and welded to the heightmap. Physics engines should be able to support that without too much complication. Rolling your own physics + collision detection is a huge undertaking for a game with such a large scope. As for networked physics, it doesn't change much from non-networked physics. In the context of a MMORPG, you'll most likely update your players by sending streams of inputs to the server, emulating single player controls. The delay factor occurs due to network latency. In a single player game, the input delay would be at most one update frame, or none if it is designed right. For networked games, you have to consider network latency. Moving left on a client will suffer a round-trip lag, since the server needs to receive the inputs first, process them, and send the result (as part of the game state) back to the player. Considering a typical latency of 300ms for a rpg, the game will feel quite laggy on the client end. To combat that, clients run a simulation of their own inputs, while sending the inputs to the server, and then check for the server results for that input set. If the server results diverge too much from the client simulation, the client is snapped back to what the server has computed. That's what Gaffer's method does, and what FPS games do as well. MMORPGs can use similar methods to reduce input lag. There is no reason why the method used by FPS games cannot be used for MMORPGs. It introduces more complexity, but it hides latency quite well. Note that RPGs have usually very simple physics and limited interactions compared to FPS games. If I take Guild Wars for example, there is no player-player collisions, no dynamic objects that can get in the way, and no projectiles, it's mostly point-and-click, and navigating a terrain. Furthermore, a lot of commands either take a long time to activate (spells) or are not sensitive to latency (talking to NPCs, inventory transactions, picking up stuff), those can have a bit of latency without impacting on the gaming experience. What you are left with is character control, and for that, you can either ignore lag (use a point-and-click system to move the player about by assigning a target position and let the server path-finding navigate you to it), or do client-side simulations, and correct the local results when the server results diverge too much. That's the method used in Guild Wars, as you can control the character position via direct keyboard inputs, so you need to fast input response. Also, zoning shouldn't impact your choice of using a third party library or your own. The technical challenges would be similar. Shoddy cross platform support would be a deal breaker though.   ;  [to hplus0603's post]oh, no, I'm not going to implement own physics engine, at least not now ;) seems most MMOGs doesn't provide dynamic server-side collisions so it's not required for us too. all we need is simple server-side NPC terrain movement. as I said there're two options - to implement something from scratch, e.g. generate heightmap (multilayer heightmap to support caves, multistory buildings etc.) from terrain and to implement NPC walking according to it. Not as difficult as complete physics engine. And this can be done quite efficient, tuned just for this task. On the other hand, if 3rd-party physics engine can do it with the same efficiency and its integration will be easier then implementing that static collisions - why not? what engines gamedev's can recommend? I'm reviewing Bullet and ODE, rejected Havok (very expensive) and almost rejected PhysX (source code is very expensive).   ;  [to oliii]thanks for detailed explanation. some questions:what is benefit of sending user inputs instead of character's pos updates? just cannot get this. client makes own simulation in any case, so it does collision detection. it can sends pos updates to server. server can take on trust received client po and just _occasionally_ check for client cheating. usually it won't perform any calculation simply storing new character pos.IMO the main difference between MMORPG and FPS is in server-side density of physics simulation. FPS needs dynamic collisions, shooting etc. so implementing own server-side physics for FPS becomes unreasonable and available 3rd-party engines provides fat benefit. But what is right for MMORPG when much simpler physics are required? or don't I see all challenges?multilayered heightmaps: i though exactly about multilayered approach. e.g. you have terrain grid with height's, some points can have values on different layers. when NPC's moving it checks difference between two adjacent points on his way. If they exceed some value NPC is blocked. will this approach work? also worrying if such heightmap generation won't be too complicated. does anybody heard about a 3d-party solutions for this?   ;  If you need NPC navigation, you typically want to create a mesh of what areas are "walkable." Whenever the NPC position is over the walkable mesh, it can walk. When it runs into an open edge of the mesh, it stops. You can use this mesh for character checking, too (both server and client), if it's good enough.The reason to use a mesh rather than a heightfield is that you want to support stairs (represented as sloping flat areas), bridges etc; you also want walls and hedges to stop walking, whereas doors should be allowed.A good first-order approximation to a navigation mesh is to take all triangles that have a face normal pointing upwards by 45 degrees or less. Then simplify this mesh -- collapse any edge that is shorter than 0.1 meters, say; then remove any degenerate triangles. You may want to connect edges that are close sideways but separate in the up/down axis, too, to avoid things like low walls being their own separate area of walkability. You do, however, want to keep the larger up/down separation triangles, because that allows you to do bridges, multi-story houses, etc.Another option is to build a navigation network, which is a set of "checkpoints" and routes (straight or splines) between them. The characters would follow this network (as a graph), and not test collisions at all. The draw-back is that you can't do things like reason about possible cover positions for incoming fire, etc; NPCs off the grid aren't easy to deal with (typically, you'll try to steer them towards the closest grid point they can get to through a straight raycast). You also can't use this network for players. For an MMORPG, that might not matter, and the lower computational requirements might outweigh the drawbacks. Beware if players learn the routes and attack/run away kiting-style, though -- you may want to switch mobs in combat to use the full navmesh in that case.