by Greg Kotkowski

One of the best things about being a parent is that as an adult you can play with kids’ toys and nobody judges it as strange (men never grow up). As my kids are still very young, so far I’ve had possibilities to play with dolls (not my favourite), car toys (great memories come back), soap bubbles and other simple toys. This weekend was a little special because it was hailing in Padua – a rare opportunity to taste some “icecreams” that fall like the rain. In the afternoon my kids and I tried some puzzle games. One of them was a maze. I hadn’t seen these games for years. As I remember, solving mazes was a great part of my childhood.

mazeMy generation was brought up with Windows 95 which had an at that time famous screensaver of an automat trying to escape from a maze.

Kids of my age loved to observe the dummy animation in hope of finally finding an exit. At that time, many of us had a passion to draw mazes – very detailed, time-consuming and complex pictures on A4 or even A3 squared papers. One could gain a lot of respect in a group of mates if he was able to create a great maze and tell a story about many traps that make it almost impossible to pass.

And even though I am older now, why not try and draw a maze again? Well, but let me try to do it in a more high-tech fashion using a computer instead of a pen and paper.

It turns out that the problem of the maze creation is quite well known. There are many available implementations of maze generators. Surprisingly, the simplest one is just one line of code :

While (TRUE) {Print( Char[205.5 + Rand(1)])}

“Char[205]” is “\” and “Char[206]” is “/”, hence in an infinite loop the two symbols are printed at random and a random maze is being crafted. Below I present such an example created using the R language with a little fancier graphics of ggplot (the code borrowed from here). unif1b

Let us begin the game. Find a path that allows passing from the left side of the maze to the right. A naive method would be to guess and try many of the possible paths, end up in dead-ends and try other ways. Working out this method hurts my eyes. I thought about a smarter way of finding the path through the maze and I discovered quite an interesting solution (although perhaps it has been discovered long before me).

Imagine that all the maze walls are made from a dry and dense hedge. Let us set up a fire along the bottom wall of the maze. The wildfire propagates along the hedge only to the directly neighbouring hedge. If there would be no path from the left to the right side of the maze, then the fire should at least once reach the top. However, if such a path exists it serves as a border that ceases the fire from its further propagation. Below you see the maze after the wildfire – luckily quite a lot has survived.

unif141b

As the fire didn’t reach the top then according to our note the connecting path should exist. Indeed, when we take the topmost left entrance to the maze so that on the right-hand-side we have the burned walls and on the left-hand-side the unburned one (an entrance depicted by the green arrow in the figure above) we are able to pass through the maze. I was shocked by how complex the connecting path is. I doubt that I would find it without a computer and by using a naive method (but it could be a great game for young kids).

It also turns out that a visualization of the progressive fire in the maze looks quite entertaining (or am I a pyromaniac?). Each iteration of the progressive fire was plotted and 141 of the resulting pictured were merged to produce a simple gif. It is surprising to see the nature of this imaginary fire – often it seems that it is extinguished, but all of the sudden it bursts into a wild direction. To some extension, it is a quite true simulation of a real forest fire which spreads in a hard-to-predict manner. It is also interesting to note that for the maze of dimension 40×40 it took as much as 141 iterations before the fire eventually reached the last walls to be burned.

forest