Message Boards Message Boards

11
|
18951 Views
|
4 Replies
|
18 Total Likes
View groups...
Share
Share this post:

Solving mazes with Wolfram Language and Mathematica

Posted 11 years ago
Recently Ed Pegg shared an interesting research about constriction of complex mazes by computers that are influenced by some human designs. I was curious how Mathematica will do in automated maze solving of this type. I grabbed a screenshot of the following maze:



Because this image will now be stored on Wolfram Community servers we can use its URL to import it to Mathematica:

img = Import["http://goo.gl/IUUtVC"];

In WL I am aware of two ways to solve a maze: using WatershedComponents and using Pruning. The code is really minimal and here are the results: 

sol1 = Image[Clip[1 - WatershedComponents[Binarize@img], {0, 1}]];
HighlightImage[img, Dilation[sol1, 1], "HighlightColor" -> Red]



sol2 = Pruning[Thinning[Binarize@img], Infinity];
HighlightImage[img, Dilation[sol2, 1], "HighlightColor" -> Red]



These implementations find all possible solution paths and we can actually check that the solutions are identical:

HighlightImage[sol2, Dilation[sol1, 2]]



Is anyone aware of any other methods? By the way take a look at some great maze Demonstrations our users crated. These include also maze-generation algorithms. I very memorable Demonstration is by Stan Wagon and colleagues Penrose's Railway Mazes – see animation below. Share your own experience with WL and mazes!

POSTED BY: Vitaliy Kaurov
4 Replies
Posted 11 years ago
VERY cool!

I love maze solving (best thing about eating at a family restaurant is taking the child placemats with mazes on them to solve).
BTW - the simplest 2D maze to solve with a CA is the dead-end elimination algorithm (chpt. 3, p.25 in my 1994 "Modeling Nature" book - taken from Dr. Dobb's JournalVolume 18 Issue 2, Feb. 1993 Pages 32-38) . But that only works for looking at the entire maze from 'on high' (looking down at it), not when you're IN the maze.
POSTED BY: Richard Gaylord
Thank you, Richard, I am glad you enjoyed the post. It's interesting that you mentioned that a Cellular Automaton (CA) can solve a maze. I will try to find your book, in meantime I point out a Demonstration by Alexander Varga that uses a CA to solve a maze - it is related to a Wolfram Science Summer School project - Search for a Polyomino with a Forced Aperiodic Tiling - he did in 2012.

Maze Solving with a 2D Cellular Automaton

POSTED BY: Vitaliy Kaurov
Well...since you ask... There were a series of blog posts on the subject:

which solved Blenheim Maze based on its the areal image including usage of graph-theoretical tools.






[Shared at request of Vitaliy-- it began as private email response to "Is anyone aware of any other methods?". In that vein, a hot area of late is getting slime molds to do mazes. I have this mental image: "No, back up...yeah, that's right...good slime mold...here's a sugar treat..."]
POSTED BY: Daniel Lichtblau
Haha, a nice brute force approach! Finding the shortest path, though, may be out of slime molds' reach - it'll loose to graph theory. And even though backing up is constraint by sugar treats - it will still probably exit the way it came - undeniable power of random walks ;-)
POSTED BY: Vitaliy Kaurov
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract