I am working on a game called "Maze Rush" where you guessed it, have to rush to the exit of a maze and so my first major hurdle was generating mazes you enjoy escaping from so I tried the several methods, the code for the algorithms can be found at: https://github.com/r3zv/reze

Algorithms

In the realm of maze generation there are sort of two categories a maze generation algorithm can fall into "biased" and "non biased" algorithms.

There are algorithms that are more biased towards shorter corridors and other to longer ones but there are some that are not biased in any sense, we will explore one algorithm for each of this case, so buckle up.

Randomized DFS

If you have ever taken a class / course in "Algorithms & Data Structures" there is a change you heard about DFS (Depth First Search) and we will be using it to create some mazes.

Here is the gist of the algorithm:

You initialize your grid with empty cells at positions (i, j) where both i and j are odd numbers (considering 0 index based) and the rest of the cells are walls, it should look something like this:

Now let's assume we start generating from cell (1, 1), the algorithm will pick a random direction (N, E, S, W) and if are not already connected to the first empty cell in that direction we break the wall that separates the empty cells, here is a quick example:

1. We start at (1, 1)

2. We generate a random direction, let's say S(outh)

3. Look at (2, 2) that is empty cell

4. Look at (2, 1) there is still a wall there

5. Break the wall at (2, 1) 6. Repeate the same from (2, 2)

A possible itteration of the algorithm could result in a maze like:

But wait, there is no exit? Yes there is not exit at this point, we will have to find a logic which we will use to determin where an exit should be placed.

The logic for the exit is the same in all 3 algorithms, the exit algorithm will be described at the end of the post.

Randomized Kruskal

Kruskal is also a populare algorithm that you might have heard about, it is primarly used for determining the MST (Minimum Spanning Tree) but we can also use it to generate mazez.

TODO

Wilson's Algorithm

TODO

Finding an exit

Here is what we look for when we want to create an exit to the maze:

1. Be resonably far apart from where the start of the maze is. 2. There is at least a path from the start position to it. 3. It it positioned on the edge of the maze.

TODO