Time to Reinvent the Route-Finder

Authoring Inform 7
21

Okey dokey, I edited the example project to look at a 4 x 4 grid labelled AA to DD (included below in the Details). I included the definition of diagonals and the 10/14 edge cost rule. When I run it and type DISTANCE, it shows every edge has a weight of 10. So the cost rule fired, but the cost of 14 was never applied, suggesting it recognised no diagonals.

Summary 
"AA to DD"

Include Dijkstra Pathing by Daniel Stelzer.

Distancing is an action applying to nothing. Understand "distance" as distancing.
Carry out distancing:
	recalculate Dijkstra routes from the location;
	repeat with the place running through rooms:
		say "[The place]: [the Dijkstra distance to the place][line break]".

Routing is an action applying to one visible thing. Understand "route [any room]" as routing.
Carry out routing:
	recalculate Dijkstra routes from the location;
	let L be a list of rooms;
	let T be the noun;
	while T is not the location:
		add T at entry 1 in L;
		let T be the Dijkstra predecessor of T;
		if T is nothing, break;
	add T at entry 1 in L;
	let the way be the Dijkstra route to the noun;
	say "Route from [the location] to [the noun]: [L]. Start by going [way]."

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;
	otherwise:
		rule succeeds with result 10;

AA is a Room. AB is east of AA. AC is east of AB. AD is east of AC.

BA is a Room. BB is east of BA. BC is east of BB. BD is east of BC.
BA is north of AA. BB is north of AB. BC is north of AC. BD is north of AD.

CA is a Room. CB is east of CA. CC is east of CB. CD is east of CC.
CA is north of BA. CB is north of BB. CC is north of BC. CD is north of BD.

DA is a Room. DB is east of DA. DC is east of DB. DD is east of DC.
DA is north of CA. DB is north of CB. DC is north of CC. DD is north of CD.

BB is northeast of AA. BB is northwest of AC.
BC is northeast of AB. BC is northwest of AD.

CB is northeast of BA. CB is northwest of BC.
CC is northeast of BB. CC is northwest of BD.

DB is northeast of CA. DB is northwest of CC.
DC is northeast of CB. DC is northwest of CD.

DA is northwest of CB. DD is northeast of CC.
BA is northwest of AB. BD is northeast of AC.

CA is northwest of BB. CD is northeast of BC.

Test me with "distance".

-Wade

22

Hmmm…let me play around with that. It’s possible the direction isn’t getting conveyed properly to the rules.

1 Like
23

Sorry! Yeah, I knew that because cleaning the code up and making the repo public was something I did specifically because we’d discussed pathfinding before SpringThing!

I still haven’t played it yet, but that’s just because I religiously avoid playing games in genres/types I’m currently working on because I’m worried about being “influenced”. I wonder if there’s a psychological term for this, because I’ve heard other authors/creators talk about something similar.

2 Likes
24

Aha, found it. I accidentally stored the door and direction in the wrong variables (so “edge direction” pointed to a door and “edge door” pointed to a direction).

I’ll upload a new version once I’ve tested it a bit more, but for now, replace this:

