Hacker News Reader

Comment by stux | Hacker News Reader

> 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?

View on HN

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.

Good point. I wonder how many articles discuss old games and over-analyze choices that may actually be labelled as

//TODO: good enough, fix later

In the actual source code

I was wondering how tileman gimmick accounts seemed to be forcing their pathfinding to unlocked tiles. That would explain it.

As an ex tileman (100k tiles before the lag got to be too much), you pick this up pretty early!

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.

Interesting, when I was a WoW GM our special “GM WoW Client” contained a lot of features that QA would use.

One of these was showing NPC pathing in the form of dots with lines in between. At any time the WoW client would know next 5 or so waypoints of a mob that was idle patrolling.

I guess it’s more efficient to send a batch of waypoints occasionally than one at a time more regularly.

It was a interesting watching boss fights where the pathing would update quite regularly, especially if the tank had just died and it was systematically clobbering everyone else.

There is also real world considerations. Like packet loss, latency and jitter. Some users might have less than perfect connections so sending more at time when it is known is for better user experience. I think we often forget just how good many modern internet connections are. Especially if you are sitting in office with very high bandwidth fibre connection.

You're putting the computation of waypoint finding on the all clients, or on your server.

People spam click, so it's cheaper to compute it once and pass it around.

It's a trade-off, especially for longer paths, especially when you count the cost of server RAM cache misses.

Reply on news.ycombinator.com