Generating a 2D map using the Random Walk algorithm

Published

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:

Create a grid of size NxM

Choose a random starting position in the grid

Set the position as visited

Choose a new random position by moving a single cell from the current position (go left / up / right / down)

If the position is valid (the position is not out of bonds for the grid), set this new position as the current position

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).

usingSystem.Collections.Generic;usingUnityEngine;publicclassRandomWalkGenerator{publicbool[,] GenerateMap(Vector2Intsize_map, intnb_steps) {// create the grid, which will be filled with false value// true values define valid cells which are part of our visited mapbool[,] grid =newbool[size_map.x, size_map.y];// choose a random starting pointSystem.Random rnd =newSystem.Random();Vector2Int curr_pos =newVector2Int(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, downList<Vector2Int> allowed_movements =newList<Vector2Int> { Vector2Int.left, Vector2Int.up, Vector2Int.right, Vector2Int.down };// iterate on the number of steps and move aroundfor (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 onewhile (true) {// choose a random directionVector2Int new_pos = curr_pos + allowed_movements[rnd.Next(allowed_movements.Count)];// check if the new position is in the gridif (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 loopbreak; } } }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!