DragonRuby Dungeon generator- can animate or be called.

dungeon_generator.rb

# MIT License
# Copyright (c) 2020 Ross Becker
#
# Permission is hereby granted, free of charge, to any person obtaining a copy
# of this software and associated documentation files (the "Software"), to deal
# in the Software without restriction, including without limitation the rights
# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the Software is
# furnished to do so, subject to the following conditions:
#
# The above copyright notice and this permission notice shall be included in all
# copies or substantial portions of the Software.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
# SOFTWARE.

class Array
  def sample(count = 1, random: Random.new)
    if count == 1
      self[random.rand(self.length)]
    else
      Array.new(count) { self[random.rand(self.length)] }
    end
  end

  def shuffle(random: Random.new)
    source = self.dup
    Array.new(source.length) { source.delete_at(random.rand(source.length)) }
  end
end

class DungeonGenerator
  attr_gtk

  attr_reader :game_state, :grid_size_x, :grid_size_y, :x_margin, :y_margin, :cell_size

  attr_reader :rooms, :maze, :connect, :remove, :dungeon

  def initialize(grid_max_x: 29, grid_max_y: 29, grid_cell_size: 20, seed: Kernel.rand(1000000))
    @rng = Random.new(seed)
    self.args = $gtk.args

    @grid_size_x = grid_max_x
    @grid_size_y = grid_max_y
    @x_margin = 40
    @y_margin = 40
    @cell_size = grid_cell_size
    @game_state = :room
    @displayed_time = false
    @seed = seed

    #@rooms = state.new_entity_strict(:roomstate, attempted: 0, attempts: 250, rng: GaussianRandom.new(3,8, rng: @rng), rects: [])
    @rooms = state.new_entity_strict(:roomstate, attempted: 1, attempts: 250, rng: lambda { @rng.rand(6) + 3 }, rects: [])
    @maze = state.new_entity_strict(:mazestate, points: {}, flood_fill_stack: [])
    @connect = state.new_entity_strict(:connectstate, connectors: [], first_room: nil, flood_fill: [], main_region: {})
    @remove = state.new_entity_strict(:removestate, dead_ends: [])

    @dungeon = Array.new(grid_size_x+1) { Array.new(grid_size_y+1, nil)}

    @state_times = Hash.new { |h,k| h.keys.each { |ik| h[ik][:end] ||= Time.now}; h[k] = Hash.new; h[k][:start] = Time.now; h[k] }
  end

  def call
    while game_state != :done
      calc
    end
    show_time

    { rooms: rooms.rects, maze: maze.points.keys, seed: @seed }
  end

  def tick(args)
    self.args = args

    calc

    show_time

    render
  end

  def show_time
    if game_state == :done && !@displayed_time
      @displayed_time = true
      @state_times.delete(:done)
      @state_times.each { |state, times| puts "#{state} took #{times[:end] - times[:start]} seconds." }
      total_time = @state_times.values.reduce(0) { |total, times| total + (times[:end] - times[:start]) }
      puts "Total time: #{total_time}"
    end
  end

  def render
    render_dungeon_background
    render_room
    render_maze
    render_connect
    render_grid_lines
    outputs.labels << [800, 700, state.game_state]
  end

  def render_dungeon_background 
    background = [0, 0, grid_size_x, grid_size_y, dungeon_background_color]
    outputs.solids << scale_rect(background)
  end

  def render_room
    rooms.rects.each do |room|
      outputs.solids << scale_rect(room)
    end
  end

  def render_maze
    maze.points.keys.each do |x, y|
      rect = [x, y, 1, 1, maze_color]
      outputs.solids << scale_rect(rect)
    end
  end

  def render_connect
    connect.main_region.keys.each do |x, y|
      rect = [x, y, 1, 1, connect_color]
      outputs.solids << scale_rect(rect)
    end
  end

  def scale_rect rect 
    x, y, width, height, r, g, b = *rect
    [x_margin + (x * cell_size), y_margin + (y * cell_size), width * cell_size, height * cell_size, r, g, b]
  end

  def render_grid_lines 
    for x in 0..grid_size_x
      outputs.lines << vertical_line(x)
    end
    for y in 0..grid_size_y
      outputs.lines << horizontal_line(y)
    end
  end

  def vertical_line column
    [x_margin + (column * cell_size), y_margin, x_margin + (column * cell_size), y_margin + (grid_size_y * cell_size)]
  end

  def horizontal_line row
    [x_margin, y_margin + (row * cell_size), x_margin + (grid_size_x * cell_size), y_margin + (row * cell_size)]
  end
 
  def calc
    @state_times[game_state]
    calc_room
    calc_maze
    calc_connect
    calc_remove
    @state_times[game_state]
  end

  # Attempts to generate a room a certain number of times
  # If the room is valid it draws it
  # Else attempts another one
  def calc_room
    return unless game_state == :room

    if rooms.attempted >= rooms.attempts
      @game_state = :maze
      return
    end
    rooms.attempted += 1

    new_room = random_room
    if valid_room?(new_room)
      add_room(new_room)
    else
      calc_room # Attempt to generate another room
    end
  end

  def add_room(room)
    x, y, width, height = room
    rooms.rects << room
    for dx in x..(x+width-1)
      for dy in y..(y+height-1)
        dungeon[dx][dy] = :room
      end
    end
  end

  def valid_room? room
    rect_within_bounds?(room) && !rect_touches_room?(room)
  end

  def random_room
    [ *rectangularize(random_square), *room_color ]
  end

  def random_square
    size = rooms.rng.call
    [@rng.rand(grid_size_x), @rng.rand(grid_size_y), size, size]
  end

  def rectangularize(square)
    # Weird math to make room more rectangular and less squarey
    x, y, width, height = square
    rectangularity = @rng.rand(width / 2 + 1)
    width_or_height = @rng.rand(2)
    if width_or_height == 0
      width += rectangularity
    else
      height += rectangularity
    end

    # Force rect to have odd width and height
    if width % 2 == 0
      width -= 1
    end
    if height % 2 == 0
      height -= 1
    end

    [x, y, width, height]
  end

  def rect_within_bounds? rect
    x, y, width, height = *rect
    (x + width < grid_size_x) && (y + height < grid_size_y)
  end
 
  def point_intersect_room? x, y
    dungeon[x][y] == :room
  end

  def rect_intersect_room? rect
    rooms.rects.any? { |room| room.intersect_rect?(rect) }
  end
 
  def point_touches_room? x, y
    rect_touches_room?([x, y, 1, 1])
  end
 
  def rect_touches_room? rect
    x, y, width, height = rect
    expanded_rect = [x - 1, y - 1, width + 2, height + 2]
    rect_intersect_room?(expanded_rect)
  end


  def calc_maze
    return unless game_state == :maze
 
    return maze_flood_fill unless maze.flood_fill_stack.empty? # Maze Flood Fill Animations

    # Checks every point starting from bottom left corner
    # Tries to start a new maze path
    start_point = dungeon_points.detect { |x, y| maze_starting_point?(x, y) }
    if start_point
      add_and_flood_maze(*start_point)
      return
    end

    @game_state = :connect # If there are no more maze starting points
  end

  def maze_flood_fill
    return calc_maze if maze.flood_fill_stack.empty? # Start new maze if no flood fills
   
    # x, y is the point to be flood filled
    # direction is the direction in which the flood fill was approached
    x, y, direction = *maze.flood_fill_stack.pop

    return maze_flood_fill unless maze_flood_fillable?(x, y, direction)
   
    add_and_flood_maze(x, y)
  end

  def add_and_flood_maze x, y
    add_maze(x, y)
    valid_directions(x, y).shuffle(random: @rng).each do |direction|
      maze.flood_fill_stack << translate_point(x, y, direction)
    end
  end
  # Prepares to flood fill from any newly added maze
  def add_maze x, y
    maze.points[[x, y]] = true
  end

  def maze_flood_fillable? x, y, direction
    empty_point?(x, y) && !bumps_into_maze?(x, y, direction) && !point_touches_room?(x, y)
  end

  def empty_point? x, y
    !maze?(x, y) && dungeon[x][y] == nil
  end

  def bumps_into_maze? x, y, direction
    significant_points(x, y, direction).any? { |sig_x, sig_y| maze?(sig_x, sig_y) }
  end

  # Points that have to be empty to flood fill x, y
  # Depends on the direction the flood fill was approached in
  def significant_points x, y, direction
    return left_significant_points(x, y) if direction == :left
    return up_significant_points(x, y) if direction == :up
    return right_significant_points(x, y) if direction == :right
    return down_significant_points(x, y) if direction == :down
  end
 
  def left_significant_points x, y
    [[x, y - 1], [x, y + 1], [x - 1, y - 1], [x - 1, y], [x - 1, y + 1]]
  end
 
  def up_significant_points x, y
    [[x - 1, y], [x + 1, y], [x - 1, y + 1], [x, y + 1], [x + 1, y + 1]]
  end

  def right_significant_points x, y
    [[x, y - 1], [x, y + 1], [x + 1, y - 1], [x + 1, y], [x + 1, y + 1]]
  end
 
  def down_significant_points x, y
    [[x - 1, y], [x + 1, y], [x - 1, y - 1], [x, y - 1], [x + 1, y - 1]]
  end


  # 0. Identify All Connectors
  # 1. Pick a random room to be main region
  # 2. Open a random connector touching the main region
  # 3. Flood fill all to main region
  # 4. Remove extra connectors
  # 5. If any connectors left, go to #2
  def calc_connect
    return unless game_state == :connect

    # Only runs when calc_connect is called for the first time
    unless connect.first_room
      connect.connectors.push(*init_connectors)
      connect.first_room = rooms.rects.first
    end

    if connect.flood_fill.empty?
      remove_extra_connectors
      if connect.connectors.empty?
        return @game_state = :remove
      end
      open_connector
    end

    connect_flood_fill
  end

  def init_connectors
    dungeon_points
      .select { |x, y| connector?(x, y) }
  end

  def dungeon_points
    @dungeon_points ||= 
    (0..(grid_size_x - 1)).to_a
      .product((0..(grid_size_y - 1)).to_a)
  end

  def remove_extra_connectors
    connect.connectors.select! { |x, y| connector?(x, y) }
  end

  # Flood fills multiple directions at once
  # Attempts to flood fill to all adjacent points
  def connect_flood_fill
    current_flood_fill = connect.flood_fill.dup
    connect.flood_fill = 
      current_flood_fill.flat_map do |x, y|
        add_main_region(x, y)
        adjacent_points(x, y)
          .select { |a_x, a_y| connect_flood_fillable?(a_x, a_y) }
      end.uniq
  end

  def add_main_region x, y
    connect.main_region[[x, y]] = true
  end

  def connector? x, y
    return false unless empty_point?(x, y)

    # 3 Types of regions
    connects_main_region = 0
    connects_maze        = 0
    connects_rooms       = 0
    # Checks what region the adjacent points belong to
    adjacent_points(x, y).each do |adj_x, adj_y|
      if main_region?(adj_x, adj_y)
        connects_main_region = 1
      elsif maze?(adj_x, adj_y)
        connects_maze = 1
      elsif point_intersect_room?(adj_x, adj_y)
        connects_rooms += 1
      end
    end
    (connects_main_region + connects_maze + connects_rooms) > 1
  end

  def connect_flood_fillable? x, y
    return false if main_region?(x, y)
    return true if point_intersect_room?(x, y)
    return true if maze?(x, y)
    false
  end

  def open_connector
    main_connectors = connect.connectors.select { |x, y| touches_main_region?(x, y) }
    connector = connect.connectors.delete(main_connectors.sample(random: @rng))
    connect.flood_fill << connector
    add_connector_to_maze connector

    if @rng.rand(5) == 0 # 20% Chance For Extra Connector
      return unless connector

      room = room_touching_connector(*connector) # The room that is being connected
      return unless room

      random_room_connector = connectors_touching_room(room).sample(random: @rng) # The possible extra connectors
      return unless random_room_connector
     
      connect.flood_fill << random_room_connector
      add_connector_to_maze random_room_connector
    end
  end

  def add_connector_to_maze connector
    x, y = connector
    maze.points[[x,y]] = true
  end

  def room_touching_connector x, y
    adjacent_points(x, y)
      .select {|adj_x, adj_y| !main_region_or_room?(adj_x, adj_y) && point_intersect_room?(adj_x, adj_y) }
      .each do |adj_x, adj_y|
        r = rooms.rects.detect { |rect| rect.intersect_rect?([adj_x, adj_y, 1, 1]) }
        return r unless r.nil?
      end
    nil
  end

  def connectors_touching_room room
    x, y, width, height = room
    expanded_room = [x - 1, y - 1, width + 2, height + 2]
    connect.connectors
      .select { |x, y| touches_main_region?(x, y) && expanded_room.intersect_rect?([x, y, 1, 1]) }
  end


  def touches_main_region? x, y
    adjacent_points(x, y).any? { |a_x, a_y| main_region_or_room?(a_x, a_y) }
  end
 
  def main_region? x, y
    connect.main_region[[x,y]]
  end

  def main_region_or_room? x, y
    return true if connect.first_room.intersect_rect?([x, y, 1, 1])

    main_region?(x, y)
  end
 

  def translate_point x, y, direction
    if direction == :left
      x -= 1
    elsif direction == :up
      y += 1
    elsif direction == :right
      x += 1
    elsif direction == :down
      y -= 1
    end
    [x, y, direction]
  end

  def valid_directions x, y
    directions = []
    unless x == 0
      directions << :left
    end
    unless x == grid_size_x - 1
      directions << :right
    end
    unless y == 0
      directions << :down
    end
    unless y == grid_size_y - 1
      directions << :up
    end
    directions
  end

  def maze_starting_point? x, y
    empty_point?(x, y) && !point_touches_maze?(x, y) && !point_touches_room?(x, y)
  end

  def point_touches_maze? x, y
    neighbor_points(x, y).any? { |neighbor_x, neighbor_y| maze?(neighbor_x, neighbor_y) }
  end

  def maze? x, y
    maze.points[[x, y]]
  end

  def neighbor_points x, y
    Array.new.tap do |points|
      for px in ([x-1,0].max)..([x+1,grid_size_x].min)
        for py in ([y-1,0].max)..([y+1,grid_size_y].min)
          points << [px, py] unless px == x && py == y
        end
      end
    end
  end

  def adjacent_points x, y
    points = []
    unless x == 0
      points << [x - 1, y]
    end
    unless x == grid_size_x - 1
      points << [x + 1, y]
    end
    unless y == 0
      points << [x, y - 1]
    end
    unless y == grid_size_y - 1
      points << [x, y + 1]
    end
    points
  end
 
  def diagonal_points x, y
    [
      [x - 1, y - 1],
      [x + 1, y - 1],
      [x + 1, y + 1],
      [x - 1, y + 1],
    ].reject { |x, y| x < 1 || y < 1 || x > grid_size_x || y > grid_size_y }
  end
 

  # Removes all maze dead ends
  def calc_remove
    return unless game_state == :remove
   
    if remove.dead_ends.empty?
      calc_dead_ends # Calc initial dead ends
    end

    remove_dead_ends # Remove dead ends while finding new ones

    if remove.dead_ends.empty?
      @game_state = :done
    end
  end

  def calc_dead_ends
    remove.dead_ends = maze.points.keys.select { |x, y| dead_end?(x, y) }
  end

  def dead_end? x, y
    return false unless maze?(x, y)
    adjacent_points(x, y).reject { |a_x, a_y| empty_point?(a_x, a_y) }.length <= 1
  end

  def remove_dead_ends
    dead_ends = remove.dead_ends.dup
    remove.dead_ends = []

    dead_ends.each do |x, y|
      # Deletes dead end
      remove_main_region(x, y)
      remove_maze(x, y)

      # New dead ends must be adjacent to old dead ends
      remove.dead_ends.push(
        *adjacent_points(x, y)
          .select { |x, y| dead_end?(x, y) }
      )
    end
  end

  def remove_maze x, y
    maze.points.delete([x, y])
  end
  
  def remove_main_region x, y
    connect.main_region.delete([x,y])
  end

  def dungeon_background_color
    [170, 170, 170]
  end
 
  def random_color
    [@rng.rand(256), @rng.rand(256), @rng.rand(256)]
  end

  def room_color
    [246, 156, 196]
  end

  def maze_color
    [253, 253, 149]
  end

  def connect_color
    [134, 243, 247]
  end

end

# Use:
# $game = DungeonGenerator.new(grid_max_x: 29, grid_max_y: 21, grid_cell_size: 32, seed: 1586186539 )
#
# to animate:
# def tick(args); $game.tick(args); end
#
# to call and get a dungeon back:
# $newdungeon = $game.call