That sounds good, though email would be better thanks.
Dannii, I’ve got an implementation of A* pathfinding laying around. It’s pretty darn slow. Would you be interested in that?
Yes that sounds good too. If you have a map where it was particularly slow that’d be good too.
What kind of path finding is built into I7? I’ve never looked at the details.
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]
I’m looking for slow algorithms that together will provide a somewhat comprehensive performance stress test of our interpreters. So the ideal test would be something you actually wanted to use, but was too slow so you couldn’t. Then we can use the tests to profile our interpreters to find what’s slow, and prove that our interpreter changes actually help. (Of course a lot of the time the solution will be a better algorithm, but this extension will help with that too!)
So your code looks good. I’ll have to strip out all the printing code though.
If anyone hits this topic off search engine, like I did today, there is a newer version of the extension at: raw.githubusercontent.com/i7/ex … arking.i7x
Version 1/130803 of Benchmarking (for Glulx only) by Dannii Willis
Thank you Dannii. As we are moving more into a diverse set of mobile devices, some of which are ultra-conservative on battery, it might make sense to add a BogoMIPS like fast call in this extension so that an Inform 7 story could make choices based on how fast the device interpreter is? For example, on slow Glulx interpreters like Incant for Android - a loading message could be presented.
Extension Version 1/130803 doesn’t currently build on Inform 7 build 6M62. Error:
In Part 2 - The interface unindexed in the extension Benchmarking by Dannii
Willis:
>--> The table 'Table of User Styles (continued)' (~/Inform/Extensions/dannii
willis/benchmarking.i7x, line 506) won't work as a continuation, because it
contains a column not found in the original 'Table of User Styles' (~/Inform/Extensions/jon
ingold/flexible windows.i7x, line 614).
The old table has columns: window, style name, background color, color, first
line indentation, fixed width, font weight, indentation, italic,
justification, relative size, reversed.
The new table has columns: style name, glulx color.I reworked the Glk color table and got that to compile, but now it has another compile error on Inform 7 build 6M62. Version 1/130803 of Benchmarking (for Glulx only) by Dannii Willis:
In Part 1 - The framework, Section - Real numbers unindexed in the extension
Benchmarking by Dannii Willis:
>--> You wrote 'R1 specifies a real number' (~/Inform/Extensions/dannii
willis/benchmarking.i7x, line 203): but you can only specify ways to write
new kinds of value, as created with sentences like 'A weight is a kind of
value.', and not the built-in ones like 'number' or 'time'.Assistance appreciated.
Inform now has native real-number support. You could change the extension to use this, or (easier) change all occurrences of “real number” to “custom number” or such.