Multiplayer synchronization and pathfinding

Question

I have a point & click type interface on a client, which runs an A* on the server, for path-finding.

The game is controlled like an RTS, but the world is persistent, so players should be able to join/leave at any time, and there will only be 30 or so units at most on the screen.

What is the best way to synchronize the player movements between the server and client, once I've computed the path(s)?

Does the server need to sync the clients on every animation step/frame? or can it just tell the client "go to position X,Y" for each node on the path, and each moving player? Or is it best to just run the animation timers on both client and server, and have it be implicitly synchronized that way?

What would the typical data-exchange be like for path-based movement?

EDIT:

Some of you have been suggesting lockstep, because I said "RTS", but the game isn't an RTS, it just has the same kind of interface. The big difference is I need to be able to have players join and leave the game at any time. Sorry for not being more specific.

Answer 1

An alternative is to do pathfinding on the client that owns the unit. This has the advantage of spreading the work out more evenly. A disadvantage of doing all the pathfinding on the server is that the server has to do all of it; a disadvantage of sending only 'move to X,Y' commands to clients is that each client has to find every single path. Instead, every 'tick' in the lock-step cycle, each client tells the server, literally, each of their unit's next step. The server makes sure the unit actually can move there, and moves the unit. Since the client doesn't have all the information (Notably, what the other client's units are doing), an invalid movement command isn't treated as an error. This is giving up some bandwidth to gain more time for calculating paths.

Replace server with peer; this method works for a peer-to-peer games as well, so long as you make sure the order in which unit movements are considered is the same on all machines.

Answer 2

RTS games typically have lockstep-sync (sync happens every frame). Telling any paths to the client would allow hacked clients to abuse the extra information.

Answer 3

Neither. The only thing you should send are the commands. Example: These 20 units should move to (X,Y) and then let each player figure out how they get there. The tricky part is making sure they all do the exact same thing. To achieve this a lockstep model is used, the links below should explain it in detail. Also, you should only sync the important pieces. Anything that doesn't change the gameplay shouldn't get synced. Animations in RTS games is usually only for the visual side.

Another thing, RTS games are usually not client-server, but P2P. That way one of the players can't cheat because when any inconsistency is detected, you simply disconnect.

Here is something to help you get going: http://www.gamasutra.com/view/feature/3094/1500_archers_on_a_288_network_.php http://altdevblogaday.com/2011/07/09/synchronous-rts-engines-and-a-tale-of-desyncs/ http://altdevblogaday.com/2011/07/24/synchronous-rts-engines-2-sync-harder/

Answer 4

Once the path is calculated, the server just uses that path to control the character. The presence of a path makes no difference to this problem - you still just send the same data, whether that is regular position updates or whatever. Usually it's fine to send regular positions (interpolated on the client to smooth them) and a separate message when the unit stops.

Answer 5

In my game (a multiplayer RPG type game) I send parts of the path to the client (for NPC nearby), ie. the 3 next positions and the Time when the NPC should be there. For players I just send the latest valid position + its timestamp so that on the client I can do dead reckoning (or something more elaborate if wanted).

This works completely OK mostly because there are no collisions between players/NPC (with a low lag you don't really notice anything, with a, say 250+ msec lag you notice the difference if you can see the two screens (of two players) at the same time but it still is not really noteciable on 'one screen').

So I'd say: go with server authoring (validationg positions + timestamps of players and also for the AI in the beginning, you can make a more elaborated system for the NPC later on without any big problems) + client prediction.

ps. I use a millisecond precision which works perfectly OK except that a signed int only holds for some 3 weeks before I have to restart the server.

You might also want to check out time prediction (ie. trying to get in sync as closely as possible with the server).