I’m working on an online multiplayer game, and I’m kind of confused how pathfinding works in a situation like this. You certainly don’t want to have pathfinding operating on the server, but you need to prevent things like having different units walk on top of eacher, or land on top of each other, pick an invalid spot, etc… How is this best done? How do games like Warcraft or Everquest take care of this?
Thanks and God bless,
-Toby Reyelts
[quote]You certainly don’t want to have pathfinding operating on the server
[/quote]
Is this a 2D or 3D game?
I’m no expert, but I’m not so sure pathfinding operations shouldn’t be done on the server. If you have a situation where you have several people in a room, and you want a NPC to run across the screen, I would think it would use less time to get the data to all the other clients if it was the server that computed the operation.
If a client computed the operation, it would need to send the results to the server, which would then need to send the results to the other clients. Wheras if the server computed the operation, it would just need to send the result to both clients.
2D but I’m not sure how that is relevant.
[quote]I’m no expert, but I’m not so sure pathfinding operations shouldn’t be done on the server. If you have a situation where you have several people in a room, and you want a NPC to run across the screen, I would think it would use less time to get the data to all the other clients if it was the server that computed the operation.
[/quote]
First of all, I’m not talking about NPCs. Almost all of the entities/avatars/whatever are player controlled, in this scenario. Secondly, I don’t understand your point. Either way, all clients (at least in the immediate vicinity) have to be informed of the update, regardless of whether the server or client calculated it.
What I’m trying to avoid are the computations for paths for tens of thousands of clients per second. I just can’t see how it would be possible for any server to handle this, on top of its already burdensome load. I can imagine the server just receiving updates about client positions and broadcasting those out to other clients, maybe while performing some simple security logic.
What I’m asking is how this is done in real, deployed online games with many users (i.e. > 10,000).
God bless,
-Toby Reyelts
in real live games like that, there is no path finding done for clients… because they’re real people. All that anyone needs to know is position and mesh state. As for controlling things like monsters, well if you take the big Final Fantasy game on the PS2, I’m pretty sure they have like 30 or so massive servers to handle all their stuff. So they have an incredible investment to handle all of the computations and transmission of all the data.
Also, if you want clients to do the pathfinding computation for monsters or NPC’s, that IS a bad idea. What if that client lags or times out or disconnects? Boom you have no more monster. Aside from that, what if someone hacks the game and send whatever data it wants to for that monster. It wouldn’t be THAT hard considering what they’d monitor for uploading. They’d take a look at everything you’re sending out, which would be stuff related to the position of the individual user, and then stuff related to the path/position of its assigned NPC’s/monsters. So someone could hack that to have the player control the NPC’s to do whatever they like. You definitely don’t want to give control over your AI characters to the client. The client is unreliable and can disappear at any time, don’t give it control over things that will be in play for all of the other characters too.
IIRC, Command And Conquer used pathfinding for the player. You simply select the player and tell them where you want to go, and they will get there using pathfinding.
You could perhaps have multiple “super-clients” whereby collectively, they would calculate the paths and relay the information back to the server for the server to dish it out to the rest. If one of the “super-clients” disconnects, simply get another “normal-client” and promote it to “super-client”.
That way, the load is spread out into a more controlled fashion, the server keeps track of where the people are, so if a “super-client” disconnects, it can just give the information back down and promote a normal client using the information.
If you have >10K players, perhaps 500-1000 of those could be super-clients. But, you have to make sure that the clients dont know they are super-clients and that the algo’s for pathfinding is relatively cheap in order for the client not to notice.
DP
I don’t know what Everquest does, but I know what RTS games (and Tribal Trouble) typically do: Perfectly synchronize all clients at the cost of higher latency. If all clients is in the exact same state, you only need to transmit commands (e.g. “move unit a and b to position x”) and the server only serves to broadcast commands to all clients.
Take a look at the gamasutra article:
(the “strictfp” keyword is helpful to keep the states in sync in spite of floating point state.
You originally just said an “online multiplayer game”. You also asked how Warcraft and EQ do this…unsurprisingly, the answer is typically different for those two types of game (one genre has to deal with a max of a few hundred creatures in the entire world, the other has to deal with a max of millions of creatures in the world).
Then you don’t care about warcraft?
Developers usually do pathfinding on the local client machine because there is no reason for doing it on the server, unless your clients are mobile phones with VERY low processing power. Your worries like “units walk on top of each other” are impossible.
Think about how that could happen…perhaps you’re thinking that the client sees a path from A to B which goes behind some bushes (or into shroud in an RTS) which - unbeknownest to them - is currently occupied by enemy units.
This happens all the time in singleplayer RTS’s, too, and the answer is that you set off on the path until you can no longer use the path. What you do then is algorithm-dependnent; naive devs often just re-do the entire pathfinding from scratch at this point (which is OK if you have very small numbers of units) or to just make their levels have wider channels to reduce the problem! Professional developers tend to pick an algorithm where they can re-calcualte a sub-segment of the path without having to do the whole thing. Otherwise every single game would have people walking all over each other.
The local client does the calculation using what the player knows about the terrain - it uses the exact info that is being displayed to the player. If the player has uncovered a bridge over the river, which is now shrouded, the pathfinding knows about the bridge, but because it is shrouded, it can only assume that it is empty - there is no reason for it to actually ask the server whether the bridge is empty or not (that would be cheating!).
Most of the research into pathfinding algorithms for games these days is “how do you cheaply re-calculate the path every few frames because it keeps changing?”. Game Programming Gems 4 contains a nice one where you can not only recalculate the best path on each frame for almost zero cost, but you can also use it to do cheap AI.
[quote]in real live games like that, there is no path finding done for clients…
[/quote]
This doesn’t make any sense. There is always pathfinding. I click somewhere, and it will route my unit around obstacles that are in the way - that is pathfinding.
[quote]Also, if you want clients to do the pathfinding computation for monsters or NPC’s, that IS a bad idea.
[/quote]
I don’t, and I agree. Like I said before, the vast majority of units in the game are player controlled (i.e. 99.9%).
God bless,
-Toby Reyelts
[quote]I don’t know what Everquest does, but I know what RTS games (and Tribal Trouble) typically does : Perfectly synchronize all clients at the cost of higher latency. If all clients is in the exact same state, you only need to transmit commands (e.g. “move unit a and b to position x”) and the server only serves to broadcast commands to all clients.
[/quote]
Hi Elias,
That is exactly what I was thinking, and it is a good match for our problem. We’re not a twitch game, so additional latency in a low number of millis shouldn’t be a problem.
[quote]Take a look at the gamasutra article:
God bless,
-Toby Reyelts
Look - I’m not surprised that they might handle them differently, which is perfectly fine because I was asking for different strategies (in the plural) for handling my kind of situation. And what both Everquest and Warcraft have in common is that it is probably impossible for the server to do all the pathfinding for all the clients.
[quote]Your worries like “units walk on top of each other” are impossible.
[/quote]
I think what I’m primarily worried about are synchronization issues - like if I don’t keep the clients perfectly in synch at all times. It seems like from Elias’s answer, you do always keep the clients in perfect synch. On the other hand - I’ve noticed that WC3 will just pause the entire game if somebody starts to lag - I’d rather we just ignore that player (i.e. let their unit remain where it is) if we miss responses from them.
[quote]Game Programming Gems 4 contains a nice one where you can not only recalculate the best path on each frame for almost zero cost,
[/quote]
I’ve noticed there are lots of variations on A* out there - like D*, LPA* - I assume this is just one more variation.
God bless,
-Toby Reyelts
I only meant that I might be accidentally answer the one you weren’t interested in :).
Actually, most Warcrafts certainly could do the pathfinding for all clients. Bigger RTS’s (like AoE, where the unit limit is much higher) would have more trouble, and I’m not sure if it’s possible yet on consumer hardware for them to manage up to e.g. 16 player games (AoE can potentially have up to 8 player games with 1600 units, IIRC).
I’m obviously misunderstanding your question, because I can’t see how synch has anything to do with pathfinding?
OTOH, full synch is not generally considered the best way of doing RTS’s; it’s a bit like TCP vs UDP: this is one of a couple of alternatives where some people fervently prefer one, others just as fervently prefer others.
IIRC the quoted gama article is quite good, mentioning some of the reasons why full synch is bad, as well as the good points. Suffice it to say, you definitely do not have to go full synch, and might find it much easier not to; like TCP/UDP it depends upon your game-design, and which features you intend to add, and which ones you want to make easier for yourself.
Personally, I’m not a fan of full-synch. It’s an old, tried and tested, but fairly naive design for these problems; it works, and conceptually it’s easy to reason about, but I find the disadvantages and implementation problems painful. Since I don’t really understand your problem yet I’m not sure what alternatives might be worth looking at.
“In determinisitc environments, such as pathfinding with stationary obstacles, we use search algorithms like A*. … randomness breaks A* … we describe an algorithm for solving such multistep decision problems with randomness. The basic algorithm is called dynamic programming (DP)”.
You could contact the author (pivazyan at stanford.edu) for further advice or do a google for DP stuff. Or buy the book ;).
PS: I was being lazy when I said “zero cost” above. I just re-read the gem, and it’s not a zero-cost algorithm (i.e. you just lookup a value on each frame, no re-calc necessary), although recalculation tends to be very small. It’s actually a variable-quality algorithm: the recalculation is an iterative attractor. Each successive iteration reduces the error margin (i.e. like Newton-Raphson etc), so in any frame you can spend as much or as little spare ms as you have available to get “as good as you can afford” quality…
If you’re wanting to just click from one place to another, and have your player move, then yes you could calculate that Client side. I’d recommend doing something like draw a straight line between the player and the destination, and if there’s ever a collision, put a point on the line at that collision, and move the point the shortest distance left or right so that it gets outside the collision.
The path information is never transmitted to the server, it is just stored with the client to tell it each frame where to move, and the server gets the new position data every frame. Then the server can check each position and say, “is he going too fast or walking through a wall? If so, he’s cheating, kick him” which isn’t THAT costly if you want to have that sort of check. Otherwise it just sends out the new position. But the point is, the path is just another piece of info that the client keeps and never has to transmit. It’s just replacing the function of your brain which would normally do the path finding, and well, you wouldn’t warn the server ahead of time which path you’re going to take before you take it would you? 
I just want to emphasize what others have said - don’t confuse path finding with execution of the movement. Let the client find the best path it can with the information it has now, and let the server worry about whether the path is valid as the avatar moves.