Maze generation: Difference between revisions
Content added Content deleted
m (→Graph) |
|||
Line 3,517: | Line 3,517: | ||
<lang ruby>class Maze |
<lang ruby>class Maze |
||
DIRECTIONS = [ [1, 0], [-1, 0], [0, 1], [0, -1] ] |
DIRECTIONS = [ [1, 0], [-1, 0], [0, 1], [0, -1] ] |
||
def initialize(width, height) |
def initialize(width, height) |
||
@width = width |
@width = width |
||
@height = height |
@height = height |
||
@start_x = rand(width) |
@start_x = rand(width) |
||
@start_y = 0 |
@start_y = 0 |
||
@end_x = rand(width) |
@end_x = rand(width) |
||
@end_y = height - 1 |
@end_y = height - 1 |
||
⚫ | |||
# Which walls do exist? Default to "true". Both arrays are |
# Which walls do exist? Default to "true". Both arrays are |
||
# one element bigger than they need to be. For example, the |
# one element bigger than they need to be. For example, the |
||
# @vertical_walls[ |
# @vertical_walls[x][y] is true if there is a wall between |
||
# (x,y) and (x+1,y). The additional entry makes printing |
# (x,y) and (x+1,y). The additional entry makes printing easier. |
||
⚫ | |||
# easier. |
|||
@ |
@horizontal_walls = Array.new(width) { Array.new(height, true) } |
||
⚫ | |||
# Path for the solved maze. |
# Path for the solved maze. |
||
@path = Array.new( |
@path = Array.new(width) { Array.new(height) } |
||
⚫ | |||
# "Hack" to print the exit. |
# "Hack" to print the exit. |
||
@horizontal_walls[@ |
@horizontal_walls[@end_x][@end_y] = false |
||
⚫ | |||
reset_visiting_state |
|||
# Generate the maze. |
# Generate the maze. |
||
generate |
generate |
||
end |
end |
||
# Print a nice ASCII maze. |
# Print a nice ASCII maze. |
||
def print |
def print |
||
# Special handling: print the top line. |
# Special handling: print the top line. |
||
⚫ | |||
⚫ | |||
for x in (0...@width) |
|||
⚫ | |||
⚫ | |||
puts line |
|||
# For each cell, print the right and bottom wall, if it exists. |
# For each cell, print the right and bottom wall, if it exists. |
||
@height.times do |y| |
|||
for y in (0...@height) |
|||
line = "|" |
line = @width.times.inject("|") do |str, x| |
||
str << (@path[x][y] ? " * " : " ") << (@vertical_walls[x][y] ? "|" : " ") |
|||
for x in (0...@width) |
|||
line.concat(@path[y][x] ? " o " : " ") |
|||
line.concat(@vertical_walls[y][x] ? "|" : " ") |
|||
⚫ | |||
puts line |
|||
line = "+" |
|||
for x in (0...@width) |
|||
⚫ | |||
end |
end |
||
puts line |
puts line |
||
⚫ | |||
⚫ | |||
end |
end |
||
end |
end |
||
private |
private |
||
# Reset the VISITED state of all cells. |
# Reset the VISITED state of all cells. |
||
def reset_visiting_state |
def reset_visiting_state |
||
@visited = Array.new(@ |
@visited = Array.new(@width) { Array.new(@height) } |
||
end |
end |
||
# Check whether the given coordinate is within the valid range. |
|||
def coordinate_valid?(x, y) |
|||
(x >= 0) && (y >= 0) && (x < @width) && (y < @height) |
|||
end |
|||
# Is the given coordinate valid and the cell not yet visited? |
# Is the given coordinate valid and the cell not yet visited? |
||
def move_valid?(x, y) |
def move_valid?(x, y) |
||
(0...@width).cover?(x) && (0...@height).cover?(y) && !@visited[x][y] |
|||
end |
end |
||
# Generate the maze. |
# Generate the maze. |
||
def generate |
def generate |
||
⚫ | |||
reset_visiting_state |
reset_visiting_state |
||
⚫ | |||
end |
end |
||
# Depth-first maze generation. |
# Depth-first maze generation. |
||
def generate_visit_cell(x, y) |
def generate_visit_cell(x, y) |
||
# Mark cell as visited. |
# Mark cell as visited. |
||
@visited[ |
@visited[x][y] = true |
||
# Randomly get coordinates of surrounding cells (may be outside |
# Randomly get coordinates of surrounding cells (may be outside |
||
# of the maze range, will be sorted out later). |
# of the maze range, will be sorted out later). |
||
coordinates = [] |
coordinates = DIRECTIONS.shuffle.map { |dx, dy| [x + dx, y + dy] } |
||
for dir in DIRECTIONS.shuffle |
|||
coordinates << [ x + dir[0], y + dir[1] ] |
|||
⚫ | |||
for new_x, new_y in coordinates |
for new_x, new_y in coordinates |
||
next unless move_valid?(new_x, new_y) |
next unless move_valid?(new_x, new_y) |
||
⚫ | |||
# Recurse if it was possible to connect the current |
# Recurse if it was possible to connect the current and |
||
# |
# the cell (this recursion is the "depth-first" part). |
||
# part). |
|||
connect_cells(x, y, new_x, new_y) |
connect_cells(x, y, new_x, new_y) |
||
generate_visit_cell |
generate_visit_cell(new_x, new_y) |
||
end |
end |
||
end |
end |
||
# Try to connect two cells. Returns whether it was valid to do so. |
# Try to connect two cells. Returns whether it was valid to do so. |
||
def connect_cells(x1, y1, x2, y2) |
def connect_cells(x1, y1, x2, y2) |
||
if x1 == x2 |
if x1 == x2 |
||
# Cells must be above each other, remove a horizontal |
# Cells must be above each other, remove a horizontal wall. |
||
⚫ | |||
⚫ | |||
⚫ | |||
else |
else |
||
# Cells must be next to each other, remove a vertical |
# Cells must be next to each other, remove a vertical wall. |
||
⚫ | |||
# wall. |
|||
⚫ | |||
end |
end |
||
end |
end |
||
Line 3,634: | Line 3,610: | ||
maze = Maze.new 20, 10 |
maze = Maze.new 20, 10 |
||
maze.print</lang> |
maze.print</lang> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |