To fit the map of the rooms in the game into a cubical grid, preserving distances and angles where possible, and so to give each room approximate coordinate locations.

• §8. Grand strategy
• §8.3. Page directions
• §8.13. Map reading
• §12. Submap construction
• §8.21. Partitioning to component submaps
• §8.23. Movements of single rooms
• §8.24. Synchronising movements of locked rooms
• §8.26. Positioning within components
• §19. Heat
• §24. Subdividing our submap
• §25. Finding how to divide
• §27. Zones 1 and 2 for a single cut
• §29. Zones 1 and 2 for a double cut
• §31. Tactics
• §32. The cooling tactic
• §35. The quenching tactic
• §36. The diffusion tactic
• §38. The radiation tactic
• §8.28. The explosion tactic
• §8.29. Stage 3, positioning the components
• §8.31. Stage 5, bounding the universe
• §8.32. Stage 6, removing blank planes
• §45. Unit testing

§1. We assign \((x, y, z)\) coordinates to each room, aiming to make the descriptive map connections ("The Ballroom is east of the Old Kitchens") as plausible as possible in coordinate terms. To do this well feels like a research-level problem in graph theory or aesthetics, but we will just have to muddle through.

Those experimenting with this code may like to use "Include spatial map in the debugging layout", and the internal test cases with names in the form Index-MapLayout-*.

§2. We will partition the set of rooms into "components", which are disjoint nonempty collections of rooms joined together by proximity. Proximity comes about in two ways:

• (i) Map connections in directions along lattice lines (EAST, UP, and so on but not INSIDE or OUTSIDE);
• (ii) Locks placed between rooms by sentences intended to give this algorithm hints about layout.

As we will see, we will map rooms using a symmetric form of relationships: if X relates to Y then Y relates to X. This will take some fixing, because map connections in Inform needn't be symmetrical.

We must then solve two different problems. The first is to place rooms at grid positions within each individual component. We assign each possible arrangement a numerical measure of its geometric distortion, and then try to minimise this, but of course any exhaustive search would be prohibitively slow. This problem is quite likely NP-complete, and it looks likely that we can embed notorious problems in complexity theory within it (say, the bandwidth minimization problem). We do have the advantage of experience about what IF maps look like, and of not having to deal well with bizarre maps, but still, we shouldn't expect to achieve a perfect choice. We must be very careful about running time; it's unacceptable for the Inform indexer to take longer to run than Inform itself. The code below is roughly quadratic in the number of rooms, which is a reasonable compromise given how few works of IF have really enormous room counts.

The second problem is to place the components onto a global grid so that they make sensible use of space on the index page, but don't get in each other's way.

§3. A "connected submap" is a map formed from some subset of the rooms in the model world, together with any spatial relationships between them, such that it's possible to go from any X to any Y in the submap using only some sequence of these relationships.

Connected submaps will arise initially because we'll take every component of the map and make it into a connected submap; but then more will exist temporarily as we cut these up. Each room will, at any given time, belong to exactly one submap.

At any given point in our calculations each room has a grid location which is a triple of integers \((x, y, z)\). The position of the origin is undefined, and not relevant, since only the location of one room relative to another is important. We will cache the values of the corner points of the smallest cuboid \((x_0, y_0, z_0)\) to \((x_1, y_1, z_1)\) which contains all of the rooms in our submap. Similarly, we cache the penalty score for the current arrangement of rooms relative to each other within the submap as the "heat", a term to be explained later.

typedef struct connected_submap {
    struct faux_instance *first_room_in_submap;  double-headed linked list of rooms
    struct faux_instance *last_room_in_submap;
    struct cuboid bounds;
    int heat;  current penalty score for bad placement of rooms
    int positioned;  already placed within the global map grid?
    int *incidence_cache;  how many of our rooms occupy each grid position?
    int incidence_cache_size;  how large that cache is
    struct cuboid incidence_cache_bounds;  bounds of the incidence cache array
    int superpositions;  number of pairs of rooms which share the same grid location
    struct index_session *for_session;
    int discarded;
    CLASS_DEFINITION
} connected_submap;

• The structure connected_submap is accessed in 2/ii, 2/sas and here.

§4. One special room is the "benchmark", from which the map is arranged. This is usually the room in which the player begins.

int SpatialMap::benchmark_level?Usage of SpatialMap::benchmark_level:
§8.29.1.1, §8.29.1.2, §8.29.1.3
Faux Instances - §10.4
Render HTML Map - §8(index_session *session) {
    if (FauxInstances::benchmark(session) == NULL) return 0;
    return Room_position(FauxInstances::benchmark(session)).z;
}

§5. We are going to be iterating through the set of rooms often. Looping over all rooms can afford to be fairly slow, but it's essential in order to keep the running time down that we loop through submaps with overhead no worse than the number of rooms in the submap; this is why we keep the linked list.

define LOOP_OVER_SUBMAP(R, sub)
    for (R = sub->first_room_in_submap; R; R = R->next_room_in_submap)

§6. These algorithms are trying to do something computationally expensive, so it's useful to keep track of how much time they cost. The unit of currency here is the "drogna"; 1 drogna is equivalent to a single map or lock lookup, or a single exit heat calculation.

Just as each submap has a bounding cuboid, so does the whole assemblage:

typedef struct map_calculation_data {
    struct cuboid Universe;

    int spatial_coordinates_established;
    int partitioned_into_components;

    int drognas_spent;  in order to measure roughly how much work we're doing
    int cutpoint_spending;
    int division_spending;
    int slide_spending;
    int cooling_spending;
    int quenching_spending;
    int diffusion_spending;
    int radiation_spending;
    int explosion_spending;
} map_calculation_data;

• The structure map_calculation_data is accessed in 4/rhm, 4/rem and here.

§7.

map_calculation_data SpatialMap::fresh_data?Usage of SpatialMap::fresh_data:
Indexing API - §5(void) {
    map_calculation_data calc;
    calc.Universe = Geometry::empty_cuboid();

    calc.spatial_coordinates_established = FALSE;
    calc.partitioned_into_components = FALSE;

    calc.drognas_spent = 0;  in order to measure roughly how much work we're doing
    calc.cutpoint_spending = 0;
    calc.division_spending = 0;
    calc.slide_spending = 0;
    calc.cooling_spending = 0;
    calc.quenching_spending = 0;
    calc.diffusion_spending = 0;
    calc.radiation_spending = 0;
    calc.explosion_spending = 0;
    return calc;
}

§8. Grand strategy. Here is the six-stage strategy. I estimate that the running time is as follows, where \(R\) is the number of rooms:

• (1) Linear time, \(O(R)\), so essentially instant.
• (2) Linear time, \(O(R)\), so essentially instant.
• (3) About \(O(R^2\log R)\), at worst, but generally better in practical cases.
• (4) This could be as bad as \(O(R^2)\), but only in bizarre circumstances.
• (5) Linear time, \(O(R)\), so essentially instant.
• (6) In theory about \(O(R^{4/3})\), but in practice \(O(R)\).

We allow this function to be called more than once only for the convenience of the unit test below, which makes spatial positioning happen early in order to get the results in time to write them in the story file.

void SpatialMap::establish_spatial_coordinates?Usage of SpatialMap::establish_spatial_coordinates:
Map Element - §1
Render EPS Map - §1(index_session *session) {
    if (session->calc.spatial_coordinates_established) return;
    faux_instance_set *faux_set = Indexing::get_set_of_instances(session);
    (1) Create the spatial relationship arrays8.14;
    (2) Partition the set of rooms into component submaps8.21;
    session->calc.partitioned_into_components = TRUE;
    (3) Position the rooms within each component8.26;
    (4) Position the components in space8.29;
    (5) Find the universal bounding cuboid8.31;
    (6) Remove any blank lateral planes8.32;
    (5) Find the universal bounding cuboid8.31;
    session->calc.spatial_coordinates_established = TRUE;
}

§8.1. To make the code less cumbersome to read, all access to the position will be using the following:

define Room_position(R) R->fimd.position

void SpatialMap::set_room_position?Usage of SpatialMap::set_room_position:
§8.23, §8.24, §31, §38.1(faux_instance *R, vector P) {
    vector O = Room_position(R);
    R->fimd.position = P;
    if (R->fimd.submap) SpatialMap::move_room_within_submap(R->fimd.submap, O, P);
}

void SpatialMap::set_room_position_breaking_cache?Usage of SpatialMap::set_room_position_breaking_cache:
§8.18(faux_instance *R, vector P) {
    R->fimd.position = P;
}

§8.2. Locking is a way to influence the algorithm in this section by forcing a given exit to be locked in place, forbidding it to be distorted.

