[zbs1970]

Very similar to the pathfinder I wrote for Ultima in 1990. At the time I was too young and naive to know that there were lots of existing similar graph algorithms (this was before the internet and, more importantly, I was 20 years old and therefore already knew everything LOL).

One nice thing we added to those "large" game worlds back then was to pre-compute "highway" routes and then path-find at run-time to a nearby "on-ramp" to save time. Also, we cheated by teleporting NPCs when no-one was looking.

[Farer]

Wow~ You’re one of the developers of Ultima, a game I truly loved! The concept of using "highways" is really fascinating!

However, in my project, everything is in plain view for everyone to observe, so I won’t be able to use any cheats like that!

[zbs1970]

Yes. I worked on Ultima 7, 8 and Online (but only on UO in early stages as a manager to help get it started). Glad you enjoyed them. I think I still have box copies around here somewhere.

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.

[Farer]

Yes, I was a huge fan of Ultima 7, 9 and Online. I remember that incredible sense of freedom gave me a kind of liberation(?). It’s an honor to be able to have this conversation with you. Thinking about how you were already grappling with pathfinding issues and addressing them in real-time back then makes me feel a bit envious. I’m sure there weren’t many people who could have had such experiences at that time. It’s thanks to people like you with those experiences that today’s programming languages and skills have developed as they have. My technical level is far below yours, but I want to complete a lightweight pathfinding algorithm for my project, no matter what. Thank you for sharing such an inspiring story.