7
\$\begingroup\$

I am teaching programming (in this case - 1 on 1 tutoring of a teenager interested in programming) and this code will be a final stage of a progression toward program generating a maze.

Any comments how this code can be improved are welcomed! But problems with unclear code that break standard practices are especially welcomed, performance issues are less important here.

Note that as I am teaching beginner I prefer to avoid more complicated or Python specific constructions like for example if __name__ == '__main__', generator, itertools and focus on more generic ones - structure of a program, debugging strategies, loops or classes.

"""
maze generator
"""
import random
from PIL import Image

def main():
    WIDTH = 100
    HEIGHT = 100
    TILE_SIZE_PX = 4
    WHITE = (255, 255, 255)
    PASSAGE_COLOR = WHITE
    BLACK = (0, 0, 0)
    WALL_COLOR = BLACK
    maze = Maze(width=WIDTH, height=HEIGHT)
    maze.output_maze("maze.png", passage_color=PASSAGE_COLOR, wall_color=WALL_COLOR, tile_size_in_pixels=TILE_SIZE_PX)
    maze = MazeWithWideCorridors(width=WIDTH, height=HEIGHT)
    maze.output_maze("maze_alternative.png", passage_color=PASSAGE_COLOR, wall_color=WALL_COLOR, tile_size_in_pixels=TILE_SIZE_PX)


class Maze:
    """
    generates maze using DFS based algorithm
    """
    def __init__(self, width, height):
        self.WIDTH = width
        self.HEIGHT = height
        self.PASSAGE_COLOR = (255, 255, 255)
        self.WALL_COLOR = (0, 0, 0)
        self.image = Image.new("RGB", (self.WIDTH, self.HEIGHT), self.WALL_COLOR)
        self.pixels = self.image.load()
        self.generate()

    def generate(self):
        """
        expands maze starting from (0, 0) as a seed location,
        as long as eligible places to carve new tunnels exist
        """
        candidates_list = []
        candidates_list.append((0, 0))
        while len(candidates_list) > 0:
            processed = candidates_list.pop()
            x = processed[0]
            y = processed[1]
            self.pixels[x, y] = self.PASSAGE_COLOR
            new_candidates = self.children(x, y)
            if len(new_candidates) > 0:
                candidates_list.append(processed)
                candidates_list.append(random.choice(new_candidates))

    def output_maze(self, image_output_filepath, tile_size_in_pixels=1, passage_color=(255, 255, 255), wall_color=(0, 0, 0)):
        """
        shows maze image at the screen and
        outputs maze to specified location in image_output_filepath
        using file format implied by extensions
        """
        output = Image.new("RGB", (self.WIDTH, self.HEIGHT))
        output_pixels = output.load()
        for x in range(self.WIDTH):
            for y in range(self.HEIGHT):
                if self.pixels[x, y] == self.PASSAGE_COLOR:
                    output_pixels[x, y] = passage_color
                else:
                    output_pixels[x, y] = wall_color
        output = output.resize((self.WIDTH*tile_size_in_pixels, self.HEIGHT*tile_size_in_pixels))
        output.show()
        output.save(image_output_filepath)

    def children(self, parent_x, parent_y):
        """
        returns list of all currently eligible locations to expand from (parent_x, parent_y)
        list contains tuples of integers
        """
        up = (parent_x, parent_y - 1)
        left = (parent_x - 1, parent_y)
        right = (parent_x + 1, parent_y)
        down = (parent_x, parent_y + 1)
        returned = []
        if self.is_safe_to_tunnel(parent_x, parent_y, up[0], up[1]):
            returned.append(up)
        if self.is_safe_to_tunnel(parent_x, parent_y, left[0], left[1]):
            returned.append(left)
        if self.is_safe_to_tunnel(parent_x, parent_y, down[0], down[1]):
            returned.append(down)
        if self.is_safe_to_tunnel(parent_x, parent_y, right[0], right[1]):
            returned.append(right)
        return returned

    def is_safe_to_tunnel(self, parent_x, parent_y, x, y):
        """
        returns true if location (x, y) can be turned into a passage
        false otherwise

        protects agains going outside image or making
        loop or passage wider than 1 tile

        returns false if (x, y) is not inside the image
        returns false if (x, y) is already a passage
        returns false if there are passages around (x, y) that are
        not on (parent_x, parent_y) location or around it
        returns true if location (x, y) can be turned into a passage
        """
        if not self.inside_image(x, y):
            return False
        if self.pixels[x, y] == self.PASSAGE_COLOR:
            return False
        if self.is_colliding_with_other_tunnels(parent_x, parent_y, x, y):
            return False
        return True

    def is_colliding_with_other_tunnels(self, parent_x, parent_y, x, y):
        """
        checks whatever tunnel at this legal location can
        be placed without colliding with other tunnels
        """
        for offset in self.offsets_to_surrounding_tiles():
            if self.is_populated(x + offset[0], y + offset[1]):
                x_distance_to_parent = x + offset[0] - parent_x
                y_distance_to_parent = y + offset[1] - parent_y
                if abs(x_distance_to_parent) + abs(y_distance_to_parent) > 1:
                    return True
        return False

    def offsets_to_surrounding_tiles(self):
        """
        returns list of 2-tuples with distances to
        each of 8 neighbouring tiles
        """
        return [(1, 0), (1, -1), (0, -1), (-1, -1),
                (-1, 0), (-1, 1), (0, 1), (1, 1)]

    def is_populated(self, x, y):
        """returns true if this locations contains passage, false if wall or is outside image"""
        if not self.inside_image(x, y):
            return False
        if self.pixels[x, y] == self.PASSAGE_COLOR:
            return True
        return False

    def inside_image(self, x, y):
        """
        returns true if (x, y) is inside image,
        return false otherwise
        """
        if x < 0:
            return False
        if y < 0:
            return False
        if x >= self.WIDTH:
            return False
        if y >= self.HEIGHT:
            return False
        return True

