Anonymous user
Maze solving: Difference between revisions
→{{header|Nim}}
Line 3,249:
{{Out}}
[[File:MathematicaMazeGraphSolving.png]]
=={{header|Nim}}==
{{trans|Go}}
<lang Nim>import random, strutils
type
Direction {.pure.} = enum None, Up, Left, Down, Right
Maze = object
cells: seq[string]
hwalls: seq[string]
vwalls: seq[string]
####################################################################################################
# Maze creation.
func initMaze(rows, cols: Positive): Maze =
## Initialize a maze description.
var h = repeat('-', cols)
var v = repeat("|", cols)
for i in 0..<rows:
result.cells.add newString(cols)
result.hwalls.add h
result.vwalls.add v
proc gen(maze: var Maze; r, c: Natural) =
## Generate a maze starting from point (r, c).
maze.cells[r][c] = ' '
var dirs = [Up, Left, Down, Right]
dirs.shuffle()
for dir in dirs:
case dir
of None:
discard
of Up:
if r > 0 and maze.cells[r-1][c] == '\0':
maze.hwalls[r][c] = chr(0)
maze.gen(r-1, c)
of Left:
if c > 0 and maze.cells[r][c-1] == '\0':
maze.vwalls[r][c] = chr(0)
maze.gen(r, c-1)
of Down:
if r < maze.cells.high and maze.cells[r+1][c] == '\0':
maze.hwalls[r+1][c] = chr(0)
maze.gen(r+1, c)
of Right:
if c < maze.cells[0].high and maze.cells[r][c+1] == '\0':
maze.vwalls[r][c+1] = chr(0)
maze.gen(r, c+1)
proc gen(maze: var Maze) =
## Generate a maze, choosing a random starting point.
maze.gen(rand(maze.cells.high), rand(maze.cells[0].high))
####################################################################################################
# Maze solving.
proc solve(maze: var Maze; ra, ca, rz, cz: Natural) =
## Solve a maze by finding the path from point (ra, ca) to point (rz, cz).
proc rsolve(maze: var Maze; r, c: Natural; dir: Direction): bool {.discardable.} =
## Recursive solver.
if r == rz and c == cz:
maze.cells[r][c] = 'F'
return true
if dir != Down and maze.hwalls[r][c] == '\0':
if maze.rSolve(r-1, c, Up):
maze.cells[r][c] = '^'
maze.hwalls[r][c] = '^'
return true
if dir != Up and r < maze.hwalls.high and maze.hwalls[r+1][c] == '\0':
if maze.rSolve(r+1, c, Down):
maze.cells[r][c] = 'v'
maze.hwalls[r+1][c] = 'v'
return true
if dir != Left and c < maze.vwalls[0].high and maze.vwalls[r][c+1] == '\0':
if maze.rSolve(r, c+1, Right):
maze.cells[r][c] = '>'
maze.vwalls[r][c+1] = '>'
return true
if dir != Right and maze.vwalls[r][c] == '\0':
if maze.rSolve(r, c-1, Left):
maze.cells[r][c] = '<'
maze.vwalls[r][c] = '<'
return true
maze.rsolve(ra, ca, None)
maze.cells[ra][ca] = 'S'
####################################################################################################
# Maze display.
func `$`(maze: Maze): string =
## Return the string representation fo a maze.
const
HWall = "+---"
HOpen = "+ "
VWall = "| "
VOpen = " "
RightCorner = "+\n"
RightWall = "|\n"
for r, hw in maze.hwalls:
for h in hw:
if h == '-' or r == 0:
result.add HWall
else:
result.add HOpen
if h notin {'-', '\0'}: result[^2] = h
result.add RightCorner
for c, vw in maze.vwalls[r]:
if vw == '|' or c == 0:
result.add VWall
else:
result.add VOpen
if vw notin {'|', '\0'}: result[^4] = vw
if maze.cells[r][c] != '\0': result[^2] = maze.cells[r][c]
result.add RightWall
for _ in 1..maze.hwalls[0].len:
result.add HWall
result.add RightCorner
#———————————————————————————————————————————————————————————————————————————————————————————————————
when isMainModule:
const
Width = 8
Height = 8
randomize()
var maze = initMaze(Width, Height)
maze.gen()
var ra, rz = rand(Width - 1)
var ca, cz = rand(Height - 1)
while rz == ra and cz == ca:
# Make sur starting and ending points are different.
rz = rand(Width - 1)
cz = rand(Height - 1)
maze.solve(ra, ca , rz, cz)
echo maze</lang>
{{out}}
<pre>+---+---+---+---+---+---+---+---+
| | > > > > > > > > > > v |
+ + ^ +---+---+---+---+ v + +
| | ^ < < | | v | |
+ +---+ ^ + +---+ + v +---+
| | ^ | | | > > v |
+ +---+ ^ +---+---+ +---+ v +
| | ^ | | v |
+---+ + ^ + + +---+---+ v +
| | ^ | | | v |
+ +---+ ^ +---+---+ + + v +
| > > > > ^ | | | | v |
+ ^ +---+---+ + +---+ + v +
| ^ < < | F | | v |
+---+ ^ + ^ +---+---+---+---+ v +
| S | ^ < < < < < < < < < < |
+---+---+---+---+---+---+---+---+</pre>
=={{header|Perl}}==
| |||