131 lines
4.3 KiB
Plaintext
131 lines
4.3 KiB
Plaintext
global showMice
|
|
|
|
import Utils # To get 'Args' singleton class
|
|
|
|
procedure main(A)
|
|
Args(A)
|
|
if \Args().get("help","yes") then helpMesg()
|
|
showMice := Args().get("showmice","yes") # Show movements of all mice
|
|
mh := Args().get("rows") | 32 # Maze height (rows)
|
|
mw := Args().get("cols") | 48 # Maze width (columns)
|
|
|
|
mz := DisplayMaze(GenerateMaze(mh,mw)) # Build and show maze
|
|
|
|
QMouse(mz.maze,findStart(mz.maze),&null,0) # Start first quantum mouse
|
|
waitForCompletion() # block until all quantum mice have finished
|
|
|
|
# Mark the best path into the maze and display it.
|
|
if showPath(mz.maze) then DisplayMazeSolution(mz) else write("No path found!")
|
|
end
|
|
|
|
procedure helpMesg()
|
|
write(&errout,"Usage: qSolve [--showmice] [--cols=C] [--rows=R]")
|
|
write(&errout,"\twhere:")
|
|
write(&errout,"\t\t--showmice # displays all mice paths as they search")
|
|
write(&errout,"\t\t--cols=C # sets maze width to C (default 16) columns")
|
|
write(&errout,"\t\t--rows=R # sets maze height to R (default 12) rows")
|
|
stop()
|
|
end
|
|
|
|
# A "Quantum-mouse" for traversing mazes. Each mouse lives for just one cell, but
|
|
# can spawn other mice to search from adjoining cells.
|
|
|
|
global qMice, bestMouse, bestMouseLock, region, qMiceEmpty
|
|
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
|
|
|
|
class QMouse(maze, loc, parent, len, val)
|
|
|
|
method getLoc(); return loc; end
|
|
method getParent(); return \parent; end
|
|
method getLen(); return len; end
|
|
method atEnd(); return EMPTY ~= iand(val, FINISH); end
|
|
method goNorth(); if EMPTY ~= iand(val,NORTH) then return visit(loc.r-1, loc.c); end
|
|
method goSouth(); if EMPTY ~= iand(val,SOUTH) then return visit(loc.r+1, loc.c); end
|
|
method goEast(); if EMPTY ~= iand(val,EAST) then return visit(loc.r, loc.c+1); end
|
|
method goWest(); if EMPTY ~= iand(val,WEST) then return visit(loc.r, loc.c-1); end
|
|
|
|
method visit(r,c)
|
|
critical region[r,c]: if EMPTY = iand(maze[r,c],SEEN) then {
|
|
if /bestMouse | (len <= bestMouse.getLen()) then { # Keep going?
|
|
mark(maze, r,c)
|
|
unlock(region[r,c])
|
|
return Position(r,c)
|
|
}
|
|
}
|
|
end
|
|
|
|
initially (m, l, p, n)
|
|
initial { # Construct critical region mutexes and completion condvar
|
|
qMice := mutex(set())
|
|
qMiceEmpty := condvar()
|
|
bestMouseLock := mutex()
|
|
region := list(*m) # Minimize critical region size
|
|
every r := 1 to *m do region[r] := list(*m[1])
|
|
every !!region := mutex()
|
|
}
|
|
maze := m
|
|
loc := l
|
|
parent := p
|
|
len := n+1
|
|
val := maze[loc.r,loc.c] | fail # Fail if outside maze
|
|
insert(qMice, self)
|
|
thread {
|
|
if atEnd() then {
|
|
critical bestMouseLock:
|
|
if /bestMouse | (len < bestMouse.getLen()) then bestMouse := self
|
|
}
|
|
else { # Spawn more mice to look for finish
|
|
QMouse(maze, goNorth(), self, len)
|
|
QMouse(maze, goSouth(), self, len)
|
|
QMouse(maze, goEast(), self, len)
|
|
QMouse(maze, goWest(), self, len)
|
|
}
|
|
|
|
delete(qMice, self)
|
|
if *qMice=0 then signal(qMiceEmpty)
|
|
}
|
|
end
|
|
|
|
procedure mark(maze, r,c)
|
|
ior(maze[r,c],SEEN)
|
|
if \showMice then markCell(r,c,"grey",5)
|
|
return Position(r,c)
|
|
end
|
|
|
|
procedure clearMaze(maze) # Clear out dregs from maze creation
|
|
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) # Anywhere in maze
|
|
clearMaze(maze) # Remove breadcrumbs
|
|
every r := 1 to *maze & c := 1 to *maze[1] do # Locate START cell
|
|
if EMPTY ~= iand(maze[r,c],START) then return mark(maze, r,c)
|
|
end
|
|
|
|
procedure showPath(maze)
|
|
if path := \bestMouse then { # Mark it in maze
|
|
repeat {
|
|
loc := path.getLoc()
|
|
maze[loc.r,loc.c] +:= PATH
|
|
path := \path.getParent() | break
|
|
}
|
|
return
|
|
}
|
|
end
|
|
|
|
procedure waitForCompletion()
|
|
critical qMiceEmpty: while *qMice > 0 do wait(qMiceEmpty)
|
|
end
|