Society of Robots - Robot Forum

Software => Software => Topic started by: prolog on December 19, 2007, 10:50:31 PM

Title: Simple maze traversal algorithm
Post by: prolog on December 19, 2007, 10:50:31 PM: [youtube=425,350]jjDKgY7Cnsc[/youtube]

Does anyone know a simple algorithm to traverse a simple maze (which has no loops and has only one way out)....

As far as my high school C++ knowledge goes, I have to use the depth first search algorithm, just like traversing a tree.
How can I make the robot 'remember' the solution without using pointers?

By the way, my controller is pic16F877A, which has very limited RAM
Title: Re: Simple maze traversal algorithm
Post by: Ro-Bot-X on December 19, 2007, 11:47:31 PM: Do a search on the forum, I posted pseudocode for that a while ago.
Title: Re: Simple maze traversal algorithm
Post by: prolog on December 20, 2007, 12:26:02 AM: I did search the forum before posting

I entered "maze" but didn't find anything related to it

http://www.societyofrobots.com/robotforum/index.php?topic=2001.0

and

http://www.societyofrobots.com/robotforum/index.php?topic=1688.0

Thanks :)
Title: Re: Simple maze traversal algorithm
Post by: cooldog on December 20, 2007, 06:33:44 AM: the robot that you posted is just a line follower that turns around at the end of the line

also does the robot hafe to follow lines or stay inside the lines
Title: Re: Simple maze traversal algorithm
Post by: prolog on December 29, 2007, 01:43:18 AM: Quote from: cooldog on December 20, 2007, 06:33:44 AM
the robot that you posted is just a line follower that turns around at the end of the line

I don't think it's just a line follower, bro

It 'remembers' the traversed paths. I guess it's using Stack
Title: Re: Simple maze traversal algorithm
Post by: paulobrasko on December 31, 2007, 03:40:17 PM: You could use a sharp IR range finder sensor if your maze is made of real walls instead of lines drawn in the floor. There is at least one good tutorial in the SoR that I read before explaining how to determine a wall and give good hints in terms of determining if a hole in the wall is big enough for your robot to pass through. Look at SENSORS - SHARP IR RANGE FINDER tutorial. It is out somewhere.

Paulo Brasko
Title: Re: Simple maze traversal algorithm
Post by: Admin on December 31, 2007, 03:44:00 PM: http://www.societyofrobots.com/sensors_sharpirrange.shtml
Title: Re: Simple maze traversal algorithm
Post by: Rick Brooks on January 01, 2008, 09:21:04 AM: The robot in the video looks like Mike Dvorsky's "WhoseLost" that took second place at last year's CIRC contest.
http://circ.mtco.com/competitions/2007/linemaze.htm
Mike has an excellent writeup on his algorithm on CIRC's Yahoo groups.
http://f1.grp.yahoofs.com/v1/cFV6R-zyypYUB4O7FfsJLGj9a0r7e_hKOUJAM8THtryJ0Pj-JVBfHKnmh7ODokJgjshY8ucis6PKxxL7DrXD5Jr-ygYamhOw_rBhYVRx/Line%20Maze%202.pdf
Additional questions could be posted to the CIRC's Yahoo groups for Mike.

Rick Brooks
Title: Re: Simple maze traversal algorithm
Post by: prolog on January 04, 2008, 09:53:12 AM: The line maze is exactly what i'm looking for...

By the way, the second link is dead
Can I have the address of the yahoo group?
Title: Re: Simple maze traversal algorithm
Post by: prolog on January 04, 2008, 09:58:29 AM: Quote from: prolog on January 04, 2008, 09:53:12 AM

By the way, the second link is dead
Can I have the address of the yahoo group?

I got it..
http://tech.groups.yahoo.com/group/circgroup/

Thanks :)