class MapGenerator
  fork_pbb = 0.05
  turn_pbb = 0.05

  map : array [2, bool]
  mutable room_locations : list [int * int] = []

  rand : System.Random = System.Random ()

  MaybeRoom (x : int, y : int) : void
    when (rand.NextDouble () < 0.9)
      room_locations ::= (x, y)
 
  Path (x : int, y : int, dir : int) : void
    if (x < 1 || y < 1 || x > width - 2 || y > height - 2)
      MaybeRoom (x, y)
    else if (map [x, y]) {}
    else
      if (rand.NextDouble () < fork_pbb)
        when (rand.NextDouble () < 0.5)
          Path (x, y, dir + 1)
        when (rand.NextDouble () < 0.5)
          map [x, y] = false
          Path (x, y, dir + 3)
        when (rand.NextDouble () < 0.1)
          MaybeRoom (x, y)
        map [x, y] = false
        Path (x, y, dir)
      else if (rand.NextDouble () < turn_pbb)
        if (rand.NextDouble () < 0.5)
          Path (x, y, dir + 1)
        else
          Path (x, y, dir + 3)
      else
        map [x, y] = true
        def (x, y) =
          match (dir % 4)
            | 0 => (x + 1, y)
            | 1 => (x, y - 1)
            | 2 => (x - 1, y)
            | 3 => (x, y + 1)
            | _ => assert (false)
        Path (x, y, dir)
        when (rand.NextDouble () < 0.05)
          MaybeRoom (x, y)

  width : int
  height : int

  public this (w : int, h : int)
    width = w
    height = h
    map = array (w, h)

  MapOK () : bool
    mutable free = 0
    
    for (mutable i = 0; i < width; ++i)
      for (mutable j = 0; j < height; ++j)
        when (map [i, j]) free++
    
    if (free * 10 > width * height)
      true
    else
      room_locations = []
      for (mutable i = 0; i < width; ++i)
        for (mutable j = 0; j < height; ++j)
          map [i, j] = false
      false

  DigRooms () : void
    def dig (x, y)
      when (x >= 1 && y >= 1 && x <= width - 2 && y <= height - 2)
        map [x, y] = true
    
    foreach ((x, y) in room_locations)
      def rx = Dice.Roll (3, 3) - 2
      def ry = Dice.Roll (2, 3) - 2
      for (mutable i = x - rx; i <= x + rx; ++i)
        for (mutable j = y - ry; j <= y + ry; ++j)
          dig (i, j)

  public Generate () : array [2, bool]
    Path (width / 2, height / 2, rand.Next (4))
    if (MapOK ())
      DigRooms ()
      map 
    else Generate ()