8
$\begingroup$

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)?

$\endgroup$
4
  • 1
    $\begingroup$ Is it a zero gravity maze? I.e. can you tell which direction is up/down? $\endgroup$ Commented Dec 6, 2020 at 17:39
  • 5
    $\begingroup$ You can only solve a 2D maze by following a wall if the wall is not an island. If it is an island and you can't mark (or remember) the wall, you'll go round in circles for ever. $\endgroup$ Commented Dec 6, 2020 at 17:46
  • 1
    $\begingroup$ @WeatherVane Note that there are other algorithms, Pledge algorithm can take you out of a 2D maze with islands (but no bridge) without remembering or marking places. $\endgroup$
    – Florian F
    Commented Dec 6, 2020 at 19:32
  • $\begingroup$ @FlorianF thanks... interesting. $\endgroup$ Commented Dec 6, 2020 at 22:45

2 Answers 2

6
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ If the 3D-Maze is actually in normal gravity wouldn't the sense of up/down be enough to determine the rest? $\endgroup$
    – Falco
    Commented Dec 7, 2020 at 12:35
  • $\begingroup$ @Falco No, suppose the 'right' (east) corridor leads to a dead-end. When you return, the north corridor would appear to be 'right', when it's actually 'forward'. Because you favor 'up' before 'forward,' you would go 'up' first. Without a compass or memorization, you would assume that the north corridor is the next path to take, when in actuality, it's the 'up' corridor. $\endgroup$
    – Nilster
    Commented Dec 7, 2020 at 14:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.