Time to Reinvent the Route-Finder

Authoring Inform 7
1

As I prepare to overcomplicate yet another thing, I want to check and see if there’s an obvious solution I’ve missed.

The core of my current project is that NPCs can do things you can’t, but you can never communicate with them directly. So you have to try to manipulate the environment to make things happen to your benefit.

One of these NPCs is running around putting out any metaphorical fires that happen. You need to cause problems in particular rooms and then ensure the map is set up such that his route to those problems will open the doors you need. So far so good. Inform’s got good route-finding built in, and I’ve got my Enhanced Route Finding extension to improve it even further.

Some doors are jammed and he can’t use them. Some rooms are cramped and he prefers to avoid them. Some rooms are overheated and he really prefers to avoid them. So far so good. Inform can handle all of this.

But how does he choose his targets in the first place?

The obvious solution is to use a superlative adjective:

Definition: a room (called the place) is ready if the number of moves from the location of Bashti to the place through moderate rooms using easy doors is less than 5.

Let the goal be the readiest sabotaged room…

Unfortunately superlatives only work with properties of objects, not calculated values. So this is off the table.

My current plan is to make a table, and put each sabotaged room in its own row. Then for each one, I’ll record:

  • The number of moves from Bashti’s location to this place, through easy rooms only
  • The number of moves through easy and cramped rooms
  • The number of moves through easy, cramped, and overheated rooms

Then I can calculate some kind of heuristic for how easy it will be to get to that room. Maybe add a penalty to the second and third columns, change “there is no route” to 9999, then take the minimum distance between the three. Sort by this heuristic column, and the top row is his new destination.

But this seems like a lot of wheel-reinventing going on. Is there a simpler or more elegant way to do this in I7?

(Side note: for anyone else who wants to do this, remember to calculate the values one column at a time, not one row at a time. With fast route-finding Inform reruns the shortest-path algorithm every time you change which subset of rooms and doors you’re looking for, and caches the results. So you want to change that subset as few times as possible. This is my reason for putting them in a table instead of storing the heuristic value as a property of each object.)

5 Likes
2

I recent(-ish)ly tackled a similar set of problems in TADS3. The basic approach I ended up using is basically to go through each room, computing the path to each other room. From this path, just remember the “next hop”, creating a hash table for the room in which the destination is the key and the next hop is the value.

For the specific case you’re describing, you’d just compute your paths using edge weights to represent pathing “preferences”: so instead of using a default weight of 1, cramped rooms have a weight of 3 and overheated rooms are 5.

Not for I7, but I implemented a fairly complete precomputed table-based routing system for TADS3/adv3, detailed in this thread. There’s a git repo for the code, linked in the thread.

3 Likes
3

FWIW, I couldn’t think of anything that improves on your table approach.

1 Like
4

The main disadvantages to using precomputed tables are:

  • Memory use
  • More expensive if traversibility flags (or in this case path weights) change frequently

The memory issue can be managed by dividing the map into more “zones”, but I think for most IF map sizes (<100 rooms) it’s not going to be a big deal even if you’re not subdividing the map. At least on modern hardware.

And I’ll just add a disclaimer that while I wrote the implementation and all the T3 code, the idea itself isn’t mine; it’s a (somewhat simplified version of) how a lot of network routing works. I don’t think I’ve ever seen it used in IF before, but I’ve seen analogous approaches used in other kinds of game design (e.g., roguelikes).

2 Likes
5

…sorry, I meant “your table approach” in reply to Daniel’s original post; I had missed how ambiguous it became coming after your post!

1 Like
6

Yeah, I was just adding a disclaimer for clarity.

I’d actually cite whoever originally came up with the idea of next hop routing but I don’t know if that’s even known.

1 Like
7

The tables ended up becoming impractical, so I just went through and reimplemented Dijkstra’s algorithm. As jbg pointed out, it’s simpler to have an algorithm that handles edge weights from the start, rather than trying to hack that in later.

1 Like
8

Speaking of which, here’s the current version. Works well enough so far but I can’t guarantee it’s free of bugs.

For all your single-source-shortest-path needs!

Dijkstra Pathing-v1.i7x (11.5 KB)

4 Likes
9

This looks great. Does it work %100 on distances? Or does number of required moves also figure in? What I mean is – say a room to the northeast could be reached in a single 2km move by going northeast, or two 1km moves (N then E, or E then N) will it favour the one move path?

-Wade

1 Like
10

Just distances. It only cares about the edge weights, not how many moves it will take to follow them.

In that example, it will actually default to the one-move path, but that’s just a detail of the implementation—if there are multiple paths with the same total distance, I don’t think this algorithm guarantees anything about which one will be preferred.

