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

0 Members and 2 Guests 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 »
Logged

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.
Logged
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 :)
Logged

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
Logged
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 »
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
Logged

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
Logged

Offline Admin

  • Administrator
  • Supreme Robot
  • *****
  • Posts: 11,704
  • Helpful? 173
    • Society of Robots
Re: Simple maze traversal algorithm
« Reply #6 on: December 31, 2007, 03:44:00 PM »
Logged

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
Logged

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 »
Logged

Offline prologTopic starter

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

SMF spam blocked by CleanTalk