An implementation of the recursive backtracker maze generator algorithm. The API allows users to specify the probability for replacing a '.' with a '#', and generate potentially unsolvable mazes. Setting the probability to 0 guarantees that the generated maze is solvable.

RecursiveBacktrackerMazeGenerator.fs

module RecursiveBacktrackerMazeGenerator

// ++++++++++
// + Random +
// ++++++++++

module Random =
  let _rng = new System.Random()

  let nextInt lo hi = _rng.Next(lo, hi)

  let nextDouble () = _rng.NextDouble ()

// +++++++++
// + Array +
// +++++++++

module Array =
  let swap i j (a: _[]) =
      let x = a.[i]
      a.[i] <- a.[j]
      a.[j] <- x

  let shuffleInPlace xs =
    let n = Array.length xs
    for i = 0 to Array.length xs - 1 do
      swap i (Random.nextInt i n) xs

  let shuffle xs =
    let ys = Array.copy xs
    shuffleInPlace ys
    ys

// +++++++++++
// + Index2D +
// +++++++++++

module Index2D =
  let up ij =
    let struct (i, j) = ij
    struct (i - 1, j)

  let right ij =
    let struct (i, j) = ij
    struct (i, j + 1)

  let down ij =
    let struct (i, j) = ij
    struct (i + 1, j)

  let left ij =
    let struct (i, j) = ij
    struct (i, j - 1)

  let get (xss : _ [,]) (struct (i, j)) = xss.[i, j]

  let set (xss : _ [,]) x (struct (i, j)) = xss.[i, j] <- x

  let inBounds xs ij =
    let struct (i, j) = ij
    0 <= i && i < Array2D.length1 xs &&
    0 <= j && j < Array2D.length2 xs

// +++++++++
// + Int32 +
// +++++++++

module Int32 =
  let inline isEven x = x % 2 = 0

  let inline isOdd x = not (isEven x)

  let ofBool : bool -> int = System.Convert.ToInt32

// ++++++++++++++++++++++
// + The maze generator +
// ++++++++++++++++++++++

let inline wallGrid n m =
  Array2D.init n m (fun i j -> Int32.isOdd i || Int32.isOdd j)

let inline neighborsAndWalls ij =
  [| struct ((Index2D.up    >> Index2D.up   ) ij, Index2D.up    ij)
   ; struct ((Index2D.right >> Index2D.right) ij, Index2D.right ij)
   ; struct ((Index2D.down  >> Index2D.down ) ij, Index2D.down  ij)
   ; struct ((Index2D.left  >> Index2D.left ) ij, Index2D.left  ij)
  |]

let recursiveBacktracker n m =
  let makeOdd x = x + (Int32.ofBool (Int32.isEven x))
  let n2        = makeOdd n
  let m2        = makeOdd m
  let xs        = wallGrid n2 m2
  let visited   = Array2D.zeroCreate n2 m2

  let rec go current =
    Index2D.set visited true current

    let goNeighbor (struct (neighbor, wall)) =
      if Index2D.inBounds visited neighbor &&
         not (Index2D.get visited neighbor)
        then
          Index2D.set xs false wall
          go neighbor

    neighborsAndWalls current
    |> Array.shuffle
    |> Array.iter goNeighbor

  go (struct (0, 0))
  n2, m2, xs

let randomize probability xs =
  let n = Array2D.length1 xs
  let m = Array2D.length2 xs

  let modify i j x =
    if      i = 0     && j = 0     then x
    else if i = n - 1 && j = m - 1 then x
    else
      if Random.nextDouble () < probability
        then not x
        else x

  Array2D.mapi modify xs

let pretty xs =
  let n  = Array2D.length1 xs
  let m  = Array2D.length2 xs
  let sb = new System.Text.StringBuilder()

  let append (c : char) = sb.Append c |> ignore

  for i = 0 to n - 1 do
    for j = 0 to m do
      if j = m && i = n - 1 then ()
      if j = m              then append '\n'
         else
          match xs.[i, j] with
          | false -> append '.'
          | true  -> append '#'

  sb.ToString()

// +++++++
// + API +
// +++++++

let createMaze hashtagProbability rows columns =
  let rows, columns, maze = recursiveBacktracker rows columns
  rows, columns, pretty (randomize hashtagProbability maze)

let printMaze hashtagProbability rows columns =
  let rows, columns, maze = createMaze hashtagProbability rows columns

  printfn "rows:    %d" rows
  printfn "columns: %d" columns
  printfn "%s" maze