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

1. Steve Eck says:

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.

2. Jeff Parker says:

There are actually several ways to do this some more practical than others and it is also going to depend on the types of mazes.

For example you could have mazes that just go on the X and Y plains, you could have a Maze that goes on X,Y and Z like a dungeon in a game, or you could have any of the other 2 that has special portals and so on. Then there are Mazes that follow all kinds of different directions. For ease of explaining I will use a maze presumably drawn on graph paper so that there is only 4 directions you can go.

Probably the easiest and fastest way for a computer to solve the maze is use the dead end filler technique. Where you go through and find each square dead end and fill it in or mark it as dead until you reach a spot that has another direction, just go through and do that for each dead end, as you do this more and more dead ends will be found eventually leaving only the possible path or paths if there are more than one through the maze.

Another way if you want to act like a person is to build a recursive algorithm that keeps track of where you have been, you would want 2 type of data stores keeping track of where you have been as well. The primary one you will be building is a tree structure, each node is a square in the maze which could have possible branches of up, down, left and right. You also need to shove each of thee nodes as a reference in and an easily searchable data structure to form a grid like maybe an array list of array lists. This way you can use the always go left method or you can use a pick and new direction at random or you can go right, which will then let you back up the the tree if you get in a dead end, however you need to always check the other data structure that is a grid and see if you have been in that place before, if so then you know your in a loop and you can back out, and what I mean by back out is tread running into yourself as a dead end. So basically you are doing a Depth first search and building the tree and then also a breadth search on the tree to see if you have been there before. This is definitely not the fastest way but it should find your way through all the time. There is a name for that algorithm but I can remember of the top of my head but the algorithm wasn’t invented for a computer to use but a human in a hedge maze. The Data stores and using a tree structure is just my thinking about that method.

3. Alex O says:

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.

4. Martin Soles says:

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.

5. Xepol says:

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 5000×5000 cell maze, but it might on a 20×20 maze.  Does it matter how long a machine takes to process the solution?

If you can’t define best, you can’t find it.

6. Martin Soles says:

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.

Just extract, compile, and watch the programmer art (and lack of comments, I know).

7. Massif says:

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.

8. 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?

9. orcmid says:

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.

10. orcmid says:

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?

11. johnmont says:

Xepol hit on one of the things I love about this problem: the question is vague. That said, by "best" I meant "consistently fastest."

12. johnmont says:

Martin, I love your app — it’s really fun. Only one problem: your mazes don’t have exits!

13. orcmid says:

I couldn’t help thinking about this more.  There obviously needs to be an XML schema for sharing mazes.

Then we can have maze wars!  Demonic composers against Angelic solvers.  Heh, heh, heh.

[The King County Metro bus system finds really wacky itineraries, by the way.  It also will fail to find a route that passes near a desired destination.  I agree it is too-hard of a problem.]

Now, in representing a maze in a formal way, there need be no fixed topology as long as there’s at least one entry point and at least one (possibly-hidden) different exit for any starting point chosen.

Also, there does need to be some way to tell the reverse of an entrance into any node.

One could use applications to decorate mazes and then consider additional functionality (hazards, one-way passages, randomly reconnecting points, nodes where it is hard to tell if it is one that has been visited before, etc.)

OK, on lunch break, have errands and work to do.

What a great set of possibilities though.

What are the chances for a meet-the-NPT-team geek dinner?

14. Martin Soles says:

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.

15. johnmont says:

Sweet!

16. scali says:

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.

17. Martin Soles says:

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.

18. 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)