void SpatialMap::lock_exit_in_place?Usage of SpatialMap::lock_exit_in_place:
Faux Instances - §10.2(faux_instance *I, int exit, faux_instance *I2,
    index_session *session) {
    SpatialMap::lock_one_exit(I2, exit, I, session);
    SpatialMap::lock_one_exit(I, SpatialMap::opposite(exit, session), I2, session);
}

void SpatialMap::lock_one_exit(faux_instance *F, int exit, faux_instance *T,
    index_session *session) {
    LOGIF(SPATIAL_MAP, "Mapping clue: put %S to the %s of %S\n",
        FauxInstances::get_name(T), SpatialMap::usual_Inform_direction_name(exit, session),
        FauxInstances::get_name(F));
    F->fimd.lock_exits[exit] = T;
}

§8.3. Page directions. These are any of the 12 standard IF directions (N, NE, NW, S, SE, SW, E, W, U, D, IN, OUT), and are indexed with an number between 0 and 11 inclusive. These are so called because they refer to directions on the page on which the map will be plotted — the page direction 6 really means rightwards, not east, but it's still convenient to think of them that way.

For most Inform projects, page directions correspond to directions in the story file. But that needn't be true; some story files create exotic directions like "port" and "starboard". So the following array gives the correspondence of story directions to page directions; if the value is 12 or more, the direction won't be shown on the index at all. The initial setup is for the 12 standard story directions to correspond exactly to the 12 page directions.

If we want to show one of the exotic directions, we can use a sentence like:

Index map with starboard mapped as east.

When we read this, we associate direction object 13, say (the starboard direction) with page direction 6:

faux_instance *SpatialMap::mapped_as_if?Usage of SpatialMap::mapped_as_if:
Render HTML Map - §7.1.4(faux_instance *I, index_session *session) {
    faux_instance_set *faux_set = Indexing::get_set_of_instances(session);
    int i = I->direction_index;
    if (session->story_dir_to_page_dir[i] == i) return NULL;
    faux_instance *D;
    LOOP_OVER_FAUX_DIRECTIONS(faux_set, D)
        if (D->direction_index == session->story_dir_to_page_dir[i])
            return D;
    return NULL;
}

§8.4. This is therefore how we know whether a given story direction will actually be visible on the map we draw:

int SpatialMap::direction_is_mappable?Usage of SpatialMap::direction_is_mappable:
Render HTML Map - §1.3(int story_direction, index_session *session) {
    if ((story_direction < 0) || (story_direction >= MAX_DIRECTIONS)) return FALSE;
    int page_direction = session->story_dir_to_page_dir[story_direction];
    if (page_direction >= 12) return FALSE;
    return TRUE;
}

§8.5. Each page direction involves a given offset in lattice coordinates: for example, direction 6 (E) involves an offset of \((1, 0, 0)\), because a move in this map direction increases the \(x\)-coordinate by 1 and leaves \(y\) and \(z\) unchanged.

vector SpatialMap::direction_as_vector?Usage of SpatialMap::direction_as_vector:
§8.8, §8.9, §8.24, §22, §23, §24.1.4, §34, §38.1
Render HTML Map - §1.3.4
Render EPS Map - §1.2.1.6.1.2, §9(int story_direction, index_session *session) {
    if ((story_direction < 0) || (story_direction >= MAX_DIRECTIONS))
        return Zero_vector;
    int page_direction =
        (session)?(session->story_dir_to_page_dir[story_direction]):story_direction;
    switch(page_direction) {
        case 0: return N_vector;
        case 1: return NE_vector;
        case 2: return NW_vector;
        case 3: return S_vector;
        case 4: return SE_vector;
        case 5: return SW_vector;
        case 6: return E_vector;
        case 7: return W_vector;
        case 8: return U_vector;
        case 9: return D_vector;
    }
    return Zero_vector;
}

§8.6. Page directions all have opposites:

int SpatialMap::opposite?Usage of SpatialMap::opposite:
§8.2, §8.14.1, §8.14.1.1, §8.14.1.3, §8.14.1.4, §9, §26.2.3.2, §8.27
Render EPS Map - §1.2.1.6.1, §1.2.1.6.1.1(int story_direction, index_session *session) {
    if ((story_direction < 0) || (story_direction >= MAX_DIRECTIONS)) return 0;
    int page_direction =
        (session)?(session->story_dir_to_page_dir[story_direction]):story_direction;
    switch(page_direction) {
        case 0: return 3;  N — S
        case 1: return 5;  NE — SW
        case 2: return 4;  NW — SE
        case 3: return 0;  S — N
        case 4: return 2;  SE — NW
        case 5: return 1;  SW — NE
        case 6: return 7;  E — W
        case 7: return 6;  W — E
        case 8: return 9;  UP — DOWN
        case 9: return 8;  DOWN — UP
        case 10: return 11;  IN — OUT
        case 11: return 10;  OUT — IN
    }
    return 0;
}

§8.7. Lateral directions can be rotated clockwise (seen from above), if way is positive; or anticlockwise if it's negative.

int SpatialMap::rotate_direction?Usage of SpatialMap::rotate_direction:
§8.14.1(int story_direction, int way, index_session *session) {
    if ((story_direction < 0) || (story_direction >= MAX_DIRECTIONS)) return 0;
    int page_direction =
        (session)?(session->story_dir_to_page_dir[story_direction]):story_direction;
    int i, N = 1; if (way < 0) N = 7;
    for (i=1; i<=N; i++) {
        switch(page_direction) {
            case 0: page_direction = 1; break;  N — NE
            case 1: page_direction = 6; break;  NE — E
            case 2: page_direction = 0; break;  NW — N
            case 3: page_direction = 5; break;  S — SW
            case 4: page_direction = 3; break;  SE — S
            case 5: page_direction = 7; break;  SW — W
            case 6: page_direction = 4; break;  E — SE
            case 7: page_direction = 2; break;  W — NW
            default: page_direction = -1; break;
        }
    }
    return page_direction;
}

§8.8. Lateral directions are the ones which (a) are mappable, and (b) involve movement along the \(x-y\) grid lines.

int SpatialMap::direction_is_lateral?Usage of SpatialMap::direction_is_lateral:
Render HTML Map - §1.3.4(int story_direction, index_session *session) {
    return Geometry::vec_lateral(
            SpatialMap::direction_as_vector(story_direction, session));
}

§8.9. Along-lattice directions are those which (a) are mappable, and (b) involve movement along grid lines. Clearly lateral directions are along-lattice, but not necessarily vice versa.

int SpatialMap::direction_is_along_lattice?Usage of SpatialMap::direction_is_along_lattice:
§22, §23(int story_direction, index_session *session) {
    vector D = SpatialMap::direction_as_vector(story_direction, session);
    if (Geometry::vec_eq(D, Zero_vector)) return FALSE;
    return TRUE;
}

§8.10. For speed, we don't call these functions when looping through directions; we use these hard-wired macros instead.

define LOOP_OVER_DIRECTION_NUMBERS(i)
    for (i=0; i<12; i++)
define LOOP_OVER_STORY_DIRECTIONS(i)
    for (i=0; ((i<FauxInstances::no_directions(session)) && (i<MAX_DIRECTIONS)); i++)
define LOOP_OVER_LATTICE_DIRECTIONS(i)
    for (i=0; i<10; i++)
define LOOP_OVER_NONLATTICE_DIRECTIONS(i)
    for (i=10; i<12; i++)

§8.11. Strictly speaking the following is more to do with rendering than calculating, but it seems to belong here. In the HTML map, rooms have a five-by-five cell grid, and exits are plotted at positions on the boundary of that grid; for example, a line running in page direction 6 will be plotted with an icon at cell \((4, 2)\).

void SpatialMap::cell_position_for_direction?Usage of SpatialMap::cell_position_for_direction:
Render HTML Map - §1.3.4(int story_direction, int *mx, int *my,
    index_session *session) {
    *mx = 0; *my = 0;
    if ((story_direction < 0) || (story_direction >= MAX_DIRECTIONS)) return;
    int page_direction =
        (session)?(session->story_dir_to_page_dir[story_direction]):story_direction;
    switch(page_direction) {
        case 0: *mx = 2; *my = 0; break;
        case 1: *mx = 4; *my = 0; break;
        case 2: *mx = 0; *my = 0; break;
        case 3: *mx = 2; *my = 4; break;
        case 4: *mx = 4; *my = 4; break;
        case 5: *mx = 0; *my = 4; break;
        case 6: *mx = 4; *my = 2; break;
        case 7: *mx = 0; *my = 2; break;
        case 8: *mx = 1; *my = 0; break;
        case 9: *mx = 3; *my = 4; break;
        case 10: *mx = 4; *my = 3; break;
        case 11: *mx = 0; *my = 1; break;
    }
}

