| Author | Message | |||
| Karl Scherer (Karl)
New member Username: Karl Post Number: 334 Registered: 9-2000 |
'Modified Right-Hand Rule' to escape 3d-mazes an old hat? To all puzzlists, and especially to all maze-experts such as Adrian Fisher! I have found a simple 'Modified Right-Hand Rule' to escape any 3d-maze. I have never heard or read about something like that and hence I am eager to find out whether it is well known or not. Please let me know if you have any information about it. Here are the details: Background In my Zillions games 'Bigmazes', 'Bigmazes II', 'Bigmazes III', the computer first builds a large randomized 50x50 maze (in many possible design styles, by the way) and then the human player or (if the player hits the SOLVE button) the computer finds a way to the exit. Hence I had to invent a simple, but efficient method so that the computer can find and then display a solution. 2d-mazes without loops For purely 2d-mazes without loops (i.e. graph is a tree), I implemented the famous right-hand rule (RHR) to help the computer find the goal, and then ignored the double-track parts to display the other walked parts as solution, which then is automatically the shortest path to the exit. 2-d mazes with loops As long as we know that the start and the finish are at the periphery, the RHR still solves that game. However, the solution presented (with double-tracked arms pruned as above) is not necessarily the shortest path in these cases. 3d-mazes Any 3d-maze can be represented as a "2d-maze with bridges". I call these mazes "self-crossing 2d-mazes". In these mazes, what is the most simple way to teach the computer to find a way out? I have never heard of a simple method that does the trick. Can we find some simple rules which are not based on the knowledge what the maze layout looks like, but rather on local knowledge only such as 'have we walked this piece of path before'? To help your imagination, let us assume that we can see our shoe prints on the sandy floor, and the sheer existence of these shoeprints are our only help for navigation. How would you find your way out? The 'Modified Right-Hand Rule' In the following let the term 'path' mean the connection between two intersections, but excluding the intersection points. The 'Modified Right-Hand Rule' (MRHR) I finally came up with consists of three rules: 1. When you walk a path the first time and you come to an intersection where you have been before, you immediately turn back and retrace this leg to the last intersection. 2. Never walk on a path which you have walked on twice already. 3. Apart from the cases above, observe the right-hand rule. The game 'Self-Crossing I' of my Zillions maze collection 'Bigmazes III' uses this Modified Right-Hand Rule to find and present a solution. The presented solution again has all double-walked (and hence redundant) path pieces pruned. The method comes up with a corrrect solution every time and never ends in a loop, a dead end and back at the entrance. I am quite sure that the MRHR is mathematically correct, but I have not written down a proper proof yet. Hence my question is : is this all well known, or is it unknown even to the maze experts? I am looking forward to all your comments. The latest update of Bigmazes III (with the new MRHR implementation !) is available from http://karl.kiwi.gen.nz/swindex2.html or from coming Sunday from the Zillions home page, as are the lastest (very improved) updates for 'Bigmazes' and 'Bigmazes II'. Happy puzzling, Karl Scherer | |||
| Greg Schmidt (Gschmidt2)
New member Username: Gschmidt2 Post Number: 6 Registered: 1-2007 |
Hi Karl, You wrote: [2d-mazes without loops For purely 2d-mazes without loops (i.e. graph is a tree), I implemented the famous right-hand rule (RHR) to help the computer find the goal, and then ignored the double-track parts to display the other walked parts as solution, which then is automatically the shortest path to the exit. ] I don't see why this should find the shortest path. Consider the maze below (the solid lines represent the halls, not the walls). (see attachment)
The twisty path will be the first path found to the exit. It is longer than the other path. I believe the only way to guarantee optimality is by using an incrementally deepening search algorithm such as breath-first search. Tremaux's algorithm works for all mazes including 3d mazes. http://www.astrolog.org/labyrnth/algrithm.htm Tremaux's algorithm: This Maze solving method is designed to be able to be used by a human inside of the Maze. It's similar to the recursive backtracker and will find a solution for all Mazes: As you walk down a passage, draw a line behind you to mark your path. When you hit a dead end turn around and go back the way you came. When you encounter a junction you haven't visited before, pick a new passage at random. If you're walking down a new passage and encounter a junction you have visited before, treat it like a dead end and go back the way you came. (That last step is the key which prevents you from going around in circles or missing passages in braid Mazes.) If walking down a passage you have visited before (i.e. marked once) and you encounter a junction, take any new passage if one is available, otherwise take an old passage (i.e. one you've marked once). All passages will either be empty, meaning you haven't visited it yet, marked once, meaning you've gone down it exactly once, or marked twice, meaning you've gone down it and were forced to backtrack in the opposite direction. When you finally reach the solution, paths marked exactly once will indicate a direct way back to the start. If the Maze has no solution, you'll find yourself back at the start with all passages marked twice. The above algorithm seems similar to yours with the exception that a random path is chosen. It doesn't seem to matter how the paths are chosen (rightmost or random) as the important part is that all paths will systematically be explored. -- Greg | |||
| Greg Schmidt (Gschmidt2)
New member Username: Gschmidt2 Post Number: 7 Registered: 1-2007 |
Oops, I just realized that my maze example contains a loop - so we agree that a shortest path will not necessarily be found. The way to find shortest paths in mazes with loops would be to use breadth-first or some other form of incrementally deepening search. (I also spelled it "breath-first" search in my previous post. Well it is an "exhaustive" search!  ) -- Greg | |||
| Karl Scherer (Karl)
New member Username: Karl Post Number: 336 Registered: 9-2000 |
Private email exchange with Adrian Fisher clarified a few things: - The "Modified Right-Hand Rule" (MRHR) indeed always works and finds the way out. - The "Modified Right-Hand Rule" (MRHR) is really not a single 'rule', but a set of three rules. So it is still true that "no single rule" can solve a 3D maze. - The idea of MHRH is not new, but it seems that it has never been used before for solving a randomized computer-generated maze and to display a solution. Please anybody correct me if I am wrong. - MRHR seems to be the most simple strategy to find your way out without knowing anything about the overall design, in the sense that you (or the solving-program which I worked on) has to store the fewest number of bits of local information, namely exactly three bits : (A) whether the path I just have walked to the current intersection has been walked on before (i.e., whether I have been retracing) (B) whether the path to the right has been walked on (C) whether the path to the right has been walked on twice. Note to Greg: Thanks for your feedback. Note that even though the algorithm you quoted is similar to MRHR, it needs more information than MRHR and is therefore NOT the simplest: It needs to know information about paths which are not to the right, since because of its randomness it not always chooses to check the path to the right. Also, randomness needs more programming. Try implementing it in my Zillions game "Bigmazes III" for example,and you will see what I mean! Cheers, Karl | |||
| Greg Schmidt (Gschmidt2)
New member Username: Gschmidt2 Post Number: 9 Registered: 1-2007 |
I believe "random" in this context would simply mean that it doesn't matter how you choose the path (subject, of course, to always picking an unexplored path). Randomness in a stochastic (ie. probabilistic) sense is clearly not a requirement for the Tremaux algorithm to work since it's not inherently a stochastic algorithm. By that I mean that randomness is not required in the sense that it is for the performance of truly stochastic methods such as Monte Carlo or Genetic algorithms. Stating that it's "random" is a more general way to specify the algorithm in order to indicate that any path choice mechanism will work. To further this point, consider an insertion sort. From Wikipedia: "In abstract terms, every iteration of an insertion sort removes an element from the input data, inserting it at the correct position in the already sorted list, until no elements are left in the input. The choice of which element to remove from the input is arbitrary and can be made using almost any choice algorithm" So a concise way of specifying this algorithm would be to say "pick the next element at random". Rightmost is just one of many ways to satisfy the "any old choice will do" methodology, leftmost is another way. These and an infinite number of other rules for path picking are subsumed by the Tremaux algorithm. What Tremaux (or the insertion sort algorithm above for that matter) doesn't mention is that a specific selection method such as rightmost may lead to a simpler implementation which is what you have found to be true in ZoG. -- Greg |
Maze Example