According to TFA, they're using A-star[1]. This seems to be common.[2]
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?
I am not a game programmer but presumably: yes, yes, no. Though TFA says the original edition's A-star implementation was "outright broken".
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?
I am not a game programmer but presumably: yes, yes, no. Though TFA says the original edition's A-star implementation was "outright broken".
[1] https://en.wikipedia.org/wiki/A*_search_algorithm
[2] https://gamedev.stackexchange.com/questions/5013/how-does-pa...