I6 Template Layer

Valency Adjectives.

These are defined in the Standard Rules; the following routines must either test the state (if set is negative), or change the state to set.

One To One Relations.

We provide routines to assert a 1-to-1 relation true, or to assert it false. The relation rel is represented by a property number, and the property in question is used to store the fact of a relationship: O₁ ~ O₂ if and only if O1.rel == O2.

There is no routine to test a 1-to-1 relation, since the predicate calculus code in NI simplifies propositions which test these into direct looking up of the property relation.

Symmetric One To One Relations.

Here the relation is used for both objects: O₁ ~ O₂ if and only if both O1.relation_property == O2 and O2.relation_property == O1.

Various To Various Relations.

Here the relation is represented by an array holding its metadata. Each object in the domain of the relation provides two properties, holding its left index and its right index. The index is its position in the left or right domain. For instance, suppose we relate things to doors, and there are five things in the world, two of which are doors; then the left indexes will range from 0 to 4, while the right indexes will range from 0 to 1. It's very likely that the doors will have different left and right indexes. (If the relation relates a given kind to itself, say doors to doors, then left and right indexes will always be equal.)

It is possible for either the left or right domain set to be an enumerated kind of value, where the I6 representation of values is 1, 2, 3, ..., N, where there are N possibilities. In that case we obtain the index simply by subtracting 1 in order to begin from 0. We mark the domain set as being a KOV rather than a kind of object by storing 0 instead of a property in the relevant part of the relation metadata: note that 0 is not a valid property number.

The structure for a relation consists of eight --> words, followed by a bitmap in which we store 16 bits in each --> word. (Yes, this is wasteful in Glulx, where --> words store 32 bits, but memory is not in short supply in Glulx and the total cost of relations is in practice small; we prefer to keep all the code involved simple.) The structure is precompiled by the Inform compiler: we do not create new ones on the fly.

In the case of a symmetric various to various relation, we could in theory save memory once again by storing only the lower triangle of the bitmap, but the time and complexity overhead are not worth it. When asserting that O₁ ~ O₂ for a symmetric V-to-V, we also automatically assert that O₂ ~ O₁, thus maintaining the bitmap as a symmetric matrix; but in reading the bitmap, we look only at the lower triangle. This costs a little time, but has the advantage of allowing the route-finding routine for V-to-V to use the same code for symmetric and asymmetric relations.

If this all seems rather suboptimally programmed in order to reduce code complexity, I can only say that careless drafts here were the source of some extremely difficult bugs to find.

Equivalence Relations.

For every equivalence relation there is a corresponding function f such that x ~ y if and only if f(x)=f(y), where f(x) is a number identifying the equivalence class of x. Rather than inefficiently storing a large relation bitmap (and then having a very complicated time updating it to keep the relation transitive), we store f: that is, for every object in the domain set, there is a property prop such that O.prop is the value f(O).

Show Various to Various.

The rest of the code for relations has no use except for debugging: it implements the RELATIONS testing command. Speed is unimportant here.

Show One to One.

Show Reversed One to One.

There's no such kind of relation as this: but the same code used to show 1-to-1 relations is also used to show various-to-1 relations, since the storage is the same. To show 1-to-various relations, we need a transposed form of the same code in which left and right are exchanged: this is it.

Show Equivalence.

Relation Emptying.

These routines, mercifully a little simpler, define the adjective "empty" as it applied to relations. Each routine has to forcibly empty the relation if the clear flag is set, and in any case return either true or false to say whether the relation is empty at the end of the call. For relations in groups, "empty" is understood to mean that each object relates only to itself.

Map Route-Finding.

The general problem we have to solve here is: given x, y ∈ R, where R is the set of rooms and we write x ~ y if there is a map connection from x to y, (i) find the smallest m such that there exist x = r₁ ~ r₂ ~ ... ~ r_m = y ∈ R, or determine that no such m exists, and (ii) find d, the first direction to take from x to lead to r₂, or set d=0 if no such path exists or if m=1 so that x=y.

Thus a typical outcome might be either "a shortest path from the Town Square to the Hilltop takes 11 moves, starting by going northeast from the Town Square", or alternatively "there's no path from the Town Square to the Hilltop at all". Note that the length of the shortest path is unambiguous, but that there might be many alternative paths of this minimum length: we deliberately do not specify which path is chosen if so, and the two algorithms used below do not necessarily choose the same one.

