Is there a way to write code for a Boe-Bot to solve a maze regardless of the maze's pattern or set up using QTI sensors? I have a Board of Education with a BS2 chip. I have not been very successful in coding it so far. Thank you for any help.
The brute force way is to use either the right or left turn rule. That is, for the right turn rule always turn right whenever there is a right or T junction encountered, and reverse direction when a dead end is encountered. Substitute left for right if using left turn rule.
Let me rephrase that. The left/right turn rule works for traversing any maze that has an entrance, an exit, and one or more routes through it. The entrance and exit could be the same point. Every robot maze I have ever been involved in from the mid 70's to the present has had a separate entrance and exit and one or more possible routes between them.
Whit, thanks for the pointer as that code was interesting to read. It looks like they use a random walk to find the exit. That's not as bad an idea as it first seems because it would eventually solve a maze with a loop in it.
Most mazes are generally standard mazes. The maze is on a single level, has the entrance and exit on the outside, and all the walls are connected. For this kind of maze the right hand rule works fine. To a computer scientist, such a maze is really a tree, and you are doing a depth first search. Here's a cool video which illustrates this concept:
The right hand rule is a good place to start, but technically this algorithm is maze running, not maze solving. A maze solver records the path through the maze, and when it back tracks it edits out the unproductive turns. The second time it runs the maze it will go directly from start to finish. I haven't written one of these for a BS2 robot, and frankly it seems hard given the constrained programming environment on the BS2.
Years ago I wrote a maze solver on a desktop computer for a virtual mouse which used Tremaux's algorithm. Here's a video (not mine) which shows how it works:
My program actually produced similar output though, but it is long lost now. Another technique is called dead end filling which looks like the following:
Comments
http://forums.parallax.com/showthread.php?p=797492
Let us know how it goes!
The right turn rule applied here will return to the START point without ever entering END.
I believe, however, that if all the maze walls are connected, it will work.
-Phil
Most mazes are generally standard mazes. The maze is on a single level, has the entrance and exit on the outside, and all the walls are connected. For this kind of maze the right hand rule works fine. To a computer scientist, such a maze is really a tree, and you are doing a depth first search. Here's a cool video which illustrates this concept:
http://www.youtube.com/watch?v=k1tSK5V1pds
The right hand rule is a good place to start, but technically this algorithm is maze running, not maze solving. A maze solver records the path through the maze, and when it back tracks it edits out the unproductive turns. The second time it runs the maze it will go directly from start to finish. I haven't written one of these for a BS2 robot, and frankly it seems hard given the constrained programming environment on the BS2.
Years ago I wrote a maze solver on a desktop computer for a virtual mouse which used Tremaux's algorithm. Here's a video (not mine) which shows how it works:
http://www.youtube.com/watch?v=6OzpKm4te-E&NR=1&feature=fvwp
My program actually produced similar output though, but it is long lost now. Another technique is called dead end filling which looks like the following:
http://www.youtube.com/watch?v=FkueaIT6RSU&NR=1