§8.12. And similarly:

char *SpatialMap::find_icon_label?Usage of SpatialMap::find_icon_label:
§34, §35.1, §36.1, §38.1
Render HTML Map - §11.2.1(int story_direction, index_session *session) {
    if ((story_direction < 0) || (story_direction >= MAX_DIRECTIONS)) return NULL;
    int page_direction =
        (session)?(session->story_dir_to_page_dir[story_direction]):story_direction;
    switch(page_direction) {
        case 0: return "n";
        case 1: return "ne";
        case 2: return "nw";
        case 3: return "s";
        case 4: return "se";
        case 5: return "sw";
        case 6: return "e";
        case 7: return "w";
        case 8: return "u";
        case 9: return "d";
        case 10: return "in";
        case 11: return "out";
    }
    return NULL;
}

char *SpatialMap::usual_Inform_direction_name?Usage of SpatialMap::usual_Inform_direction_name:
§8.2, §24.1.2(int story_direction, index_session *session) {
    if ((story_direction < 0) || (story_direction >= MAX_DIRECTIONS)) return "<none>";
    int page_direction =
        (session)?(session->story_dir_to_page_dir[story_direction]):story_direction;
    switch(page_direction) {
        case 0: return "north";
        case 1: return "northeast";
        case 2: return "northwest";
        case 3: return "south";
        case 4: return "southeast";
        case 5: return "southwest";
        case 6: return "east";
        case 7: return "west";
        case 8: return "up";
        case 9: return "down";
        case 10: return "inside";
        case 11: return "outside";
    }
    return "<none>";
}

§8.13. Map reading. The map is read in the first faux_instance by the SpatialMap::room_exit function below, which works out what room the exit leads to, perhaps via a door, which we take a note of if asked to do so.

faux_instance *SpatialMap::room_exit?Usage of SpatialMap::room_exit:
§10, §44
Render HTML Map - §1.3, §11.2.2
Render EPS Map - §1.2.1.6, §1.2.1.6.1(faux_instance *origin, int dir_num,
    faux_instance **via) {
    if (via) *via = NULL;
    if ((origin == NULL) || (FauxInstances::is_a_room(origin) == FALSE) ||
        (dir_num < 0) || (dir_num >= MAX_DIRECTIONS)) return NULL;
    faux_instance *ultimate_destination = NULL;
    faux_instance *immediate_destination = origin->fimd.exits[dir_num];
    if (immediate_destination) {
        if (FauxInstances::is_a_room(immediate_destination))
            ultimate_destination = immediate_destination;
        if (FauxInstances::is_a_door(immediate_destination)) {
            if (via) *via = immediate_destination;
            faux_instance *A = NULL, *B = NULL;
            FauxInstances::get_door_data(immediate_destination, &A, &B);
            if (A == origin) ultimate_destination = B;
            if (B == origin) ultimate_destination = A;
        }
    }
    return ultimate_destination;
}

faux_instance *SpatialMap::room_exit_as_indexed?Usage of SpatialMap::room_exit_as_indexed:
§8.14, §8.14.1, §8.14.1.1, §8.14.1.3, §8.14.1.4(faux_instance *origin, int dir_num,
    faux_instance **via, index_session *session) {
    for (int j=0; j<MAX_DIRECTIONS; j++) {
        if (session->story_dir_to_page_dir[j] == dir_num) {
            faux_instance *I = SpatialMap::room_exit(origin, j, via);
            if (I) return I;
        }
    }
    return NULL;
}

§8.14. In practice, the map itself isn't the ideal source of data. It's slow to keep checking all of that business with doors, and in any case the map is asymmetrical. Instead, we use the following. The tricky point here is that we want to record a sort of symmetric version of the map, which takes some adjudication.

As can be seen, step (1) runs in \(O(R)\) time, where \(R\) is the number of rooms.

(1) Create the spatial relationship arrays8.14 =

    faux_instance *R;
    LOOP_OVER_FAUX_ROOMS(faux_set, R) {
        int i;
        LOOP_OVER_LATTICE_DIRECTIONS(i) {
            faux_instance *T = SpatialMap::room_exit_as_indexed(R, i, NULL, session);
            if (T) Consider this Inform map connection for a spatial relationship8.14.1;
        }
    }

• This code is used in §8.

§8.14.1. We first find a spread of nearly opposite directions: for instance, if i is northeast, then back is SW, cw is W, cwcw is NW, ccw is S, ccwccw is SE. We also find the backstep, the room you get to if trying to go back from the destination in the back direction; which in a nicely arranged map will be the room you start from, but that can't be assumed.