[ DijkstraWeight from to door dir ;

With this:

[ DijkstraWeight from to dir door ;

With this fix, here’s the output:

AA: 0
AB: 10
AC: 20
AD: 30
BA: 10
BB: 14
BC: 24
BD: 34
CA: 20
CB: 24
CC: 28
CD: 38
DA: 30
DB: 34
DC: 38
DD: 42

4 Likes
25

Yeah it works. Thanks! I’m gonna try adding this extension to my WIP soon.

-Wade

1 Like
26

Ok, I’m now getting this into my WIP, connected to a modded version of Approaches, and having some snags. Though overall, it’s going well. If we forget about doors, it’s doing the right thing :slight_smile:

My approach is - When I’m about to try route-finding, I calculate the Dijk values manually using the phrase, then call one of the route-finding phrases that say they won’t recalculate automatically. I do it this way because I’ve added phrase options to the recalculation phase that mimic the normal route-finding options:

To recalculate Dijkstra distance/distances/path/paths/route/routes from (source - a room), via visited rooms, and/or using doors, and/or using even locked doors

and I want the calculations to sit there until I ask for a new set.

I’ve created Edge Cost rules that support these options and they seem to work fine on their own. When I type ‘distance’, everything reports correctly re: the visited and presence-of-doors options. But when I then say:

'now approach-heading is the Dijkstra route to the current destination'
(current destination being a room variable)

… approach-heading is set to nothing if there’s a door in the path. The player doesn’t move.

This made me wonder – might the above phrase be recalculating the route again anyway via the default algorithm, giving no leeway to doors etc.? That was my first guess, but I’m not sure.

Sorry I don’t have a full example. It’s inveigled across multiple extensions and giant source, but I can probably reduce it to one if need be.

Here’s my edge cost rule:

Edge cost rule (this is the default room cost rule):
	if the edge door is not nothing:[if we encounter a door-]
		say "FOUND A DOOR.";
		unless DIJ-LOCKED is true:[if using 'even using locked doors' option, we have no problem trying any door]
			if DIJ-DOORS is true:[if using 'using doors' option, we only won't tolerate locked ones]
				if edge door is locked:
					say "DOOR LOCKED.";
					rule succeeds with result -1;
				otherwise:
					say "DOOR UNLOCKED.";
			otherwise:[if we're not using any door-accepting options at all]
				rule succeeds with result -1;
	if the edge direction is diagonal:
		rule succeeds with result 14;
	otherwise:
		rule succeeds with result 10;

-Wade

27

Hmm. Can you tell me what “the Dijkstra distance to [destination]” and “the next step on the Dijkstra path to [destination]” return in that case?

The way the algorithm currently works, it doesn’t actually store the directions used on the shortest path, only the rooms. So there’s a separate phrase which then says “okay, assuming X and Y are adjacent, what direction should I go from X to get to Y?” I think that phrase is the one that’s malfunctioning, but this will let me know for sure.

28

Okay. The “the Dijkstra distance to [destination]” correctly returned the distance.

“the next step on the Dijkstra path to [destination]” crashed with an endless series of "[** Programming error: tried to find the “.” of (something) **

-Wade

29

Oho. So that’s where the problem lies. Now if only Inform would tell me what exactly it was trying to find the “.” of.

I’ll investigate further!

1 Like
30

Unfortunately I haven’t been able to reproduce this problem. If you replace your edge cost rule with a simple default one that ignores doors, what happens?

1 Like
31

Hm. Okay, I threw out the fancy edge cost rules and put back the 10/14 default success one, and temporarily removed all options from the recalculation phrase. Now it gives the correct approach heading, correct distance, but then goes into the same programming error with the next step call.

EDIT:

Just to show that I’m calling these correctly and with no interference between, these are the consecutive lines:

say "1approach-heading = [approach-heading]";
say "the Dijkstra distance to current destination is [the Dijkstra distance to current destination].";
say "the next step on the Dijkstra path to the current destination is [the next step on the Dijkstra path to current destination].";

-Wade

2 Likes
32

I should add a more drastic and really weird finding. If I make a totally spare project with nothing but a room and the extension, I couldn’t even get that phrase (the next step on the Dijkstra path to the (room)) to compile at first.

I would have expected a runtime error if it got to run:

Include Dijkstra Pathing by Daniel Stelzer.

AA is a room.

When play begins:
	say next step on Dijkstra path to AA;

The error message said it didn’t like the text ‘destination’, which doesn’t even appear in this source. I have to say ‘said’ because, after switching the project setting from 6M62 to Current, trying to compile again, getting the exact same error, then switching back again, now I was getting the same error, just in a different context. It would compile it, then give the ‘Translating the source - failed’’ screeen. With info in the console ‘# Error: No such constant as “destination”’

-Wade

1 Like
33

OHO. That’s exactly what I needed to know.

It’s a syntax error on my part. Normally when you want to access an I7 variable from I6 code, you use (+ plus brackets +). But if you’re using it to pass an argument from a phrase definition, you need to use {braces} instead. I originally wrote all this code with plus brackets, then went through to change them all to braces.

When doing that, I missed one.

To decide what object is the/-- next step on the/-- Dijkstra path from (source - a room) to (destination - a room):
	(- DijkstraStep({source}, {destination}) -).

To decide what object is the/-- next step on the/-- Dijkstra path to (destination - a room):
	(- DijkstraStep(dijkstra_source, (+ destination +)) -).

That should of course be {destination}. I don’t think this will fix all of your issues, but it might fix some of them. (And I didn’t notice because I was never calling the phrase without providing a source.)

1 Like
34

Great!

Okay, having fixed ‘+ destination +’, and having put all my rules back, I think I can say it’s all working. Why now and not before? Well, I found a door in my game where I didn’t remember there was a door :roll_eyes:

The test case was three rooms joined from west to east, with a door I could open or slam between rooms 1 and 2. But it turned out there was also a door between rooms 2 and 3 that I forgot about it. It was a very forgettable door because all these doors start open, but I had swooped in on this little area as a good test zone because of how I remembered it being. I just remembered wrong :slight_smile:

Thanks again for your persistence and for writing this extension.

EDIT: I hope this post is all true. Still testing and testing.

-Wade

3 Likes
35

Okay (he said again) I’ll describe my current situation. There is a bug in my game involving the phrase options. I can re-code to get around it as is, I think, but it may be that the extension isn’t working quite as intended, too. I’ll just describe it and see what you think @Draconis

Basically I bracketed the phrase ‘recalculate Dijkstra routes from the location’ code with the setting and clearing of flags for whether I want - visited rooms only - accepting doors - accepting even locked doors.

By looking at my game’s rules output, I can see these flags are set, the recalc code is run, the flags are cleared, but then the edge cost rules run a bunch more times, presumably in response to the next line:

now approach-heading is the Dijkstra route to the current destination

So now that the edge cost rules aren’t allowing for any of the option flags, they always end in failure due to my implementation of those flags.

My first question is: Should the extension be firing the edge cost rules again if we ask for ‘the Dijkstra route to the destination’? If it should, I need to change how I’m using my flags. I would then uncouple them from the ‘recalculation’ routine.

-Wade

1 Like
36

This comes down to what exactly it caches. When you recalculate the routes, it stores for each room:

  • The distance from the source room
  • The previous room on the route from the source room

This means you can see the whole route by following those “previous room” vectors.

But, since it only stores the rooms and not the directions to get to them, the route-finder later needs to decide what directions to go to follow that route. And when it does that, it needs to call the edge cost rules again, to make sure it’s not trying to use a direction with a weight of -1. This shouldn’t really matter, unless there are multiple directions leading to the same place, since it already knows what the next step on its path is, and it’s just trying to find any valid direction that leads to that next step. But it sounds like in your case it does.

Now, this could be fixed by storing an additional property on every room: the direction taken to get to it from its parent in the spanning tree. This wouldn’t take too much more memory, and would probably speed things up significantly, since calling an I7 rulebook is slower than calling an I6 routine.

So tl;dr this is working as intended but can be improved.

1 Like
37

All right, I’ve made this change. Here’s the new version.

Dijkstra Pathing-v1.i7x (11.4 KB)

This is the v10 code again, I’m afraid, so you’ll need to change the version number and filename again, and add after "Definitions.i6t" again.

4 Likes
38

Terrific! Looks like it’s all working now, my options included. Thanks much.

-Wade

2 Likes
39

Hi, so I’m experiencing some weird behaviour in how the extension is treating doors. The below adaption of your example shows what is happening. Basically - if a door is more than one room away it is being treated as if it has infinite distance, or doesn’t exist. But as soon as you are next to it, the algorithm picks it up perfectly. Am I doing something wrong / misunderstanding something?

Include Dijkstra Pathing by Daniel Stelzer.

Alpha is a room. Beta is a room. Delta is a room. Epsilon is a room.

Beta is north of Alpha. 
Epsilon is northwest of Delta.

The dimensional gate is a door. It is east of beta and west of delta.

Routing is an action applying to one visible thing. Understand "route [any room]" as routing.
Carry out routing:
	recalculate Dijkstra routes from the location;
	let L be a list of rooms;
	let T be the noun;
	while T is not the location:
		add T at entry 1 in L;
		let T be the Dijkstra predecessor of T;
		if T is nothing, break;
	add T at entry 1 in L;
	let the way be the Dijkstra route to the noun;
	say "Route from [the location] to [the noun]: [L]. Start by going [way]."

Test me with "route delta / route epsilon / n / route delta / route epsilon".
3 Likes
40

Great catch! It was a bug in DijkstraCalculate. At line 70, there’s this code:

if(there ofclass K4_door){
	door = there;
	@push location; location = source;
	there = there.door_to();
	@pull location;
}

In other words, store the current value of location, set location to source, ask the door where it leads from the current location (i.e. source), then restore the original value of location.

But we don’t want to know where the door leads from source, the place our pathing began; we want to know where the door leads from obj, the room currently under consideration! From source it probably leads nowhere.

So change source to obj in line 72 and that’ll be fixed. I’ve attached an updated version.

Dijkstra Pathing-v1.i7x (11.4 KB)

4 Likes