4-dimensional mazes
As I noted last time, the maze algorithm doesn't know are care about topography or dimensionality. All it cares about is a list of nodes with each node's initially unconnected neighbors. How the nodes are laid out is post-processing.
One-dimensional mazes aren't so challenging: each node has 2 neighbors. Two directions, for example east and west.
With a 2-dimensional maze with square nodes, each node has 4 neighbors (no cutting corners). Obviously 2-dimensional is more challenging than one-dimensional: there's no the opportunity for dead-ends and multiple path options. Sample directions are north, east, south, and west: two more than the 1-dimensional case.
To three dimensions, each node (assuming cubic nodes) has 6 neighbors. In addition to north, east, south, and west, you can add up and down to the list of directions.
So there's a pattern here. Each time you add a dimension you add two more neighbors and two more directions, the two directions being the opposite of each other. West is the opposite of east, south the opposite of north, down the opposite of up.
It happens we live in a 3-dimensional world, but there's nothing particularly special mathematically about three dimensions. The maze algorithm doesn't care. It's just as happy in 4 dimensions as in 3.
So following the pattern, if we add a dimension, we need to add two neighbors and add two directions. I like "in" and "out" for these directions.
My maze program, which I wrote to generate semiconductor structures using the structure generator for semiconductor modeling. But for debugging, it also generates a simple text rendering of the maze.
Here's a one-dimensional maze. It's fairly dull:
In on the left, out on the right, no choices to be made in between.
Two-dimensional mazes offer choices. Here you enter on the left, exit to the right:
For 3-d, the structure editor will have no problems (I'll show that in a later post), but for text-art, I'll represent multiple layers like multiple "floors" in a building floor plan. Access from one floor to another are represented with arrows: an upward arrow for access to the floor above, a downward arrow for access to a floor below, or an up-down arrow for access to either.
Here's a 3 × 3 × 3 example, where again you enter on the left and exit on the right:
For four dimensions, I simply extend the floor plan model. In addition to stacking floors one above the other, I stack them in multiple columns. In a node, a right arrow signifies that there's access to the corresponding node in the column to the right, a left arrow signifies access to the corresponding to the column to the left, while a left-right arrow specifies access to either. With so many choices, up to eight, from each node things get complex quickly. Even for a simple 3 × 3 × 3 × 3 case, which has 91 nodes:
In this example, the entrance is in the upper right "floor" on the left wall. The exit is in the upper middle "floor" on the right wall.
This was done in Scheme Lisp. A long time ago, I wrote a 4-dimensional maze generator in Microsoft BASIC. In that case, I made a video game of it. You can fairly clearly project three dimensions onto a 2-dimensional screen. But 4-dimensions get challenging. So I just represented three: the fourth dimension was hidden.
The trick is which dimensions should be visible? For coordinates x, y, z, and u, I'd render x, y, and z, with u hidden. Whether access is available or not in the u dimension isn't shown. There'd be a number of options here; for example you could put a symbol on the screen for whether u-direction "in" and/or "out" access is open. But instead I allowed the user to "rotate" so the u direction is visible.
So to do this, in addition to the standard pivots in three dimensions, I added two additional actions: permute right and permute left.
Suppose x is the direction ahead, y to the right, and z up. Then if I permute right, then I shift each coordinate: y is ahead, z is to the right, and u is up. Do it again and z is ahead, u is right, and x is up. A third permute and u is ahead, x is right, and y is up. A fourth permute and I'm back where I started. Initially u is hidden, then x is hidden, then y is hidden, then z is hidden. A fourth permute and u is hidden again.
Anyway, enough of that for now. Maybe I'll do something about bicycling again soon.
One-dimensional mazes aren't so challenging: each node has 2 neighbors. Two directions, for example east and west.
With a 2-dimensional maze with square nodes, each node has 4 neighbors (no cutting corners). Obviously 2-dimensional is more challenging than one-dimensional: there's no the opportunity for dead-ends and multiple path options. Sample directions are north, east, south, and west: two more than the 1-dimensional case.
To three dimensions, each node (assuming cubic nodes) has 6 neighbors. In addition to north, east, south, and west, you can add up and down to the list of directions.
So there's a pattern here. Each time you add a dimension you add two more neighbors and two more directions, the two directions being the opposite of each other. West is the opposite of east, south the opposite of north, down the opposite of up.
It happens we live in a 3-dimensional world, but there's nothing particularly special mathematically about three dimensions. The maze algorithm doesn't care. It's just as happy in 4 dimensions as in 3.
So following the pattern, if we add a dimension, we need to add two neighbors and add two directions. I like "in" and "out" for these directions.
My maze program, which I wrote to generate semiconductor structures using the structure generator for semiconductor modeling. But for debugging, it also generates a simple text rendering of the maze.
Here's a one-dimensional maze. It's fairly dull:
+--+--+--+--+--+--+--+--+
+--+--+--+--+--+--+--+--+
0 1 2 3 4 5 6 7In on the left, out on the right, no choices to be made in between.
Two-dimensional mazes offer choices. Here you enter on the left, exit to the right:
+--+--+--+--+--+--+--+--+
7 | | | |
+ + + +--+--+--+ + +
6 | | | | |
+ + +--+ +--+--+--+ +
5 | | | | | |
+ +--+ +--+ + + + +
4 | | | | | |
+--+ + + +--+--+--+ +
3 | | | | |
+ +--+ + + +--+--+ +
2 | | | | | |
+ + + + +--+--+ +--+
1 | | | | | | |
+ + + +--+ + +--+ +
0 | | |
+--+--+--+--+--+--+--+--+
0 1 2 3 4 5 6 7For 3-d, the structure editor will have no problems (I'll show that in a later post), but for text-art, I'll represent multiple layers like multiple "floors" in a building floor plan. Access from one floor to another are represented with arrows: an upward arrow for access to the floor above, a downward arrow for access to a floor below, or an up-down arrow for access to either.
Here's a 3 × 3 × 3 example, where again you enter on the left and exit on the right:
z = 2
+--+--+--+
2 |↓ |↓ |
+ + +--+
1 | |
+--+ + +
0 |↓ |↓ |
+--+--+--+
0 1 2
z = 1
+--+--+--+
2 |↑ |↑ |↓ |
+ +--+ +
1 |↓ |↓ |
+--+--+--+
0 |↕ |↓ |↕ |
+--+--+--+
0 1 2
z = 0
+--+--+--+
2 | |↑
+ + + +
1 |↑ |↑ | |
+--+--+ +
0 |↑ ↑ |↑ |
+--+--+--+
0 1 2For four dimensions, I simply extend the floor plan model. In addition to stacking floors one above the other, I stack them in multiple columns. In a node, a right arrow signifies that there's access to the corresponding node in the column to the right, a left arrow signifies access to the corresponding to the column to the left, while a left-right arrow specifies access to either. With so many choices, up to eight, from each node things get complex quickly. Even for a simple 3 × 3 × 3 × 3 case, which has 91 nodes:
z = 2
+--+--+--+ +--+--+--+ +--+--+--+
2 | → →| |↓←| → ←| |↓ | ←|↓ |
+--+--+--+ +--+--+--+ +--+ +--+
1 | ↓ | | → ↓ | → ←| | ←|
+ +--+--+ +--+--+ + +--+ + +
0 |↓ |↓ →| |↓→ | ←| | ←| |
+--+--+--+ +--+--+--+ +--+--+--+
0 1 2 0 1 2 0 1 2
z = 1
+--+--+--+ +--+--+--+ +--+--+--+
2 |↓ | →|↓ | |↑ |↓↔| →| |↕ |↓←|↕←|
+--+ + + + +--+ + + +--+--+
1 |↓→| ↑ | | ←|↑ |↓ | | |
+--+--+ + +--+ +--+ +--+--+--+
0 |↑→|↑→| →| |↕←| ←| ←| |↓ ↓ |
+--+--+--+ +--+--+--+ +--+--+--+
0 1 2 0 1 2 0 1 2
z = 0
+--+--+--+ +--+--+--+ +--+--+--+
2 |↑ ↑→| | ↑ | ←| |↑ ↑ |↑ |
+--+--+--+ + + +--+ +--+--+ +
1 |↑ | →| | →| |↑←| | ←| |
+--+ + + +--+--+--+ + + +--+
0 | →| →| →| |↑←| ← ←| |↑ | ↑ |
+--+--+--+ +--+--+--+ +--+--+--+
0 1 2 0 1 2 0 1 2
In this example, the entrance is in the upper right "floor" on the left wall. The exit is in the upper middle "floor" on the right wall.
This was done in Scheme Lisp. A long time ago, I wrote a 4-dimensional maze generator in Microsoft BASIC. In that case, I made a video game of it. You can fairly clearly project three dimensions onto a 2-dimensional screen. But 4-dimensions get challenging. So I just represented three: the fourth dimension was hidden.
The trick is which dimensions should be visible? For coordinates x, y, z, and u, I'd render x, y, and z, with u hidden. Whether access is available or not in the u dimension isn't shown. There'd be a number of options here; for example you could put a symbol on the screen for whether u-direction "in" and/or "out" access is open. But instead I allowed the user to "rotate" so the u direction is visible.
So to do this, in addition to the standard pivots in three dimensions, I added two additional actions: permute right and permute left.
Suppose x is the direction ahead, y to the right, and z up. Then if I permute right, then I shift each coordinate: y is ahead, z is to the right, and u is up. Do it again and z is ahead, u is right, and x is up. A third permute and u is ahead, x is right, and y is up. A fourth permute and I'm back where I started. Initially u is hidden, then x is hidden, then y is hidden, then z is hidden. A fourth permute and u is hidden again.
Anyway, enough of that for now. Maybe I'll do something about bicycling again soon.
Comments