Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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?

share|improve this question

4 Answers 4

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.

share|improve this answer
    
So your server DOES run the pathfinding function, and broadcast every 3 seconds or so a "photograph" of the current positions, am I right? What would you think if I do this, will it work?: Client sends target position, pathfinding on server broadcast just the next tile that user should go to (doing this I don't have problems if the map changes and a tile is no longer walkable), then server waits a little bit (for the avatar to move on clients) and send next tile. My fear is: if there's a lot of users moving, knowing that for each I have to run pathfinding and broadcast it, is this reasonable? –  Carlos Navarro Jun 6 '13 at 15:07
    
doing this I don't have problems if the map changes and a tile is no longer walkable In our game, Pathfinding walk mesh changes did occur so infrequently, that we just recalculated all current paths when it happened. (All our path searches where asynchron to the UI thread). About your specific question: Sure, sending only chunks of the path (be it one tile, three tiles or whatever) will do the trick too, if your walking mesh changes are frequent. If your consern is saving CPU/memory on the client (he does not have to calculate paths and store the walk mesh), then I'd answer: You will be... –  Imi Jun 7 '13 at 8:29
    
...surprised how usefull a client-side walk mesh can be. For example, you can predict whether a walk command could succeed and display some X-cursor to the user - all without asking the server. So think about whether you may want an pathfinding engine on the client side anyway and if so, it can also be used to calculate the paths.. ;) –  Imi Jun 7 '13 at 8:30
    
Also, remember that this "recalculation" is very bandwidth friendly. Every client gets the message that caused the walking mesh to change anyway (e.g. some door opens). And everyone already know the target tile. So everyone already got all information he needs to do the recalc. If you have frequent walk mesh changes, you might want to tweak your pathfinding algorithm, e.g. use a sector based aka "hierarchical" mesh representation to ignore changes in sectors not walked through. (BTW: That helps even if you have a server-only pathfinding solution) –  Imi Jun 7 '13 at 8:40

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.

share|improve this answer
    
thanks for answering! My idea is doing something like that, with the "recalculation" donde in server (I explain why I'm planning to do that in a comment of Philipp's answer), but the problem is again timing! May be I'm getting obsessed with time and I should just go for it? –  Carlos Navarro Jun 6 '13 at 14:50

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.

share|improve this answer
    
Thanks for answering! The idea is to send the next tile every x msecs. That is, if server knows userA is in tile (A,B) and wants to go to tile (C,D) it runs the pathfinding which returns just the next tile userA should go to. Pros: I can check the map every time, so if suddenly a tile which was walkable when user clicked in the target is no longer walkable, I won't have any problem. Cons: How to set this time dif. between sending the next tiles? I can measure it and set it on server, BUT what if there's a lot of people online and moving? this would mean a lot of calculations (i.e., more time) –  Carlos Navarro Jun 6 '13 at 14:54

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.

share|improve this answer
    
The idea is to send the "next tile" every x msecs. That is, if server knows userA is in tile (A,B) and wants to go to tile (C,D) it runs the pathfinding which returns just the next tile userA should go to. Pros: I can check the map every time, so if suddenly a tile which was walkable when user clicked in the target is now not walkable, I won't have any problem. Cons: How to set this time difference between sending the next tiles? I can measure it and set it on the server, BUT what if there's a lot of people online and moving? this would mean a lot of calculations (i.e., more time)... –  Carlos Navarro Jun 6 '13 at 14:41
    
I just edited my comment (where I explain why I prefer not to do that) Thank you very much for answering:) –  Carlos Navarro Jun 6 '13 at 14:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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