Author Topic: Simple maze traversal algorithm  (Read 6035 times)

0 Members and 1 Guest are viewing this topic.

Offline prologTopic starter

  • Jr. Member
  • **
  • Posts: 9
  • Helpful? 0
Simple maze traversal algorithm
« 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
« Last Edit: December 19, 2007, 11:00:48 PM by prolog »

Offline Ro-Bot-X

  • Contest Winner
  • Supreme Robot
  • ****
  • Posts: 1,431
  • Helpful? 25
  • Store: RoBotXDesigns.ca
    • Ro-Bot-X Designs
Re: Simple maze traversal algorithm
« Reply #1 on: December 19, 2007, 11:47:31 PM »
Do a search on the forum, I posted pseudocode for that a while ago.
Check out the uBotino robot controller!

Offline prologTopic starter

  • Jr. Member
  • **
  • Posts: 9
  • Helpful? 0
Re: Simple maze traversal algorithm
« Reply #2 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 :)

Offline cooldog

  • Supreme Robot
  • *****
  • Posts: 751
  • Helpful? 4
  • be nice to nerds, one day they will be your boss
Re: Simple maze traversal algorithm
« Reply #3 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
robot will rule the world and i will be building them
-admin

favorite web sites
http://www.societyofrobots.com/
http://www.instructables.com/

Offline prologTopic starter

  • Jr. Member
  • **
  • Posts: 9
  • Helpful? 0
Re: Simple maze traversal algorithm
« Reply #4 on: December 29, 2007, 01:43:18 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

Offline paulobrasko

  • Beginner
  • *
  • Posts: 6
  • Helpful? 1
Re: Simple maze traversal algorithm
« Reply #5 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

Offline Admin

  • Administrator
  • Supreme Robot
  • *****
  • Posts: 11,702
  • Helpful? 173
    • Society of Robots

Offline Rick Brooks

  • Jr. Member
  • **
  • Posts: 13
  • Helpful? 1
    • BrooksBots
Re: Simple maze traversal algorithm
« Reply #7 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

Offline prologTopic starter

  • Jr. Member
  • **
  • Posts: 9
  • Helpful? 0
Re: Simple maze traversal algorithm
« Reply #8 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?
« Last Edit: January 04, 2008, 09:53:52 AM by prolog »

Offline prologTopic starter

  • Jr. Member
  • **
  • Posts: 9
  • Helpful? 0
Re: Simple maze traversal algorithm
« Reply #9 on: January 04, 2008, 09:58:29 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 :)

 


Get Your Ad Here