Skip to content

Instantly share code, notes, and snippets.

@Ikariusrb
Last active August 7, 2022 16:35
Show Gist options
  • Save Ikariusrb/16a8db5e75a9ff2c6568accd69d281da to your computer and use it in GitHub Desktop.
Save Ikariusrb/16a8db5e75a9ff2c6568accd69d281da to your computer and use it in GitHub Desktop.
DragonRuby Dungeon generator- can animate or be called.
# 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment