OiO.lk Community platform!

Oio.lk is an excellent forum for developers, providing a wide range of resources, discussions, and support for those in the developer community. Join oio.lk today to connect with like-minded professionals, share insights, and stay updated on the latest trends and technologies in the development field.
  You need to log in or register to access the solved answers to this problem.
  • You have reached the maximum number of guest views allowed
  • Please register below to remove this limitation

Python Maze Generation using PIL going wrong

  • Thread starter Thread starter asdf
  • Start date Start date
A

asdf

Guest
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

Code:
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)
<p>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:</p>
<p>Issue One:
Maze wall lines are incomplete, but present. The line length is not as it should be, leading to a "half maze".</p>
<p>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.</p>
<p>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!</p>
<p><a href="https://i.sstatic.net/12LFrz3L.png" rel="nofollow noreferrer">Example maze generated from script</a></p>
<pre><code>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)
</code></pre>
<p>The above script is recommended to be run using pypy (makes generation a lot faster)</p>
 

Latest posts

B
Replies
0
Views
1
Blundering Ecologist
B
Top