Highway roadmaps often include a mileage chart. The concept is simple: scan down the rows until you find your starting city, then scan across the columns to find your destination. The cell where these two intersect holds the number of miles from start to finish.
A similar chart can be constructed for the starmaze with one difference: in the starmaze, the distance from pattern A to pattern B is not necessarily the same as the distance from B to A, so we need the whole matrix, not just a triangular half.
There's just one problem. With 512 patterns in the starmaze, the total number of cells is 5122 - over a quarter of a million! A chart that big would fill a wall. It occurred to me, however, that if each number was converted to a single colored pixel the resulting block would fit easily even on a small computer screen. What would such a thing look like? What secrets might it reveal?
To find out I assigned a unique color for each possible distance, from 1 (for neighboring patterns) to 11 (the length of the solution path). I didn't bother with distances of 12 or 13 because they are too few and far between. And I used black for cells which start in the pit or end in the source to indicate that "you can't get there from here." I then plotted the whole thing as a 512 by 512 square.
The result is a starmaze distance map. I soon discovered that distance maps are beautiful and full of surprises. Showing all 11 possible distances at once produces a big turquoise-colored square with echoes of a checkerboard:
Looking at this map is like looking at the surface of an ocean. It's beautiful but overwhelming. You can sense vast complexities beneath the waves but cannot see them clearly.
Fortunately, my distance map is interactive. I can choose to display any combination of distances. When you filter the map to show only pairs at certain distances intriguing structures rise to the surface. The following map shows only pairs that are 1, 10, or 11 steps apart:
Again, you can see faint traces of checkerboards at various scales, four quadrants of 256 by 256, quadrants of 128 within each of those, smaller 32 by 32 squares within those, and some structures which are 8 by 8. These are the recursive rhythms of binary numbers made visible.
Another thing to notice is the symmetry. A highway map is symmetrical about the the diagonal line from upper left to lower right. But, as mentioned above, this is not the case for these maps, since the distance from A to B and from B to A often differ. In fact if the distance from A to B is 1, then the distance from B to A is guaranteed not to be 1 because all the passages in the starmaze are one-way.
There is, however, symmetry about the other diagonal line from upper right to lower left. This occurs because the distance from A to B does match the distance from the inverse of B to the inverse of A. Every path from A to B has a mirror image path from inverse B to inverse A, so the distances come out the same. And since the patterns are plotted in the standard order, the inverse of pattern A is at position (511 - A). As a result, this "law of mirror image paths" appears in the map as a diagonal reflection.
By choosing different combinations of distances, many different beautiful maps can be plotted. Here is another example, showing pairs which are either 1 or 7 steps apart:
Obviously, there are more pixels of some colors than of others. The average (mean) distance from one room to another within the maze is 5.775951, so most rooms are 5 or 6 steps apart and the chances that any two rooms are neighbors is slight. The following table makes this clear:
Notice that the number of neighbors, 2304, is also the number of edges in a 9-cube. Every pair of neighboring rooms is connected by a unique edge and every edge connects a unique pair of neighbors.
About 1 out of every 8 room pairs are 4 steps apart. Since the shortest path from a room back to itself is almost always 4, the distance 4 map includes a diagonal line from upper left to lower right:
If we zoom in a bit, you can see the wealth of repeating features that fill all of these distance maps. The following image is from the upper left corner of the distance 4 map:
Notice the tiny single-pixel break in the diagonal line about 16 pixels in. This is the starting room, one of only four exceptions to the rule that the shortest distance from a room back to itself is 4.
The crossbars on this line occur every 16 pixels, starting at pixel 8, in the first and last quarters of the diagonal line. The first crossbar occurs because the distances from 4 to 11, 5 to 10, 6 to 9, and 7 to 8 are all 4 as are the reverse distances (11 to 4, 10 to 5, etc.). This same curious set of relationships occurs again 16 pixels later (23 to 24, 22 to 25, etc.) when the center cell in all these patterns is flipped on, and again for every crossbar on the line.
Other similar sets of recurring relationships form coherent shapes which appear again and again in these maps. I call these shapes "constellations." The little 8 by 8 square interference pattern which appears along the left edge starting about 16 pixels down is one common constellation. You can see where this particular type of constellation comes from if you look at maps consisting of all the odd layers or all the even layers.
The following image is a 400% magnification of the map of even distances (2, 4, 6, 8, and 10):
This striking effect arises because of the starmaze's property of parity. All paths in the starmaze alternate between sun rooms and moon rooms. One consequence of this is that the distance from any sun room to any other sun room, or between any moon room and any other moon room is always an even number.
This map, then, shows pixels for all room pairs of the same type. The first row of pixels represent distances from pattern 1, a sun room. Because of parity, colored pixels in this row will only appear under columns corresponding to other sun rooms: 3 and 4, 6, 9, 11 and 12, 14, etc. The distribution of sun and moon rooms has a distinctive rhythm, alternation with periodic sequential pairs, that is made visible in this map.
Grand Tour MapsDistance maps say as much about the order of the rooms as they do about the relationships between those rooms. All the maps so far have been in "standard order" with the patterns arranged according to their room numbers. But just as a highway distance chart can list its cities in any order, so we can list our rooms in any order.
One ordering that yields interesting insights into the properties of the starmaze is the grand tour order. The grand tour is a special path through the maze that starts and ends at the pit, moving always to adjacent rooms and visiting each room exactly once.
Here is the Grand Tour Order map for all distances:
The first thing to notice is the black vertical line extending down the middle of the map. This column corresponds to pattern 511, the source, which appears in the middle of the grand tour instead of at the end as it does in the standard order. Since you can never return to the source the distance from any room to the source is not defined.
As with the standard order, looking at all distances at once is like looking at the surface of an ocean. Here, though, you can more clearly see some major diagonal lines in the structure. As before, lets bring this into focus by looking at only distances 1, 10, and 11:
If you look closely at the distance 10 and 11 pixels, you may notice that, unlike the standard order, this map is no longer symmetrical about the diagonal from lower left to upper right. The reason is that, in grand tour order, the inverse of room A is no longer guaranteed to be at position (511 - A).
The yellow distance 1 pixels show a very striking and regular pattern, like a ruler with crossbars extending down the diagonal from upper left to lower right. At first glance this may seem to lie exactly on that diagonal, but this is not the case. Instead, the diagonal in this map is slightly offset, with a yellow pixel showing at every intersection of A and (A + 1).
This makes sense because in grand tour order we move from neighbor to neighbor. So the next room in that order is always one step away.
The reason for the crossbars is a little less obvious. It has to do with the way the grand tour algorithm works its way through the nine-dimensional starmaze hypercube. The algorithm visits all 8 corners of a cube, jumps up to the tesseract enclosing that cube, works its way around that, jumps up to the 5-cube enclosing that tesseract, etc. Each time it jumps to a new level, half of the rooms it visits are only 1 step away from rooms on the previous level. And the other half of the rooms are only 1 step away from rooms on the next level. This "Echo" of previous and subsequent levels manifests itself as the crossbars appearing on each side of the diagonal.
Each level has twice as many rooms as the last, which is why the length of the crossbars keeps increasing as the tour continues. The recursive nature of the algorithm reveals itself in the recursive way in which the length of the crossbars rise and fall (1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, etc.) And because only half the rooms are 1 step away on each side of the main diagonal the crossbars appear as dotted lines in a distance 1 map.
It turns out, though, that all the crossbar rooms that are not 1 step away are some other odd number of steps away. (This is because of parity. Neighboring cells have always have opposite parity and rooms of opposite parity are always an odd number of steps apart.) So, in a map with all the odd distances present, the dotted lines are filled in and the crossbars become perfectly regular.
The following map shows this perfect crossbar in more detail. The map is magnified to show only the small square outline in the upper left corner of the previous map. All the odd distances are shown, with no even distances. In addition, other pixels not a part of the crossbar have been removed. The result is a clear close-up view of this remarkable structure:
It's worth spending a few minutes to appreciate all the symmetries and rhythms in these crossbars. The black lines at the center of the main diagonal are distances from a room to itself; since this distance is always either 4 or (in two cases) 6, those pixels are black in this map.
Crossbar rooms on one side of the diagonal show the distance from row A to column B; their corresponding rooms on the opposite side show the distance from row B to column A. If A to B is 1, then B to A is guaranteed not to be 1.
Most of the smaller crossbars alternate from 1 (yellow) to 3 (orange). The crossbars of length 16 tend to alternate from 1 (yellow) to 5 (gray). But there are occasional exceptions. Drilling into these exceptions can sometimes prove interesting.
Consider the lone green pixel on the first 16-length crossbar inside the square outline in the above map. Let's zoom into the six pixels within that outline and look at them on an atomic level. In order to understand the distances represented by these six pixels, I have shown the patterns corresponding to each row and column:
The patterns shown here may seem random at first, but a closer examination reveals much about how this distance map works and why this one pixel is green instead of gray.
First of all, ignore whether the individual cells of each pattern are filled or empty and instead focus just on the shapes, the circles and squares. Since the grand tour moves from neighbor to neighbor, adjacent patterns differ by only a single shape. So, across the columns we see that cell 1 (the south yang) of the first pattern changes from a square to circle to produce the second pattern. In the second pattern, only cell 3 (the east yang) changes to produce the third pattern. Then cell 1, then cell 2 (the northeast yin), and finally cell 1 again to produce the sixth pattern.
This rhythm (1, 3, 1, 2, 1) is the signature of the grand tour algorithm. A similar rhythm occurs down the rows.
This crossbar we're looking at in this close-up occurs at the jump from the first tesseract to its enclosing 5-cube. For this reason, the center cell, which represents the 5th dimension, is the key player.
To create the first yellow pixel, the pattern in row 1 changes to the pattern in column 6 by traveling though the center cell. This causes the center all four yang cells to flip. The same is true for the second yellow pixel between row 2 and column 5.
For the remaining four pixels, the reverse is true. You can travel directly from the pattern in column 4 to the pattern in row 3 by choosing the center cell. The same is true between column 3 and row 4, column 2 and row 5, and column 1 and row 6. If you look at the previous map you will see that the four corresponding pixels on the opposite side of this crossbar are all yellow.
Yellow pixels on the opposite (northeast) side of the diagonal represent the future, rooms along the tour with a neighbor on a later (higher) level. Yellow pixels on this (southwest) side represent the past, rooms along the tour with a neighbor on a previous (lower) level. The patterns in our 6 rows all have squares in the center because they occur on level 5; the earlier patterns in our 6 columns had not yet reached level 5. Our 2 yellow pixels represent paths directly back to previous levels. The remaining 4 represent paths which took only 1 step to move up, but now take either 5 or 7 steps to move back down.
So why is our third pixel the only green (distance 7) pixel on the entire crossbar? If you look closely at the patterns on either end, on row 3 and column 4, you might be able to guess the answer. Of all the 32 distance pairs on this crossbar, this pair are the only ones in which the four yang cells happen to be all off on one end and all on on the other.
This becomes more clear when we examine the actual shortest paths between our six pairs of patterns. The following diagram shows each of the six paths as calculated by my Starmaze Explorer program:
The starting and ending patterns of all these paths differ only by the shape of the center cell, so we know that any path between them will flip the center an odd number of times and any other cell an even number of times.
For the last 3 gray (length 5) paths, the order of steps may vary somewhat but the basic solution is always the same. In each of these paths, the center cell is flipped once and 1 yang cell and 1 yin cell are each flipped twice.
But in the green path, the initial lack of yang cells disrupts this approach and forces an extra yin cell to be flipped twice, thus increasing the path length from 5 to 7.
Each pixel in the map has its own story to tell, its own secret to reveal. But above all, the maps themselves are simply beautiful. Like any satisfying work of art or music, they lie at the enticing boundary between regularity and chaos. For me, they make visible the beauty I sense everywhere in the starmaze.