158 lines
4.1 KiB
Nim
158 lines
4.1 KiB
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
|