Hello,

I'm currently programming the movement engine for my multiplayer game. The game is played through a server which validates everything and sends updates to other clients.
Now I'm at the point where it has to validate player movement and send updates to all clients seeing that player.

Now my question is how I should process movement packets from clients. What I thought of: Having one extra thread which does movement validation. This thread has a queue which stores incoming movement packets based on the order in which they arrive. Then, in every iteration, it takes the next movement packet from the queue and validates it. After it validates it it sends an update to all relevant clients.

Also of note: the game has tile based movement. Meaning one movement advances the player one tile further.

Is this an OK approach or is there a better one?

I tend to just tell people to implement a fixed-time update loop. Update your game every 100 ms or something with the following update:

update
{
process all packets and mark the state that has changed
for each player build a packet containing the relevant state changes for them and send them
}

Pretty simple without flooding the network like your system would probably do if there was a few players. In the system I described you send at most 10 packets a second to each player. (If there's no data to send then you don't even have to send a packet). Reading material that explains these ideas in more detail.

I agree with the method Sirisian describes, and have done this method several times in my own games. If you are looking at tile based movement 10 updates a second will be more then enough for your needs, this number of updates also will work fine for more action based games if you add a interpolation method on the client to smooth the movements.

If you are looking at tile based movement 10 updates a second will be more then enough for your needs

Number of updates is not all that interesting.

An important question is how the conflicts are conveyed to user.X B
A .
If both A and B want to move to tile X, who will fail and how.


For collision with static elements, collision data can be client-side and acted upon instantly. Server merely validates the position, perhaps just asserting that player is not inside a solid tile.

For mobile elements, interaction must compensate for latency. So any action must allow for some 150-1000ms of free movement before it's corrected.

The simplest way to solve it is by allowing sprites to overlap. Many sprite based games, even non-networked ones, do just that. When collision occurs, sprites flash and one takes damage.

Another representation is to use Civilization-like approach. Sprite takes ~500ms to move between adjacent tiles, regardless of destination. If destination tile is occupied (by mobile, not by static element), sprite is snapped or animated back to original position but interaction is still resolved. 500ms is enough to compensate for most of network latency.

Another way is queue commands and combine latency masking with prediction. A player might hit WWWWAAS in 100ms, yet is only allowed to move one tile per 200ms. Entire command chain is sent to server as well as clients without validation. Both server and client then know the intentions and can proactively resolve conflicts. Command queue might be limited to only 1-3 commands to avoid too much of a lock in. Such system might favor batching or spamming commands vs. reactive movement. With rectangular tiles, long-term planning of movement isn't unusual, one can quickly make a mental plan on how to move through some room, so this approach might work well in practice. Exact timings depend on various tweaks. Due to client/server simulation, it's perhaps more complex to implement.

Another thing that might work is just brute force approach. Move everything, if conflict occurs, snap back. For low latencies (~<500ms), it might just work well enough.


Since the movement and world representation is trivial, none of the above requires any meaningful load on CPU or network, so it can be all processed on the spot inside the main loop.

If some kind of path planning is required, then the algorithm can integrate validation by only planning for a few steps ahead, but some sanity check must be included to avoid characters getting stuck. One way is to include path traveled so far and if character ever crosses it, cancel the planning or simulate more in depth. But that's a different problem.

What would putting all that into a thread solve? Not everything has to be threaded, you know.