Pathfinding done on the client or the server?

depends. you use a deterministic engine? In that case, you wont need to do anything but send commands.

In case of a server / client, the server has complete authority. The client should merely send 'requests', that the server will authorise or refuse.

While the request is being sent, the client can predict the response of the host. If the host refuses the command, then the unit will have to move back to a safe position (either ping the unit back to position, or move them back with some other path finding), and you can then send a new request for that unit.

So, if some dynamic obstacle is added, the server can refuse the client move, and the refuse message will be sent along the new obstacle data.

While that is good advice if the main issue was synchronization - I am actually hoping to give the authority over the pathfinding to the client, rather than the server.

I want to reduce the strain on the server, and pathfinding is one of the most expensive routines. If I could get the clients to compute their own paths and send those to the server then that would be great, but I'm concerned there maybe problems that I can't currently see with doing so. It does open up the possiblity of cheating, but is finding a smarter path actually cheating? (Thats a debate for another thread, just consider that not a problem!)

Quote:

Original post by thelovegoose It does open up the possiblity of cheating, but is finding a smarter path actually cheating? (Thats a debate for another thread, just consider that not a problem!)

No, but the client is then free to say: I'm at (0,0), and in next second, I'm at (9000, 5000), whereas the normal movement speed is 1 step per second. Also, client is free to move through walls and other obstacles.

It's not only not a problem, but it's de-facto number one factor which determines where to do path-finding.

If you don't care whether client can map anywhere at any time (your game doesn't depend on location of players, nor do you have any spatial elements, such as walls, unpassable terrain, body blocking), then client can do all path-finding.

Most mainstream RTS games are set up so that the simulations are deterministic, so that commands get sent and simulated on the clients as opposed to networking individual unit positions and velocities. RTS games are really the only genre that commonly does that afaik. Other game genres do pathfinding generally on the server only.

Why would it differ from, for example, a player moving a unit manually? There are no hidden problems as long as the server authenticates the validity of the movement itself. The path is just a plan for future movement. I would have the client calculate the path locally, but send movement instructions to the server. The server will validate the individual movements. If the server attempts to move a unit in an invalid direction, it can stop moving that unit and inform the client(s) of this.

If you are using lockstep simulation, then path finding has to run on both server and client -- the only command that gets transmitted is "this unit, start moving to that destination, at time T." This saves a lot of network bandwidth, but means that everybody have to run the pathfinding code (and thus use more CPU).

If you're doing entity updates instead, then pathfinding only needs to come from the controller for the entity (which might be the client controlling the entity), as long as each entity movement is checked for validity.

@Antheus

I'm suggesting that the server has the authority over the movement of the character, just not the calculation of the path.
So the server would need to verify that the starting point fits with its record of where the unit is.

Because the server will need to be ABLE to pathfind (to cope with a change in positioning of obstacles some way through following a path), perhaps the server could pathfind when a client provides a starting position that does not match the position held for that unit on the server, dealing with the problem of clients providing a fake starting position, or if the position held for that unit on the client had got out of sync.

, just reading other responses now

Quote:

Original post by Antheus No, but the client is then free to say: I'm at (0,0), and in next second, I'm at (9000, 5000), whereas the normal movement speed is 1 step per second. Also, client is free to move through walls and other obstacles.

Pathfinding on the client doesn't imply at all that they have that degree of control over the game. Most RTS games will desync on situations of big differences in simulation results like that, often resulting in the match being unable to continue.

If it was me on a hobby/indie project, I would put the time into a hierarchical path finding solution, and keep it server only. I can't imagine that going the full blown deterministic route would be a worthwhile use of time for such a project. Split your map up into larger tiles, maintain a faster high level graph of how large regions of the world connect. Or depending on how dynamic the environment is(can paths be blocked/opened dynamically?) you could potentially precalculate the pathing into a large lookup table. It involves a good chunk of memory depending on your map size(n^2), but the end result is practically free path finding. That route is primarily for a mostly static environment, though you could potentially update the lookup table at runtime if things aren't changing too much.

Other than that, make sure you aren't path finding for individual units, that's probably the biggest gain you can make. If a player selects a group of 15 units and tells them to go somewhere, generate 1 path and have the remaining units follow a leader with some offset or formation off of the leader.

Quote:

Original post by Kylotan There are no hidden problems as long as the server authenticates the validity of the movement itself.

This is the key problem that most of you have missed... the server cannot validate a movement unless it solves the pathfinding problem itself, or reviews the solution provided by the client. In either case you have a delay (computation or transmission). In this situation, if your server is being overloaded by pathfinding, then throw more hardware at the problem. If that's not feasible, then run the pathfinding on a separate core or in a separate thread to decouple it from the frame-critical tasks of the server. If that means that clients have to wait a slighltly longer time before receiving the go ahead for a movement, then so be it.

Of course, if your maps are known before game startup (or even at compile time), you can precompute the connectivity of convex sub-regions of the map and turn the authentication into a lookup.

If you provide a client side pathfinder that acts as a predictor for the movement authentication process then, as stated above, you can cover the server processing time with an initial move. If the server sends back an invalid move response then halt the unit where it is (or in its closest valid state). This will automatically tell the user that something is wrong with the request they made. If you move the unit back to the starting point the user will not know whether the problem was an interface one (the movement didn't register) a transmission one (the movement request was lost) or an authentication one (the movement request was rejected).

Cheers,

Timkin

Validating the path as a clear path, and that the start point is indeed the starting point of the unit(s) the player is trying to move is acceptable.
The server wouldn't need to verify that it was optimal as the pathfinding is deterministic, so all that would need to be done is to check that the segments of the path do not go through any obstructed areas, which is far less expensive an operation than pathfinding and satisfactory for our purposes.

We can't throw more hardware at the problem because we are adopting the model of having client-hosts rather than dedicated servers. So one of the players is also running the server. I'd be interested to hear if anyone would advise strongly against this, its not set in stone that we should do it this way.

Our maps are dynamic, so we can't precompile paths.

Also, we can't have a lock step simulation as we are running a physics simulation, which can have slightly different outcomes on different machines, and therefore clients need to be updated every so often by the host to not let minor differences become large ones.
(We do actually apply commands in lock step, but there are widespread updates to take care of the deviations in the physics models)

Thanks for the input so far...

[Edited by - thelovegoose on May 1, 2008 10:06:00 AM]