(Side note: this should work perfectly fine with zero-weight edges, so if you want to find the path that uses the fewest possible doors but doesn’t care about total distance, that’s also doable. The one thing Dijkstra’s algorithm can’t handle is negative edge weight; that requires some fancier logic. So in this implementation, a negative weight will be taken as “this path does not exist”, effectively infinite.)

11

I remember my original trouble with pathfinding was: On a regular grid that also has diagonal connections between points, Inform’s path-finding would sometimes make diagonal swerves when travelling between two points in a single row of the grid, or two points in a single column. I wanted it to just go in a straight line. In any build, the occurence of the swerves was predictable, and could be hacked out. But I’d like to stop having to do that.

It sounds like that in the zero weight grid that I described, your extension – even if only by implementation detail – will move diagonally all it can first, then hold straight?

I suppose I should try it.

EDIT: Folks did supply code to try to help me before, but it looked a bit heavy for me at the time. Yours being an extension with docs and an example makes it more approachable for me.

-Wade

1 Like
12

It’ll depend on your weights. If you do something like this:

Definition: a direction is diagonal if it is northeast or it is northwest or it is southeast or it is southwest.

Edge cost rule:
    if the edge direction is diagonal, rule succeeds with result 14;
    rule succeeds with result 10.

Then it’ll consider each diagonal move to be 1.4 times as long as the others, which is pretty close to accurate for a grid. Now if it’s trying to go due north it won’t swerve east and west (because there’s a penalty for doing so).

Do let me know how (slash if) it works for you! And if you come up with more examples I’d love to extend the docs with them.

1 Like
13

Thanks. I’m up to the trying it out bit, but forgot to mention (as it’s only become a semi-recent requirement that I do) that I’m in 6M62. I changed the extension version number so 6M62 would tolerate it, but compilation of the example project failed like so:

Summary 
... ++ Ended: Translation succeeded: 6 rooms, 1 thing

Inform 7 has finished.

/Applications/Inform 10-1-2.app/Contents/MacOS/inform6 \

-kE2SDwG +include_path=/Applications/Inform 10-1-2.app/Contents/Resources/Library/6.11,.,../Source /Users/wadeclarke/Documents/crap.inform/Build/auto.inf /Users/wadeclarke/Documents/crap.inform/Build/output.ulx

Launching: /Applications/Inform 10-1-2.app/Contents/MacOS/inform6 "-kE2SDwG" "+include_path=/Applications/Inform 10-1-2.app/Contents/Resources/Library/6.11,.,../Source" "/Users/wadeclarke/Documents/crap.inform/Build/auto.inf" "/Users/wadeclarke/Documents/crap.inform/Build/output.ulx"

Inform 6.41 for MacOS (22nd July 2022)

File "/Users/wadeclarke/Documents/crap.inform/Build/auto.inf"; Line 36743 # Error: "distance" is a name already in use and may not be used as a new property name (Individual property "distance" was defined at line 10617)

> Property distance

File "/Users/wadeclarke/Documents/crap.inform/Build/auto.inf"; Line 36744 # Error: Variable must be defined before use: "dijkstra_source"

> Global dijkstra_source ...

-Wade

14

Ah, okay. That will require a couple little tweaks, because the rules for I6 inclusions changed between versions.

If you look in volume 2 of the extension, it has three parts: a little bit of I6 that defines a couple things, an Inform 7 property definition, and then a huge block of I6 with all the routines in it. Change the ending of that first one to:

-) after "Definitions.i6t".

And then if it keeps complaining about Property distance just remove that line. See what happens with that.

15

Hehe, this multiplied the errors by a lot.

If you want to have a crack at fixing it yourself instead of by remote, perhaps you can put the example project in an empty project, and in the settings tab, choose 6M62 as your version.

-Wade

16

That change was sufficient for me to get it to compile on 6M62. The “Graph Theory” example seems to run fine.

I did also change the version number to a 6M62-compatible format:

Version 1/230615 of 6M62 Dijkstra Pathing by Daniel Stelzer begins here.
17

Sorry, you’ll need to say what ‘that first one’ means exactly.

-Wade

18

He means the block:

Include (-
Property distance;
Global dijkstra_source;
Constant INFINITY = 10000; ! A value that will never be reached; we could make this much larger on Glulx but why bother?

Array weight_params --> 4;
-).

at the start of “Volume 2 - I6 Code”. Change it to:

Include (-
Property distance;
Global dijkstra_source;
Constant INFINITY = 10000; ! A value that will never be reached; we could make this much larger on Glulx but why bother?

Array weight_params --> 4;
-) after "Definitions.i6t".
19

That’s what I’d thought, but I was still getting weird crashing.

I think I must have mutilated the extension by accident while making changes. I re-downloaded, made the changes on a fresh copy and now it’s working.

-Wade

20

I used it in I Am Prey.

2 Likes