On mazes with Rust

While browsing the internets, I came across a maze as a wallpaper. I wanted to learn Rust and decided to experiment with Rust by generating mazes.

The result of those experiments is available on github.

3 Algorithms

On wikipedia, there are 3 algorithms. I started implementing the Prim’s algorithm. It took 295 iterations to generate this maze:

maze -r plain -g100x100 --foreground #585858 --animation --algorithm prim prim.gif

Then I worked on Kruskal’s algorithm. Here it needed 287 iterations to generate this maze

maze -r plain -g100x100 --foreground #585858 --animation --algorithm kruskal kruskal.gif

Finally I worked on a Backtracker algorithm. This example took 169 iterations.

maze -r plain -g100x100 --foreground #585858 --animation --algorithm backtracker backtracker.gif

Different rendering modes

I started with 2-colors mazes:

maze -g630x400 --foreground #ffffff --background #000000 plain.png

I added different rendering mode based on previous image generation work I did. One that look like the background of the blog but not quite good:

maze -g 635x400 -r mosaic mosaic.png

One about invaders:

maze -g 637x399 --foreground #585858 -r invaders invaders.png

Bias

Since the algorithm are based on random number, I wanted to introduce some bias.

maze -g 630x400 --foreground #585858 -b 0.65 vertical_bias.png

Here, we can see the impact of the algorithm. It gets more vertical as it goes to the right starting from the top left corner.

I added an option to specify the starting point of the algorithm.

maze -g 630x400 --foreground #585858 -b 0.65 -o 0.5x0.5 bias_centered.png

Shading

These 2-colors images are nice but let’s bring some more colors!

The color goes from red to white based on the length of path from the center:

maze -g630x400 -o 0.5x0.5 --gradient length maze.png

An other option is to have the solution of the maze drawn and then have a shading based on how far the cells are from the solution. It generates what I call the lava river:

maze -g630x400 --foreground #d70000\ #585858 --gradient solution lava_river.png

Here, we see the impact of the Prim algorithm. It tends to produce mazes that go from top left to bottom right in a direct way.

With the Kruskal algorithm:

maze -g630x400 --foreground #d70000\ #585858 --gradient solution --algorithm kruskal kruskal.png

With the backtracker algorithm:

maze -g630x400 --foreground #d70000\ #585858 --gradient solution --algorithm backtracker backtracker.png

Contributions

During my development of maze.rs, I wrote 2 crates:

• debug_macros to add the macro dbg!() that prints a message (like println!()) but have it prefixed by the file and line where the call is written.
• color_scaling: function to have some shading between 2 colors.

I also wrote some ebuilds in my gentoo overlay.

I also found a bug in the rust library I used to generate a gif and patched it.