Generating a 2D map using the Random Walk algorithm

Published Jul 17, 2023

When talking about procedural generation of maps, we always hear about the usual suspects: Perlin Noise, Voronoi Noise and Cellular Automata.
These are very appropriate in some contexts, both 2D and 3D, but for some cases a simpler alternative can be best: the Random Walk algorithm.

So in what contexts does the Random Walk algorithm shine?

• 2D grid based maps
• Natural-looking formation
• First pass in a more complex procedural generation system

I personally think it’s a great fit for caves and overworlds. See a few samples of maps generated using the Random Walk algorithm:

The Random Walk algorithm also provides the following technical benefits:

• Simple to implement
• Extremely fast runtime
• Map is guaranteed to be fully connected

So let’s dive into it then! The Random Walk is also sometimes called the “Drunkard’s walk” in the context of a 2D grid and the name is obvious considering how it works:

1. Create a grid of size NxM
2. Choose a random starting position in the grid
3. Set the position as visited
4. Choose a new random position by moving a single cell from the current position (go left / up / right / down)
5. If the position is valid (the position is not out of bonds for the grid), set this new position as the current position
6. Go back to 4 and iterate until the completion condition is fulfilled (for example number of iterations)

Now we can see why the Random Walk sometimes gets the name of Drunkard’s walk! The modelling is basically an entity that moves erratically in any direction at each time step. The entity can also move back to previously visited cells, so previous iterations do not have an effect on the current iterations, which make the Random Walk a stochastic / memoryless process.

Hopefully this explains the technical benefits we mentionned before: the algorithm is simple and fast to implement since we are simply choosing a direction at random at each timestep, and the result is guaranteed to be fully connected as we are only moving between neighbouring cells.

Larger sized maps can be generated almost instantly and can exhibit very interesting shapes.

Number of iterations is the main driver of runtime, so let’s not go too crazy!

Alright, now let’s take a look at the code! This is a C# implementation that works in Unity. The method takes a Vector2Int to define the size of the map to be generated, as well as the number of steps (or number of iterations for the loop).

using System.Collections.Generic;
using UnityEngine;

public class RandomWalkGenerator
{
    public bool[,] GenerateMap(Vector2Int size_map, int nb_steps)
    {
        // create the grid, which will be filled with false value
        // true values define valid cells which are part of our visited map
        bool[,] grid = new bool[size_map.x, size_map.y];

        // choose a random starting point
        System.Random rnd = new System.Random();
        Vector2Int curr_pos = new Vector2Int(rnd.Next(size_map.x), rnd.Next(size_map.y));

        // register this position in the grid
        grid[curr_pos.x, curr_pos.y] = true;

        // define allowed movements: left, up, right, down
        List<Vector2Int> allowed_movements = new List<Vector2Int>
        {
            Vector2Int.left,
            Vector2Int.up,
            Vector2Int.right,
            Vector2Int.down
        };

        // iterate on the number of steps and move around
        for (int id_step = 0; id_step < nb_steps; id_step++) {
            // for each step, we try to find a new cell to go to.
            // We are not guaranteed to find a position that is valid (i.e. inside the grid)
            // So we use a while loop to allow us to check multiple positions and break out of it
            // when we find a valid one
            while (true) {
                // choose a random direction
                Vector2Int new_pos = curr_pos + allowed_movements[rnd.Next(allowed_movements.Count)];
                // check if the new position is in the grid
                if (new_pos.x >= 0 && new_pos.x < size_map.x && new_pos.y >= 0 && new_pos.y < size_map.y) {
                    // this is a valid position, we set it in the grid
                    grid[new_pos.x, new_pos.y] = true;

                    // replace curr_pos with new_pos
                    curr_pos = new_pos;

                    // and finally break of the infinite loop
                    break;
                }
            }
        }

        return grid;
    }
}

As you can see, the Random Walk / Drunkard Walk is a very simple algorithm to implement, cheap to run and can generate interesting shapes.

The generated results might be suitable as-is, but you can augment the algorithm or make it part of a more complex procgen process using other methods.

Here are a few ideas:

• Use a Cellular Automaton to smoothen the edges
• Floodfill to create lakes and mountains in non-visited cells
• Perlin Noise or Voronoi Noise to define biomes
• Voronoi cells or Poisson sampling to distribute pickable items or locations of interest on the map

We’ll be exploring these topics in subsequent articles. Thanks for reading, and as always the code is available for you to use!