zbs1970

Not commenting on the physics of this; I want to point out that I thought the narrative structure of this book was amazing. I have not read a hard-core piece of analysis in any field before or since that I thought was a page-turner the way this was. When I read it in 2008 I remember completing each chapter and feeling like "we're screwed" and then the next chapter feeling like "ok, we're going to make it." Presenting such analysis in the form of a race between supply and demand was narrative genius and I think should serve as an example of how ideas can be presented in a way that is both exciting and not-dumbed-down.

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.

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.