Growing Tree Algorithm for Maze Generation

let directions = [|
    0, 1   // down
    1, 0   // right
    0, -1  // up
    -1, 0  // left
|]

type CellType = Free | Wall

/// Several heuristics for choosing the next cell
type GrowMethod = 
    | RecursiveBacktracker 
    | Prim 
    | ChooseTheOldest
    (overriden ToString())

let createMaze xMax yMax =
    let maze = Array2D.create xMax yMax Wall
    // Check if (x, y) are valid coordinates
    let inline inMaze x y = 0 <= x && x < xMax && 0 <= y && y < yMax

    // The wall at (x, y) between current cell and another can be removed 
    // if all it's neighbors are walls too (we leave a border of walls)
    let canRemoveWall x y = 
        let dirs =
            directions |> Array.sumBy (fun (dx, dy) ->
                let x', y' = x + dx, y + dy
                if inMaze x' y' && maze.[x', y'] = Wall then 1 else 0)
        dirs = 3

    // Check if a cell is not free yet and the wall can be removed
    let getPossibleDirections (x, y) = async {
        return directions |> Array.filter (fun (dx, dy) ->
            let x', y' = x + dx, y + dy
            inMaze x' y' && maze.[x', y'] = Wall && canRemoveWall x' y')}
    maze, getPossibleDirections

let inline map f (x, y) = f x, f y

type MazeControl() as this =
    inherit UserControl()

    let pause() = Async.Sleep 25

    let canvas = Canvas(Background = SolidColorBrush Colors.Blue)
    do this.Content <- canvas

    // Create a rectangle at the cell: current - red, others - white
    let createRectangle (cell, current) = (...)

    // Fill a cell with corresponding color
    let fill = createRectangle >> canvas.Children.Add
 
    
    let drawMaze xMax yMax growMethod =
        (...)
        let maze, getPossibleDirections = createMaze xMax yMax
        // List of the cells to choose from
        let cells = new ResizeArray<_>()
        
        // To get the Recursive Backtracker we choose the most recent cell
        // For Prim - the random one
        // And the third one - the oldest
        let chooseNext() = 
            let ind = 
                match growMethod with
                | RecursiveBacktracker -> cells.Count - 1
                | Prim -> rand.Next cells.Count
                | _ -> 0
            cells.[ind]

        // Choose a start point
        let sx, sy = rand.Next (1, xMax-1), rand.Next (1, yMax-1)
        maze.[sx, sy] <- Free
        cells.Add (sx, sy)

        // Draw the maze
        let rec run() = async {
            if cells.Count = 0 then () // If there're no cells - finish
            else
                // Go to the next cell and draw it as current
                let cell = chooseNext()
                fill (cell, true) 
                do! pause()

                let! possibleDirections = getPossibleDirections cell
                match possibleDirections.Length with
                | 0 -> cells.Remove cell |> ignore  // There's no way to go - remove it
                | len -> 
                    // Randomly choose a direction
                    let dx, dy = possibleDirections.[rand.Next len]
                    let x, y = fst cell + dx, snd cell + dy
                    maze.[x, y] <- Free
                    // Add to list as a candidate for a futures growth
                    cells.Add (x, y)
               
                fill (cell, false) // It's not current any more
                do! run()  
        }
        run()
    
    /// Drawing a 21x21 maze with a specified method
    member this.DrawMaze growMethod =
        Async.CancelDefaultToken() // Cancel drawing of the previous maze
        canvas.Children.Clear()  
        drawMaze 21 21 growMethod |> Async.StartImmediate