Tricky labyrinth solving

simba1382
46 ●1 ●2 ●6

Hello, I'm trying to do a project with some of my friends, and we came upon that:

Say I had to decipher this Labyrinth programatically, how could I go on about that? My first decision when trying to solve labyrinths by image recognition is obviously simply painting the open path, this way the paint end (The arrow in the start of the labyrinth is there to provide a way for the recognition to see 'ok that's the start')would indicate the exit.

Problem is, with those filters in place, I can't paint it, nor I have any other idea on how to solve it. So, would there be any way of doing so with Open CV? (or any other option would be fine too, if possible)

Thanks!

Comments

Why is it so noisy? Is this a kind of captcha test to keep away bots from websites?

Ben (Feb 19 '13)edit

I applied a few filters to make it harder (Since I knew how to solve a 'clean' labyrinth), the object was making the machine confused, it can't so easily determine what is path and what is wall.

simba1382 (Feb 19 '13)edit

add a comment

2 answers

Sort by » oldest newest most voted

answered Feb 19 '13

rics

1093 ●1 ●14 ●21

You can check the wiki page of Maze solving algorithms for possible solutions.

An interesting approach finds connected components of walls (second image on the right). Cris on his nice page describes how to use connected components to find the way through the maze (among other methods).

In your case first of all you should remove the lighter shade from the lower triangle by darkening all the pixels there in the value channel of the HSV color space (cvtColor and add). Next step is to remove color differences of wall and open path areas for example with a median filter or with a threshold. Then you can flood fill the image to get an image similar to this (I have done the modifications in gimp but after playing with the constant it can be done in OpenCV as well):

image description

Then - according to Cris - you can select the wall color next to the arrow and use only this color. When you dilate this binary image with a few pixels and erode it back the difference of the dilated and the eroded image gives the path through the maze.

Comments

Thanks a lot for this link, truly amazing expalanation. I'm going to test the suggestions you made me right now and see what I can learn from them.

simba1382 (Feb 19 '13)edit

add a comment

answered Feb 19 '13

Geppertm
275 ●3 ●11

Hi, I would first use some kind of threshold on the image. So you have all ways white and all walls black.

Then I would create a Integer-array with the map of the Labyrinth.

Now you can easy use the algorythm first turn left, walk forward till there´s a Wall then turn right,walk forward till wall then turn right........ This will work for the most Labyrinths.

You search all impasse [if way = 0 and wall = 1 , all the fields that border on three ones] and fill them till the next crossing. That will give you all possible ways.[work´s everytime]

You can also use: Maze Algorythm from Gaston Tarry [work´s everytime]

add a comment

Tricky labyrinth solving

Comments

2 answers

Comments

Links

Question Tools

Stats

Related questions

Tricky labyrinth solving edit savecancel

Comments

2 answers

Comments

Links

Question Tools

Stats

Related questions

Tricky labyrinth solving