1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
|
DIRS = [ :up, :right, :down, :left ]
Pos = Struct.new(:x, :y) do
def move(dir)
case dir
when :up
Pos.new(x, y - 1)
when :right
Pos.new(x + 1, y)
when :down
Pos.new(x, y + 1)
when :left
Pos.new(x - 1, y)
end
end
def dir_from(pos)
diff_x = x - pos.x
diff_y = y - pos.y
case Pos.new(diff_x, diff_y)
when Pos.new(0, -1)
:up
when Pos.new(1, 0)
:right
when Pos.new(0, 1)
:down
when Pos.new(-1, 0)
:left
end
end
def to_s()
"(#{x}, #{y})"
end
end
Tile = Struct.new(:pos, :up, :right, :down, :left)
class Maze
attr_reader :width
attr_reader :height
def initialize(width, height)
@width = width
@height = height
@h_walls = Array.new(@width) { Array.new(@height + 1, true) }
@v_walls = Array.new(@width + 1) { Array.new(@height, true) }
end
def inBounds?(pos)
x = pos.x
y = pos.y
x >= 0 && y >= 0 && x < @width && y < @height
end
def get(pos)
raise IndexError unless inBounds?(pos)
x = pos.x
y = pos.y
Tile.new(pos, @h_walls[x][y], @v_walls[x + 1][y], @h_walls[x][y + 1], @v_walls[x][y])
end
def neighbors(pos)
neighbors = []
DIRS.each do |dir|
neighbors.push(pos.move(dir)) if inBounds?(pos.move(dir))
end
neighbors
end
def set(pos, dir, state)
raise IndexError if pos.x >= @width
raise IndexError if pos.y >= @height
case dir
when :up
@h_walls[pos.x][pos.y] = state
when :right
@v_walls[pos.x + 1][pos.y] = state
when :down
@h_walls[pos.x][pos.y + 1] = state
when :left
@v_walls[pos.x][pos.y] = state
end
end
def to_s
drawingField = Array.new(@height * 2 + 1) { " " * (@width * 2 + 1) }
@v_walls.each_index do |x|
@v_walls[x].each_index do |y|
next if @v_walls[x][y] == false
drawingField[y * 2][x * 2] = "█"
drawingField[y * 2 + 1][x * 2] = "█"
drawingField[y * 2 + 2][x * 2] = "█"
end
end
@h_walls.each_index do |x|
@h_walls[x].each_index do |y|
next if @h_walls[x][y] == false
drawingField[y * 2][x * 2] = "█"
drawingField[y * 2][x * 2 + 1] = "█"
drawingField[y * 2][x * 2 + 2] = "█"
end
end
drawingField.join("\n")
end
end
class MazeGenerator
attr_reader :maze
def initialize(width, height)
@maze = Maze.new(width, height)
end
def generate()
@visitedCells = [@currentPos]
@stack = [Pos.new(0, 0)]
while !@stack.empty?
step()
end
end
def step()
neighbors = @maze.neighbors(@stack.last)
neighbors.select! do |neighbor|
!@visitedCells.include? neighbor
end
if neighbors.empty?
@stack.pop()
else
randomNeighbor = neighbors.sample
print "Removing wall between ", @stack.last, " and ", randomNeighbor, "\n"
@maze.set(@stack.last, randomNeighbor.dir_from(@stack.last), false)
@stack.push(randomNeighbor)
@visitedCells.push(randomNeighbor)
end
end
end
mazeGenerator = MazeGenerator.new(15, 15)
mazeGenerator.generate
puts mazeGenerator.maze
|
