Task

For a maze generated by this task, write a function
that finds (and displays) the shortest path between two cells.



Note that because these mazes are generated by the Depth-first search algorithm, they contain no circular paths,
and a simple depth-first tree search can be used.




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