Example: a slice |
 |
The floor plan is a lower dimensional maze. |
 |
A 4-dimensional maze is a finite integer grid in 4-space with only certain cube-walls included. Your perception is limited to a 3-dimensional subspace, and the intersection of this hyperplane with the maze (the slice). At rest, this slice is parallel to a coordinate hyperplane, and perpendicular to one coordinate axis (the hither & yon directions). You travel through the maze as follows: Within the slice, you can move forward/back one unit or rotate your perspective by a quarter-turn. You may also move hither/yon one unit, shifting the slice over along with yourself. Finally you can rotate the slice by a quarter-turn, i.e., let one visible direction go to the hither direction, while fixing two perpendicular slice axes through your position. You cannot travel through walls. There are visual symbols denoting hither and yon portals, and there is sonar which indicates the depths of the passageways in those directions. We give you one maze with an automated tour; mazes may also be generated randomly.
Thank you for tolerating ASCII conventions such as:
The 4D integer grid is the set of points (x,y,z,w) in real 4-space with at least one integer coordinate. We rewrite it as the union of 4 types of 3D cubes, each type parallel to one of the 4 coordinate 3-planes. Let xyz-wall[i,j,k,h] be the set {(x,y,z,w): i <= x <= i+1, j <= y <= j+1, k <= z <= k+1, w=h} for integers i,j,k & h. Note that each forms a unit cube which is parallel to the coordinate xyz-plane. Similarly define xyw-walls, xzw-walls and yzw-walls, and note that the union of all such cubes is the 4D integer grid.
We will consider a bounded subset of the integer grid such that
0 <= x,y,z,w <= N. This can be written as a union of 3-walls:
{yzw-wall[i,j,k,l]: 0 <= i <= N, 0 <= j,k,l < N} Union
{xzw-wall[i,j,k,l]: 0 <= j <= N, 0 <= i,k,l < N} Union
{xyw-wall[i,j,k,l]: 0 <= k <= N, 0 <= i,j,l < N} Union
{xyz-wall[i,j,k,l]: 0 <= h <= N, 0 <= i,j,k < N}
These four types of cubes are colored yellow, blue, green, and red,
respectively. Any intersection of two differently colored walls
is shown in grey.
Definition: A 4D maze is a subcollection of these 3-walls. We do not distinguish between a maze and the associated space (the union of its walls in 4-space). Arbitrary n-dimensional mazes with (n-1)-dimensional walls may be similarly defined.
The goal of this project was to find and implement a way to reasonably navigate a 4D maze despite the limitation of being 3D people with 3D vision in a 3D world. To motivate the model chosen, we first describe a natural way that a 2D person (FlatBoy) could navigate a 3D maze. Let's assume that a 2D person has a flat 2D field of perception, i.e., he can only detect objects and colors within a plane which contains his person. Now suppose that he is inside the maze, and then fix some 2-plane in 3-space to be his field of perception. Then his perception of the maze will be precisely the intersection of the maze with his planar field of perception. We call this a 2D cross-section or "slice" of the 3D maze.
For the moment, let us further suppose that this slice is parallel to the x & y axes and that FlatBoy is located within some unit- sized room within the maze. Then his slice will intersect the upright walls (as opposed to ceiling/floor walls) that are at the same z-level as himself, and so it will be precisely the floor plan of his current z-level. Now as 3D people, we are accustomed to thinking of a 3D building as a series of levels that are perfectly described by the series of z-level floor plans, if we add only some means of changing between consecutive z-levels (like stairways). So we add up & down symbols to the slice, indicating each place where there is no ceiling/floor-wall (and hence a place where FlatBoy may change levels). (We could also give him sonar.) Now these z-level floor plans are not only his naturally defined fields of perception, but also provide a natural means to navigate a 3D maze.
|
|
|
||
|
|
|
The chief drawback to this model is that the one direction is treated differently: the slice is always perpendicular to the z-axis, and ceiling/floor-walls are never perceived directly. So we extend to him the ability to rotate his field of perception so that it may also be perpendicular to the x-axis or y-axis. Each new type of slice will intersect the ceiling/floor-walls and one other type of wall, which will form a sort of floor plan, but for a fixed x- or y-level. Up (and down) symbols will now more generally indicate the direction that is wall-free, perpendicular to the slice, and which is designated by his local orientation of front and left together with the right-hand rule. (Note: Although this insures that the up direction will be consistent throughout a rotation, the up and down symbols have no clear meaning during the rotation and so will not be drawn then.) During a rotation between slices perpendicular to, say, the z- and y-axes, the axis of rotation is parallel to the x-axis; so that he doesn't have to move in space, that axis passes through his location. With this addition, the model becomes symmetric with respect to the unit vectors of an orthogonal basis.
 |
| |||
 |
||||
 |
 |
|||
 |
||||
 |
 |
"illiMaze4D" allows a real 3D person to traverse a virtual 4D maze by means of an analagous slicing model. For each coordinate axis, the perpendicular interior levels are indexed from 0 to N. The user's location is an integer array {i,j,k,h}, which means that the user's actual coordinates in the maze are {i+.5, j+.5, k+.5, h+.5}, (so the user is in the center of some unit hypercube of the 4D lattice). If, for example, the current slice is parallel to the xyz-coordinate plane (and perpendicular to the w-axis), then as it contains the user's position it must have the equation w = h+.5. Other types of slices (parallel to other coordinate 3-planes) have similar equations. During a rotation between slices perpendicular to, say, the z- and x-axes, the axes of rotation are parallel to the the (remaining) y- and w-axes, and pass through the user's coordinates. The field of perception is a 3D floor plan that consists of the intersection of the slice and the maze, plus symbols that indicate openings in the hither/yon directions. The (local) hither direction will be determined by the local directions of left, up and front, and by a 4D version of the right-hand rule. This will give a consistent meaning to the hither direction throughout a slice rotation.
There is also "sonar": A high pitched chirp is followed by an "echo", and the delay is proportional to the distance to the nearest wall in the hither direction. The quickest echo will occur when there is no opening in (and hence no symbol for) that direction. A slightly lower pitched chirp w/echo does the same for the -hidden direction. (We go into more detail during the hypertour.
To have sound, you must first start up VSS. (It works with version 3.1 - if you have trouble with some other version please let me know.)
In the CAVE, REL & NL in Beckman, illiMaze4D is available on CAVEbuttonfly, in subdirectory illiMath. (This doesn't allow any arguments to be specified.) You may also run it directly from `~pelsmaje/public/demo/BestMaze.x'.
On any SGI in the Grafixlab, run `~pelsmaje/public/ncsa_maze/moMaze2'. On the PC named trivial, run idaho???? Other PC's?
(The PC version) Not yet available for download off of WWW
You begin outside a maze, and using the wand and/or keyboard, you can move and rotate in space. Begin by taking the hypertour.
There are also instructions online for navigating the maze, in the CAVE and on a console.
