Ask Your Question
0

Tricky labyrinth solving

asked 2013-02-18 19:25:18 -0500

simba1382 gravatar image

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!

edit retag flag offensive close merge delete

Comments

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

Ben gravatar imageBen ( 2013-02-19 02:37:08 -0500 )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 gravatar imagesimba1382 ( 2013-02-19 07:37:46 -0500 )edit

2 answers

Sort by » oldest newest most voted
3

answered 2013-02-19 02:34:49 -0500

rics gravatar image

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.

edit flag offensive delete link more

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 gravatar imagesimba1382 ( 2013-02-19 07:56:53 -0500 )edit
0

answered 2013-02-19 02:06:25 -0500

Geppertm gravatar image

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.

or

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]

edit flag offensive delete link more
Login/Signup to Answer

Question Tools

Stats

Asked: 2013-02-18 19:25:18 -0500

Seen: 1,435 times

Last updated: Feb 19 '13