9
\$\begingroup\$

This Python code generates mazes with color and size customization. I intend to add several new maze generating algorithms(Sidewinder, Kruskal, Prim ...) to the Maze class but for now, there is only one (Binary tree algorithm). I need feedback for the overall code and there are a few specific points that I need suggestions on how to refactor/improve without affecting the features, main concern is feedback for accuracy of pixel calculations.


  • In _make_grid_image(): How to improve the drawing technique to be more accurate without leaving traces that need to be fixed (I fixed them by x_end and y_end coordinates for closing the maze)
  • In make_binary_tree_maze_image() and make_binary_tree_maze_visualization(): both functions share the same logic (one creates a single image and one generates a GIF of the maze being created) however, because of the inaccuracy of the drawing, I added some constants to adjust the painting and the over painting for each frame in the case of GIF generation and at the end in the case of the generation of a single maze image. In order not to confuse you, try changing the line_width default parameter in the Maze constructor and generate a single image using make_binary_tree_maze_image(). The result most probably will contain traces of the painting and overpainting of lines. I need suggestions on how to improve this without affecting the functionalities given that I will be using the same code for future methods of the Maze class (that will include other maze generating algorithms).

The code works perfectly fine, have fun generating mazes and awaiting your suggestions for improvements.

Note: generation of 500 x 500 gif frames might take a while (30-60 secs) however generating a single full maze image takes less than a second, more for really large images (1000+ x 1000+)

Here are GIF examples for mazes created by binary tree algorithm:

50 x 50 Dark Blue x Red 50 x 50 Black x White

50 x 50 Purple x Light Green 50 x 50 Yellow x Dark Orange


#!/usr/bin/env python
from PIL import Image, ImageDraw
import random
import os
import glob
import imageio
import shutil


class Cell:
    """Create grid cell."""
    def __init__(self, row_index, column_index, rows, columns):
        """
        Initialize grid cell.
        row_index: cell row index.
        column_index: cell column index.
        rows: number of rows in grid.
        columns: number of columns in grid.
        """
        if row_index >= rows or row_index < 0:
            raise ValueError(f'Expected a row index in range(0, {rows}) exclusive, got {row_index}')
        if column_index >= columns or column_index < 0:
            raise ValueError(f'Expected a column index in range(0, {columns} exclusive, got {column_index}')
        self.row = row_index
        self.column = column_index
        self.rows = rows
        self.columns = columns
        self.linked_cells = []

    def neighbors(self, grid):
        """Return North, South, East, West neighbor cells."""
        neighbors = []
        north = self.row - 1, self.column
        if north[0] < 0:
            north = 0
            neighbors.append(0)
        if north:
            neighbors.append(grid[north[0]][north[1]])
        south = self.row + 1, self.column
        if south[0] >= self.rows:
            south = 0
            neighbors.append(0)
        if south:
            neighbors.append(grid[south[0]][south[1]])
        east = self.row, self.column + 1
        if east[1] >= self.columns:
            east = 0
            neighbors.append(0)
        if east:
            neighbors.append(grid[east[0]][east[1]])
        west = self.row, self.column - 1
        if west[1] < 0:
            west = 0
            neighbors.append(0)
        if west:
            neighbors.append(grid[west[0]][west[1]])
        return neighbors

    def link(self, other, grid):
        """Link 2 unconnected cells."""
        if self in other.linked_cells or other in self.linked_cells:
            raise ValueError(f'{self} and {other} are already connected.')
        if self.columns != other.columns or self.rows != other.rows:
            raise ValueError('Cannot connect cells in different grids.')
        if self not in other.neighbors(grid) or other not in self.neighbors(grid):
            raise ValueError(f'{self} and {other} are not neighbors and cannot be connected.')
        if not isinstance(other, Cell):
            raise TypeError(f'Cannot link Cell to {type(other)}.')
        self.linked_cells.append(other)
        other.linked_cells.append(self)

    def unlink(self, other):
        """Unlink 2 connected cells."""
        if self not in other.linked_cells or other not in self.linked_cells:
            raise ValueError(f'{self} and {other} are not connected.')
        self.linked_cells.remove(other)
        other.linked_cells.remove(self)

    def coordinates(self):
        """Return cell (row, column)."""
        return self.row, self.column

    def __str__(self):
        """Cell display."""
        return f'Cell{self.coordinates()}'


