使用 PIL 的 Python 迷宫生成出错了

Question

我一直在研究专门的圆形迷宫生成，使用 PIL 库将迷宫绘制到图像上。

在上面的输出图像中，有两个问题。

1. 迷宫墙线不完整，但存在。线路长度不符合应有的长度，导致“半迷宫”。

2. 随着圆形迷宫的扩展性质，每一层（或我在脚本中命名的“级别”）决定放入该层的单元格数量，从而允许一个看起来更自然的迷宫，而不是带有走廊的迷宫当您远离中心时，它们的尺寸会继续增大。当将两层连接在一起时，这会导致轻微的差异。并非每个级别都有。就在细胞计数需要增加的时候。

我该如何解决这些问题？以下是目前的实现。

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)

Answer 1

您错误地计算了单元格的坐标并颠倒了检查相邻单元格的条件。

您需要清楚地定义单元格的几何形状，如下例所示。

1. 迷宫中的点在笛卡尔坐标系中将被描述为（x，y），在极坐标系中将被描述为（r，a）。原点是圆的中心，x 轴从左到右，y 轴从上到下。根据定义，x = r cos(a) 和 y = r sin(a)。

2. 令 d 为细胞径向壁的长度。并令第 i 层为满足 r_i < r < r_i+1 的区域，其中 r_i = i d。

3. 令 a_i 为第 i 层中单元的弧所对的角度。并令第 i 层中的第 j 个单元格为满足 j a_i < a < (j+1) a_i

   的区域

那么，绘图代码应该如下所示。

    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)
                if self.parent_index_1d(level, 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 self.left_index_1d(level, 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
                    )