In the previous post, I generated a simple maze. I wasn’t sure the algorithm worked as intended unless I debugged or animated it. I chose the second option. I also added marking the beginning and end of the maze quest.
There are some options provided by Matplotlib to create animations, like subfigures, delays, and even a special routine to animate the chart. Terrified by the complexity, I chose the simplest solution to dump the chart to a PNG file at every step:
Since I had a bunch of PNG files, I needed a tool to combine them into a GIF or AVI file. I decided to use open source video converting tool, FFmpeg. The options I first chose were:
ffmpeg.exe -framerate 6 -i maze_%03d.png video.avi
-framerate 6– 6 frames per second
-i maze_%03d.png– these are the file names with my animation’s frames.
%03dmeans there are digits with preceding zeroes, in total 3 characters: 001, 002, …, 999
video.avi– this is the name of the output video
The generated video was not of best quality, and had strange artefacts in the animated frames. I looked how to improve the quality and I ended up with:
ffmpeg.exe -framerate 6 -i maze_%03d.png -codec:v libx264 -vf fps=25 -pix_fmt yuv420p video.mp4
-codec:v libx264– use libx264 video codec (open source implementation of MPEG-4 H.264
-filter:v fps=25– use “frame rate” output video filter to set 25 fps (though this is the default)
-pix_fmt yuv420p– use yuv420p pixel format. Why? Because it was suggested in the documentation 😉
You can watch the video here:
Mark current position
The next idea was to mark the current position to visualize backtracking. So I created a yellow circle:
and updated its position at every step:
At some moment I wanted to also show the distance from the beginning (the initial cell) by decreasing the size of the circle. I thought of the following way of determining the radius:
- at some point, say 5% (cell B2) of the maximum possible distance (which is
size_x * size_y), the radius should be equal to 0,4 (cell D2)
- at another point, say 50% (cell B1) of the maximum possible distance, the radius should be equal to 0,1 (cell D1)
Because the radius will be decreasing with distance, I assumed the formula would be:
radius = max_distance * b / (x + max_distance * a)
I determined the formula and created a Google spreadsheet to experiment and determine the optimal parameters that so the circle size degrades visibly but slowly.
Please note that there is an error in the comment: the parameters 0.24 and 0.4 were not obtained from those values of
R2. In fact, I modified a bit the calculated values until I was satisfied with the effect.
And there is an error in the function itself: it accepts a parameter which is ignored. I did not detect the error previously because I passed exactly the same value for the parameter:
len(visitedCells). By the way, this is the distance from the initial cell.
Mark ending points
I also wanted to mark the farthest point from the initial cell; that would be the end point of the maze. I thought (hopefully rightly) that the farthest point is one of the points at which the algorithm hits a wall and has to backtrack. So I added a check whether we are backtracking or going forward (the
backing variable) and implemented this functionality in
What is going on here?
- line 122: we are only interested in cells when we backtrack
- line 123: this is the distance from the initial cell, which will be used i.a. to determine if this is the farthest point from the start
- line 125: similarly, but much simpler, I wanted to increase the size of the end circle as the distance from the start increases:
min(0.4, 0.5 * distance / size_x / size_y)
- lines 125-127: drawing every point when the algorithm backtracks with a light red circle
- lines 129-140: drawing only one farthest point with a vivid red circle
- the circle is created only once if
Noneand then stored in that key
- it has a high
zorderto show it on top of
dead_endcircles instead of behind them
- whenever new farther distance is determined, that farthest circle is moved and resized
- the circle is created only once if
In the next post, I describe refactoring of this Python code and expain some advanced class concepts, like static methods, inner classes or private members.