Amaze Me

This came up in the context of the development experience we’re working on. One of the objects we supply to work with is a maze – you can create a new maze, take a step in the maze, check to see if the direction you’re facing is a valid move, turn, and so on.

Anyway, Adam and I were standing in his office looking at the maze feature he’d created and I asked what a good algorithm was for solving it. He suggested on approach (when you hit a wall, always turn left), but we quickly discovered that could cause an infinite loop. I suggested a modification – when you hit a wall, turn a random direction. That seems to solve the maze, but it’s highly non-deterministic (albeit very memory efficient).

What’s the best solution?

Comments

• Anonymous
  June 28, 2006
  Keep a 'trail' of your progress through the maze.  When navigating the maze, always try turns in the same order.  If you hit a total dead-end, back up and try the next turn in sequence in the previous sequare (ie where you turned left before, try going straight, where you went straight before, try turning right.
  
  This is easy to code and will always solve a maze without re-trying paths, but I don't know if it guarentees minimal visits to every node in the maze.
• Anonymous
  June 28, 2006
  The comment has been removed
• Anonymous
  June 28, 2006
  Depends on the size of the puzzle.
  
  Branch and bound based solution that Jeff Parker describes last in his post is probably the best overall.
• Anonymous
  June 28, 2006
  I can't remember where this algorithm came from (my wayback machine goes to the Commodore Pet era; this algorithm was published in a C64 magazine, though).
  
  I call it the "try right" algorithm. It will traverse every square of the maze as long as the maze does not have any loops in it (otherwise, I would recommend the dead end filler technique). This is very similar to what you suggest.
  
  In your current location, you are always moving in a set direction (from your last move). Always see if you can move to your right. If not, try straight ahead. No? Fine, look to the left? Still no? You are at a deadend, turn completely around. I'll see if I can come up with something in a jiffy.
• Anonymous
  June 28, 2006
  whoa, let's hold up a moment.  You've just had a HHGTG moment.  Asking for the best solution is liking asking for the answer the meaning of life, the universe and everything.
  
  The answer only makes sense in the context of the question.
  
  If you don't clearly know the question, you can't have a meaninful answer.  I always immediately throw the breaks on when people start asking me for things like the "Best" solution to a problem that has multiple variables that need to be balanced.
  
  Even for something as simplistic as a maze, you can find many variables:
  
  1. Most deterministic solution
  2. Shortest path
  3. Minimimum processing time
  4. Minimum code size.
  5. Minimum data requirements
  6. Minimum price
  7. Minimum path retracing
  
  Does the maze have to be a fixed size, a maximum size?  Does it have any deterministic features?
  
  Since you want the best, you have to decide what you consider the best to me.  Maybe you need it all to fit into a 2k machine.  The best solution there probably doesn't involve storing a map of 5000x5000 cell maze, but it might on a 20x20 maze.  Does it matter how long a machine takes to process the solution?
  
  If you can't define best, you can't find it.
• Anonymous
  June 28, 2006
  Alright. I had a little bit of time and did a quick VB project to show what I was meaning. Yeah, yeah, I had to do a full maze generator in order to show you the maze traversal.
  
  http://www.madjic.com/SimpleMaze.zip
  
  Just extract, compile, and watch the programmer art (and lack of comments, I know).
• Anonymous
  June 28, 2006
  I haven't tried it in all mazes - but I believed that as a person always ensuring you have your left hand on a wall at all times will lead you through a maze. (Shouldn't be to hard to code.)
  
  You shouldn't get stuck in a loop - but you may well spend an exceedingly long time solving the maze.
• Anonymous
  June 28, 2006
  go the way with the most options.
  
  whenever you hit an square, where you have more possibilities, go that way, that gets you in the direction with the most squares, where you didn't were bevore. no matter, if you can go directly to them or not. its just an simple overview. but in the most cases gives you the shortest tries. (yep, its allways good to use such dead end helpers and it depends on the maze.)
  but it would be cool to try that out. shall i program an maze generator in the weekend? or someone has one?
• Anonymous
  June 29, 2006
  I did a maze generator once.  Printed them out on a Diablo 1620.
  
  If you can mark visited squares, then you can avoid refollowing already-visited paths.  
  
  Then use a stack of all squares visited where there were any choices.  Choose any way you want.
  
  Everytime you reach a dead-end or an already-visited square, back up to the last choice in the stack and take a different turn (remember which it was).  If there are no further turns, back up again.
  
  If you ever get to an exit, the stack will give, in reverse sequence, the choices you made at every choice point on the route to that exit.
  
  If you want to know a shortest path, there is a simple embellishment for finding all routes and remembering each new one if it is shorter than any previous ones.
  
  A couple of other solutions should work too,  but I like the bread-crumbs and choice stack approach for the simplicity of explanation.  It is a good one to benchmark against for testing optimization techniques.
• Anonymous
  June 29, 2006
  One thing I like about the breadcrumbs and branch-point history in a stack is how it doesn't require the topology of the maze to be known, so it works where sweeping the maze and filling in dead-ends might be difficult or even not possible (as when working a a dungeon adventure or following a hedge maze in person).
  
  If you can't leave breadcrumbs in every square, you're still all right if you can tell when an intersection is one you've been in before.  Not quite good enough for a "maze of twisty little passages all alike" where randomization happens, but then there has to be some challenge left, aye?
• Anonymous
  June 29, 2006
  Xepol hit on one of the things I love about this problem: the question is vague. That said, by "best" I meant "consistently fastest."
  
  The other thing I love about this problem is that there are hundreds of possible solutions.
• Anonymous
  June 29, 2006
  Martin, I love your app -- it's really fun. Only one problem: your mazes don't have exits!
• Anonymous
  June 29, 2006
  The comment has been removed
• Anonymous
  June 29, 2006
  You can put the exit anywhere you like. The generator simply guarantees that there are no loops that have to be dealt with. At one time, I had a version that would calculate the two dead ends that were the farthest apart. One would be the entrance. The other was the exit.
  
  I played around with the code a bit at work today (left it there, though). It was mostly cosmetic stuff, like picking colors, sizes, and speed. I'll post it tomorrow evening when I get back home. Who knows, maybe I'll be nice and add code for the start and end dots.
• Anonymous
  June 29, 2006
  Sweet!
• Anonymous
  June 30, 2006
  I'm not sure whether or not you know the location of the exit...
  
  If you do, you could treat both the entrance and exit as starting points and try to get them to intersect.  I'm not sure if that would change how efficient it is, every cycle you are trying 2 possibilities instead of one.
  
  Then there's the branching way, where you try every possibility starting from the end and working your way backwards systematically in a recursive method.  Unfortunatly, that's a memory hog and inefficient, although intuitive.
  
  You could possibly try having each "crossroad" being a node, and each path between nodes being a path of value 1.  Apply Dijkstra's algorithm.  Hey, it might work.  The internet does it all the time.
• Anonymous
  July 01, 2006
  I've posted the updated maze generator and traversal app. I'm not happy with the way that it figures out an exit spot (i.e, it's not putting it at a dead end, let alone the farthest one from the starting position). But, I did clean the code up a bit.
  
  Enjoy.
• Anonymous
  July 12, 2006
  Wall following (keep your left hand on the wall)
  Wall following with angle counting for obstacles (Pledge algorithm)
  random moves (inefficient but surprisingly successful for information poor environments - see the Roomba at work)
  breadcrumbs/chalk marks (Trevaux algorithm)
  
  it's a fairly well-explored space (hah!) in AI - worth asking your colleagues in 112/113 ;-)