Wednesday, October 12, 2016

[gxpgqixq] Notes on higher dimensional mazes

Consider two different types of 2D mazes on a grid of squares:

Some of the squares are black (indicating blocked); other squares are white (indicating passage).  Call this type of maze a "maze of blocks".

All the squares are white, but there are infinitesimally thin walls preventing passage between certain adjacent squares.  Call this type of maze a "maze of walls".

Depicting a 3D maze of blocks in 2D is fairly easy: just show slices.

A 4D maze of blocks is similarly easy.  A MxNxPxQ maze could be depicted as a PxQ array of MxN slices.  It could also be depicted as a MxN array of PxQ slices.  These different depictions are interesting when two of the dimensions are small, 2 or 3.

Consider a MxNx3x3 maze of blocks.  First, depict it as a 3x3 array of MxN mazes.  One can determine whether one can move along the 3rd or 4th dimension by looking at the corresponding square on an adjacent MxN maze.  This can be annoying or time consuming if the MxN maze is large.  Add annotations to each square in the MxN maze showing which 3rd and 4th dimension steps are possible: thin colored rectangles.  The ultimate goal is to provide enough information so that a person can form a model of the maze (or local parts of it) in their heads (interestingly, a 4-dimensional model) and solve chunks of it in their heads.

I have seen a 3D maze of walls depicted in slices, with certain squares in each slice marked with a small black square indicating a hole down or a larger thin ring indicating passageway up the ceiling.  Could be generalized to 4D with the same per-square annotations described above.

***

The simplest maze structure is a tree: there exists a unique path between any pair of nodes.  Make the maze a little bit harder (or easier, depending on the point of view) by adding loops.  The obvious starting idea is just one loop, and lots of trees hanging off of it.  What next?

In 3 dimensions and more, there are no constraints on graphs that can be embedded in a maze: there are no problems with paths needing to cross like in 2D.  Other loopy graphs: tetrahedron and higher simplices (equivalently complete graphs), torus grid of 2 or more dimensions, hypercubes, cross polytopes.  Cubic graphs, including snarks, are neat.  Cross polytopes and simplices have very small diameter.  Which loopy graphs are interesting for mazes?

***

Consider a maze of blocks of N dimensions, where N is quite large, but the maze has width 2 in all dimensions.  (Maze total volume is 2^N.)  Is it difficult?  How can one depict it to aid solving?

For a GUI, N switches denoting the coordinates, a light above each switch signifying whether changing that coordinate is permitted (not a solid block).  Maybe not just a light but the name of the room (block).

What interesting loopy graphs above can be embedded in a 2^N maze of blocks?  If not 2^N, then maybe 3^N offers enough space.

A 2^N maze of walls might lose most its geometric aspect; it might as well be an abstract graph.

No comments :