I'm thinking of an alternative way to pathfind in our RTS game.
Quote:This is our current design:
* User orders a unit to move.
* Client finds the closest node to the position clicked, and pathfinds there.
* If there is a path, the client tells the server where it wants to go and the server does the pathfinding as well.
The above works nicely. But what if I made one modification to that last point?
Quote:Like this:
* If there is a path, the client tells the server what nodes it wants to travel to get to the position. The server then checks if it is possible to move that way without running into a non-walkable node.
Perhaps this is how it's normally done? Can anyone spot any difficulties with the modification? The only downside that I can see is that the modification will make for larger packets to send to the server if startNode and endNode are far apart.
Thanks!
There is a number of problems with both solutions. It depends on what you want to optimize. Bandwith, responsiveness, server cpu performance, client cpu performance, security againt cheaters, simplicity of the client/server model?
Your solution improves server cpu performance to the cost of bandwith but still have a problem if there is any latency. The version of the "world" your clients have will always be a few frames behind the server. Thus the client might think there exist no path, while there exist one on the server. That may or may not cause problems, depending on the dynamicity? of your world.
Personally, for an RTS, I would only send user commands to the server. But hey, I never coded an RTS.
I think RTS games are generally run in lockstep by delaying all commands by a fraction of a second to give them time to reach the other players, and buffering commands to be sent in groups a small number of times per second. Syncing clients with an authoritative server would be a nightmare, requiring several times more bandwidth and server computation and providing unsatisfactory results when the server has to send corrections to a client.
The increase in packets from sending an entire path instead of just the pathing query could be significant, especially if the player orders a group of units to move at the same time. The list of node traversals in a single update could easily become a few kilobytes. Even running in lockstep, there is still the issue of dynamic obstacles like the units of other players. Whenever a path is blocked you'd need to be able to update the planned node traversals, and some degenerate cases could result in large updates being sent freqeuently.
Some pathing algorithms don't require finding the entire path at once and instead find an incremental solution, maybe using a hierarchical decomposition to make sure that the path will eventually reach the destination. And in a one player RTS game a single PC must be capable of performing all the player's pathing queries, all the AI's pathing queries, and the AI planning at the same time, suggesting that if you plan to have a one player mode then a single computer would already be capable of doing all the necessary processing when given only command lists.
Hi, I have made some thinking on the subject of pathfinding on an everchanging environment. My best solution was to setup milestone points. This has great advantages over others when the distance is longer. Basically you find your path, and place milestones on your path with constant distance between them. This method can work for your case too. Having milestones reduces the cost of path calculation a lot. So when you are in short of CPU cycles you can instruct clients to use less distance between milestones. This method is a mix and can be adjusted to have two points (start and end) as in the first method and all points as in the second. Hope this helps, Cem
