Maze solving: Difference between revisions
Content added Content deleted
m ('setq' is not needed) |
(Slightly simplified) |
||
Line 11: | Line 11: | ||
(let (Path NIL Best NIL) |
(let (Path NIL Best NIL) |
||
(recur (This Path) |
(recur (This Path) |
||
( |
(when (and This (not (: mark))) |
||
(push 'Path This) |
(push 'Path This) |
||
(if (== Goal This) |
(if (== Goal This) |
||
(unless (and Best (>= (length Path) (length Best))) |
(unless (and Best (>= (length Path) (length Best))) |
||
(setq Best Path) ) |
(setq Best Path) ) |
||
( |
(=: mark T) |
||
(recurse (: west) Path) |
|||
(recurse (: east) Path) |
|||
(recurse (: south) Path) |
|||
(recurse (: north) Path) |
|||
(=: mark NIL) ) ) ) |
|||
(=: mark NIL) ) ) ) ) |
|||
(disp Maze 0 |
(disp Maze 0 |
||
'((This) (if (memq This Best) " # " " ")) ) ) )</lang> |
'((This) (if (memq This Best) " # " " ")) ) ) )</lang> |
Revision as of 06:46, 16 December 2010
Maze solving is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
For a maze generated by this task, write a function that finds (and displays) the shortest path between two cells. Note that because these mazes are generated by the Depth-first search algorithm, they contain no circular paths, and a simple depth-first tree search can be used.
PicoLisp
<lang PicoLisp>(de shortestPath (This Goal Maze)
(let (Path NIL Best NIL) (recur (This Path) (when (and This (not (: mark))) (push 'Path This) (if (== Goal This) (unless (and Best (>= (length Path) (length Best))) (setq Best Path) ) (=: mark T) (recurse (: west) Path) (recurse (: east) Path) (recurse (: south) Path) (recurse (: north) Path) (=: mark NIL) ) ) ) (disp Maze 0 '((This) (if (memq This Best) " # " " ")) ) ) )</lang>
Using the maze produced in Maze generation#PicoLisp, this finds the shortest path from the top-left cell 'a12' to the bottom-righ exit 'p1':
: (shortestPath 'a12 'p1 (maze 16 12)) + +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ 12 | # | # # # | # # # | # # # # | # # # | + + + + + +---+ + +---+---+ + +---+ +---+ + 11 | # # | | # # | | # # | | # # | | # # | # # | + +---+ +---+---+ +---+---+ + +---+---+ +---+ +---+ 10 | | | | | # # | # # | # # | # # | | + + + +---+ + + + + +---+---+ +---+ +---+ + 9 | | | | | # | # # | # # | # | # # | # # | + +---+---+ + +---+ +---+---+ + + + +---+ + + 8 | | | | # # # | # | # # | # | # | # | + + + + + +---+---+ +---+ +---+---+ +---+ + + 7 | | | | # # # | | # # | # # | # # | # | +---+ +---+---+---+---+ +---+ +---+ + +---+ +---+ + 6 | | | | # | | | # | # # # | | # | + +---+ +---+ +---+ + +---+ + +---+---+---+ + + 5 | | | # # | | # | | # | +---+ +---+ +---+ +---+ +---+---+ + +---+ +---+ + 4 | | | | # # | | # # | # | | | # # | + +---+ +---+ +---+ +---+ + + +---+---+ + +---+ 3 | | | | | # # # | # | # # # | | # # | + +---+---+ + + +---+---+---+ +---+ + + +---+ + 2 | | | | | | # # | | # | # # # | + + + +---+ + + +---+ +---+ +---+ + +---+---+ 1 | | | | # # # | # # # +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ a b c d e f g h i j k l m n o p