loading

Hello fellow makers, lazy guys and curious types!

This ible will teach you how to automate solving mazes - to solve any maze in well under a minute. You will learn to solve simple digital maze as well as photos of printed out maze puzzles (this one is a bit more complex but I promised solving mazes in under a minute so... how complex can it be :) How and why this works will be explained as well.

Since I know someone is going to ask sooner or later: I got all mazes used in this Ible from HERE. it is one of better maze generator I found.

What you will need:

  • A computer (any - Raspberry Pi is more than enough)
  • image processing program (any - even MS Paint will do; Gimp (which is free) is recommended, Photoshop may be a bit better though)

Yes , that is it. So let's get started! (And don't forget to vote for me in how to play a game contest and automation contest if you like it :)

Step 1: Using MS Paint (or Any Other Software)

Microsoft Paint might be useless when it comes to image processing but it has all the necessary tools for solving mazes. For small ones (like the one on above pictures) this is the best option. No preparations needed whatsoever - two quick steps and you are done.

The process:

  1. Open a maze in your favourite image editor.
  2. Fill one border with colour of your choice by clicking it with paint bucket tool.
  3. Follow the gap between the two colours (original and painted border) with paint brush.

if anything isn't clear, see images with comments above. They should help.

That is absolutely it! You solved that maze in well under a minute!

The part where you follow colour gap may get harder when overall maze size and complexity increase. To avoid headaches (or just support your laziness :) I prepared a tutorial that does that step for you (step 2 if you have Photoshop, step 3 if you prefer Gimp).

Step 2: Using Photoshop

