Something has puzzled me about pathfinding in games. There is a well-known algorithm[1] for finding an optimal path: you start at the destination, assign that a cost of 0, make a queue from the points that can reach it directly, compute for each of those points the minimum "cost of directly reaching a marked point + cost written on the marked point", and then, while the queue is nonempty, taking the point with the cheapest minimum cost, marking that point with that cost, adding the point's neighbors to the queue, and recomputing the "minimum cost" for everything that can directly reach the point. You can then either terminate when your source point gets marked, or maybe keep going and keep the whole table around for the next time you need a path to that destination.

At least in turn-based games like Civilization, where most of the runtime is spent letting the player think while refreshing the display, it seems eminently feasible to do this every time a unit is given a goto command. (Also the number of points isn't that large: probably a few thousand distinct squares, much less if you restrict yourself to continents.) Yet Civilization II, at least, yields obviously suboptimal results, and I think I read that one thing it does is run a "perfect" search for every square on the screen, but do something more stupid if part of the optimal path is off the visible screen.

In an RTS, the terrain is probably somewhat more continuous, so there may be more "points" to deal with, and probably more paths need to be computed. Structures are built and destroyed, changing the terrain and the paths; units are moved around much more frequently, though arguably the presence of units should be ignored unless you're very close to the destination. Commands are issued much faster. All these add to the problem, but still...

I would expect games to be implemented first with perfect pathfinding, and then, if that was prohibitively expensive, to have optimizations, possibly "lossy optimizations" (i.e. heuristics), perhaps a bunch of caching or maybe "computing things at low resolution first"... And every optimization could be easily tested against the perfect pathfinding. If the optimizations would often lead to abysmal path-choosing, then this would be very easy to discover in testing.

So I'm surprised that games could have been released with pathfinding bad enough to become infamous. And yet this seems to have happened in multiple games (e.g. in Starcraft). How? Am I severely underestimating the problem difficulty? Did people not even try for perfection because of how slow CPUs were? Did people just assume basic heuristics would work and not bother to check—I guess they didn't have the advantage of learning from the failures of the previous generation?

[1] "Dijkstra's algorithm" seems to be what the kids call it. Did Dijkstra only ever come up with one algorithm? I think "frontier algorithm" would be an improvement. Oh well. https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm