Society of Robots - Robot Forum

Electronics => Electronics => Topic started by: mobz on September 17, 2007, 09:09:27 PM

Title: best maze algorithm
Post by: mobz on September 17, 2007, 09:09:27 PM
im new in robot design,so i need some advice on some good algorithms to implement in a robot to traverse a maze.
Title: Re: best maze algorithm
Post by: Admin on September 24, 2007, 07:24:59 PM
Like this?
http://www.societyofrobots.com/programming_wavefront.shtml
Title: Re: best maze algorithm
Post by: snow on September 25, 2007, 03:05:51 PM
What kind of maze? How many cells?
Title: Re: best maze algorithm
Post by: HDL_CinC_Dragon on September 25, 2007, 06:01:53 PM
Heres something you can look at:

Quote from: Wikipedia page
Wall follower
Traversal using the right-hand rule

The wall follower, the best-known rule for traversing mazes, is also known as either the left-hand rule or the right-hand rule. If the maze is simply connected, that is, all its walls are connected together or to the maze's outer boundary, then by keeping one hand in contact with one wall of the maze the player is guaranteed not to get lost and will reach a different exit if there is one; otherwise, he or she will return to the entrance. If the maze is not simply connected (i.e. if the start or endpoints are in the center of the structure or the pathways cross over and under each other), this method will not be guaranteed to help the goal to be reached.

I couldnt find the wiki page on the Right-Hand rule for mazes, all I could find was the above small excerpt from Link (http://en.wikipedia.org/wiki/Maze)

It will help you if your maze is in fact "simply connected"
Title: Re: best maze algorithm
Post by: awally88 on September 26, 2007, 04:53:50 AM

Just put a big-arsed circular saw on the front and cut through the maze, if you're maze is made of thick steel or concrete it might be better to use the RH rule though ;)
Title: Re: best maze algorithm
Post by: Ro-Bot-X on September 26, 2007, 10:49:14 AM
If you need to solve the maze, meaning to find the shortest path to the exit, here's an ideea for you:

Have your robot built with sensors that will detect openings on both sides.
Make an array of nodes, all being 0 at start.
Follow the RH style driving, but every time you get at a opening to a side, that is a node, add a 1 to the value in the array if you turn right, a 2 if you go forward, or a 3 if you turn left. If the sum equals 4, make it 0 again and go to the previous node instead to the next node.
When the robot exits the maze, put it back at the begining without turning it off and have it follow the array every time it turns.

Lets have an example:
   i ______________
|    __    |__       ___ o
|   |____|       |____|
|_________|______| 

i means in and o means out

At the entrance there is an opening to the left, so following the RH rule, we go straight, that means we add a 2 to the N1 in the array. Two cells down we have another opening to the left, we turn left and add a 3 to the second node of the array, N2. Then we have a 3 for the third node, then a 1 to the N4 node, then a 1 to the N5 node, a 3 to the N6 node, then we hit the dead end. We turn around, and when we get to the opening to the right, we add a 1 to the N6 node. So N6 will now be 4, we make it 0 again and at the next opening (on the left) we go straight so we add a 2 to the N5 node, N5 will now have the value 3. We go to the next cell and we turn right so we write a 1 to the N6 node, move to the next cell and turn right again, adding a 1 to the N7 node, add a 1 to the N8 node, hit another dead end, turn back, add a 3 to the N8 node, N8 will be now reset to 0, add a 1 to the N7 node, N7 will have the value 2 and we got at the exit. We ended up with this array:

N1  N2  N3  N4  N5  N6  N7  N8  N9  N10
 2    3    3    1    3    1    2    0    0     0

Now the robot will take each turn using the value in the array, taking the shortest path to the exit.

Hope this helps...