class MazeWithWideCorridors(Maze):
    def is_colliding_with_other_tunnels(self, parent_x, parent_y, x, y):
        """
        checks whatever tunnel at this legal location can
        be placed without colliding with other tunnels
        """
        for offset in self.offsets_to_surrounding_tiles():
            if self.is_populated(x + offset[0], y + offset[1]):
                x_distance_to_parent = x + offset[0] - parent_x
                y_distance_to_parent = y + offset[1] - parent_y
                if abs(x_distance_to_parent) > 1 or abs(y_distance_to_parent) > 1:
                    return True
        return False

main()

Examples of generated files:

enter image description here enter image description here

\$\endgroup\$
  • \$\begingroup\$ What rules, if any, must the resulting maze conform to? \$\endgroup\$ – 200_success Apr 16 at 16:56
  • 1
    \$\begingroup\$ @200_success There are no limitations/rules. Be a maze and look impressive? \$\endgroup\$ – Mateusz Konieczny Apr 16 at 19:50
4
\$\begingroup\$

I'll start off with some possible improvements in the logic.

Firstly, in Maze::generate, the initialisation of candidates_list could be simplified from

candidates_list = []
candidates_list.append((0, 0))

to

candidates_list = [(0, 0)]

Secondly, right on the next line, the condition could be simplified from

while len(candidates_list) > 0:

to

while candidates_list:

The behaviour is similar: the loop runs while candidates_list contains items. If it is empty, the loop terminates. The same goes for if len(new_candidates) > 0::

if new_candidates:

Thirdly, there are a couple places where you can utilise unpacking. For instance, in Maze::generate, we have

 x = processed[0]
 y = processed[1]

This can be written in one-line as

x, y = processed

In Maze::is_colliding_with_other_tunnels, you can improve readability by unpacking the tuple directly. Instead of

for offset in self.offsets_to_surrounding_tiles():
    if self.is_populated(x + offset[0], y + offset[1]):
        x_distance_to_parent = x + offset[0] - parent_x
        y_distance_to_parent = y + offset[1] - parent_y
        if abs(x_distance_to_parent) + abs(y_distance_to_parent) > 1:
            return True
return False

offset can be unpacked into offset_x, offset_y:

for offset_x, offset_y in self.offsets_to_surrounding_tiles():
    if self.is_populated(x + offset_x, y + offset_y):
        x_distance_to_parent = x + offset_x - parent_x
        y_distance_to_parent = y + offset_y - parent_y
        if abs(x_distance_to_parent) + abs(y_distance_to_parent) > 1:
            return True
return False

