open System.Windows open System.Windows.Controls open System.Windows.Media open System.Windows.Shapes open System.Collections.Generic // [snippet: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 (*[omit:(overriden ToString())]*) with override this.ToString() = match this with | RecursiveBacktracker -> "Recursive Backtracker" | Prim -> "Prim" | ChooseTheOldest -> "Choose the Oldest"(*[/omit]*) 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) = (*[omit:(...)]*) let color, offset, size = if current then Colors.Red, 2., 6. else Colors.White, 0.5, 9. let x, y = map (fun x -> float x * 10. + offset) cell let rect = Rectangle(Width = size, Height = size, Fill = SolidColorBrush color) rect.SetValue(Canvas.LeftProperty, x) rect.SetValue(Canvas.TopProperty, y) rect (*[/omit]*) // Fill a cell with corresponding color let fill = createRectangle >> canvas.Children.Add let drawMaze xMax yMax growMethod = (*[omit:(...)]*) this.Width <- float xMax * 10. this.Height <- float yMax * 10. let rand = System.Random() (*[/omit]*) 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 // [/snippet] open Microsoft.TryFSharp App.Dispatch (fun() -> App.Console.ClearCanvas() let canvas = App.Console.Canvas let maze = MazeControl() let sp = StackPanel() let cb = ComboBox( ItemsSource = [RecursiveBacktracker; Prim; ChooseTheOldest], Margin = Thickness(0.,0.,0.,5.), HorizontalAlignment = HorizontalAlignment.Center, MinWidth = 150.) cb.SelectionChanged.AddHandler(fun _ _ -> maze.DrawMaze (cb.SelectedItem :?> GrowMethod)) sp.Children.Add cb sp.Children.Add maze canvas.Children.Add sp App.Console.CanvasPosition <- CanvasPosition.Right cb.Focus() |> ignore cb.SelectedIndex <- 0 )