How to use the Random Grid Maze to generate mazes and maps

Published Aug 9, 2023

Generating mazes and dungeon maps is an important tool for a game developer. The Random Grid Maze is a versatile algorithm that enables us to generate both mazes and more open maps with just a single parameter.

How does the Random Grid Maze algorithm work

The Random Grid Maze algorithm follows a few simple steps:

1. Create grid filled with 0s
2. Fill borders of the grid with 1s
3. Create multiple anchor points and mark them on the grid with a 1
4. Select an anchor point
5. Select a random direction
6. Move in the chosen direction
7. If the new position is already marked with 1, go to the next anchor point. Else mark the position on the grid and go back to 6.

The concept is similar to the Diffusion Aggregation algorithm in that we have a point of interest, we pick a direction and move in that direction until we hit a wall.

The algorithm can be adapted as well by using different settings for the anchor points selection, such as placing them randomly or in a repeating pattern.

How to implement the Random Grid Maze Algorithm

As explained in the previous section, the Random Grid Maze algorithm is simple to implement and quite fast.

For our implementation, we’ll be setting the anchor points on positions where both the x and y are even and enabling a probability of skipping a given cell for an anchor point to provide more variations in the results.

public int[,] GenerateMap(Vector2Int size_map, float skip_chance)
{
    int[,] grid = new int[size_map.x, size_map.y];

    // set the walls 
    for (int x = 0; x < size_map.x; x++)
    {
        grid[x, 0] = 1;
        grid[x, size_map.y - 1] = 1;
    }

    for (int y = 0; y < size_map.y; y++)
    {
        grid[0, y] = 1;
        grid[size_map.x - 1, y] = 1;
    }

    // create rng 
    System.Random rng = new();

    // set the anchor_points  
    List<Vector2Int> anchor_points = new();
    for (int x = 1; x < size_map.x - 1; x++)
    {
        for (int y = 1; y < size_map.y - 1; y++)
        {
            if (x % 2 == 0 && y % 2 == 0)
            {
                if ((float)rng.NextDouble() > skip_chance)
                {
                    grid[x, y] = 1;
                    anchor_points.Add(
                        new(
                            x, y
                        )
                    );
                }
            }

        }
    }

    // randomize posts order
    anchor_points = anchor_points.OrderBy(x => rng.Next()).ToList();

    // prep directions array 
    Vector2Int[] directions = new Vector2Int[4] {
        Vector2Int.left,
        Vector2Int.up,
        Vector2Int.right,
        Vector2Int.down
    };

    for (int i = 0; i < anchor_points.Count; i++) {
        // choose a random direction
        Vector2Int curr_direction = directions[rng.Next(4)];
        Vector2Int curr_position = anchor_points[i]; 

        while (true) {
            Vector2Int new_pos = curr_position + curr_direction;

            if (grid[new_pos.x, new_pos.y] == 1) {
                break;
            } else {
                grid[new_pos.x, new_pos.y] = 1;
                curr_position = new_pos;
            }
        }
    }

    return grid;
}

What are the results of the Random Grid Maze with different settings

The Random Grid Maze algorithm using our implementation and its base set up (no skipping anchor points) provides very convincing mazes.
In the following samples, blue cells are walls, while black cells are open cells.

As mentionned, our implementation sets anchor points at every position where x and y are even, but we can also randomly skip setting some anchor points. Generations with a 50% skip chance give us open rooms.

And with a very high skip chance, around 90%, we can see that the algorithm gives us results which are getting similar to a binary partition algorithm.

With this, the Random Grid Maze algorithm is shown as a versatile but fast algorithm that is easy to implement. It enables us to generate both mazes and structures similar to a binary partition algorithm. Some potential steps to improve on this algorithm would be to implement other initialisation algorithms, or add a post-processing pass, such as a cellular automata, to smoothen the result and avoid isolated cells.