The cases below don't exhaust the possibilities. We could be left with a 1-way connection blocked at the other end, in cases where no 2-way connection exists between rooms R and T. If so, we shrug and ignore it; this will be a situation where the connection doesn't help us. (It will still be plotted on the index page; we just won't use it in our choice of how to position the rooms.)

Consider this Inform map connection for a spatial relationship8.14.1 =

    int back = SpatialMap::opposite(i, session);
    int cw = SpatialMap::rotate_direction(back, 1, session);  clockwise one place
    int cwcw = SpatialMap::rotate_direction(cw, 1, session);  clockwise twice
    int ccw = SpatialMap::rotate_direction(back, -1, session);  counterclockwise once
    int ccwccw = SpatialMap::rotate_direction(ccw, -1, session);  counterclockwise twice

    faux_instance *backstep = SpatialMap::room_exit_as_indexed(T, back, NULL, session);

    Average out a pair of 2-way connections which each bend8.14.1.1;
    Turn a straightforward 2-way connection into a spatial relationship8.14.1.2;
    Average out a pair of 1-way connections which suggest a deformed 2-way connection8.14.1.3;
    Treat a 1-way connection as 2-way if there are no 2-way connections already8.14.1.4;

• This code is used in §8.14.

§8.14.1.1. What we're looking for here is a configuration like:

Alpha is east of Beta. Beta is south of Alpha.

This in fact sets up four connections: A is both S and W of B, and B is both N and E of A. A reasonable interpretation is that A lies SW of B, and so we form a single (symmetric) spatial relationship between them, in this direction. We check first clockwise, then counterclockwise.

Average out a pair of 2-way connections which each bend8.14.1.1 =

    if ((backstep == R) &&
        (cwcw >= 0) &&
        (SpatialMap::room_exit_as_indexed(T, cwcw, NULL, session) == R) &&
        (SpatialMap::room_exit_as_indexed(T, cw, NULL, session) == NULL) &&
        (SpatialMap::room_exit_as_indexed(R, SpatialMap::opposite(cwcw, session), NULL, session) == T) &&
        (SpatialMap::room_exit_as_indexed(T, SpatialMap::opposite(cw, session), NULL, session) == NULL)) {
        SpatialMap::form_spatial_relationship(R, SpatialMap::opposite(cw, session), T, session);
        continue;
    }
    if ((backstep == R) &&
        (ccwccw >= 0) &&
        (SpatialMap::room_exit_as_indexed(T, ccwccw, NULL, session) == R) &&
        (SpatialMap::room_exit_as_indexed(T, ccw, NULL, session) == NULL) &&
        (SpatialMap::room_exit_as_indexed(R, SpatialMap::opposite(ccwccw, session), NULL, session) == T) &&
        (SpatialMap::room_exit_as_indexed(T, SpatialMap::opposite(ccw, session), NULL, session) == NULL)) {
        SpatialMap::form_spatial_relationship(R, SpatialMap::opposite(ccw, session), T, session);
        continue;
    }

• This code is used in §8.14.1.

§8.14.1.2. The easiest case:

Turn a straightforward 2-way connection into a spatial relationship8.14.1.2 =

    if (backstep == R) {
        SpatialMap::form_spatial_relationship(R, i, T, session);
        continue;
    }

• This code is used in §8.14.1.

§8.14.1.3. Now perhaps A runs east to B, B runs south to A, but these are both 1-way connections. We'll regard this as being a single passageway running on average northeast from A to B:

Average out a pair of 1-way connections which suggest a deformed 2-way connection8.14.1.3 =

     a deformed 2-way connection made up of 1-way connections
    if ((cwcw >= 0) &&
        (SpatialMap::room_exit_as_indexed(T, cwcw, NULL, session) == R) &&
        (SpatialMap::room_exit_as_indexed(T, cw, NULL, session) == NULL) &&
        (SpatialMap::room_exit_as_indexed(R, SpatialMap::opposite(cwcw, session), NULL, session) == T) &&
        (SpatialMap::room_exit_as_indexed(T, SpatialMap::opposite(cw, session), NULL, session) == NULL)) {
        SpatialMap::form_spatial_relationship(R, SpatialMap::opposite(cw, session), T, session);
        continue;
    }
    if ((ccwccw >= 0) &&
        (SpatialMap::room_exit_as_indexed(T, ccwccw, NULL, session) == R) &&
        (SpatialMap::room_exit_as_indexed(T, ccw, NULL, session) == NULL) &&
        (SpatialMap::room_exit_as_indexed(R, SpatialMap::opposite(ccwccw, session), NULL, session) == T) &&
        (SpatialMap::room_exit_as_indexed(T, SpatialMap::opposite(ccw, session), NULL, session) == NULL)) {
        SpatialMap::form_spatial_relationship(R, SpatialMap::opposite(ccw, session), T, session);
        continue;
    }

• This code is used in §8.14.1.

§8.14.1.4. Most of the time, a 1-way connection is fine for mapping purposes; it establishes as good a spatial relationship as a 2-way one. But we suppress this if either (a) there are already 2-way connections between the rooms in general, or (b) the opposite connection exists but is to a different room (the case where backstep is not null here).

Treat a 1-way connection as 2-way if there are no 2-way connections already8.14.1.4 =

    int j, two_ways = 0;
    LOOP_OVER_LATTICE_DIRECTIONS(j)
        if ((SpatialMap::room_exit_as_indexed(T, j, NULL, session) == R) &&
            (SpatialMap::room_exit_as_indexed(R, SpatialMap::opposite(j, session), NULL, session) == T))
            two_ways++;
    if ((two_ways == 0) && (backstep == NULL))
        SpatialMap::form_spatial_relationship(R, i, T, session);

• This code is used in §8.14.1.

§9. The following ensures that SR links are always symmetric, in opposed pairs of directions:

void SpatialMap::form_spatial_relationship?Usage of SpatialMap::form_spatial_relationship:
§8.14.1.1, §8.14.1.2, §8.14.1.3, §8.14.1.4(faux_instance *R, int dir, faux_instance *T,
    index_session *session) {
    R->fimd.spatial_relationship[dir] = T;
    T->fimd.spatial_relationship[SpatialMap::opposite(dir, session)] = R;
}

§10. The spatial relationships arrays are read only by the following. Note that SpatialMap::read_smap suppresses relationships between different submaps (at least once the initial map components have been set up). This is done to make it easy and quick to cut up a submap into two sub-submaps; effectively severing any links between them. All we need do is move the rooms around from one submap to another.

SpatialMap::read_smap_cross has the ability to read relationships which cross submap boundaries, and will be needed when we place submaps on the global grid.

faux_instance *SpatialMap::read_smap?Usage of SpatialMap::read_smap:
§8.22, §18, §22, §23, §26, §28, §30, §33.1, §34, §35.1, §36, §37, §38, §8.27(faux_instance *from, int dir, index_session *session) {
    if (from == NULL) internal_error("tried to read smap at null room");
    session->calc.drognas_spent++;
    faux_instance *to = from->fimd.spatial_relationship[dir];
    if ((session->calc.partitioned_into_components) && (to) &&
        (from->fimd.submap != to->fimd.submap))
            to = NULL;
    return to;
}

faux_instance *SpatialMap::read_smap_cross?Usage of SpatialMap::read_smap_cross:
§43(faux_instance *from, int dir,
    index_session *session) {
    if (from == NULL) internal_error("tried to read smap at null room");
    session->calc.drognas_spent++;
    faux_instance *to = SpatialMap::room_exit(from, dir, NULL);
    return to;
}

§11. While we're at it:

faux_instance *SpatialMap::read_slock?Usage of SpatialMap::read_slock:
§8.22, §8.24, §26, §26.2.3.2, §28, §30, §37, §8.27(faux_instance *from, int dir,
    index_session *session) {
    if (from == NULL) internal_error("tried to read slock at null room");
    session->calc.drognas_spent++;
    return from->fimd.lock_exits[dir];
}

§12. Submap construction. Here's an empty submap, with no rooms.

connected_submap *SpatialMap::new_submap?Usage of SpatialMap::new_submap:
§8.22, §24.1.3(index_session *session) {
    connected_submap *sub = CREATE(connected_submap);
    Indexing::add_submap(session, sub);
    sub->bounds = Geometry::empty_cuboid();
    sub->first_room_in_submap = NULL;
    sub->last_room_in_submap = NULL;
    sub->incidence_cache = NULL;
    sub->incidence_cache_bounds = Geometry::empty_cuboid();
    sub->superpositions = 0;
    sub->for_session = session;
    sub->discarded = FALSE;
    return sub;
}

§13. This will loop through all of the submaps attached to a session, assuming that LS already holds the session's list:

define LOOP_OVER_SUBMAPS(sub)
    LOOP_OVER_LINKED_LIST(sub, connected_submap, LS)
        if (sub->discarded == FALSE)

§14. Doctrinally, a room is always in just one submap, except at the very beginning when we are forming the original components into submaps, when most of the rooms aren't yet in any submap. Doctrinally, too, if a room is in a submap, any room locked to it must always be in the same submap.

That makes the following function dangerous to use, since it doesn't guarantee either of those things. Use with care.

Because we keep a double-ended linked list to hold membership, adding a room to a submap takes constant time with respect to the number of rooms \(R\).

void SpatialMap::add_room_to_submap?Usage of SpatialMap::add_room_to_submap:
§8.19, §8.20, §8.22(faux_instance *R, connected_submap *sub) {
    if (sub->last_room_in_submap == NULL) {
        sub->last_room_in_submap = R;
        sub->first_room_in_submap = R;
    } else {
        sub->last_room_in_submap->next_room_in_submap = R;
        sub->last_room_in_submap = R;
    }
    R->fimd.submap = sub;
    R->next_room_in_submap = NULL;
    SpatialMap::add_room_to_cache(sub, Room_position(R), 1);
}

§15. Here is how we read from the incidence cache. Its purpose is to provide a constant running-time way to find out if a given position would collide with that of an existing room in the submap — something we could otherwise find out only by an \(O(R)\) search. If we had to maintain enormous submaps of rooms, we'd probably want a balanced geographical tree structure, of the sort used for collision detection in first-person shooters; but as it is, we have plenty of memory and relatively few possible location coordinate positions. So we simply keep a cubical array; though it may need to be resized as the rooms in the submap move around, which complicates things.

Anyway, this returns the number of rooms at position P within the submap.

int SpatialMap::occupied_in_submap?Usage of SpatialMap::occupied_in_submap:
§22, §8.28, §41(connected_submap *sub, vector P) {
    int i = Geometry::cuboid_index(P, sub->incidence_cache_bounds);
    if (i < 0) return 0;
    return sub->incidence_cache[i];
}

§16. The cache will be invalidated by any movement of a room, so the following function must be notified of any such:

void SpatialMap::move_room_within_submap?Usage of SpatialMap::move_room_within_submap:
§8.1(connected_submap *sub, vector O, vector P) {
    SpatialMap::add_room_to_cache(sub, O, -1);
    SpatialMap::add_room_to_cache(sub, P, 1);
}

§17. Here goes, then: the following increments the cached population value at P if m is 1, decrements it if \(-1\).

void SpatialMap::add_room_to_cache?Usage of SpatialMap::add_room_to_cache:
§14, §16(connected_submap *sub, vector P, int m) {
    if (Geometry::within_cuboid(P, sub->incidence_cache_bounds) == FALSE)
        Location P lies outside the current incidence cache17.1;

    int i = Geometry::cuboid_index(P, sub->incidence_cache_bounds);
    int t = sub->incidence_cache[i];
    if (t+m < 0) t = -m;
    sub->incidence_cache[i] = t+m;
    if (m == 1) sub->superpositions += 2*t;
    if (m == -1) sub->superpositions -= 2*(t-1);
}

§17.1. We make a new incidence cache which is more than large enough to contain both P and the existing one, and then copy the old one's contents into the new one before deallocating the old.

This looks as if it has cubic running time, but isn't really that bad, since the volume of the cuboid is probably about proportional to \(R\) rather than \(R^3\) (assuming rooms are fairly evenly distributed through space). Still, we ought to make sure it happens fairly seldom. We therefore expand the cuboid by a margin giving us always at least 20 more cells than we need horizontally, and 3 vertically. Since movements within submaps are modest and local, this means very few submaps need to expand more than twice at the most.

Location P lies outside the current incidence cache17.1 =

    cuboid old_cuboid = sub->incidence_cache_bounds;
    cuboid new_cuboid = old_cuboid;
    Geometry::thicken_cuboid(&new_cuboid, P, Geometry::vec(20, 20, 3));
    int extent = Geometry::cuboid_volume(new_cuboid);
    int *new_cache = Memory::calloc(extent, sizeof(int), MAP_INDEX_MREASON);
    int x, y, z;
    for (x = new_cuboid.corner0.x; x <= new_cuboid.corner1.x; x++)
        for (y = new_cuboid.corner0.y; y <= new_cuboid.corner1.y; y++)
            for (z = new_cuboid.corner0.z; z <= new_cuboid.corner1.z; z++) {
                int i = Geometry::cuboid_index(Geometry::vec(x,y,z), new_cuboid);
                new_cache[i] = 0;
            }
    int *old_cache = sub->incidence_cache;
    if (old_cache)
        for (x = old_cuboid.corner0.x; x <= old_cuboid.corner1.x; x++)
            for (y = old_cuboid.corner0.y; y <= old_cuboid.corner1.y; y++)
                for (z = old_cuboid.corner0.z; z <= old_cuboid.corner1.z; z++) {
                    int i = Geometry::cuboid_index(Geometry::vec(x,y,z), old_cuboid);
                    int t = old_cache[i];
                    if (t > 0) {
                        int j = Geometry::cuboid_index(Geometry::vec(x,y,z), new_cuboid);
                        new_cache[j] = t;
                    }
                }
    SpatialMap::free_incidence_cache(sub);
    sub->incidence_cache = new_cache;
    sub->incidence_cache_size = extent*((int) sizeof(int));
    sub->incidence_cache_bounds = new_cuboid;

• This code is used in §17.

§8.15. Here we throw away the cache, something which must otherwise only be done when the submap has no rooms...

void SpatialMap::free_incidence_cache?Usage of SpatialMap::free_incidence_cache:
§17.1, §8.16, §8.17(connected_submap *sub) {
    if (sub->incidence_cache == NULL) return;
    Memory::I7_free(sub->incidence_cache, MAP_INDEX_MREASON, sub->incidence_cache_size);
    sub->incidence_cache_bounds = Geometry::empty_cuboid();
    sub->incidence_cache = NULL;
}

§8.16. ...such as now:

void SpatialMap::empty_submap?Usage of SpatialMap::empty_submap:
§8.19(connected_submap *sub) {
    sub->first_room_in_submap = NULL;
    sub->last_room_in_submap = NULL;
    SpatialMap::free_incidence_cache(sub);
    sub->superpositions = 0;
}

§8.17. And finally:

void SpatialMap::destroy_submap?Usage of SpatialMap::destroy_submap:
§24.1.3(connected_submap *sub) {
    SpatialMap::free_incidence_cache(sub);
    sub->discarded = TRUE;
}

§8.18. Suppose we want to move all the rooms in a submap at once, and all by the same vector D. Then we can simply move the cache boundaries, too, and not have to change the contents of the cache at all.

void SpatialMap::move_component?Usage of SpatialMap::move_component:
§8.29.1.1, §8.29.1.2, §8.29.1.3, §8.29.1.3.1(connected_submap *sub, vector D) {
    faux_instance *R;
    LOOP_OVER_SUBMAP(R, sub)
        SpatialMap::set_room_position_breaking_cache(R,
            Geometry::vec_plus(Room_position(R), D));
    Geometry::cuboid_translate(&(sub->bounds), D);
    Geometry::cuboid_translate(&(sub->incidence_cache_bounds), D);
}

§8.19. The following functions will be used in order to divide an existing submap into two new ones, which we'll call Zone 1 and Zone 2, and then to merge them back again.

We start with each room in sub having a value of zone set to either Z1_number or Z2_number, the former meaning it is destined for Zone 1, the latter for Zone 2. It's assumed here that if two rooms are locked together then they have the same value of zone. With that done, we empty sub, since its rooms have all moved out.

void SpatialMap::create_submaps_from_zones?Usage of SpatialMap::create_submaps_from_zones:
§24.1.3(connected_submap *sub,
    int Z1_number, connected_submap *Zone1, int Z2_number, connected_submap *Zone2) {
    faux_instance_set *faux_set = Indexing::get_set_of_instances(sub->for_session);
    faux_instance *R;
    LOOP_OVER_FAUX_ROOMS(faux_set, R) {
        if (R->fimd.zone == Z1_number)
            SpatialMap::add_room_to_submap(R, Zone1);
        else if (R->fimd.zone == Z2_number)
            SpatialMap::add_room_to_submap(R, Zone2);
        R->fimd.zone = 0;
    }
    SpatialMap::empty_submap(sub);
}

§8.20. Convert membership of Zone 1 or 2 back into value of the zone number: the reverse process exactly.

void SpatialMap::create_zones_from_submaps?Usage of SpatialMap::create_zones_from_submaps:
§24.1.3(connected_submap *sub,
    int Z1_number, connected_submap *Zone1, int Z2_number, connected_submap *Zone2) {
    faux_instance_set *faux_set = Indexing::get_set_of_instances(sub->for_session);
    faux_instance *R;
    LOOP_OVER_FAUX_ROOMS(faux_set, R) {
        if (R->fimd.submap == Zone1) {
            SpatialMap::add_room_to_submap(R, sub);
            R->fimd.zone = Z1_number;
        }
        if (R->fimd.submap == Zone2) {
            SpatialMap::add_room_to_submap(R, sub);
            R->fimd.zone = Z2_number;
        }
    }
}

§8.21. Partitioning to component submaps. We can now go back to our strategy. The next task is to partition the map into components, that is, equivalence classes under the closure of the relation \(R\sim S\) if either \(R\) is locked to \(S\) or if there is a spatial relationship between \(R\) and \(S\).

We ensure that the first-created component is the one containing the benchmark room.

(2) Partition the set of rooms into component submaps8.21 =

    SpatialMap::create_map_component_around(FauxInstances::benchmark(session), session);
    faux_instance *R;
    LOOP_OVER_FAUX_ROOMS(faux_set, R)
        if (R->fimd.submap == NULL)
            SpatialMap::create_map_component_around(R, session);

• This code is used in §8.

§8.22. The following grows a component outwards from at, so that it also includes all rooms locked to at or with a SR to it. If at is currently not in a component, we start a new submap to hold it.

Note that SpatialMap::create_map_component_around has constant running time, i.e., it doesn't depend on \(R\), the number of rooms. It is called exactly once for each room, so phase (2) has running time \(O(R)\).

void SpatialMap::create_map_component_around?Usage of SpatialMap::create_map_component_around:
§8.21(faux_instance *at, index_session *session) {
    if (at->fimd.submap == NULL)
        SpatialMap::add_room_to_submap(at, SpatialMap::new_submap(session));

    int i;
    LOOP_OVER_LATTICE_DIRECTIONS(i) {
        faux_instance *locked_to = SpatialMap::read_slock(at, i, session);
        if ((locked_to) && (locked_to->fimd.submap != at->fimd.submap)) {
            SpatialMap::add_room_to_submap(locked_to, at->fimd.submap);
            SpatialMap::create_map_component_around(locked_to, session);
        }
        faux_instance *dest = SpatialMap::read_smap(at, i, session);
        if ((dest) && (dest->fimd.submap != at->fimd.submap)) {
            SpatialMap::add_room_to_submap(dest, at->fimd.submap);
            SpatialMap::create_map_component_around(dest, session);
        }
    }
}

§8.23. Movements of single rooms. Positions are just 3-vectors, so:

void SpatialMap::translate_room?Usage of SpatialMap::translate_room:
§24.1.4.1, §36.1, §38.1.1, §8.32(faux_instance *R, vector D) {
    SpatialMap::set_room_position(R, Geometry::vec_plus(Room_position(R), D));
}

void SpatialMap::move_room_to?Usage of SpatialMap::move_room_to:
§34, §8.28(faux_instance *R, vector P, index_session *session) {
    SpatialMap::set_room_position(R, P);
    SpatialMap::move_anything_locked_to(R, session);
}

§8.24. Synchronising movements of locked rooms. The next preliminary we need is the implementation of locking. As we've seen, the source text can instruct us to lock one room so that it lies perfectly placed with respect to another (in the sense that if there were an exit between them in that direction then it would have heat 0).

The following is for use after room R has been moved to a new grid position; it moves anything locked to R (and anything locked to that, and so on) to corresponding positions.

void SpatialMap::move_anything_locked_to?Usage of SpatialMap::move_anything_locked_to:
§8.23(faux_instance *R, index_session *session) {
    connected_submap *sub = R->fimd.submap;
    faux_instance *R2;
    LOOP_OVER_SUBMAP(R2, sub)
        R2->fimd.shifted = FALSE;
    SpatialMap::move_anything_locked_to_r(R, session);
}

void SpatialMap::move_anything_locked_to_r?Usage of SpatialMap::move_anything_locked_to_r:
§8.25(faux_instance *R, index_session *session) {
    if (R->fimd.shifted) return;
    R->fimd.shifted = TRUE;
    int i;
    LOOP_OVER_LATTICE_DIRECTIONS(i) {
        faux_instance *F = SpatialMap::read_slock(R, i, session);
        if (F) {
            vector D = SpatialMap::direction_as_vector(i, session);
            SpatialMap::set_room_position(F, Geometry::vec_plus(Room_position(R), D));
            SpatialMap::move_anything_locked_to_r(F, session);
        }
    }
}

§8.25. That allows us to define the initial state of placements in a submap. All rooms begin at (0,0,0), except that locking may offset a few of them slightly. This runs in \(O(R)\) time.

void SpatialMap::lock_positions_in_submap?Usage of SpatialMap::lock_positions_in_submap:
§8.26(connected_submap *sub, index_session *session) {
    faux_instance *R;
    LOOP_OVER_SUBMAP(R, sub)
        R->fimd.shifted = FALSE;
    LOOP_OVER_SUBMAP(R, sub)
        SpatialMap::move_anything_locked_to_r(R, session);
}

§8.26. Positioning within components. This is much more difficult. It's going to be a matter of minimising the badness of the configuration, but to talk about it it's convenient to have a better word than "badness". So the "heat" is a penalty score calculated at each map connection which keeps track of the badness of local geometric distortion; thus, lowering the temperature improves the geometry. We want to reduce the total amount of heat, ideally to absolute zero, but we also to want to avoid hot-spots.

The worst case for running time here is when the entire map is a single component; the loop over submaps doesn't therefore add to the running time.

(3) Position the rooms within each component8.26 =

    connected_submap *sub;
    int total_accuracy = 0;
    linked_list *LS = Indexing::get_list_of_submaps(session);
    LOOP_OVER_SUBMAPS(sub) {
        LOGIF(SPATIAL_MAP, "Laying out component %d\n", sub->allocation_id);
        SpatialMap::lock_positions_in_submap(sub, session);  \(O(R)\) running time
        SpatialMap::establish_natural_lengths(sub);  \(O(R)\) running time
        SpatialMap::position_submap(sub);
        total_accuracy += sub->heat;
        LOGIF(SPATIAL_MAP, "Component %d has final heat %d\n", sub->allocation_id, sub->heat);
    }
    LOGIF(SPATIAL_MAP, "\nAll components laid out: total heat %d\n\n", total_accuracy);

    LOGIF(SPATIAL_MAP, "Cost: cutpoint choosing %d drognas\n", session->calc.cutpoint_spending);
    LOGIF(SPATIAL_MAP, "Cost: dividing %d drognas\n", session->calc.division_spending);
    LOGIF(SPATIAL_MAP, "Cost: sliding %d drognas\n", session->calc.slide_spending);
    LOGIF(SPATIAL_MAP, "Cost: cooling %d drognas\n", session->calc.cooling_spending);
    LOGIF(SPATIAL_MAP, "Cost: quenching %d drognas\n", session->calc.quenching_spending);
    LOGIF(SPATIAL_MAP, "Cost: diffusion %d drognas\n", session->calc.diffusion_spending);
    LOGIF(SPATIAL_MAP, "Cost: radiation %d drognas\n", session->calc.radiation_spending);
    LOGIF(SPATIAL_MAP, "Cost: explosion %d drognas\n\n", session->calc.explosion_spending);

• This code is used in §8.

§18. Every spatial relationship has a "length", which is a positive integer. This is our preferred amount of stretch when laying out the rooms; a length of 1 means one grid increment, and that's our preference if we can have it. Initially, all SRs have length 1.

void SpatialMap::establish_natural_lengths?Usage of SpatialMap::establish_natural_lengths:
§8.26(connected_submap *sub) {
    faux_instance *R;
    LOOP_OVER_SUBMAP(R, sub) {
        int i;
        LOOP_OVER_LATTICE_DIRECTIONS(i) {
            if (SpatialMap::read_smap(R, i, sub->for_session))
                R->fimd.exit_lengths[i] = 1;
            else
                R->fimd.exit_lengths[i] = -1;
        }
    }
}

§19. Heat. Before we can get any further with (3), we need to be able to measure heat. For a submap, it's the sum of its room heats, plus additional heat (and a lot of it) for each pair of rooms occupying the same grid location. We also refresh the cached value of the smallest squarely oriented cuboid which contains the component.

The mapmaker behaves slowly if the collision heat penalty is low enough that large amounts of heat soaked up from ordinary exits can ever exceed it. On the other hand, for very large maps with horrible tangles the total number of collisions can be enormous, and quite high heats are observed; I've seen temperatures over 165,000,000, so temperatures of 1,000,000,000 are not at all out of the question. So we will be careful, just on the safe side, not to overflow a single int; we'll cap temperatures except to add a tiny extra heat so that there is still a slight incentive to remove collisions even in submaps at this unthinkably hot level.

The FHM magazine website informs me that the current (2010) maximal value of temperature is CHERYL_COLE, but I think I'll call it FUSION_POINT.

define OVERLYING_HEAT           20
define COLLISION_HEAT        50000
define FUSION_POINT     1000000000

int SpatialMap::heat_sum?Usage of SpatialMap::heat_sum:
§20, §43, §43.1(int h1, int h2) {
    int h = h1+h2;
    if (h > FUSION_POINT) return FUSION_POINT;
    return h;
}

§20. Finding the heat of a submap runs in \(O(S)\) time, where \(S\) is the number of rooms in the submap; this is the point of having the incidence cache, without which it would be \(O(S^2)\). (Even so, we will try to make \(S\) a lot smaller than \(R\).)

int SpatialMap::find_submap_heat?Usage of SpatialMap::find_submap_heat:
§24, §24.1, §24.1.1, §24.1.4, §32, §35, §35.1, §36, §36.1, §38, §38.1.1, §8.28(connected_submap *sub) {
    int heat = 0;
    sub->bounds = Geometry::empty_cuboid();
    faux_instance *R;
    LOOP_OVER_SUBMAP(R, sub) {
        heat = SpatialMap::heat_sum(heat, SpatialMap::find_room_heat(R, sub->for_session));
        Geometry::adjust_cuboid(&(sub->bounds), Room_position(R));
    }

    int collisions = sub->superpositions;
    while (collisions >= 1000) {
        heat = SpatialMap::heat_sum(heat, 1000*COLLISION_HEAT);
        collisions -= 1000;
    }
    heat = SpatialMap::heat_sum(heat, collisions*COLLISION_HEAT);
    if (heat == FUSION_POINT) heat = FUSION_POINT + sub->superpositions;
    sub->heat = heat;
    return heat;
}

§21. The total heat for a room is in turn the sum of its exit heats. This runs in constant time.

int SpatialMap::find_room_heat?Usage of SpatialMap::find_room_heat:
§20(faux_instance *R, index_session *session) {
    int i, h = 0;
    LOOP_OVER_LATTICE_DIRECTIONS(i) h += SpatialMap::find_exit_heat(R, i, session);
    return h;
}

§22. So now we come to it: measuring the heat of an exit, which is a matter of how much geometric distortion it has in the current layout. This is based primarily on the angular divergence in direction between the known exit direction and the grid direction, and only secondarily on distance anomalies, because when the user typed "the Field is east of the River" no particular distance was implied. As with Harry Beck's London Underground map (1931), we may be constrained to use only about eight possible angles but nevertheless care more about angle than length.

Note that an exit in the lattice (i.e., not IN or OUT) which joins two different rooms can only have heat 0 if the destination room lies exactly at the optimal grid offset from the origin room. (In the sense that you'd expect the room north from \((0,0,0)\) to be at \((0,1,0)\), and so on.) A component therefore has a total heat of 0 if and only if it has been aligned perfectly on a grid such that all exits are optimal.

This too runs in constant time.

define ANGULAR_MULTIPLIER 50

int SpatialMap::find_exit_heat?Usage of SpatialMap::find_exit_heat:
§21, §33.1, §35, §37(faux_instance *from, int exit, index_session *session) {
    session->calc.drognas_spent++;

    faux_instance *to = SpatialMap::read_smap(from, exit, session);
    if (to == NULL) return 0;  if there's no exit this way, there's no heat

    if (from == to) return 0;  an exit from a room to itself doesn't show on the map

    if (SpatialMap::direction_is_along_lattice(exit, session) == FALSE) return 0;  IN, OUT generate no heat

    vector D = Geometry::vec_minus(Room_position(to), Room_position(from));

    if (Geometry::vec_eq(D, Zero_vector)) return COLLISION_HEAT;  the two rooms have collided!

    vector E = SpatialMap::direction_as_vector(exit, session);
    int distance_distortion = Geometry::vec_length_squared(Geometry::vec_minus(E, D));
    if (distance_distortion == 0) return 0;  perfect placement
    int angular_distortion = (int) (ANGULAR_MULTIPLIER*Geometry::vec_angular_separation(E, D));
    int overlying_penalty = 0;
    if ((angular_distortion == 0) && (Geometry::vec_eq(E, Zero_vector) == FALSE)) {
        vector P = Room_position(from);
        int n = 1;
        P = Geometry::vec_plus(P, E);
        while ((n++ < 20) && (Geometry::vec_eq(P, Room_position(to)) == FALSE)) {
            if (SpatialMap::occupied_in_submap(from->fimd.submap, P) > 0)
                overlying_penalty += OVERLYING_HEAT;
            P = Geometry::vec_plus(P, E);
        }
    }
    return angular_distortion + distance_distortion + overlying_penalty;
}

§23. The following simply tests whether a link is correctly aligned, in that the destination room lies along a multiple of the exit vector from the origin. In effect, it tests whether angular_distortion is zero.

int SpatialMap::exit_aligned?Usage of SpatialMap::exit_aligned:
§38, §38.1(faux_instance *from, int exit, index_session *session) {
    session->calc.drognas_spent++;

    faux_instance *to = SpatialMap::read_smap(from, exit, session);
    if (to == NULL) return TRUE;  at any rate, not misaligned
    if (from == to) return TRUE;  ditto
    if (SpatialMap::direction_is_along_lattice(exit, session) == FALSE) return TRUE;  IN, OUT are always aligned

    vector D = Geometry::vec_minus(Room_position(to), Room_position(from));
    if (Geometry::vec_eq(D, Zero_vector)) return TRUE;  bad, but not for alignment reasons

    vector E = SpatialMap::direction_as_vector(exit, session);
    int angular_distortion = (int) (ANGULAR_MULTIPLIER*Geometry::vec_angular_separation(E, D));
    if (angular_distortion == 0) return TRUE;
    return FALSE;
}

§24. Subdividing our submap. Any remotely good algorithm for this task will have a dangerous running time if let loose on the entire map, and in any case, the entirety may have such a complex layout that it defeats our tactics. So we need a divide-and-rule method; one which cuts the map into two pieces, positions each piece, and then glues them back together again.

We will eventually use five tactics: cooling, quenching, diffusion, radiation and explosion. Cooling is quick and useful, so we'll try that first even before looking for subdivisions.

int unique_Z_number = 1;

void SpatialMap::position_submap?Usage of SpatialMap::position_submap:
§8.26, §24.1.3(connected_submap *sub) {
    index_session *session = sub->for_session;
    int initial_heat = SpatialMap::find_submap_heat(sub),
        initial_spending = session->calc.drognas_spent;
    LOGIF(SPATIAL_MAP, "\nPOSITIONING submap %d: initial heat %d",
        sub->allocation_id, sub->heat);
    if (sub->heat == 0) LOGIF(SPATIAL_MAP, ": nothing to do");
    if (Log::aspect_switched_on(SPATIAL_MAP_DA)) {
        faux_instance *R; int n = 0;
        LOOP_OVER_SUBMAP(R, sub) {
            if ((n++) % 8 == 0) LOG("\n    ");
            LOG(" %S", FauxInstances::get_name(R));
        }
        LOG("\n");
    }
    if (sub->heat > 0) {
        SpatialMap::cool_submap(sub);
        SpatialMap::find_submap_heat(sub);
        if (sub->heat > 0) {
            Attempt to divide the current submap in two24.1;
            SpatialMap::find_submap_heat(sub);
        }
        LOGIF(SPATIAL_MAP, "\nPOSITIONING submap %d done: cooled by %d to %d "
            "at cost of %d drognas\n\n",
            sub->allocation_id, initial_heat - sub->heat, sub->heat,
            session->calc.drognas_spent - initial_spending);
    }
}

§24.1. We will look for a way to divide the rooms up into two subsets, allocating each subset a unique zone number. (We must remember that all of this code is running recursively.)

There are three cases: sometimes the SpatialMap::work_out_optimal_cutpoint function recommends cutting a single spatial relationship, from div_F1 to div_T1, and sometimes it recommends cutting a pair. Then again, sometimes it finds no good cutpoint.

Attempt to divide the current submap in two24.1 =

    int Z1_number = unique_Z_number++, Z2_number = unique_Z_number++;
    faux_instance *div_F1 = NULL, *div_T1 = NULL; int div_dir1 = -1;
    faux_instance *div_F2 = NULL, *div_T2 = NULL; int div_dir2 = -1;
    int initial_spending = session->calc.drognas_spent;
    int found = SpatialMap::work_out_optimal_cutpoint(sub, &div_F1, &div_T1, &div_dir1,
        &div_F2, &div_T2, &div_dir2);
    session->calc.cutpoint_spending += session->calc.drognas_spent - initial_spending;
    if (found) {
        Set the zone numbers throughout the two soon-to-be zones24.1.2;
        Divide the submap into zones, recurse to position those, then merge back24.1.3;
        Slide the two former zones together along the F1-to-T1 line, minimising heat24.1.4;
        if (SpatialMap::find_submap_heat(sub) > 0) SpatialMap::radiate_submap(sub);
    } else
        Position this indivisible component24.1.1;

• This code is used in §24.

§24.1.1. When we can't divide, we use our remaining three tactics, stopping if the submap should reach absolute zero:

Position this indivisible component24.1.1 =

    if (SpatialMap::find_submap_heat(sub) > 0) {
        SpatialMap::quench_submap(sub, NULL, NULL);
        if (SpatialMap::find_submap_heat(sub) > 0) {
            SpatialMap::diffuse_submap(sub);
            if (SpatialMap::find_submap_heat(sub) > 0) {
                SpatialMap::quench_submap(sub, NULL, NULL);
                if (SpatialMap::find_submap_heat(sub) > 0) {
                    SpatialMap::radiate_submap(sub);
                    if (SpatialMap::find_submap_heat(sub) >= COLLISION_HEAT)
                        SpatialMap::explode_submap(sub);
                }
            }
        }
    }

• This code is used in §24.1.

§24.1.2. Supposing we can divide, though, we need to set zone numbers throughout the submap, and the procedure is different depending on whether we're dividing at one relationship F1-to-T1 or at two, F1-to-T1 and F2-to-T2.

Set the zone numbers throughout the two soon-to-be zones24.1.2 =

    int Z1_count = 0, Z2_count = 0;
    if (div_F2) {
        int predivision_spending = session->calc.drognas_spent;
        SpatialMap::divide_into_zones_twocut(div_F1, div_T1, div_F2, div_T2,
            Z1_number, Z2_number, session);
        faux_instance *R;
        LOOP_OVER_SUBMAP(R, sub) {
            if (R->fimd.zone == Z1_number) Z1_count++;
            if (R->fimd.zone == Z2_number) Z2_count++;
        }
        LOGIF(SPATIAL_MAP, "Making a double cut: %S %s to %S and %S %s to %S at cost %d\n",
            FauxInstances::get_name(div_F1),
            SpatialMap::usual_Inform_direction_name(div_dir1, session),
            FauxInstances::get_name(div_T1),
            FauxInstances::get_name(div_F2),
            SpatialMap::usual_Inform_direction_name(div_dir2, session),
            FauxInstances::get_name(div_T2),
            session->calc.drognas_spent - predivision_spending);
        session->calc.division_spending += session->calc.drognas_spent - predivision_spending;
    } else {
        int predivision_spending = session->calc.drognas_spent;
        SpatialMap::divide_into_zones_onecut(sub, div_F1, div_T1,
            &Z1_count, &Z2_count, Z1_number, Z2_number, session);
        LOGIF(SPATIAL_MAP, "Making a single cut: %S %s to %S at cost %d\n",
            FauxInstances::get_name(div_F1),
            SpatialMap::usual_Inform_direction_name(div_dir1, session),
            FauxInstances::get_name(div_T1),
            session->calc.drognas_spent - predivision_spending);
        session->calc.division_spending += session->calc.drognas_spent - predivision_spending;
    }
    LOGIF(SPATIAL_MAP, "This produces two zones of sizes %d and %d\n",
        Z1_count, Z2_count);

• This code is used in §24.1.

§24.1.3. Divide the submap into zones, recurse to position those, then merge back24.1.3 =

    connected_submap *Zone1 = SpatialMap::new_submap(sub->for_session);
    connected_submap *Zone2 = SpatialMap::new_submap(sub->for_session);
    SpatialMap::create_submaps_from_zones(sub, Z1_number, Zone1, Z2_number, Zone2);
    LOGIF(SPATIAL_MAP, "Zone 1 becomes submap %d; zone 2 becomes submap %d\n",
        Zone1->allocation_id, Zone2->allocation_id);
    LOG_INDENT;
    SpatialMap::position_submap(Zone1);
    SpatialMap::position_submap(Zone2);
    LOG_OUTDENT;
    SpatialMap::create_zones_from_submaps(sub, Z1_number, Zone1, Z2_number, Zone2);
    LOGIF(SPATIAL_MAP, "Destroying submaps %d and %d\n",
        Zone1->allocation_id, Zone2->allocation_id);
    SpatialMap::destroy_submap(Zone1);
    SpatialMap::destroy_submap(Zone2);

• This code is used in §24.1.

§24.1.4. The zone-1 rooms are now correctly placed with respect to each other, and vice versa, but we might have a horrendous breakage where the two sets of rooms meet. We need to rejoin them, and we do this by stretching the F1-to-T1 line segment to that length which minimises the total heat of the submap. For a single cut, this is clearly the smallest length such that there's no collision between old zone-1 and old zone-2 rooms.

The worst case is a configuration like so:

X is west of Y. X1 is northeast of X. X2 is northeast of X. Y1 is northwest of Y. Y2 is northwest of Y1.

We've cut between X and Y. To give clearance so that X2 and Y2 do not collide, the new length X to Y needs to be 5.

However, it's computationally too expensive to check every possible length as high as that: it would run in \(O(S^2)\) time, and we must remember that this is the divide-and-rule code running on even the largest submaps, so that this is effectively an \(O(R^2)\) algorithm. On a 300-room example source text (the entire London Underground map, zones 1 to 7) this results in sliding taking up about 80 percent of our time, which is unacceptable.

We therefore cap the length once we have reduced below the collision penalty.

define CAP_ON_SLIDE_LENGTHS 10

Slide the two former zones together along the F1-to-T1 line, minimising heat24.1.4 =

    int preslide_spending = session->calc.drognas_spent;
    vector Axis = SpatialMap::direction_as_vector(div_dir1, session);

    int worst_case_length = 0;
    faux_instance *R;
    LOOP_OVER_SUBMAP(R, sub) worst_case_length++;
    worst_case_length--;

    int L, coolest_L = 1, coolest_temperature = -1;
    for (L = 1; L <= worst_case_length; L++) {
        SpatialMap::save_component_positions(sub);
        Displace zone 2 relative to zone 124.1.4.1;
        int h = SpatialMap::find_submap_heat(sub);
        if ((h < coolest_temperature) || (coolest_temperature == -1)) {
            coolest_temperature = h;
            coolest_L = L;
        }
        SpatialMap::restore_component_positions(sub);
        if ((coolest_temperature >= 0) && (coolest_temperature < COLLISION_HEAT) &&
            (L == CAP_ON_SLIDE_LENGTHS))
            break;
    }
    LOGIF(SPATIAL_MAP, "Optimal axis length for cut-exit is %d (heat %d), at cost %d.\n",
        coolest_L, coolest_temperature, session->calc.drognas_spent - preslide_spending);
    session->calc.slide_spending += session->calc.drognas_spent - preslide_spending;
    L = coolest_L;
    Displace zone 2 relative to zone 124.1.4.1;

• This code is used in §24.1.

§24.1.4.1. Here we slide rooms which came from Zone 2 so that they retain their positions with respect to each other, and therefore to T1, and so that T1 is placed correctly aligned along the axis from F1 with length L.

Because there can never be locks across zone boundaries, this process can't break a lock between two rooms.

Displace zone 2 relative to zone 124.1.4.1 =

    div_F1->fimd.exit_lengths[div_dir1] = L;
    vector D = Geometry::vec_plus(
        Geometry::vec_scale(L, Axis),
        Geometry::vec_minus(Room_position(div_F1), Room_position(div_T1)));
    faux_instance *Z2;
    LOOP_OVER_SUBMAP(Z2, sub)
        if (Z2->fimd.zone == Z2_number)
            SpatialMap::translate_room(Z2, D);

• This code is used in §24.1.4 (twice).

§25. Finding how to divide. That completes the logic for how we divide and conquer the submaps, except, of course, that some of the critical steps weren't spelled out. We do that now. First, the code to find good cutpoint(s): map connection(s) which, if removed, would divide the submap efficiently. We prefer single cuts if possible, but can live with double cuts; we want as evenly spread a division as possible. (The "spread" is the difference in room count of the larger zone compared to the smaller zone; we want to minimise this.)

Here is the basic idea. We will recursively spread a generation count out into the submap, with the first room (first below) belonging to generation 1. We'll use the zone field to store this, since it's an integer attached to each room which isn't yet in use. SpatialMap::assign_generation_count is recursively called so that it visits each room exactly once, and increases the generation on each call. Thus a line of rooms from first would have generations 1, 2, 3, ... When SpatialMap::assign_generation_count finds a connection from its current position to a room with a lower generation, we say that there's a "contact".

What makes the function so effective is that it returns a great deal of data about the high-spots of the history after it was called. The mechanism for this, though, is that the caller has to set up a pile of arrays, and then pass pointers to SpatialMap::assign_generation_count; on its exit, the arrays are then populated with answers.

This calculation runs in \(O(S)\) time, where \(S\) is the number of rooms in the submap. It's guaranteed to find the optimal single cut, if one exists; it's not guaranteed to find the optimal double cut — I suspect this is not possible in \(O(S)\) running time, though possibly in \(O(S\log S)\) — but in any case we have heuristic reasons why we don't always want the optimal double cut. What can be said is that we at least try to find good spreads, usually succeed in practice, and are guaranteed to find at least one double cut if any exists.

The guarantees are void in a small number of cases where locks have been applied: for instance, if the entire submap is locked together, nothing can ever be cut. Should that happen, the user will find that the map-maker may run slowly; it's his own fault.

define EXPLORATION_RECORDS 3  how much we keep track of
define BEST_ONECUT_ER 0  what's the best-known single link to cut?
define BEST_PARALLEL_TWOCUT_ER 1  what's the best-known pair of links equal in direction?
define BEST_TWOCUT_ER 2  and in general?
define CLIPBOARD_SIZE 3  a term to be explained below

int SpatialMap::work_out_optimal_cutpoint?Usage of SpatialMap::work_out_optimal_cutpoint:
§24.1(connected_submap *sub,
    faux_instance **from, faux_instance **to, int *way,
    faux_instance **from2, faux_instance **to2, int *way2) {
    index_session *session = sub->for_session;
    faux_instance *first = NULL; int size = 0;

    Find the size of and first room in the submap, and give all rooms generation 025.1;
    first->fimd.zone = 1;

    int best_spread[EXPLORATION_RECORDS];
    faux_instance *best_from1[EXPLORATION_RECORDS], *best_to1[EXPLORATION_RECORDS];
    int best_dir1[EXPLORATION_RECORDS];
    faux_instance *best_from2[EXPLORATION_RECORDS], *best_to2[EXPLORATION_RECORDS];
    int best_dir2[EXPLORATION_RECORDS];

    int outer_contact_generation[CLIPBOARD_SIZE], outer_contact_dir[CLIPBOARD_SIZE];
    faux_instance *outer_contact_from[CLIPBOARD_SIZE], *outer_contact_to[CLIPBOARD_SIZE];
    Initialise all this cutpoint search workspace25.2;

    SpatialMap::assign_generation_count(first, NULL, size, best_spread,
        best_from1, best_to1, best_dir1,
        best_from2, best_to2, best_dir2,
        outer_contact_generation, outer_contact_from, outer_contact_to, outer_contact_dir, session);

    Look at the results and return connections to cut, if any look good enough25.3;
    return FALSE;
}

§25.1. Find the size of and first room in the submap, and give all rooms generation 025.1 =

    faux_instance *R;
    LOOP_OVER_SUBMAP(R, sub) {
        R->fimd.zone = 0;  i.e., not yet given a generation
        size++;
        if (first == NULL) first = R;
    }
    if (size == 0) return FALSE;

• This code is used in §25.

§25.2. See below.

Initialise all this cutpoint search workspace25.2 =

    int i;
    for (i = 0; i < CLIPBOARD_SIZE; i++) {
        outer_contact_generation[i] = -1;
        outer_contact_from[i] = NULL; outer_contact_to[i] = NULL; outer_contact_dir[i] = -1;
    }
    for (i = 0; i < EXPLORATION_RECORDS; i++) {
        best_spread[i] = size+1;  an impossibly high value
        best_from1[i] = NULL; best_to1[i] = NULL; best_dir1[i] = -1;
        best_from2[i] = NULL; best_to2[i] = NULL; best_dir2[i] = -1;
    }