Just want to note first I know there are lots of topics on this. I've bought books, read tons of posts here, but still stuck on a few topics from a conceptual level. One of them is concerning how larger online games manage path finding server side when there are lots of actors.

My problem isn't necessarily how to program the path finding when it comes to move NPC from position1 to position2 that's pretty straight forward but if the goal is to have as little to no physics done as possible on the server side I'm stuck on: How do larger games manage pathfinding for lets say NPC's chasing players?

We know the following:

  • Mobs will only chase x distance
  • While not chasing players the mobs normally have a predefined path to follow so the server doesn't have to calculate that nonstop.
  • If no players are around the calculations can stop and free that resource up.

Most of my server side code is easily managed without the need of running the client exe. Is it normal to lets say have a cluster of servers that does nothing but manage pathfinding for certain areas of the world? So for example the server exe would communicate to the client exe(sitting on a server) I need to move npc from current position (x,y,z) to the current player position of (x,y,z) calculate my path. The client does this, respond to the server.exe request, this is then shared with the player clients?

I guess the same could be said for players themselves. If we need to validate their movements are accurate we need to know that they were able to move to x/y/z coordinates by checking it against a client somehow? The only other option I can think of is that somehow these companies are exporting their navmesh in some format that the server exe can look at and run calculations against.

I hope one of y'all out there smarter then me will be able to see where I'm getting hung up on.

  • \$\begingroup\$ "somehow these companies are exporting their navmesh in some format that the server exe can look at and run calculations against." -- They definitely are doing that if the game uses a navmesh at all. The server usually has access to all of the world geometry, including nav meshes, so that they can compute things like occlusion (for culling entities you can't see anyways) and validating player movement. \$\endgroup\$ – Romen Oct 8 '20 at 20:43
  • \$\begingroup\$ They do physics on the server. Are you using a physics system that only works for clients? Then maybe your server does need to pretend to be a client. \$\endgroup\$ – user253751 Oct 9 '20 at 10:50
  • \$\begingroup\$ @Romen that was the only thing that made sense to me but lets say we're using Unity or UE4, is there much of a point to build a server completely outside of those frameworks versus just using a headless client. It seems like you'd be doing a lot of duplicate work just to try to cut out some un-needed dependencies. Since posting this question I've been doing some testing to see if running the server outside of UE4 versus running the server using the client setup in headless mode really has any meaningful impact on performance. \$\endgroup\$ – Silent Oct 9 '20 at 14:11
  • \$\begingroup\$ Both Unity and Unreal Engine are capable of running an instance of the game as a headless dedicated server. The dedicated server aspect really depends on how you implement networking, but the scenes, blueprints/behaviours, etc. are all still running in the engine just without being rendered. If you implement a dedicated server that doesn't use the engine at all, you would have to implement all of that behaviour outside of the engine.. which is also done when there's a very good technical reason for it. \$\endgroup\$ – Romen Oct 9 '20 at 16:09

Without going much into specifics, as it differs game by game and company by company...

Pathfinding pretty much has to be done on an authoritative server unless you want serious hacking to be the norm on your clients. Coarse-grained pathfinding can be smoothed in terms of the final path displayed on clients. These coarser calculation results imply less work done on the server (enabling more clients to be calculated for, per computational unit).

Yes, the server needs access to terrain geometry, and indeed to the entire data model in most full-fledged MMOs. How could it be otherwise? Remember that there is an overlap between logical geometry and renderable geometry, in many if not most games.

Frequent validation (at least once in every five seconds, if not much more frequent) of positions is normal, with the server authoritatively redefining the client position if it is out of kilter with what the server expects.

Given the necessity of server-side pathfinding for security reasons, you need native server code that runs very fast indeed (bare metal), and this means the usual trade-offs seen in optimisation.

  • \$\begingroup\$ Thank you much for your insight! \$\endgroup\$ – Silent Oct 7 '20 at 22:29
  • \$\begingroup\$ If you dont mind I'd love to ask a couple other questions based on your response: - Course-grained: I love this idea, is the idea to do course grained on the server but then have the client do the fine grained? - Terrain Geometry: I was thinking this same thing but kept reading opposite statements sometimes even from the same author. Is your suggestion to have a client running on the server that the server can communicate back and fourth with, or do you typically see basically a expanded version of the client that encompasses the server and "client" all in one exe? \$\endgroup\$ – Silent Oct 7 '20 at 22:29
  • \$\begingroup\$ @Silent No problem. I think you've got the idea. Interpolation on a coarse grained set of points can give you a smooth result without having to actually produce the smooth path on the server, yes. I wouldn't go with an embedded client, no; I would have modules that are common between client and server codebases, so that the server encompasses its own code and (portions of) the client code. In a "pure client" setup as found in old mainframe days, a client was no more than a "renderer" which took all business logic from the server. Yours may be similar, though more logic is likely on client. \$\endgroup\$ – Engineer Oct 8 '20 at 5:18
  • \$\begingroup\$ As regards geometry: supply a heightmap (whether a vertex- or tile-descriptive heightmap is up to the designer) from which your renderable geometry (OpenGL or Direct3D) is generated. The heightmap is for fast game logic processing on the server (at least); the matching vertex-based geometry (3D points) is suited to the rendering pipeline of the GPU. \$\endgroup\$ – Engineer Oct 8 '20 at 5:22
  • 1
    \$\begingroup\$ this is perfect, alright I think I'm on the right track now. I'll work on exporting the heightmap then figuring out how to do pathfinding on that and not in the app thats running the full game engine. I really appreciate your insight and direction. \$\endgroup\$ – Silent Oct 8 '20 at 18:49

A way this is often handled is through microtasking. Imagine you have the geometry for a truly vast world. This world can be split into a grid of regions (to any level of detail wanted). The size of these regions will result in a storage/computation balance.

You can pre-calculate Which of these regions are 'connected'. That is, from which region one can directly move to another. Or, more like, which regions need to be crossed to get from A to B.

When it comes to then calculating long paths, we can query the region-to-region path, and only have to calculate the paths between these regions and solder those together. This cuts down on actual computation massively, but in a large complex world it does result in a storage requirement of up to N^3.

  • \$\begingroup\$ thank you for the response! These helped me. \$\endgroup\$ – Silent Oct 8 '20 at 18:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.