Version 1.0.230615 of Dijkstra Pathing by Daniel Stelzer begins here.
Volume 1 - Prerequisites
Use slow route-finding. [Fast route-finding uses certain properties that I've co-opted; in theory it could be made to work but for now this is simpler.]
Volume 2 - I6 Code
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;
-).
A room has a number called Dijkstra distance. The Dijkstra distance property translates into I6 as "distance".
Include (-
[ DijkstraWeight from to door dir ; ! The weight of the edge - currently implemented in I7, but that can change if needed for efficiency
weight_params-->0 = from;
weight_params-->1 = to;
weight_params-->2 = dir;
weight_params-->3 = door;
return ResultOfRule((+ edge cost rules +));
];
[ DijkstraPopMin list prev best bestprev dist ;
dist = INFINITY;
while(list){
if(list.distance < dist){
best = list;
bestprev = prev;
dist = list.distance;
}
prev = list;
list = list.room_index;
}
if(dist == INFINITY) return nothing; ! Nothing has finite distance, which means all unvisited rooms are disconnected from the rest of the graph
if(best == nothing) return nothing; ! List is empty
if(bestprev) bestprev.room_index = best.room_index; ! Remove it from the list
return best;
];
[ DijkstraCalculate source list obj dir there door alt ; ! Run Dijkstra's algorithm for single-source shortest path from `source`
dijkstra_source = source;
list = nothing; ! a linked list that will be our unvisited set
objectloop(obj has mark_as_room){ ! initialize everything
obj.vector = nothing; ! pointer to parent in the minimal spanning tree
obj.distance = INFINITY; ! distance from source
obj.room_index = list; ! repurposing the room_index property to make the list
list = obj;
}
source.distance = 0;
while(list){
obj = DijkstraPopMin(list); ! Pulled out into a separate routine for clarity
! print "Visiting ", (the) obj, "^";
if(obj == nothing) break;
if(obj == list) list = obj.room_index; ! Removed the head? Head should be the next one now
obj.room_index = -1; ! Mark as visited
objectloop(dir ofclass K3_direction){
! print " Looking ", (a) dir, "^";
there = Map_Storage-->((obj.IK1_Count)*No_Directions + dir.IK3_Count); ! Get the room or door that leads in direction `dir` from `obj`
if(there ofclass K4_door){
door = there;
@push location; location = source;
there = there.door_to();
@pull location;
}else{
door = nothing;
}
! print " That way: ", (the) there, "^";
if(there == nothing) continue;
if(there.room_index == -1) continue; ! If it's already been visited
! print " Room found: ", (the) there, "^";
alt = DijkstraWeight(obj, there, dir, door);
if(alt < 0) alt = INFINITY; ! Negative result means impassible
else alt = alt + obj.distance;
if(alt < there.distance){
! print " Reassigning ", (the) there, ": ", alt, "^";
there.distance = alt;
there.vector = obj;
}
}
}
];
[ DijkstraDistance source dest ;
if(dijkstra_source ~= source) DijkstraCalculate(source);
if(dest.distance == INFINITY) return -1;
return dest.distance;
];
[ DijkstraStep source dest tmp ; ! Calculate which room we need to go to next
if(dijkstra_source ~= source) DijkstraCalculate(source);
if(dest.distance == INFINITY) return nothing; ! No route
while(dest ~= source){
tmp = dest;
dest = dest.vector;
}
return tmp;
];
[ DijkstraPredecessor source dest ;
if(dijkstra_source ~= source) DijkstraCalculate(source);
if(dest.distance == INFINITY) return nothing; ! No route
return dest.vector;
];
[ DirToStep source step dir there door ; ! Choose the (or rather *a*) direction that leads from `source` to `step`
if(source == nothing) return nothing;
if(step == nothing) return nothing;
objectloop(dir ofclass K3_direction){
there = Map_Storage-->((source.IK1_Count)*No_Directions + dir.IK3_Count); ! Get the room or door that leads in direction `dir` from `source`
if(there ofclass K4_door){
door = there;
@push location; location = source;
there = there.door_to();
@pull location;
}else{
door = nothing;
}
if(DijkstraWeight(source, there, dir, door) == -1) continue; ! If this edge has infinite weight, don't consider it
if(there == step) return dir;
}
return nothing;
];
-).
Volume 3 - I7 Code
Part 1 - Rulebooks
The edge cost rules are a rulebook producing a number.
Last edge cost rule (this is the default room cost rule):
rule succeeds with result 1.
Part 2 - Phrases
To recalculate Dijkstra distance/distances/path/paths/route/routes from (source - a room):
(- DijkstraCalculate({source}); -).
To decide what number is the/-- Dijkstra distance from (source - a room) to (destination - a room):
(- DijkstraDistance({source}, {destination}) -).
To decide what number is the/-- Dijkstra distance to (destination - a room):
(- DijkstraDistance(dijkstra_source, {destination}) -).
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 +)) -).
To decide what object is the/-- route from (source - a room) to (step - a room):
(- DirToStep({source}, {step}) -).
To decide what object is the/-- Dijkstra route from (source - a room) to (destination - a room):
(- DirToStep({source}, DijkstraStep({source}, {destination})) -).
To decide what object is the/-- Dijkstra route to (destination - a room):
(- DirToStep(dijkstra_source, DijkstraStep(dijkstra_source, {destination})) -).
To decide what object is the/-- Dijkstra predecessor of (destination - a room):
(- DijkstraPredecessor(dijkstra_source, {destination}) -).
To decide whether connecting (first - a room) and (second - a room):
if the edge source is first and the edge destination is second, yes;
if the edge source is second and the edge destination is first, yes;
no.
Part 3 - Variables
To decide what object is the Dijkstra source: (- dijkstra_source -). [Not using "translates as" because we don't want I7 code changing this, but if you need to, you can do that]
[These four are for referencing in the edge cost rules.]
To decide what room is the edge source: (- weight_params-->0 -).
To decide what room is the edge destination: (- weight_params-->1 -).
To decide what direction is the edge direction: (- weight_params-->2 -).
To decide what object is the edge door: (- weight_params-->3 -).
Dijkstra Pathing ends here.
---- DOCUMENTATION ----
Inform's default route-finder works great for many purposes. But sometimes it's insufficient, and we want a general-purpose path-finding algorithm instead. This extension implements Dijkstra's algorithm for that purpose. It calculates the shortest path from the starting point to every reachable room, then lets you query it as needed.
The key enhancement is the "edge cost" rulebook, which lets you set edge weights however you like. These rules can access four different values describing the edge:
the edge source
the edge destination
the edge direction
the edge door
If the direction doesn't matter (i.e. your map is an undirected graph), there's also a shorthand:
when connecting (first - a room) and (second - a room)
This is true no matter which is the source and which is the destination.
These rules should return a non-negative integer for the weight, or -1 to mean "this edge should not be considered". One rule is provided to simulate the default Inform behavior:
Last edge cost rule (this is the default room cost rule):
rule succeeds with result 1.
This assigns a weight of 1 to every edge, unless other rules intervene.
To run the algorithm itself:
recalculate Dijkstra distance/distances/path/paths/route/routes from (source - a room)
This performs all the calculations and caches the results. Now you can query a few different values:
the/-- Dijkstra distance to (destination - a room) -- number
This returns the sum of the edge weights on the shortest path to that destination, or -1 if there is no path.
the/-- next step on the/-- Dijkstra path to (destination - a room) -- room
This returns the next room on that path, or nothing if there is no path.
the/-- Dijkstra route to (destination - a room) -- direction
This returns the direction to the next room on that path, or nothing if there is no path.
Alternate versions of all of these phrases are available that do the calculations for you automatically:
the/-- Dijkstra distance from (source - a room) to (destination - a room) -- number
the/-- next step on the/-- Dijkstra path from (source - a room) to (destination - a room) -- room
the/-- Dijkstra route from (source - a room) to (destination - a room) -- direction
Note: For efficiency, these versions will not re-run the algorithm if the source hasn't changed, even if the map has (e.g. a door has closed in a way that changes edge weights). If this happens, re-run the algorithm by manually calling "recalculate Dijkstra routes from" your source room.
Finally, this extension provides one utility phrase that may be useful to authors:
the/-- route from (source - a room) to (step - a room) -- direction
This returns the direction which leads from "source" to "step", potentially via doors, or nothing if the rooms are not adjacent. It respects the edge weight rules, so if a map connection is given an edge weight of -1, it will not be considered.
One limitation: If there are multiple connections between two rooms, the algorithm will consider them correctly, but the route-finder will not. In other words, if going north from the Lab leads to the Portico with weight 5, and going east from the Lab leads to the Portico with weight 3, the algorithm will correctly surmise that the distance from the Lab to the Portico is 3, but the route-finder may attempt to go north instead of east to get there. If this becomes a problem, change the DirToStep routine to check every direction and choose the one with minimum distance, rather than returning as soon as it finds its goal.
Example: * Graph Theory
*: "Graph Theory"
Include Dijkstra Pathing by Daniel Stelzer.
Alpha is a room. Beta is a room. Gamma is a room. Delta is a room. Epsilon is a room. Digamma is a room.
Beta is north of Alpha. Delta is east of Beta.
Gamma is east of Alpha. Delta is north of Gamma.
Epsilon is northeast of Beta. Epsilon is northwest of Delta.
Edge cost rule when connecting Alpha and Beta: rule succeeds with result 5.
Edge cost rule when connecting Beta and Delta: rule succeeds with result 5.
Edge cost rule when connecting Delta and Epsilon: rule succeeds with result 15.
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]."
Test me with "distance / route alpha / route beta / route gamma / route delta / route epsilon / route digamma".