Ah, sorry. This isn’t directly related to Inform pathfinding–it finds a path through a grid of cells rather than on a graph of room connections (as the built-in pathfinding does). Don’t know if it would still be useful to you, but here it is:
[spoiler][code]“A-Star”
Release along with an interpreter.
[-----------]
[Multi-window]
Include Flexible Windows by Jon Ingold.
The map-window is a text-grid g-window spawned by the main-window. The position is g-placeabove. The scale method is g-fixed-size. The measurement is 9.
When play begins:
open up the map-window.
Window-drawing rule for the map-window:
move focus to the map-window, clearing the window;
let M be 0;
let count be 0;
repeat with N running through the grid of the location:
increase count by 1;
increase M by 1;
if M > the grid-width of the location:
now M is 1;
say “[line break]”;
if count is the flat-position of the marker:
say " @";
else if count is listed in the least-cost path:
say " X";
otherwise:
select a row with a tile number of N in the Table of Tiles;
say " [key entry]";
return to main screen.
Instead of jumping:
find path to goal in the location;
refresh windows.
[-----------]
[Single-window]
[To display map:
say “[line break][fixed letter spacing]”;
let M be 0;
let count be 0;
repeat with N running through the grid of the location:
increase count by 1;
increase M by 1;
if M > the grid-width of the location:
now M is 1;
say “[line break]”;
if count is the flat-position of the marker:
say " @";
else if count is listed in the least-cost path:
say " X";
otherwise:
select a row with a tile number of N in the Table of Tiles;
say " [key entry]";
say “[variable letter spacing][line break]”
Instead of jumping:
find path to goal in the location;
display map.
After looking:
display map.]
[--------------]
Include (- Array Cost_Map --> 256; -) after “Definitions.i6t”.
A map room is a kind of room.
A map room has a list of numbers called the grid.
A map room has a number called the grid-width.
The goal is a list of numbers variable. The goal is {9, 3}.
The starting point is a list of numbers variable. The starting point is {2, 5}.
The marker is a list of numbers variable. The marker is {2, 5}.
To decide whether (N - a number) is the flat-position of (G - a list of numbers):
let pos be ( (entry 2 of G - 1) * grid-width of location) + (entry 1 of G);
if N is pos, decide yes.
To decide what number is flat-position of (G - a list of numbers):
decide on ( (entry 2 of G - 1) * grid-width of location) + (entry 1 of G);
Walkability is a kind of value. The walkabilities are unwalkable and walkable.
The open list is a list of numbers variable.
The least-cost path is a list of numbers variable.
Table of Visited Nodes
node position closed-node parent F-score G-score H-score
a number truth state number number number number
with 99 blank rows
To evaluate the/-- walkability of the/-- map for (R - a map room):
write index to cost-map for the grid of R;
repeat with pos running from 1 to the number of entries of the grid of R:
select row with tile number of (entry pos of grid of R) in the table of tiles;
add (pass entry) to the cost-map at pos.
To write index to the/-- cost-map for (L - a list of numbers):
(- Cost_Map --> 0 = LIST_OF_TY_GetLength({-pointer-to:L}); -)
To add (W - a walkability) to the/-- cost-map at (pos - a number):
(- Cost_Map --> {pos} = {W} - 1; -)
To find path to goal in (R - a map room):
[create bitmap version of the map to define inaccessible squares]
evaluate the walkability of the map for R;
[initialize temporary variables]
let path completed be false;
let W be grid-width of R;
let G be a number;
[zero out the administrative lists]
let the goal position be the flat-position of the goal;
blank out the whole of the table of visited nodes;
now the open list is {};
[add starting node to the open list and initialize costs]
add flat-position of starting point to the open list;
choose row 1 from the table of visited nodes;
now the node position entry is entry 1 of the open list;
now the parent entry is 0;
now the G-score entry is 0;
now the H-score entry is the heuristic distance from the flat-position of the starting point to the goal position in the map of R;
now the F-score entry is G-score entry + H-score entry;
[now closed-node entry is false;]
[main loop: select neighbor with the best score and follow on.]
while the number of entries of the open list > 0:
[sort the table of visited nodes in F-score order;][this sort function now replaced with priority queue on the open list]
select row with a node position of (entry 1 in the open list) in the table of visited nodes;
let best F be F-score entry;
[choose row with a closed-node of false in the table of visited nodes;]
let current node be a number;
let current node be node position entry;
let G be G-score entry;
[now closed-node entry is true;]
remove the current node from the open list;
if the current node is the goal position:
now path completed is true;
break;
let candidates be the neighbors of the current node in the map of R;
repeat with selected running through candidates:
if selected is not listed in the open list:
choose blank row in the table of visited nodes;
now node position entry is selected;
now parent entry is current node;
if ABS (current node - selected) is 1 or the remainder after dividing ( ABS (current node - selected) ) by W is 0:[short way of determining whether neighbor is orthagonal]
now G-score entry is G + 10;
otherwise:
now G-score entry is G + 14;
now H-score entry is the heuristic distance from selected to the goal position in the map of R;
now F-score entry is G-score entry + H-score entry;
[now closed-node entry is false;]
[let F1 be F-score entry;]
if F-score entry < (best F + 1):
add selected at entry 1 in the open list;
otherwise:
add selected to the open list;
otherwise if there is a node position of selected in the table of visited nodes:
select row with a node position of selected in the table of visited nodes;
let G1 be a number;
if ABS (current node - selected) is 1 or the remainder after dividing ( ABS (current node - selected) ) by W is 0:[short way of determining whether neighbor is orthogonal]
now G1 is G + 10;
otherwise:
now G1 is G + 14;
if G1 < G-score entry:
now parent entry is current node;
now G-score entry is G1;
now H-score entry is the heuristic distance from selected to the goal position in the map of R;
now F-score entry is G-score entry + H-score entry;
[now closed-node entry is false;]
[say “[current node]: added [selected]; F: [F-score entry]; G: [G-score entry]; H: [H-score entry].”;]
if path completed is true:
now the least-cost path is {};
add goal position to least-cost path;
select row with a node position of goal position in the table of visited nodes;
let seek be parent entry;
while seek is not flat-position of starting point:
add seek at entry 1 in least-cost path;
select row with a node position of seek in the table of visited nodes;
now seek is parent entry;
say “Path: [least-cost path].”
To decide what number is ABS (N - a number):
if N < 0, decide on 0 - N;
decide on N.
[To decide which number is the heuristic distance from (S - a number) to (E - a number) in the map of (R - a room):
let L be the coordinates of S in the map of R;
let M be the coordinates of E in the map of R;
let X_dist be entry 1 of L - entry 1 of M;
let Y_dist be entry 2 of L - entry 2 of M;
if X_dist < 0, now X_dist is 0 - X_dist;
if Y_dist < 0, now Y_dist is 0 - Y_dist;
if X_dist > Y_dist:
decide on (14 * Y_dist) + (10 * (X_dist - Y_dist) );
otherwise:
decide on (14 * X_dist) + (10 * (Y_dist - X_dist) ).]
To decide which number is the heuristic distance from (S - a number) to (E - a number) in the map of (R - a room):
let diff be ABS (S - E);
let Y_dist be diff / grid-width of R;
let X_dist be the remainder after dividing diff by grid-width of R;
if X_dist > (grid-width of R / 2), now X_dist is grid-width of R - X_dist;
if X_dist > Y_dist:
decide on (14 * Y_dist) + (10 * (X_dist - Y_dist) );
otherwise:
decide on (14 * X_dist) + (10 * (Y_dist - X_dist) ).
To decide what list of numbers is the coordinates of (N - a number) in the map of (R - a room):
let L be a list of numbers;
let W be the grid-width of R;
If N is 1, now N is 2;
let Y be ( (N - 1) / W ) + 1;
let X be N - (Y * W);
add X to L;
add Y to L;
decide on L.
To decide which list of numbers is the neighbors of (N - a number) in the map of (R - a map room):
let L be a list of numbers;
let candidates be a list of numbers;
let W be the grid-width of R; [width]
let Y_max be the number of entries of the grid of R;
let H be Y_max divided by W; [height]
let X be ( (N / W) * W ) + 1; [first position of current row]
if N < (W + 1), now X is 1;
let X_max be W + (X - 1); [position at end of current row]
unless N + 1 > X_max:
add (N + 1) to L;
if (N + 1) - W > 0, add ( (N + 1) - W ) to L;
if (N + 1) + W < Y_max, add ( (N + 1) + W ) to L;
unless (N - 1) is less than X:
add (N - 1) to L;
if (N - 1) - W > 0, add ( (N - 1) - W ) to L;
if (N - 1) + W < Y_max, add ( (N - 1) + W ) to L;
unless (N - W) < 1, add (N - W) to L;
unless (N + W) > Y_max, add (N + W) to L;
repeat with item running through L:
if square (item) in the cost-map is walkable, add item to candidates;
[select row with tile number of (entry item of grid of R) in the table of tiles;
if the pass entry is walkable, add item to candidates;]
decide on candidates.
To decide whether the/-- square (N - a number) in the cost-map is walkable:
(- Cost_Map --> {N} -)
Include (-
Global seekStartAddress;
Global seekRows;
Global seekVal;
Global seekReturnValue;
-) after “Definitions.i6t”.
To select a/the/-- row with (TC - a word value valued table column) of (W - a word value) in/from (T - table name):
(- {-require-ctvs}
ct_0 = {T};
ct_1 = -1;
seekStartAddress = ({T})–>(TableFindCol({T}, {TC}, true)) + (COL_HSIZE * WORDSIZE);
seekRows = TableRows({T}) + 2;
seekVal = {W};
@linearsearch seekVal WORDSIZE seekStartAddress WORDSIZE seekRows 0 4 ct_1;
if (ct_1 < 1) return RunTimeProblem(RTP_TABLE_NOCORR, {T});
-).
Include (-
Global quickloopSearchFor;
Global quickloopStartAddress;
Global quickloopRowsLeft;
Global quickloopReturnValue;
-) after “Definitions.i6t”.
To repeat through (tab - table name) until (row - number) with (tc - a word value valued table column) as (val - a word value) begin – end:
(- {-require-ctvs} ! {-zero-counter:reviewHistoryCol}
ct_0 = {tab};
!print "rows: ", {row}, "; value: ", {val}, ". ";
ct_1 = -1;
quickloopSearchFor = {val};
quickloopStartAddress = ({tab})–>(TableFindCol({tab}, {tc}, true)) + (COL_HSIZE * WORDSIZE);
quickloopRowsLeft = {row};
quickloopReturnValue = -1;
while (1) {
@linearsearch quickloopSearchFor WORDSIZE quickloopStartAddress WORDSIZE quickloopRowsLeft 0 4 quickloopReturnValue;
quickloopReturnValue++;
if (quickloopReturnValue == 0) break;
ct_1 = ct_1 + quickloopReturnValue; ! set the chosen row for I7
quickloopStartAddress = quickloopStartAddress + (WORDSIZE * quickloopReturnValue); ! set start point for next iteration
quickloopRowsLeft = quickloopRowsLeft - quickloopReturnValue; ! decrease #/rows left to check
!-).
Table of Tiles
tile number pass key
0 unwalkable " "
1 unwalkable “#”
2 walkable “·”
[-----------------]
The kitchen is a map room. The grid-width is 10. The grid is {
0, 0, 0, 1, 2, 1, 0, 0, 0, 0,
1, 1, 1, 1, 2, 1, 1, 1, 1, 1,
1, 2, 2, 2, 2, 2, 2, 2, 2, 1,
1, 1, 1, 1, 1, 2, 2, 1, 1, 1,
1, 2, 2, 1, 2, 2, 2, 2, 2, 1,
1, 2, 2, 1, 2, 2, 2, 2, 2, 1,
1, 2, 2, 2, 2, 1, 1, 1, 1, 1,
1, 1, 1, 2, 2, 1, 0, 0, 0, 0,
0, 0, 1, 2, 2, 1, 0, 0, 0, 0
}.
[The kitchen is a map room. The grid-width is 9. The grid is {
0, 0, 0, 1, 2, 1, 0, 0, 0,
1, 1, 1, 1, 2, 1, 1, 1, 1,
1, 2, 2, 2, 2, 2, 2, 2, 1,
1, 1, 1, 1, 1, 2, 2, 1, 1,
1, 2, 2, 1, 2, 2, 2, 2, 1,
1, 2, 2, 1, 2, 2, 2, 2, 1,
1, 2, 2, 2, 2, 1, 1, 1, 1,
1, 1, 1, 2, 2, 1, 0, 0, 0,
0, 0, 1, 2, 2, 1, 0, 0, 0
}.]
Dumping is an action applying to nothing. Understand “dump” as dumping.
Carry out dumping:
debug node position in the Table of Visited Nodes.
[say “Table of Visited Nodes[line break]”;
repeat through the Table of Visited Nodes:
say “[node position entry]; [F-score entry].”]
To debug (TC - a table column) in (T - a table name):
(- TableColumnDebug({T}, {TC}); -)[/code][/spoiler]
. Can you check what “the minimum timer resolution” is, with an After running the benchmark framework rule? It stores the samples in a list, so with that many samples it’s sure to cause problems.