Mazes

Fig. 1. Yo, I heard you like mazes...

(Check out the application here.)

There is scarcely anything in the world that I like more than mazes. It wasn't until quite recently till I had an opportunity to navigate a real hedge maze made out of planted bushes, located in Egeskov in Fyn, Denmark. The maze proved to be considerably more dificult than I expected! It took me nearly 40 minutes to get to the exit. I greatly recommend this wonderful place - there are lots of other amazing things to see there!

Fig. 2. Egeskov maze (from egeskov.dk).

This post is about mazes. I made a little JS application for maze generation, solving and general maze playfulness (see fig. 3). The application is located HERE, and the source code is available at https://github.com/dagothar/labyrinth.

Fig. 3. The Labirynth application.

The demo includes following features:

• create mazes of various dimensions using backtracking method,
• navigate mazes using W, S, A, D keys,
• click on the maze to make the Theseus dot go to the indicated direction,
• animated maze creation,
• customize maze looks (cell dimensions and color),
• upload your own background (makes for some nice avatar pictures!),
• test out parametrizable modified normal distribution used for maze generation,
• bugs (?).

Many resources are available on the topic of maze generation on the web. One that I can certainly recommend is Jamis Buck's blog: http://weblog.jamisbuck.org/2011/2/7/maze-generation-algorithm-recap. The blog contains very good descriptions, implementations and animations of various maze generation algorithms. The author has also published a book: Mazes for programmers (which I ordered, but unfortunately it haven't arrived yet; maybe I shall make a review when it does?).

I use a staple of maze generation algorithms: a recursive backtracker. Simply put, each step a connection to a randomly selected neighbouring cell is made by removing the wall in between. If there are no neighbours to choose from, you follow the carved path backwards, until there is an adjacent unexplored cell. The procedure is repeated until all of the cells are explored. One of the bonus features of the method is that you get the tree like structure of the cells completely free of charge, making the subsequent navigation queries that much easier. See the maze being carved out in fig. 4.

Fig. 4. Building a regular maze.

I made it so that you can easily solve the maze and move the Theseus around with a simple click of a mouse (see fig. 5).

Fig. 5. Solving the maze.

You can also upload your own background image and get some nice effects! (You should probably set the transparency on the path/wall colors for this to work).

One of the interesting things you can do is to give a 'kick' to the distribution of offsets used when selecting the next neighbouring cell. You can scale, twist and turn the normal distribution so that some directions are preferred to the others. This could possibly make the generated mazes more interesting giving them some kind of structure. 

How is the distribution 'stretched'? A couple of transformations are applied: scaling, rotation and translation. See the image below for the visual explanation (fig. 6).

Fig. 6. Modifying the random offset distribution for selecting new tiles to explore.

Mathematically, the new distribution is calculated as:

x = randn()

y = randn()

nx = sx*cos(a) * x - sy*sin(a) * y + tx;

ny = sx*sin(a) * x + sy*cos(a) * y + ty;

where x and y are random variables with normal distribution, sx and sy are scaling factors, a is the angle and tx/ty are the translations.

I made the application such that custom user expressions can be used to change the shape of normal 2D distribution. This is done by entering JavaScript language expressions into assorted fields: Angle, X scale, Y scale, X translation and Y translation. All JS math function can be used in these. Additionally, the following variables are available:

• x - the current column of the maze,
• y - the current row of the maze,
• cx - the center column of the maze,
• cy - the center row of the maze.

Check the text below for some ideas and examples.

Note: The maze generation starts at the row and column indicated by the red dot. Some of the effects are achieved when starting from the center of the grid.

Let's try that with the following set of distribution parameters (see fig. 7):

x scale:

Math.sqrt(Math.pow(x-cx, 2)+Math.pow(y-cy,2))

y scale:

Math.sqrt(Math.pow(x-cx, 2)+Math.pow(y-cy,2))

x translation:

-(x-cx)

y translation:

-(y-cy)

Such a distribution prefers the choice of the newly explored cells located close to the center of the maze. The effect seen in fig. 7 is a maze in which the passages tend to align slightly in concentric layers starting in the middle.

Fig. 7. Building 'ring' maze.

In the example below, the distribution is somewhat stretched and the angle depends on the angular position of the current cell with respect to the middle of the maze (see fig. 8). The parameters are (angles are in radians!):

angle:

1.57+Math.atan2(y-cy, x-cx)

x scale:

3

Fig. 8. Building 'concentric' maze.

The next maze shows the usage of the trigonometric functions. It is built on a 32x32 grid, so that the values of 0.1x and 0.1y span the [0, pi] range. The angle and translation parameters are left as default, but scaling is done in the following fashion:

x scale:
10*Math.sin(0.1*x)

y scale:
10*Math.sin(0.1*y)

The result is shown in fig. 9. The sides of the maze are mostly horizontal/vertical pathways, while the center remains tangled like in a regular maze. The center forms a characteristic 'bump'.

Fig. 9. Building 'bump' maze.

Another example - switching corridor directions:

x scale:
(x-cx)/(y-cy)>0 ? 20 : 1

y scale:
(x-cx)/(y-cy)>0 ? 1 : 20

Fig. 10. Checker-pattern maze.

What kind of a maze can you build?