curse-you-go-rogue/06_MazeWorld/maze.go

package main

import (
  "math/rand"
  "time"
  "log"
  "fmt"
)

func (room *Room) Overlaps(other Room) bool {
        // other left          > this right == other too far right
    return !(  other.X                > room.X + room.Width ||

        // other right        < this left == other too far left
     other.X + other.Width < room.X ||

        // other top           > this bottom == too far below
     other.Y                > room.Y + room.Height ||

        // other bottom        < this top == too far above
     other.Y + other.Height < room.Y)
}

func (room *Room) Contains(at Position) bool {
  return at.X >= room.X &&
    at.X <= room.X + room.Width -1 &&
    at.Y >= room.Y &&
    at.Y <= room.Y + room.Height - 1
}


func (game *Game) NeighborWalls(pos Position) []Position {
  neighbors := game.Neighbors(pos)
  result := make([]Position, 0)

  for _, at := range neighbors {
    cell := game.Level[at.Y][at.X]

    if cell == WALL {
      result = append(result, at)
    }
  }

  return result
}

func (game *Game) HuntNext(on *Position, found *Position) bool {
  for y := 1; y < game.Height ; y += 2 {
    for x := 1; x < game.Width ; x += 2 {
      if game.Level[y][x] != WALL {
        continue
      }

      neighbors := game.Neighbors(Position{x, y})

      for _, pos := range neighbors {
        if game.Level[pos.Y][pos.X] == SPACE {
          *on = Position{x, y}
          *found = pos
          return true
        }
      }
    }
  }

  return false
}

func (game *Game) HAKStep(from Position, to Position) {
  game.Level[from.Y][from.X] = SPACE
  row := (from.Y + to.Y) / 2
  col := (from.X + to.X) / 2
  game.Level[row][col] = SPACE
}

func (game *Game) NewMaze() []Position {
  on := Position{1, 1}
  found := Position{1,1}

  game.DeadEnds = make([]Position, 0)
  game.Rooms = make([]Room, 0)

  for {
    neighbors := game.NeighborWalls(on)

    if len(neighbors) == 0 {
      game.DeadEnds = append(game.DeadEnds, on)

      if !game.HuntNext(&on, &found) {
        break
      }

      game.HAKStep(on, found)
    } else {
      rand_neighbor := rand.Int() % len(neighbors)
      nb := neighbors[rand_neighbor]
      game.HAKStep(nb, on)
      on = nb
    }

    if SHOW_RENDER {
      game.Render()
      time.Sleep(50 * time.Millisecond)
    }
  }

  return game.DeadEnds
}

func (game *Game) RoomShouldExist(room Room) bool {
  // 1 offset means it won't be on the perimeter
  top_left := Position{room.X - 1, room.Y - 1}
  bottom_right := Position{room.X + room.Width + 2, room.Y + room.Height + 2}

  // range of 2 so it's not at the perimeter
  if !game.Inbounds(top_left, 2) ||
     !game.Inbounds(bottom_right, 2) {
    return false
  }

  // if it overlaps a game.NoRoomRegion then false
  if(room.Overlaps(game.DeadArea)) {
    return false
  }

  // if this room overlaps any other room then false
  for _, other := range game.Rooms {
    if room == other {
      continue
    }

    if room.Overlaps(other) {
      return false
    }
  }

  return true;
}

func room_sweetspot(width int, room_size int) int {
  if width < 20 {
    return 4
  } else if width < 30 {
    return  width / room_size / 2
  } else if width < 50 {
    return width / room_size
  } else {
    return width / 2
  }
}