(This might also be a good opportunity to let your student have a go at rewriting the above into a one-liner using any and a comprehension. Might be a lil' long-winded though. 🤔)

This can also be done in MazeWithWideCorridors::is_colliding_with_other_tunnels.

I think you might also be interested in knowing that the following is possible in Maze::children:

if self.is_safe_to_tunnel(parent_x, parent_y, *up):
    returned.append(up)

*up also does unpacking, but here, unpacks a tuple as arguments into the function. Generally, this can be done when the function accepts arguments from the tuple sequentially. This saves a fair deal of typing.

I actually don't know what the community consensus is on this one – whether it is recommended or not. But it's such a neat Python feature...


With regards to naming, I would argue that your variables x_distance_to_parent should be named x_displacement_to_parent since they seem to still take into account positive/negative values, implying direction. From a physics perspective, distance is a scalar and doesn't take direction into account.

However, rather than using x_displacement, I'd stick with x_distance as it's more understandable. To be consistent with the previous paragraph, I'd take the absolute value immediately. For instance, in Maze::is_colliding_with_other_tunnels, instead of

x_distance_to_parent = x + offset[0] - parent_x
y_distance_to_parent = y + offset[1] - parent_y
if abs(x_distance_to_parent) + abs(y_distance_to_parent) > 1:
    return True

consider

x_distance_to_parent = abs(x + offset_x - parent_x)
y_distance_to_parent = abs(y + offset_y - parent_y)
if x_distance_to_parent + y_distance_to_parent > 1:
    return True

This can also be considered in MazeWithWideCorridors::is_colliding_with_other_tunnels.


With regards to style, PEP 8 recommends two lines right after imports and two lines right before and after class declarations.

import random
from PIL import Image
                                        # <<<    1
                                        # <<<    2    (after imports)
def main():
    # ...
                                        # <<<    1
                                        # <<<    2    (before class)
class Maze:
    # ...

    def inside_image(self, x, y):
        # ...
                                        # <<<    1
                                        # <<<    2    (before/after class)
class MazeWithWideCorridors(Maze):
    # ...
                                        # <<<    1
                                        # <<<    2    (after class)
main()

This may seem overtly pedantic, but well, it's PEP 8 ¯\_(ツ)_/¯.

\$\endgroup\$
  • 1
    \$\begingroup\$ PEP 8, thanks! I forgot to rerun autopep8 after final refactoring. \$\endgroup\$ – Mateusz Konieczny Apr 16 at 20:03
  • 1
    \$\begingroup\$ I started applying improvements (starting from github.com/matkoniecz/quick-beautiful/commit/… ) - thank you for a help! \$\endgroup\$ – Mateusz Konieczny Apr 16 at 20:06
  • \$\begingroup\$ using len(candidates_list) > 0 over candidates_list was intentional, I prefer explicit over implicit magic. \$\endgroup\$ – Mateusz Konieczny Apr 16 at 20:10
  • \$\begingroup\$ I think that now I went through suggestions, thanks you again! \$\endgroup\$ – Mateusz Konieczny Apr 16 at 20:17
  • 1
    \$\begingroup\$ @MateuszKonieczny You're very much welcome. You do make a case for using len(candidates_list) > 0. I personally prefer candidates_list. :P I guess in the end, it does come down to some element of subjection and preference. Good luck with your lessons! \$\endgroup\$ – TrebledJ Apr 16 at 20:33
3
\$\begingroup\$

I don't see anything major. Just some nitpicks:

offsets_to_surrounding_tiles could be written using a list comprehension/generator expression so the offsets don't need to be hard-coded:

def offsets_to_surrounding_tiles2():
    return [(x, y)
            for y in range(-1, 2)
            for x in range(-1, 2)
            if (x, y) != (0, 0)] # So we don't include the centre

>>> offsets_to_surrounding_tiles()
[(1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1)]

This has the benefit that if you ever decided to expand beyond the Moore Neighborhood that you're currently using, you can modify this function to generate the offsets for a greater neighborhood by including a depth parameter:

def offsets_to_surrounding_tiles2(depth):
    return [(x, y)
            for y in range(-depth, depth + 1)
            for x in range(-depth, depth + 1)
            if (x, y) != (0, 0)]

>>> offsets_to_surrounding_tiles2(1)
[(-1, -1), (0, -1), (1, -1), (-1, 0), (1, 0), (-1, 1), (0, 1), (1, 1)]

>>> offsets_to_surrounding_tiles2(2)
[(-2, -2), (-1, -2), (0, -2), (1, -2), (2, -2), (-2, -1), (-1, -1), (0, -1), (1, -1), (2, -1), (-2, 0), (-1, 0), (1, 0), (2, 0), (-2, 1), (-1, 1), (0, 1), (1, 1), (2, 1), (-2, 2), (-1, 2), (0, 2), (1, 2), (2, 2)]

This is potentially a violation of YAGNI, but it may be a good example of what can be done with comprehensions. This function could also be written as a generator expression if you think that the whole list won't necessarily need to be consumed.

It also doesn't seem proper to have this function as an instance method of the class since it doesn't have anything to do with any particular instance (evidenced by the fact that self is ignored). This would be better as a static/class method, or (imo) better yet, as a loose function unrelated to the class.


You have a few functions that use several returns instead of just using logical operators. For example:

def inside_image(self, x, y):
    if x < 0:
        return False
    if y < 0:
        return False
    if x >= self.WIDTH:
        return False
    if y >= self.HEIGHT:
        return False
    return True

I think this would be cleaner by making use of and and comparison chaining:

def inside_image(self, x, y):
    return 0 <= x < self.WIDTH
           and 0 <= y < self.HEIGHT

I think it's much easier to tell the logic at a glance with this version. Arguably, this function could be made easier to test by passing in the width and height too. Right now, you need to instantiate a Maze to test this function, which is more painful than it needs to be.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.