Maze-solving algorithm: Difference between revisions

Revision as of 20:55, 4 November 2009

Revision as of 22:02, 6 December 2009

Line 24:

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.

Note that the usehand ofis "totalremoved from the wall only when both turning"sum ratherof thanturns justmade" theand "current directionheading" are at zero. This allows the algorithm to avoid traps shaped like an upper case letter "G". IfAssuming onethe proceedsalgorithm turns left intoat the trapfirst wall, one gets turned around a full 360 [[degree (angle)|degree]]s by the walls. AAn naivealgorithm that only keeps track of "current directionheading" algorithm getsleads into aan limitinfinite cycleloop 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 total"sum turningof turns made" not being zero at that point. It follows the wall all the way around, finally leaving it heading left onoutside and just underneath the bottomletter outsideshape.

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.