func (game *Game) RandomizeRooms(room_size int) {
  // need to put dead ends in game or a map struct
  rand.Shuffle(len(game.DeadEnds), func(i, j int) {
    game.DeadEnds[i], game.DeadEnds[j] = game.DeadEnds[j], game.DeadEnds[i]
  })

  // shuffle the dead ends
  max_rooms := room_sweetspot(game.Width, room_size)
  fmt.Println("max_rooms", max_rooms)

  for _, at := range game.DeadEnds {
    // avoid dead ends near edge
    if !game.Inbounds(at, 2) { continue }

    // quit after max_rooms
    if len(game.Rooms) > max_rooms {
      break
    }

    // get the room corners
    corners := []Position{
        Position{at.X, at.Y}, // top left
        Position{at.X - room_size + 1, at.Y}, // top right
        Position{at.X - room_size + 1, at.Y - room_size + 1}, // bottom right
        Position{at.X, at.Y - room_size + 1}, // bottom left
    }

    // randomly select starting corner
    rand.Shuffle(len(corners), func(i, j int) {
      corners[i], corners[j] = corners[j], corners[i]
    })

    // for each possible starting corner
    for _, corner := range corners {
      room := Room{corner.X, corner.Y, room_size, room_size}
      // if the room is good/should exist

      if game.RoomShouldExist(room) {
        // add it to the room list
        game.Rooms = append(game.Rooms, room)
      }
    }
  }
}

func (game *Game) Clear() {
  game.FillMap(game.Level, WALL);
}


func (game *Game) PunchHole(pos Position, width int, height int) {
  for y := pos.Y; y < pos.Y + height; y++ {
    for x := pos.X; x < pos.X + width; x++ {
      game.Level[y][x] = SPACE
    }
  }
}

func (game *Game) PlaceRooms() {
  // switch from using game.DeadEnds to using the rooms list
  for _, room := range game.Rooms {
    game.PunchHole(Position{room.X, room.Y}, room.Width, room.Height)
    if SHOW_RENDER { game.Render() }
  }
}

func (game *Game) RemoveDeadEnds() {
  // for each point at dead end
  // compass to find open space
  // remove the opposite wall from the space
}

func (game *Game) Enclose() {
  // might need the perimeter from shapes
  // basically just go around the perimeter and fill in with walls
}

func (game *Game) Repair() {

}

func (game *Game) ValidDoor(x int, y int) {
  // door is valid if north/south xor east/west is open
}

func (game *Game) PlaceDoors() {
  for _, room := range game.Rooms {
    fmt.Println(room)
    // go through all the rooms, punch out doors, find longest path

    // computer longest path from room as a test
    
    // can't path out so make a hole
    // walk the perimeter
      // if it's a wall and it's a valid door location
      // make it a door
      // recomputer the longest path
      // if it's greater than the best_longest
      // record as best door and best_longest
      // if best_longest is good then done
    
    // should now have a door with the longest path
  }
}

func (game *Game) Validate() bool {
  // walk the perimeter and
    // if a dead end is there then not valid
    // if a door is there not valid
    // if any part is not a wall, not valid

  // if we have multiple rooms then confirm none overlap
  if len(game.Rooms) > 1 {
    for _, room := range game.Rooms {
      if !game.RoomShouldExist(room) {
        return false
      }
    }
  }

  var from Position

  // pick a random room
  if len(game.Rooms) > 0 {
    room := game.Rooms[0]
    from = Position{room.X, room.Y}
  } else if len(game.DeadEnds) > 0 {
    from = game.DeadEnds[0]
  } else {
    log.Println("Invalid map, doesn't have rooms or dead ends.")
    return false
  }

  // compute paths to the room
  game.ComputePaths(from.X, from.Y)

  // search the map for a space value that's also a path limit in Paths
  for y := 0; y < game.Height; y++ {
    for x := 0; x < game.Width; x++ {
      if game.Level[y][x] == SPACE && 
        game.Paths[y][x] == PATH_LIMIT {
          // that means the map is not pathable, not valid
          return false
      }
    }
  }

  // all good valid
  return true
}

func (game *Game) SetDeadArea(size int) {
  x := game.Width / 2;
  y := game.Height / 2;

  game.DeadArea = Room{
    x - size,
    y - size,
    size * 2 + 1,
    size * 2 + 1,
  }

  fmt.Println("room", game.DeadArea)
  r := game.DeadArea
  game.PunchHole(Position{r.X, r.Y}, r.Width, r.Height)
}

////////// SCRIPT and SHAPES

func (game *Game) OpenBox(outer_size int) {
  // get the center x/y
  // compensate for the box's border
  outer_size++

  // get the x,y/width,height for the outerbox
  // walk the perimeter
  // running compass around it
  // if there's a dead end then punch that out and break
}