alt Hacker News> Before any networking occurs, the client runs a breadth-first search using the local collision map to build a path from where you are to where you clicked, and then writes the packet for the server to read. [...] The packet contains the absolute position of the first waypoint in the path, followed by the delta of each waypoint in the path against the first one
How come the client sends waypoints rather than just the destination? Naively it seems like sending less data would be better. Is the pathfinding so expensive that you'd want to avoid doing it on the server? I suppose it works out as long as it's cheap to validate/correct the client's path?
Replies
Validating that a path on a grid doesn't move through impassable objects is definitely much cheaper than running a pathfinding algorithm, especially on 2004 hardware. You'd have to make those checks as well in order to run the pathfinding.
It's a trade-off, especially for longer paths, especially when you count the cost of server RAM cache misses.
The algorithm is very cheap to run for a client (linear first, then diagonal to target, stitch together as many of these as it takes in the fewest number of hops), as they have full map data downloaded. For 2k concurrent players on mid range 2004 hardware (you have to remember they had kind of old school tech even for the time, though I'd love to be proven wrong on this), and with all the other interactions that needed to run before the next game cycle, I think they probably decided it was better to be clientside.
It's also possible they could have made it work, and it would have been a technical win, but just didn't need to since they had an MVP.