class Maze:
    """
    Generate a maze using different algorithms:
    - Binary Tree algorithm.
    """
    def __init__(self, rows, columns, width, height, line_width=5, line_color='black', background_color='white'):
        """
        Initialize maze variables:
        rows: number of rows in initial grid.
        columns: number of columns in initial grid.
        width: width of the frame(s).
        height: height of the frame(s).
        line_width: width of grid/maze lines.
        line_color: color of grid/maze lines.
        background_color: color of the grid/maze background (cells/path)
        """
        if width % columns != 0:
            raise ValueError(f'Width: {width} not divisible by number of columns: {columns}.')
        if height % rows != 0:
            raise ValueError(f'Height: {height} not divisible by number of {rows}.')
        self.rows = rows
        self.columns = columns
        self.width = width
        self.height = height
        self.line_width = line_width
        self.line_color = line_color
        self.background_color = background_color
        self.cell_width = width // columns
        self.cell_height = height // rows
        self.drawing_constant = line_width // 2
        self.path = input('Enter path to folder to save maze creation GIF: ').rstrip()

    def _make_grid_image(self):
        """Initiate maze initial grid image."""
        grid = Image.new('RGB', (self.width, self.height), self.background_color)
        for x in range(0, self.width, self.cell_width):
            x0, y0, x1, y1 = x, 0, x, self.height
            column = (x0, y0), (x1, y1)
            ImageDraw.Draw(grid).line(column, self.line_color, self.line_width)
        for y in range(0, self.width, self.cell_height):
            x0, y0, x1, y1 = 0, y, self.width, y
            row = (x0, y0), (x1, y1)
            ImageDraw.Draw(grid).line(row, self.line_color, self.line_width)
        x_end = (0, self.height - self.drawing_constant),\
                (self.width - self.drawing_constant, self.height - self.drawing_constant)
        y_end = (self.width - self.drawing_constant, 0), (self.width - self.drawing_constant, self.height)
        ImageDraw.Draw(grid).line(x_end, self.line_color, self.line_width)
        ImageDraw.Draw(grid).line(y_end, self.line_color, self.line_width)
        return grid

    def _create_maze_cells(self):
        """Return maze cells."""
        return [[Cell(row, column, self.rows, self.columns) for column in range(self.columns)]
                for row in range(self.rows)]

    def _binary_tree_configuration(self):
        """Return binary tree maze configuration."""
        cells = self._create_maze_cells()
        for row in range(self.rows):
            for column in range(self.columns):
                current_cell = cells[row][column]
                north, south, east, west = current_cell.neighbors(cells)
                to_link = random.choice('nw')
                if not north and not west:
                    continue
                if to_link == 'n' and north:
                    current_cell.link(north, cells)
                if to_link == 'w' and west:
                    current_cell.link(west, cells)
                if to_link == 'n' and not north:
                    current_cell.link(west, cells)
                if to_link == 'w' and not west:
                    current_cell.link(north, cells)
        return cells

    def make_binary_tree_maze_image(self):
        """Produce a maze image using binary tree algorithm."""
        maze = self._make_grid_image()
        cells = self._binary_tree_configuration()
        linked_cells = {cell.coordinates(): [linked.coordinates() for linked in cell.linked_cells]
                        for row in cells for cell in row}
        for row in range(self.rows):
            for column in range(self.columns):
                current_cell_coordinates = (row, column)
                if (row, column + 1) in linked_cells[current_cell_coordinates]:
                    x0 = (column + 1) * self.cell_width
                    y0 = (row * self.cell_height) + (self.line_width - 2)
                    x1 = x0
                    y1 = y0 + self.cell_height - (self.line_width + 1)
                    wall = (x0, y0), (x1, y1)
                    ImageDraw.Draw(maze).line(wall, self.background_color, self.line_width)
                if (row + 1, column) in linked_cells[current_cell_coordinates]:
                    x0 = column * self.cell_width + self.line_width - 2
                    y0 = (row + 1) * self.cell_height
                    x1 = x0 + self.cell_width - (self.line_width + 1)
                    y1 = y0
                    wall = (x0, y0), (x1, y1)
                    ImageDraw.Draw(maze).line(wall, self.background_color, self.line_width)
        x_end = (0, self.height - self.drawing_constant),\
                (self.width - self.drawing_constant, self.height - self.drawing_constant)
        y_end = (self.width - self.drawing_constant, 0), (self.width - self.drawing_constant, self.height)
        ImageDraw.Draw(maze).line(x_end, self.line_color, self.line_width)
        ImageDraw.Draw(maze).line(y_end, self.line_color, self.line_width)
        return maze

    def make_binary_tree_maze_visualization(self, frame_speed):
        """
        ** NOTE: Works on Unix systems only.
        Create a GIF for maze being created by a binary tree algorithm.
        frame_speed: speed in ms.
        """
        print('GIF creation started ...')
        os.chdir(self.path)
        maze = self._make_grid_image()
        cells = self._binary_tree_configuration()
        linked_cells = {cell.coordinates(): [linked.coordinates() for linked in cell.linked_cells]
                        for row in cells for cell in row}
        count = 0
        for row in range(self.rows):
            for column in range(self.columns):
                current_cell_coordinates = (row, column)
                # Remove vertical walls
                if (row, column + 1) in linked_cells[current_cell_coordinates]:
                    x0 = (column + 1) * self.cell_width
                    y0 = (row * self.cell_height) + (self.line_width - 2)
                    x1 = x0
                    y1 = y0 + self.cell_height - (self.line_width + 1)
                    wall = (x0, y0), (x1, y1)
                    ImageDraw.Draw(maze).line(wall, self.background_color, self.line_width)
                    y_end = (self.width - self.drawing_constant, 0), (self.width - self.drawing_constant, self.height)
                    ImageDraw.Draw(maze).line(y_end, self.line_color, self.line_width)
                    maze.save(self.path + str(count) + '.png', 'png')
                    count += 1
                # Remove horizontal walls
                if (row + 1, column) in linked_cells[current_cell_coordinates]:
                    x0 = column * self.cell_width + self.line_width - 2
                    y0 = (row + 1) * self.cell_height
                    x1 = x0 + self.cell_width - (self.line_width + 1)
                    y1 = y0
                    wall = (x0, y0), (x1, y1)
                    ImageDraw.Draw(maze).line(wall, self.background_color, self.line_width)
                    x_end = (0, self.height - self.drawing_constant), \
                            (self.width - self.drawing_constant, self.height - self.drawing_constant)
                    ImageDraw.Draw(maze).line(x_end, self.line_color, self.line_width)
                    maze.save(self.path + str(count) + '.png', 'png')
                    count += 1
        rand_name = 'maze' + str(random.randint(10 ** 6, 10 ** 8))
        os.mkdir(rand_name)
        for file in os.listdir(self.path):
            if file.endswith('.png'):
                shutil.move(file, rand_name)
        os.chdir(rand_name)
        frames = glob.glob('*.png')
        frames.sort(key=lambda x: int(x.split('.')[0]))
        frames = [imageio.imread(frame) for frame in frames]
        imageio.mimsave(self.path + str(rand_name) + '.gif', frames, 'GIF', duration=frame_speed)
        print(f'Creation of {count} frames GIF successful.')


