Strategy for solving a 3D maze

Question

Given enough time, you can solve a large 2D maze by simply following a wall. Is there any similar strategy for solving a 3D maze that can be used (no marking/memorizing places you've seen in the maze is required)?

Answer 1

Given the right conditions, the 2D right-hand-wall-following algorithm works because

the four compass directions are given a cyclic order. If you enter an intersection from one direction, you automatically choose the next direction in the cyclic order, which is North, West, South, East, and then North again. If you come from the North, you will go to the West; if you come from the West, you go to the South, etc. In a maze without loops, taking any path leading away from an intersection which does not lead to the exit will eventually force you to reverse your steps and come back to that intersection, after which the next direction in the cyclic order will be explored. Eventually the correct direction is found.

Note that the actual cyclic order you use does not matter. You could explore the directions in NSEW order, and that works just as well, though in that case you cannot simply follow the wall but need to keep track of your own orientation, and act accordingly at each intersection.

For a 3D maze, I'll assume that the maze is aligned to a cubical grid, so that the paths are straight and parallel to the three axes.

You will need to do the same thing. Choose a cyclic order for the 6 directions that the paths from an intersection can have. Once again you have to keep track of your orientation in space so that you know from which direction you enter each intersection, and then can leave the intersection in the next direction in your chosen cyclic order. As mentioned before, this only works if your maze has no loops.

Answer 2

According to this Wikipedia article, a 3D maze can be solved using the wall following method if 3D corridors (up, down, etc.) can be projected onto a 2D plane.

Suppose that the maze in question has 6 directions, north, south, east, west, up, and down. 'Up' corridors can be projected as northeast, and 'down' corridors can be projected as southwest. This means, if you keep your hand on the 'right' wall, you will favor these directions respectively: Right, Up, Forward, Left, Down, Backward.

     forward up       The direction that you turn would be the
left         right    first one available starting at right and
down backward         heading counterclockwise from there

Unfortunately, this method requires a compass. Suppose you head north to an intersection with all 6 directions. Firstly, you would turn right (east) because that is the first direction available on the 2D projection. Suppose it dead-ends, and you return to the intersection. Seemingly, you should turn right because there is an available right turn, but because you originally entered the intersection whilst facing north, you must continue to test paths from that orientation. The next available turn on the 2D projection would actually be up (northeast). From an omniscient viewpoint, this seems trivial, but within the maze, it would be highly unreasonable to maintain a sense of direction without memorization or a compass.