Maze solving: Difference between revisions
Content deleted Content added
| Line 2,455: | Line 2,455: | ||
│ · · · · · · · · · │ │ │ │ │ │ │ │ │ ╵ │ |
│ · · · · · · · · · │ │ │ │ │ │ │ │ │ ╵ │ |
||
└───────────────────┴───────┴───┴───────────────┴───────┴───────────┴───────┴───────────────────┴───────┴──────── │ ┘</pre></small> |
└───────────────────┴───────┴───┴───────────────┴───────┴───────────┴───────┴───────────────────┴───────┴──────── │ ┘</pre></small> |
||
=={{header|Phix}}== |
|||
Combined generator and solver. |
|||
<lang Phix>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'))</lang> |
|||
{{out}} |
|||
<pre> |
|||
+---+---+---+---+---+---+---+---+---+---+---+ |
|||
| o - o - o | o - o - o - o | | | |
|||
+ : +---+ : +---+ : +---+---+ : + + + + |
|||
| o - o | o | o - o | | o - o | | | |
|||
+---+ : + : + : +---+ + : +---+---+---+ + |
|||
| o - o | o - o | | o - o | o - o - o | |
|||
+ : +---+---+---+ +---+---+ : + : +---+ : + |
|||
| o | | o - o | | o | |
|||
+ : + +---+---+---+---+ +---+---+ + : + |
|||
| o | | | | o - |
|||
+ : +---+---+ + + +---+---+ +---+---+ |
|||
| o | | | | |
|||
+ : +---+---+---+ +---+ +---+---+ + + |
|||
| o - o - o | | * | | | | |
|||
+ +---+ : +---+---+ : + +---+---+ + + |
|||
| | o - o - o - o | | | |
|||
+---+---+---+---+---+---+---+---+---+---+---+ |
|||
</pre> |
|||
=={{header|PicoLisp}}== |
=={{header|PicoLisp}}== |
||