if __name__ == '__main__':
    maze_test = Maze(50, 50, 500, 500)
    maze_test.make_binary_tree_maze_image().show()
\$\endgroup\$
1
  • 2
    \$\begingroup\$ I have rolled back the edits again to the point where the code is the same as the code reviewed in the answer. I have also locked the post for a short while to prevent alterations. Please do not update the code in your question after it has been answered (even if you believe it does not invalidate the answers). This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. Feel free to post a follow-up question linking back to this one instead. \$\endgroup\$
    – rolfl
    Sep 4, 2019 at 11:04

1 Answer 1

6
\$\begingroup\$

Type hints

row_index, column_index, rows, columns

I can guess that these are all int based on the docs. But adding :int (etc) will help, here.

Variable reuse

    north = self.row - 1, self.column
    if north[0] < 0:
        north = 0
        neighbors.append(0)
    if north:
        neighbors.append(grid[north[0]][north[1]])

This is confusing. north starts off as a tuple, and then maybe becomes an int. First - it shouldn't be an int, it should be a bool based on your usage. Second - it shouldn't really change type. Variables should do one thing. Here you're using it for two things - coordinates, and a flag. Third - you don't even need the flag. Just replace if north with else.

Don't repeat yourself

The block I paste above is repeated four times with only minor variations. Think about what's common (references to self.row and self.column, bounds checking, appending to neighbours) and what changes (the deltas added to the coordinates, and the comparison value for bounds checking). Use this information to create a function that's called four times.

