pythonpython-imaging-librarymaze

Python Maze Generation using PIL going wrong

I've been working on a specialized circular maze generation, using PIL library to draw a maze onto an image.

sample output image

In the above output image, there are two issues.

  1. Maze wall lines are incomplete, but present. The line length is not as it should be, leading to a "half maze".

  2. 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.

How can I solve them? The following is the current implementation.

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)
Solution

  • You incorrectly calculated coordinates of the cells and reversed the conditions for checking neighboring cells.

    You need to clearly define the geometry of the cells like the following example.

    1. A point in the maze will be described as (x, y) in a Cartesian coordinate system and (r, a) in a polar coordinate system. The origin is the center of the circle, the x axis is oriented from left to right and the y axis is oriented from top to bottom. From the definition, x = r cos(a) and y = r sin(a).

    2. Let d be the length of the radial walls of a cell. And let the i-th level be a region satisfying ri < r < ri+1, where ri = i d.

    3. Let ai be the angle by which the arcs of a cell in the i-th level are subtended. And let the j-th cell in the i-th level be a region satisfying j ai < a < (j+1) ai

    Then, the drawing code should be like the following.

        def draw_maze(self, graph):
        ...
        x0 = y0 = self.canvas_size // 2
        d = self.line_length + self.corridor_size
        for level in range(1, self.num_levels):
            r_i = (level - 1) * d
            a_i = 2*math.pi / 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 parent_cell not in graph[cell_1d] and level > 1:
                    draw.arc(
                        [x0 - r_i, y0 - r_i, x0 + r_i, y0 + r_i],
                        start=180/math.pi * cell*a_i, end=180/math.pi * (cell+1)*a_i,
                        fill='black', width=self.wall_width
                    )

                if left_cell not in graph[cell_1d]:
                    c, s = math.cos(cell*a_i), math.sin(cell*a_i)
                    draw.line(
                        [x0 + r_i*c, y0 + r_i*s, x0 + (r_i+d)*c, y0 + (r_i+d)*s],
                        fill='black', width=self.wall_width
                    )