You have photoshop, you are lazy and you want to solve a maze. If this description fits you, you came to the right place! (go to next step if you don't have photoshop - you can use gimp, which is free)

Without further ado, let's get to business:

  1. Open maze in Photoshop.
  2. Select one border with magic wand tool (just in case you are having hard time finding it: shortcut is W). Tolerance should be set low but actual value depends on quality of your maze image. If it is monochromatic, tolerance value 0 is ok. If not, you should fiddle with values (if you somehow can't solve your problems still, see step 4: Solving physical mazes).
  3. Go to Select > Modify > Expand... and expand border for just a bit more than half the width of white space between borders - just enough for selection borders to overlap/merge. If not expanded enough, blind trails will be marked as well (you do not want this).
  4. Go to Edit>Stroke... select fill colour and width (width depends on your maze size and density - go ahead and experiment; I usually start with width of three (3))

if anything isn't clear, see images with comments above. They should help.

Congratulations! You solved another maze in well under a minute! This method is the the best as it can be used unchanged for solving infinitely large mazes in seconds.

Step 3: Using Gimp

You are lazy, you want to solve a maze and you don't have photoshop. If this description fits you, you came to the right place!

I know I almost repeated introduction from previous step but there is a reason: there are no differences except for where functions are and how they are named!

Here we go:

  1. Open maze in Gimp.
  2. Select one border with Fuzzy select tool (just in case you are having hard time finding it: shortcut is U). Tolerance should be set low but actual value depends on quality of your maze image. If it is monochromatic, tolerance value 0 is ok. If not, you should fiddle with values (if you somehow can't solve your problems still, see step 4: Solving physical mazes).
  3. Go to Select > Grow... and expand border for just a bit more than half the width of white space between borders - just enough for selection borders to overlap/merge. If not expanded enough, blind trails will be marked as well (you do not want this).
  4. Go to Edit > Stroke Selection... note you should select desired stroke colour first. Optimal stroke width depends on your maze size and density - go ahead and experiment; I usually start with width of three (3)).

if anything isn't clear, see images with comments above. They should help.

Congratulations! You solved yet another maze in well under a minute! Ready for something a bit more serious? Go to next step (lazy ones as well - it will be fun).

Step 4: Solving Physical Mazes

100% digital monochromatic mazes are one thing but real satisfactions comes from hacking printed out mazes! It requires a bit more work (sorry lazy ones, I tricked you into coming here with "fun" :) but trust me, It is worth it!

Here we go:

  1. Start off by photographing your maze (the higher the resolution the better). Try to make maze as evenly lit as possible as it makes entire process much easier. My photo with flash was not good.
  2. If your photo is good, you may try selecting one wall with Fuzzy select tool (Gimp) or Magic wand tool (Photoshop - this one should work but in case it doesn't...) If selection looks right (one entire border is selected), proceed by instructions from previous two steps. If not, read on.
  3. Duplicate layer a few times (3x-4x). Set threshold for each layer (Gimp: Colors > Threshold... | Photoshop: Image > Adjustments > Threshold...) so that each layer is clear on specific part. Layers must contain clear portions of entire maze (fiddle with values a little
  4. Reconstruct maze by removing bad portions of each layer and merging them together (right click on layer > Merge down). If you are having problems with transparency (common in gimp), set mode of top layer to "multiply" and merge it down. Repeat for all layers.
  5. If necessary, manually reconstruct damaged portions of maze (be careful not to leave gaps or close off paths or method might not work)
  6. solve the maze as you would if you were given a clear maze to start with (steps 2 and 3 of this ible).
  7. Redraw solution on printed maze.

if anything isn't clear, see images with comments above. They should help.

This process might sound difficult but it takes you less than two minutes when you get a gang of it.

Step 5: How and Why This Works

Now that all of you know how it's done, I have a treat for you, the curious ones.

The idea behind all techniques found in this Ible come from this: every maze is nothing but two walls next to each other, each with some dead allies and turns. The two walls are not connected (see image above). Most common computer generated mazes follow this criteria though I may have lied when I said you will be able to solve any maze. You now know how to solve any maze that starts and ends outside of maze (even if it has multiple entry/exit points) while being forced to solve any maze that has start/finish in centre by hand or by splitting wall in centre finish area by hand [image 2] (note that you get two solutions from which the one that goes through newly formed hole should be discarded - thank you alames). Be aware however, that this method does require some trial and error. In most cases cutting outside wall does the job but in some cases, you will need to experiment.

mazes with finish in centre could also be solved by rule of right turn (which works on all solvable mazes from either start or finish position)(for those who don't know it: you turn right at each intersection or dead end; lefts work as well so long as you always turn in same direction) which could be relatively easily done by computer program.

If enough of you show support I might write an app for solving mazes. it should be a fun practice in implementing motion tracking and feature detection algorithms.

Do not hesitate to leave any questions and feedback in comments. If you enjoyed this Ible, vote for me in "how to play ___ challenge" and "automation contest". Thanks!

For a maze with start or end at the center, split the boundary around the center ending. now you have 2 separate boundaries and can proceed as before. <br>If you have multiple starts or ends in the middle, split them all. You get multiple connected boundaries, red, blue, green, purple. Each color leads from one start or end to another.
<p>if it only has one wall (ends in centre) you may need to experiment where to cut it. Sometimes around centre (like you said), sometimes around outside border. After you try a few mazes, you will begin to see where to cut it without trying a few cuts first.</p>
<p>I couldn't understand it</p>
<p>This might help: download maze from http://www.mazegenerator.net/ (hit generate, download as png), open maze in paint and click one wall wit paint bucket tool (choose some colour first). Follow the gap between black and newly coloured border and you are done.</p>
<p>it says it is not valid so what do i do now?</p>
What is not valid?
<p>Work like a charm, smart and incredible simple. </p>
<p>This works so well:D</p>
<p>cool!</p>
thanks
<p>This is pretty smart!</p>
<p>What is the hoe to play challenge...do we use garden tools? ;P</p>
<p>Great ible', by the way. Very well done and I liked the explanation and thought that went into it.</p>
<p>I was absolutely blown away by this! Maze creators hate me!</p>
Clever! I like the &quot;out of the box&quot; thinking. Wouldn't have thought to use something like that to do it.

About This Instructable

7,599views

75favorites

License:

Bio: An engineer by trade, an artist by heart. Here to share my knowledge, ideas and methods.
More by ptkrf:Carving a Zucchini Pumpkin Glowing dog pedant Star Wars themed retro arcade game 
Add instructable to: