dark theme

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

Generating a maze with the Prim's algorithm

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

Generating a maze with the Kruskal's algorithm

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

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

Generating a maze with a backtracker algorithm

Different rendering modes

I started with 2-colors mazes:

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

Simple maze

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

Mosaic maze

One about invaders:

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

Invaders maze

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

vertical bias

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

vertical bias centered

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

maze with shading from center

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

lava river

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

maze shaded based on the solution with the Kruskal algorithm

With the backtracker algorithm:

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

maze shaded based on the solution with the backtracker algorithm

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.

blog comments powered by Disqus

If you enjoyed this article, feel free to Flattr this.