Maze solving: Difference between revisions
Content deleted Content added
Line 1,479:
}
return mz
end</lang>
The following Unicon-only solution is a variant of the above. It shares the same
maze generation code and maze display code with the above but spawns threads
to parallelize the searching. The algorithm finds all solutions in the maze
and works if there are multiple exits. The shortest solution path
is then marked and displayed.
<lang unicon>global qMice, goodMice, region, qMiceLock
procedure main(A)
/mh := \A[1] | 12
/mw := \A[2] | 16
mz := DisplayMaze(GenerateMaze(mh,mw))
WriteImage(mz.filename) # save file
WAttrib(mz.window,"canvas=normal") # show it
until Event() == &lpress # wait for left mouse press
qMice := set() # Active mice
goodMice := set() # Mice that found solutions
startPos := findStart(mz.maze)
insert(qMice,QMouse(mz.maze,startPos)) # Start first quantum mouse
# block until all quantum mice have finished
critical qMiceLock: while *qMice > 0 do wait(qMiceLock)
# Mark the best path into the maze and display it.
if setPath(mz.maze, goodMice) then {
DisplayMazeSolution(mz)
WriteImage(mz.filename ?:= (="maze-", "maze-solved-" || tab(0)))
until Event() == &lpress # wait
close(mz.window)
}
else write("No path found for maze!")
end
record Position(r,c)
# Must match values used in maze generation!
$define FINISH 64 # exit
$define START 32 # entrance
$define PATH 128
$define SEEN 16 # bread crumbs for generator
$define NORTH 8 # sides ...
$define EAST 4
$define SOUTH 2
$define WEST 1
$define EMPTY 0 # like new
# A "Quantum-mouse" for traversing mazes.
class QMouse(maze, loc, path, mouse, val)
method getPath(); return path; end
method atEnd()
return 0 < iand(val, FINISH)
end
method goNorth()
if 0 < iand(val,NORTH) then return visit(loc.r-1, loc.c)
end
method goSouth()
if 0 < iand(val,SOUTH) then return visit(loc.r+1, loc.c)
end
method goEast()
if 0 < iand(val,EAST) then return visit(loc.r, loc.c+1)
end
method goWest()
if 0 < iand(val,WEST) then return visit(loc.r, loc.c-1)
end
method visit(r,c)
critical region: if 0 = iand(maze[r][c],SEEN) then {
maze[r][c] +:= SEEN
unlock(region)
return Position(r,c)
}
end
initially (m, l, p)
initial {
region := mutex(maze)
qMiceLock := mutex()
}
maze := m
loc := l
/path := []
if \p then path := copy(p)
put(path, loc)
val := maze[loc.r][loc.c] | fail
mouse := thread {
if not atEnd() then { # Spawn more mice to look for finish
insert(qMice, QMouse(maze, goNorth(), path))
insert(qMice, QMouse(maze, goSouth(), path))
insert(qMice, QMouse(maze, goEast(), path))
insert(qMice, QMouse(maze, goWest(), path))
delete(qMice, self) # This mouse didn't find a finish
}
else {
insert(goodMice, self) # This mouse found a finish
delete(qMice, self)
}
}
end
procedure clearMaze(maze)
every r := 1 to *maze & c := 1 to *maze[1] do # remove breadcrumbs
maze[r,c] := iand(maze[r,c],NORTH+EAST+SOUTH+WEST+START+FINISH)
end
procedure findStart(maze)
clearMaze(maze) # Remove breadcrumbs
h := *maze
w := *maze[1]
every ((r := 1 | h) & (c := 1 to w)) | # search perimeter
((r := 1 to h) & (c := 1 | w)) do
if iand(maze[r,c],START) > 0 then return Position(r,c)
end
procedure setPath(maze, mice)
minPathLen := *maze * *maze[1] + 1
every m := !mice do
if minPathLen >:= *m.getPath() then bestPath := m.getPath()
if \bestPath then {
every p := !bestPath do maze[p.r][p.c] +:= PATH
return
}
end</lang>
| |||