Route-finding is not an easy operation in computation terms: the various algorithms available have theoretical running times which are easy (if sobering) to compute, but which are not in practice typical of what will happen, because they are quite sensitive to the map in question. Are all the rooms laid out in a long line? Are there clusters of connected rooms like islands? Are there dense clumps of interconnecting rooms? Are there huge but possibly time-saving loops? And so on. Overhead is also important. We present a choice of two algorithms: the "fast" one has a theoretical running time of O(n³⁾, where n is the number of rooms, whereas the "slow" one runs in O(n²⁾, yet in practice the fast one easily outperforms the slow on typical heavy-use cases with large maps.

The other issue is memory usage: we essentially have to strike a bargain between speed and memory overhead. Our "slow" algorithm needs only O(n) storage, whereas our "fast" algorithm needs O(n²⁾, and this is very significant in the Z-machine where array space is in desperately short supply and where, if n > 50 or so, the user is already likely to be fighting for the last few bytes in readable memory.

The user is therefore offered the choice, by selecting the use options "Use fast route-finding" and "Use slow route-finding": and the defaults, if neither option is explicitly set, are fast on Glulx and slow on the Z-machine. If both use options are explicitly set – which might happen due to a disagreement between extensions – "fast" wins.

Cache Control.

We provide code to enable our route-finding algorithms to cache their partial results from one usage to the next (though at present only the "fast" algorithm does this). The difficulty here is that the result of a route search depends on three things, any of which may change:

(a) which subset of rooms we are route-finding through; (b) which subset of doors we are allowing ourselves to use; and (c) the current map connections between rooms.

We keep track of (c) by watching for calls to SignalMapChange() from the routines in WorldModel.i6t which alter the map. (a) and (b), however, require tracking from call to call what the current subset of rooms and doors is. (It is not sufficient to remember the criteria used last time and this time, because circumstances could have changed such that the criteria produce a different outcome. For instance, searching through lighted rooms and using unlocked doors will produce a different result if a door has been locked or unlocked since last time, or if a room has become lighted or not.) We store the set of applicable rooms and doors by enumerating them in the property room_index and by the flags in the DoorRoutingViable array respectively.

Fast Route-Finding.

The following is a form of Floyd's adaptation of Warshall's algorithm for finding the transitive closure of a directed graph.

We need to store a matrix which for each pair of rooms R_i and R_j records a_ij, the shortest path length from R_i to R_j or 0 if no path exists, and also d_ij, the first direction to take on leaving R_i along a shortest path to R_j, or 0 if no path exists. For the sake of economy we represent the directions as their instance counts (numbered from 0 in order of creation), not as their direction object values, and then store a single word for each pair (i, j): we store d_ij + D a_ij. This restricts us on a signed 16-bit virtual machine, and with the conventional set of D=12 directions, to the range 0 ≤ a_ij ≤ 5461, that is, to path lengths of 5461 steps or fewer. A work of IF with 5461 rooms will not fit in the Z-machine anyway: such a work would be on Glulx, which is 32-bit, and where 0 ≤ a_ij ≤ 357,913,941.

We begin with a_ij = 0 for all pairs except where there is a viable map connection between R_i and R_j: for those we set a_ij=1 and d_ij equal to the direction of that map connection.

Following Floyd and Warshall we test if each known shortest path R_x to R_y can be used to shorten the best known path from R_x to anywhere else: that is, we look for cases where a_xy + a_yj < a_xj, since those show that going from R_x to R_j via R_y takes fewer steps than going directly. See for instance Robert Sedgewick, Algorithms (1988), chapter 32.

The trouble with the Floyd-Warshall algorithm is not so much that it takes in principle O(n³⁾ time to construct the matrix: it does, but the coefficient is low, and in the early stages of the outer loop the fact that the vertex degree is at most D and usually much lower helps to reduce the work further. The trouble is that there is no way to compute only the part of the matrix we want: we have to have the entire thing, and that means storing n² words of data, by which point we have computed not only the fastest route from R_x to R_y but also the fastest route from anywhere to anywhere else. Even when the original map is sparse, the Floyd-Warshall matrix is not, and it is difficult to store in any very compressed way without greatly increasing the complexity of the code. This is why we cache the results: we might as well, since we had to build the entire memory structure anyway, and it means the time expense is only paid once (or once for every time the state of doors and map connections changes), and the cache is useful for all future routes whatever their endpoints.

Slow Route-Finding.

The alternative algorithm, used when only O(n) memory is available, computes only some of the shortest paths leading to R_y, and is not cached – both because the storage is likely to be reused often by other searches and because there is little gain from doing so, given that a subsequent search with different endpoints will not benefit from the results of this one. On the other hand, to call it "slow" is a little unfair. It is somewhat like Prim's algorithm for finding a minimum spanning tree, rooted at R_y, and grows the tree outward from R_y until either R_x is reached – in which case we stop immediately – or the (directed) component containing R_y has been exhausted – in which case R_x, which must lie outside this, can have no path to R_y. In principle, the running time is O(dn²⁾, where d ≤ D is the maximum vertex degree and n is the number of rooms in the component containing R_y: in practice the degree is often much less than 12, while the algorithm finishes quickly in cases where R_y is relatively isolated and inaccessible or where a shortish route does exist, and those are very common cases in typical usage. There will be circumstances where, because few routes need to be found and because of the shape of the map, the "slow" algorithm will outperform the "fast" one: this is why the user is allowed to control which algorithm is used.

For each room R_z, the property vector stores the direction object of the way to go to its parent room in the tree rooted at R_y. Thus if the algorithm succeeds in finding a route from R_x to R_y then we generate the route by starting at R_x and repeatedly going in the vector direction from where we currently stand until we reach R_y. Since every room needs a vector value, this requires n words of storage. (The vector values store only enough of the minimal spanning tree to go upwards through the tree, but that's the only way we need to traverse it.)

The method can be summed up thus:

(a) Begin with every vector blank except that of R_y, the destination. (b) Repeatedly: For every room in the domain set, try each direction: if this leads to a room whose vector was determined on the last round ( not on this one, as that may be a suboptimal route), set the vector to point to that room. (c) Stop as soon as the vector from the origin is set, or when a round happens in which no further vectors are found: in which case, we have completely explored the component of the map from which the destination can be reached, and the origin isn't in it, so we can return "no".

To prove the correctness of this, we show inductively that after round n we have set the vector for every room having a shortest path to R_y of length n, and that every vector points to a room having a vector in the direction of the shortest path from there to R_y.

Relation Route-Finding.

The general problem we have to solve here is: given x, y ∈ D, where ~ is a relation on a domain set D of objects,

(i) find the smallest n such that there exist x = r₁ ~ r₂ ~ ... ~ r_n = y ∈ D such that r_i ~ r_i+1, or determine that no such n exists, and if so (ii) find a value of r₂ in such a "route" between x and y, or set r₂=0 if x=y so that n=1.

While in general a relation can have different left and right domains (a relation between doors and rooms, say), route-finding on those relations is unlikely to be very useful, so is discouraged. (In the case of doors and rooms, a route could never be longer than 1 step, since no object is both a door and a room, for instance.) The "fast" V-to-V algorithm requires D to have the same left and right domains; NI compiles the memory caches for V-to-V relations to force any cases with different domains into using the "slow" algorithm.

MAX_ROUTE_LENGTH is used simply as a sanity check to prevent hangs if something should go wrong, for instance if the property of a 1-to-V relation has been modified by some third-party code in such a way that it loses its defining invariant.

One To Various Route-Finding.

Here we can immediately determine, given y, the unique y' such that y' ~ y, so finding a path from x to y is a matter of following the only path leading to y and seeing if it ever passed through x; thus the running time is O(n), where n is the size of the domain. It would be pointless to cache this.

Note that we can assume here that x ≠ y, or rather, that from ~= to, because that case has already been taken care of.

Various To One Route-Finding.

This time the simplifying assumption is that, given x, we can immediately determine the unique x' such that x ~ x', so it suffices to follow the only path forwards from x and see if it ever reaches y. The routine is not quite a mirror image of the one above, because both have the same return requirements: we have to ensure that the vector properties lay out the path, and also return the next step after x.

Slow Various To Various Route-Finding.

Now there are no simplifying assumptions and the problem is essentially the same as the one solved for route-finding in the map, above. Once again we present two different algorithms: first, a form of Prim's algorithm for minimal spanning trees. Note that, whereas this algorithm was not always so "slow" for the map – because of the fairly low vertex degrees involved, i.e., because most rooms had few connections to other rooms – here the relation might well be almost complete, with almost all the objects related to each other, and then the algorithm will indeed be "slow". So it is likely that the "fast" algorithm will always be better, if the memory can be spared for it.

We use the fast algorithm for a given relation if and only if the NI compiler has allocated the necessary cache memory; the two use options above, for map route-finding, don't control this.

Fast Various To Various Route-Finding.

Now, as above, a form of the Floyd-Warshall algorithm. The matrix is here stored in the cache of memory pointed to in the V-to-V relation structure. We are unable to combine a_ij and d_ij into a single cell of memory, so in fact we store two separate matrices: one for a_ij (this is cache below), the other for n_ij, where n_ij is the next object in the shortest path from O_i to O_j (this is cache2 below).

Where n<256 a shortest path must be such that a_ij ≤ 255, so can be stored in a single byte, and we similarly store n_ij as the index of the object rather than the object value itself: the index ranges from 0 to n-1, so that 0 ≤ n_ij < 255 and we can use n_ij = 255 as a sentinel value meaning "no path". Although the reconversion of n_ij back into a valid object value takes a little time, it is only O(n), and of course we know n is relatively small; and in this way we reduce the storage overhead to only n² bytes.

Where n ≥ 256, we resign ourselves to storing two words for each pair (i,j), making 2n² bytes of storage on the Z-machine and 4n² bytes of storage on Glulx, but lookup of a cached result is slightly faster.

Iterating Relations.

The following is provided to make it possible to run an I6 routine on each relation in turn. (Each right-way-round relation, at any rate.)