Subject:
|
Re: New Lego challenge !
|
Newsgroups:
|
lugnet.robotics
|
Date:
|
Mon, 13 Sep 1999 15:06:43 GMT
|
Original-From:
|
Paul Speed <PSPEED@AUGUSTSCHELLavoidspam.COM>
|
Viewed:
|
527 times
|
| |
|
|
Mario Ferrari wrote:
>
> In lugnet.robotics, Laurentino Martins writes:
> > At 03:35 13-09-1999 Monday , Mike Poindexter wrote:
> > > Got it figured out. Using the principles of right handed
> > > recursion, you can have the robot follow the right wall and it
> > > will eventually get to the light and also get out of the maze
> > > again.
> > >
> > > Incidentally, right handed recursion will get you out of any
> > > labyrinth provided that you are not starting inside it already.
> > > If you are already in it, it will likely work there as well.
> > > This would then allow the robot to work in almost any maze you
> > > create.
> >
> > Yes, unfortunately the current firmware implementation from LEGO
> > doesn't have a call stack, so you can not build recursive
> > routines. :-(
>
> Actually you don't need a recursive algorithm to apply the right
> hand rule. Simply follow either the right (or left) wall and you'll
> arrive at the exit. For a maze with no exit but a "special point"
> to reach inside (like Philippe's one), the rule works if the point
> is not surrounded by a circular path. As you can easily see, the
> right (or left) hand rule works perfectly with Philippe's labyrinth.
To be more specific, the "right hand rule" is not a recursive
algorithm at all in the classic sense. We like to think of it that
way because the "traveler" will traverse parts of the maze repeatedly,
in the worst case the whole maze. However, at each point in the maze
the "traveler" has all the information is needs to take the next step.
Nothing from the past or the future is needed to make the decision.
You just go right if you can, straight if you can, left if you can,
or do a complete 180. As long as you always evaluate those four
conditions in that order then you will successfully complete the
"right hand rule".
>
> > On the other hand I can imagine labyrinths where that bot would
> > never be able to do anything out of them.
>
> The simplest way to make one of these is to violate the previous
> constraint and surround the point to reach with a circular path.
This is where massive recursion "could" come in handy. A
recursive maze traversal would reach every point in the maze.
Unless, of course, there are parts of the maze that are just plain
unreachable, but that wouldn't really be fair.
-Paul (pspeed@progeeks.com, http://www.progeeks.com/)
|
|
Message has 1 Reply:
 | | Re: New Lego challenge !
|
| (...) The right (or left (-: ) -hand rule seems to be simple but not the most efficient. That's why I included the light beacon. Providing you have the right beacon detector (let's build one!), and you don't know which direction is the best, you can (...) (25 years ago, 13-Sep-99, to lugnet.robotics)
|
Message is in Reply To:
| | Re: New Lego challenge !
|
| (...) Actually you don't need a recursive algorithm to apply the right hand rule. Simply follow either the right (or left) wall and you'll arrive at the exit. For a maze with no exit but a "special point" to reach inside (like Philippe's one), the (...) (25 years ago, 13-Sep-99, to lugnet.robotics)
|
22 Messages in This Thread:
 
  
- Entire Thread on One Page:
- Nested:
All | Brief | Compact | Dots
Linear:
All | Brief | Compact
This Message and its Replies on One Page:
- Nested:
All | Brief | Compact | Dots
Linear:
All | Brief | Compact
|
|
|
|
