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 hop

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.