I’ve been working towards a very large project, that requires specialized circular maze generation. I am using Python’s PIL library to draw the maze onto an image. From what I am seeing, there are only two issues, and those are with the drawing itself. They are as follows:
Issue One:
Maze wall lines are incomplete, but present. The line length is not as it should be, leading to a “half maze”.
Issue Two:
With the expanding nature of a circular maze, each layer (or “level” as I name it in the script) determines the number of cells to put into said layer, allowing for a more natural looking maze, instead of one with corridors that continue to grow in size as you get further from the center. This is causing slight discrepancies when joining two layers together. It is not with every level. Just when the cell count needs to increase.
These issues have stunted my project’s growth for months, and my team is getting less and less motivated to continue with such a road block. Any help is greatly appreciated. Thanks in advance!
Example maze generated from script
from PIL import Image, ImageDraw
import math
import random
from collections import deque
class CircularMaze:
def __init__(self, levels, line_len, wall_width, corridor_size, canvas_size):
assert line_len > 0, "Line length must be greater than 0"
self.canvas_size = canvas_size
self.num_levels = levels
self.line_length = line_len
self.wall_width = wall_width
self.corridor_size = corridor_size
self.num_cells_at_level = self.cell_count_by_level()
self.total_cells = sum(self.num_cells_at_level)
def cell_count_by_level(self):
cells_by_level = [1]
for level in range(1, self.num_levels): cells_by_level.append(int(math.pow(2, math.floor(math.log2(level + 1)) + 3)))
return cells_by_level
def index_1d_from_2d(self, level, cell):
if level >= self.num_levels: raise Exception("level greater than maze levels")
idx = 0
for lvl in range(level): idx += self.num_cells_at_level[lvl]
idx += cell
return idx
def index_2d_from_1d(self, idx):
if idx >= self.total_cells: raise Exception("1D index greater than total number of cells")
level = 0
while idx - self.num_cells_at_level[level] >= 0:
idx -= self.num_cells_at_level[level]
level += 1
return level, idx
def parent_index_1d(self, level, cell):
if level <= 0: raise Exception(f'Level {level} has no parent')
elif level == 1: return 0
parent = self.index_1d_from_2d(level - 1, cell)
if self.num_cells_at_level[level - 1] < self.num_cells_at_level[level]: parent = self.index_1d_from_2d(level - 1, cell // 2)
return parent
def left_index_1d(self, level, cell):
if level <= 0: raise Exception(f'Level {level} has no left cell')
left = self.index_1d_from_2d(level, cell - 1)
if cell == 0: left = self.index_1d_from_2d(level, self.num_cells_at_level[level] - 1)
return left
def right_index_1d(self, level, cell):
if level <= 0: raise Exception(f'Level {level} has no left cell')
right = self.index_1d_from_2d(level, cell + 1)
if cell == self.num_cells_at_level[level] - 1: right = self.index_1d_from_2d(level, 0)
return right
def create_dfs_tree(self):
print("Creating DFS tree...")
graph = {node: [] for node in range(self.total_cells)}
cell_1d = random.randint(1, self.total_cells - 1)
visited = [cell_1d]
stack = deque()
stack.append(cell_1d)
total_cells_visited = 1
while len(visited) < self.total_cells:
level, cell = self.index_2d_from_1d(cell_1d)
connections = []
if level == 0:
for idx in range(1, self.num_cells_at_level[1] + 1): connections.append(idx)
else:
connections.append(self.parent_index_1d(level, cell))
connections.append(self.left_index_1d(level, cell))
connections.append(self.right_index_1d(level, cell))
if level <= self.num_levels - 2:
if self.num_cells_at_level[level] < self.num_cells_at_level[level + 1]:
connections.append(self.index_1d_from_2d(level + 1, 2 * cell))
connections.append(self.index_1d_from_2d(level + 1, 2 * cell + 1))
else: connections.append(self.index_1d_from_2d(level + 1, cell))
unvisited_connections = [conn for conn in connections if conn not in visited]
if unvisited_connections:
next_cell = random.choice(unvisited_connections)
graph[cell_1d].append(next_cell)
graph[next_cell].append(cell_1d)
visited.append(next_cell)
total_cells_visited += 1
if next_cell != 0:
stack.append(next_cell)
cell_1d = next_cell
else: cell_1d = stack.pop()
else: cell_1d = stack.pop()
if total_cells_visited % 100 == 0: print(f"Generating DFS Tree: {((total_cells_visited / self.total_cells) * 100):.2f}%")
print("DFS tree created")
return graph
def draw_maze(self, graph):
print("Drawing maze...")
image = Image.new("RGB", (self.canvas_size, self.canvas_size), "white")
draw = ImageDraw.Draw(image)
for level in range(1, self.num_levels):
radius = level * (self.line_length + self.corridor_size)
arc_angle = 360 / self.num_cells_at_level[level]
for cell in range(self.num_cells_at_level[level]):
cell_1d = self.index_1d_from_2d(level, cell)
parent_cell = self.parent_index_1d(level, cell)
left_cell = self.left_index_1d(level, cell)
if left_cell not in graph[cell_1d]:
start_angle = (cell - 0.5) * arc_angle
end_angle = cell * arc_angle
draw.arc(
[self.canvas_size // 2 - radius, self.canvas_size // 2 - radius,
self.canvas_size // 2 + radius, self.canvas_size // 2 + radius],
start=start_angle, end=end_angle, fill="black", width=self.wall_width
)
if parent_cell not in graph[cell_1d]:
angle = cell * arc_angle + arc_angle / 2
x1 = self.canvas_size // 2 + radius * math.cos(math.radians(angle))
y1 = self.canvas_size // 2 + radius * math.sin(math.radians(angle))
x2 = self.canvas_size // 2 + (radius - self.line_length) * math.cos(math.radians(angle))
y2 = self.canvas_size // 2 + (radius - self.line_length) * math.sin(math.radians(angle))
draw.line([x1, y1, x2, y2], fill="black", width=self.wall_width)
image.save("maze.png")
image.show()
levels = 15 # end goal 70 & 100
line_len = 15 # end goal 70 & 100
wall_width = 8 # end goal 8 & 12
corridor_size = 25 # end goal 25 & 50
canvas_size = 2048 # end goal 16384
maze = CircularMaze(levels, line_len, wall_width, corridor_size, canvas_size)
graph = maze.create_dfs_tree()
maze.draw_maze(graph)
The above script is recommended to be run using pypy (makes generation a lot faster)