The pathfinding was a pretty expensive part of the game. I don't remember the profiling details of course (it was 25 years ago) but I do remember us being concerned about it. If I remember correctly we ended-up spreading out the computational load over multiple frames since the P.F. cost is obviously very bursty. I vaguely recall refactoring it to make it stateful so that we could spread the computational cost over X frames. Because pathfinding and follow code were the very first things I worked on for those games I had to write a sandbox because there was no game environment to work in yet.

I also remember that we added more and more "optimization" hacks to the pathfinder because of the cost. The discussion was like: "Its taking too long when the NPCs go upstairs and they end up lost in the bedrooms by the timeout" and so we'd add hacks like "Exclude staircases". There were a number of these hacks. Each of those hacks would then create non-obvious complications and I strongly remember a lot of frustrating time chasing bug reports of the "bad pathfind in case X" variety only to discover that it was working exactly as designed and that the real problem was one of these hacks had unexpected consequences like: "We excluded to staircase but the staircase tiles extend in front of the door so now they can't find their way out."

This is a tangent to your question about pathfinding, but while I'm thinking about it ... a lesson from U7 pathfinding (and animation in general) was that the stateful requirements were common enough that by U8 I built a Domain Specific Language to model/handle it. The language I built (called Unk) and its compiler had closure concepts very similar to what I later discovered was called "async/await" semantics. This DSL made the game designers life a lot easier -- remember other than those Unk scripts everything was in C and assembly, ie no garbage collectors. Again, I was too young and naive (pre-internet!) to know that async-like language concepts already existed so I just naively "invented" it all from scratch.

It heads to the goal until an obstacle is reached, then follows the wall. Unusually, it forks and follows both the left and right wall simultaneously. It's not always optimal, but the optimal algorithms such as A* have to test more cells.

This algorithm runs my NPCs in Second Life.

[1] https://github.com/John-Nagle/lslutils/blob/master/npc/obsol...