Recursive Backtracker maze – more features and animation with Matplotlib and Python

Recursive Backtracker maze – more features and animation with Matplotlib and Python

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.

You can check the source code in GitHub or view the entire repository.

Create frames

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:

Python

Animate frames

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. %03d means 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:

Python

and updated its position at every step:

Python

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.

Python

Please note that there is an error in the comment: the parameters 0.24 and 0.4 were not obtained from those values of D1, R1, D2, 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 drawDeadEnd function:

Python

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 'marker' is None and then stored in that key
    • it has a high zorder to show it on top of dead_end circles instead of behind them
    • whenever new farther distance is determined, that farthest circle is moved and resized

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.

Learning points

It is easy to overwrite a variable in Python

Leave a Reply

avatar
  Subscribe  
Notify of