Tile-based multiplayer game: server and client load

Question

I'm developing a multiplayer tile-based game (imagine habbo) and having some trouble with the movement. The idea is to click on a tile (target tile) so your avatar moves there and everyone can see you moving there. In order to do that, there's a pathfinding function.

My first approach was: the pathfinding function was in the client and everytime the avatar moved a pixel (guided by the pathfinder) it sent a message to the server which broadcasted this update. This was obviously mad.

My second approach was to send to the server just the target tile. The server broadcasted this target tile, and each client ran the pathfinding function for each avatar in movement. I found problems with this because of synchronization: imagine two users moving that pass through the same tile at different times, maybe in one client with a little lag it happens that they pass through the same tile at the same time, so the pathfinder will stop one of them, as you can't walk over another avatar. This will lead to different positions in each client.

I've read some cases where the pathfinder runs in the server, the client just send the target tile and receives every x mseconds an update from the server with the pathfinding calculations for every avatar in movement (even himself). The problem I find here is how to set this "x mseconds" and that it might mean a lot of load to the server, handling all the pathfinding calculations...

What are the pros and cons of each approach?

Answer 1

Thats how we did it in Dungeons:

• Client sends the target-tile to the server.
• Server distributes the target tile to all clients
• Server and all clients run the same deterministic pathfinding and path walking algorithm.
• As a fail-guard, every now and then (like once every 3 seconds) the server sends his current position to all clients.

The clients check this fail-guard position towards their current positions. Usually there is no offset, but "things happen". Making a perfect deterministic path walker is very hard, especially when you have things like changing walk speeds and unit avoidance (we only had client-side unit avoidance so that wasn't a problem for us). Or for example when you run the process with "fast floating point operations" and do your walking in increments, any parallel float calculations may just drift off over time.

For us, the errors were usually so small, that we just set the client position to the received fail-guard update. But if you see bigger differences, or if you don't want or can't have a perfect deterministic path walker, then you could store the last received server position somewhere next to your current position and then "slerp" to this position over the next couple of frames.

Answer 2

You could try to recalculate and broadcast the path every time the character changes tile. It won't be as intensive as the per pixel approach but still have the benefit of calculating the actual current position of possible obstacles. You could also calculate the straight path to the end target, save this path on the moving character and on each tile moved calculate if the path is still valid or a detour is needed.

Answer 3

When creating multiplayer games with the client-server model, the server should keep the "master copy" of the simulation. That's what makes a server authoritative.

When a player clicks on a tile to move:

1. Send that tile position to the server.
2. Make the server determine if that tile position is valid to move to. This is where you can make sure the tile is in the map boundary, is valid, and the player can reach it.
3. If the tile position is valid, send a command to all the clients to update their simulation.
4. If there's an error, remember that the server holds the "master copy"! The server can send data to the client that synchronizes the game states.

The problem I find here is how to set this "x mseconds" and that it might mean a lot of load to the server, handling all the pathfinding calculations...

How many clients do you want to handle at once? If you're not processing hundreds or thousands of players, performance should be something that you should test before you make assumptions. Give your update frequency an initial value, like 10 or 15 times a second. If you have issues with bandwidth or performance, you should make further tweaks.

One last note: NEVER blindly trust the client's data. The server should do input checking and remain in control when it matters.

Answer 4

I would recommend to run the pathfinding on the server. That's the best way to avoid any asynchronity between clients. It also prevents cheating in form of speed hacks or walk-through-wall hacks, because the server has full authority over the movement of the players.

But there is no reason to send the pathfinding information every x milliseconds again and again, because during most intervals it won't change. It's completely sufficient to send each path once. The only reason to communicate again while the path is executed is when the execution of the path is cancelled (like when the user clicks somewhere else or when an obstacle suddenly appears on the path).

The "update every x ms" pattern I am reading here again and again is an anti pattern. There is no reason to send any information which is redundant or easily predictable. When possible, only inform the clients when an information has actually changed. When an information changes predictable (like the position of an object moving with a constant speed in a constant direction), you only need to inform the player when this predictable vector changes.