There are plenty of maze generation algorithms, some are described here and here. I decided to use one to learn some Python. I chose Recursive Backtracker. You can find longer descriptions in both links, but briefly:
- choose a random cell in the maze
- walk in a random direction
- when there is no possibility to walk farther, go back (backtrack) to find the first cell from which it is possible to proceed
- the algorithm ends when there is no possibility to move from any cell
Since it was my first Windows program in Python, I had to start with an IDE. At first, I tried Trinket, but it missed some features of Matplotlib. Next was Visual Studio Code. I swear at some moment the code stopped compiling when I used the official Python extension. When I checked it today, it worked very well…
As I started learning Python, I discovered some oddities and learned how to apply object-oriented patterns in Python. Maybe pure OO code shouldn’t be written in this language, but I had no trustworthy resource at a hand.
I spent a lot of time trying to figure out how to draw a simple line as part of my maze. Just a line. I found solutions that used Turtle, PyGame, ASCII, Matplotlib, Tkinter, to name some. Turtle? Chart library? ASCII? And sophisticated graphics libraries? I was surprised there was nothing quick available. I was more surprised to find that many people use Matplotlib for drawing shapes and even for animation…
Not too content, I used Matplotlib as well. Here are the most basic tasks:
import matplotlib.pyplot as pyplot
- set size of the image (chart):
- hide the labels on axes:
- show the chart:
pyplot.show()(this step seemed unnecessary in that GUI)
- draw a line:
pyplot.plot([x1, x2], [y1, y2], color='black'). Now, these are unpredictable parameters: first two Xs, then two Ys. It was confusing enough for me to create a function to draw lines with more intuitive parameters:
So far so “good”. However, my maze algorithm iteratively draws the maze by erasing walls. How to remove a line from the chart? I tried drawing it again, but with white color. As a result, there was a white line with a black border. It didn’t look too clear. So I started experimenting with different styles of charts:
This style, together with white color for lines and black color for erasing, looked good enough. I decided to leave the ticks for easier orientation in the maze.
In the top the output from Visual Studio Code, in the bottom from Spyder IDE. It’s hard to create consistent output in any compiler, maybe by customizing every style option in Matplotlib.
It turned out that Python does not support two- or more-dimensional arrays, only jagged arrays. There are libraries, like NumPy, that provide support. I decided to use what was available in pure Python, so I created:
That array has size of
size_x * size_y and is filled with
False. In order to check the cell in 3rd column (X) and 1st row (Y), I’d have to write:
visitedMaze. At least referring to that array’s items is simple.
And the last discovery for today – there is no
switch statement in Python! Some suggested workarounds for developers coming from different languages include putting numerous
elif (“else if”) or using a dictionary.
OK, so what about the algorithm itself? It’s not the shortest implementation, but I think it’s quite easy. Check the source maze.py or the entire repository. Adjust
size_y and run for a random maze.
Continue to next lesson – animation.