I am honored with yet another suspiciously bubbling beaker! (And a bit embarrassed to say that I actually have no idea what the Mad Scientists’ Club is.)
This time the innovation comes from something I needed rather than an interesting problem on the forums! As you can see from that thread, it was for Death on the Stormrider. I needed precise control over NPC movements in order to make the puzzles work. Qarrad isn’t bothered by heat, but Bashti is; he can’t go through overheated rooms, but is also the only one who can use the crawlspaces, except he should avoid them unless absolutely necessary…
And after several failed attempts with Inform’s standard route-finding, I started looking for alternatives on the forum. That led me to this thread. I recommend reading the first post there for some cool technical details, but the essence is that Inform’s slow route-finding doesn’t actually use a standard algorithm. It’s something custom-built and not-well-documented.
Specifically, I needed an algorithm that could handle a “weighted graph”: a map where the connections between rooms can have different lengths, so going from A to B (weight 5) and B to C (weight 5) can actually be better than going from A to C (weight 20). Inform’s fast route-finding is the Floyd-Warshall algorithm, which can do this, but also calculates every possible route on the map at once—which is bad for my purposes, since I need to redo the calculations every time a different NPC is moving!
Specifically, I needed a “single-source shortest path” (SSSP) algorithm: a way to calculate the best route to every room from a single origin. This can run a lot faster than an “all-pairs shortest path” (APSP) algorithm like Floyd-Warshall. The linked thread uses a classic one called “breadth-first search”…which assumes every connection between rooms has the same length. Curses!
But there’s a very famous algorithm for the SSSP problem on a weighted graph, one of the classic algorithms that every CS student has to learn: Dijkstra’s algorithm, named after the father of computer science himself! There’s only one problem: the way it’s normally implemented requires fancy data structures like priority queues and Fibonacci heaps. At bare minimum, it needs a dynamic list that you can easily add and remove things from. And while I7 can do this easily, I6 cannot.
But, the things that get put in this list are rooms! And rooms are something I6 is very good at working with! I repurposed the room_index property (normally used for fast route-finding) to form a singly-linked list of rooms, with each one’s room_index being a pointer to the next. This gave me the queue I needed, so the algorithm could work!
After several failed experiments, I made it so that every room stores three relevant properties: the calculated distance, the room before this one on the route (formally, its parent in the minimal spanning tree), and the direction to go from that room to get to this one. Since the distance is stored as a property, you can use it to make a scalar adjective in I7: if you say “a room is near if its Dijkstra distance is is at most 3”, then you can look up “the nearest room”—or “the nearest unexplored light-filled room”, or as specific as you like!
The last problem to solve is—if this is a weighted graph, how do you specify the edge weights? How do you say that the connection from A to B is ten meters long and the connection from B to C is fifteen?
For Stormrider I could have done it in pure I6, but every game would want to do it differently. So I made it store the four relevant properties (room gone from, room gone to, direction gone, and door gone through) in global variables and call out to an I7 rulebook, which authors could customize as they pleased. You can make cardinal directions cost 10 and diagonal directions cost 14, for example, if you want to simulate some nice Euclidean geometry, or make closed doors cost 1 and locked doors cost 2 to represent how many turns it’ll take to go through them.
In the end, I’m very happy with it. Every NPC in Stormrider uses this to decide where to go next, with their own set of edge cost rules (“edge cost when the actor is Qarrad” and so on). And the adventurers in Labyrinthine Library of Xleksixnrewix use it too: every turn, they move toward the nearest unexplored room, with diagonal directions costing 1.4 times as much as cardinal ones. Blocking them out of rooms with barriers in them was just another edge cost rule!
For the future, I should probably create a convenience phrase that’s less clunky than “rule succeeds with result N”, and perhaps avoid the conflict with fast route-finding. And it has one significant drawback over the default route-finder, which is that you need to explicitly recalculate routes from your chosen origin before doing anything with them. But overall, I think it’s a solid improvement over the default implementation (in everything except speed—calling the rulebook every time it considers an edge is a serious cost!) and recommend using it for anything involving complicated pathfinding!
There’s not a lot to say about it: it was a fairly trivial tweak, with the only trick being finding where to make the trivial tweak.