Maze generator for teaching Python 3

Question

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()
```

• 200_success: What rules, if any, must the resulting maze conform to?

Answer 1

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 ̄\_(ツ)_/ ̄.

• TrebledJ: @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!

Answer 2

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.