59 lines
1.8 KiB
Text
59 lines
1.8 KiB
Text
-- demo\rosetta\Maze_solving.exw
|
|
constant w = 11, h = 8
|
|
|
|
sequence wall = join(repeat("+",w+1),"---")&"\n",
|
|
cell = join(repeat("|",w+1)," ? ")&"\n",
|
|
grid = split(join(repeat(wall,h+1),cell),'\n')
|
|
|
|
procedure amaze(integer x, integer y)
|
|
grid[y][x] = ' ' -- mark cell visited
|
|
sequence p = shuffle({{x-4,y},{x,y+2},{x+4,y},{x,y-2}})
|
|
for i=1 to length(p) do
|
|
integer {nx,ny} = p[i]
|
|
if nx>1 and nx<w*4 and ny>1 and ny<=2*h and grid[ny][nx]='?' then
|
|
integer mx = (x+nx)/2
|
|
grid[(y+ny)/2][mx-1..mx+1] = ' ' -- knock down wall
|
|
amaze(nx,ny)
|
|
end if
|
|
end for
|
|
end procedure
|
|
|
|
integer dx,dy -- door location (in a wall!)
|
|
|
|
function solve_maze(integer x, y)
|
|
sequence p = {{x-4,y},{x,y+2},{x+4,y},{x,y-2}}
|
|
for d=1 to length(p) do
|
|
integer {nx,ny} = p[d]
|
|
integer {wx,wy} = {(x+nx)/2,(y+ny)/2}
|
|
if grid[wy][wx]=' ' then
|
|
grid[wy][wx] = "-:-:"[d] -- mark path
|
|
if {wx,wy}={dx,dy} then return true end if
|
|
if grid[ny][nx]=' ' then
|
|
grid[ny][nx] = 'o' -- mark cell
|
|
if solve_maze(nx,ny) then return true end if
|
|
grid[ny][nx] = ' ' -- unmark cell
|
|
end if
|
|
grid[wy][wx] = ' ' -- unmark path
|
|
end if
|
|
end for
|
|
return false
|
|
end function
|
|
|
|
function heads()
|
|
return rand(2)=1 -- toin coss 50:50 true(1)/false(0)
|
|
end function
|
|
|
|
integer {x,y} = {(rand(w)*4)-1,rand(h)*2}
|
|
amaze(x,y)
|
|
-- mark start pos
|
|
grid[y][x] = '*'
|
|
-- add a random door (heads=rhs/lhs, tails=top/btm)
|
|
if heads() then
|
|
{dy,dx} = {rand(h)*2,heads()*w*4+1}
|
|
grid[dy][dx] = ' '
|
|
else
|
|
{dy,dx} = {heads()*h*2+1,rand(w)*4-1}
|
|
grid[dy][dx-1..dx+1] = ' '
|
|
end if
|
|
{} = solve_maze(x,y)
|
|
puts(1,join(grid,'\n'))
|