Hippiekinkster
Posts: 5512
Joined: 11/20/2007
From: Liechtenstein
Status: offline
|
quote:
ORIGINAL: SampsonFL
That works in what are called non-disjoint mazes.
Disjoint mazes are like a maze inside a maze so the hand-on-the-wall trick won't get you all the way out.
Still, it's a good trick to know.
"Disjoint mazes can still be solved with the wall follower method, if the entrance and exit to the maze are on the outer walls of the maze. If however, the solver starts inside the maze, it might be on a section disjoint from the exit, and wall followers will continually go around their ring. The Pledge algorithm (named after Jon Pledge of Exeter) can solve this problem (see "Turtle Geometry: the computer as a medium for exploring mathematics", Abelson & diSessa, 1980).
The Pledge algorithm, designed to circumvent obstacles, requires an arbitrarily chosen direction to go toward. When an obstacle is met, one hand (say the right hand) is kept along the obstacle while the angles turned are counted. When the solver is facing the original direction again, and the angular sum of the turns made is 0, the solver leaves the obstacle and continues moving in its original direction.
The hand is removed from the wall only when both "sum of turns made" and "current heading" are at zero. This allows the algorithm to avoid traps shaped like an upper case letter "G". Assuming the algorithm turns left at the first wall, one gets turned around a full 360 degrees by the walls. An algorithm that only keeps track of "current heading" leads into an infinite loop as it leaves the lower rightmost wall heading left and runs into the curved section on the left hand side again. The Pledge algorithm does not leave the rightmost wall due to the "sum of turns made" not being zero at that point. It follows the wall all the way around, finally leaving it heading left outside and just underneath the letter shape.
This algorithm allows a person with a compass to find his way from any point inside to an outer exit of any finite and fair two-dimensional maze, regardless of the initial position of the solver. However, this algorithm will not work in doing the reverse, namely finding the way from an entrance on the outside of a maze to some end goal within it." Wiki
I don't think one would need a compass if the sum of the right-angle turns is some multiple of 360 degrees. Note the last sentence.
Guess it depends where ya start, eh? Good point.
_____________________________
"We are convinced that freedom w/o Socialism is privilege and injustice, and that Socialism w/o freedom is slavery and brutality." Bakunin
“Nothing we do, however virtuous, can be accomplished alone; therefore we are saved by love.” Reinhold Ne
|
RE: Get lost in a corn maze? Call 911! - 
Profile
New Messages
No New Messages
Hot Topic w/ New Messages
Hot Topic w/o New Messages
Locked w/ New Messages
Locked w/o New Messages
Post New Thread