The same applies to this block:

            if (row, column + 1) in linked_cells[current_cell_coordinates]:
                x0 = (column + 1) * self.cell_width
                y0 = (row * self.cell_height) + (self.line_width - 2)
                x1 = x0
                y1 = y0 + self.cell_height - (self.line_width + 1)
                wall = (x0, y0), (x1, y1)
                ImageDraw.Draw(maze).line(wall, self.background_color, self.line_width)
            if (row + 1, column) in linked_cells[current_cell_coordinates]:
                x0 = column * self.cell_width + self.line_width - 2
                y0 = (row + 1) * self.cell_height
                x1 = x0 + self.cell_width - (self.line_width + 1)
                y1 = y0
                wall = (x0, y0), (x1, y1)
                ImageDraw.Draw(maze).line(wall, self.background_color, self.line_width)
    x_end = (0, self.height - self.drawing_constant),\
            (self.width - self.drawing_constant, self.height - self.drawing_constant)
    y_end = (self.width - self.drawing_constant, 0), (self.width - self.drawing_constant, self.height)
    ImageDraw.Draw(maze).line(x_end, self.line_color, self.line_width)
    ImageDraw.Draw(maze).line(y_end, self.line_color, self.line_width)

Most of that is doubled up and shouldn't be.

Factor out logic

if to_link == 'n':
   target = north or west
else:
   target = west or north
current_cell.link(target, cells)

This takes advantage of the fact that

  • to_link will only ever be n or w, so you can use an else
  • or semantics in Python will take the first thing that's truthy, which is effectively what you were doing
  • Only one call to current_cell.link is needed
\$\endgroup\$
3
  • \$\begingroup\$ any suggestions regarding the paint re-paint mechanism? I want to eliminate magic numbers and draw everything accurately, one of the reasons of repetition is that I'm not an expert when it comes to image processing so this might be the best I could do but of course there must be a better way that won't leave any traces and I won't have to repaint borders for each frame and tweak numbers manually inside the functions to get accurate frames. \$\endgroup\$
    – user203258
    Sep 3, 2019 at 3:35
  • 1
    \$\begingroup\$ Paint re-paint? Do you mean the four calls to ImageDraw.Draw? \$\endgroup\$
    – Reinderien
    Sep 3, 2019 at 3:47
  • \$\begingroup\$ yeah, try changing the line width parameter in the Maze constructor and see what happens, the higher the change, the higher you will get a pixelated image unless you change self.line_width - 2 and self.line_width + 1 and play with them a little bit until the image adjusts, I need another technique that calculates which pixels (x, y) coordinates more accurately and maybe put it in a new function or so that automatically adjusts according to size and line width changes \$\endgroup\$
    – user203258
    Sep 3, 2019 at 3:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.