How to use the Diffusion Aggregation algorithm to generate 2D maps for dungeons or biomes

Published

Continuing on our series of articles exploring algorithms for procedural generation for Game Development, we’ll take a look at the diffusion aggregation algorithm. This algorithm can serve as both a generator for dungeon maps, similar to the Drunkard Walk (or Random Walk) but also it can serve to perform a partition or subdivision of a grid, making it an interesting alternative to Voronoi Diagrams.

What is the Diffusion Aggregation algorithm

The Diffusion Aggregation algorithm, also known as Diffusion-Limited Aggregation (or DLA) algorithm is a computational model used to simulate the growth of “aggregates”. In plain terms, this means that the Diffusion Aggregation process starts from an initial area or shape in a grid and grows by adding new points connected to the initial area. This initial area is also called a “seed” and impacts the generation process.

Why use the Diffusion Aggregation algorithm

The Diffusion Aggregation algorithm is simple to implement since it consists in simply moving particles on a grid and tracking collisions. For this reason it is also quite fast in its basic form, as it only requires tracking a single particle at a time.

The main reason to use the Diffusion Aggregation algorithm is for its results: it creates branching, fractal patterns which make for very interesting maps. Just like the Random Walk algorithm, it is suited for generating seemingly naturally created structures, such as grottos. These structures are also guaranteed to be fully connected.

How does the Diffusion Aggregation algorithm work

The Diffusion Aggregation Algorithm follows a few simple steps:

Create a grid filled with 0s

Create the initial seed and set the relevant cells as 1 in the grid

Create a particle

Move this particle to a random neighbouring cell

Repeat 4. until the particle reaches a non-empty cell in the grid (the particle collides with the existing shape being created)

Set the position prior to the collision as 1 in the grid

Go back to 3. and repeat until the termination condition has been met.

It’s good to note that we use a random (or stochastic) movement in a 2D setup for our particles, but you can also use more complex non-stochastic models and even extend it to 3D.

How to generate a 2D map with the diffusion aggregation algorithm in C# for Unity

As explained in the previous section, the algorithm is a grid based process so we’ll need to provide a size argument for our map, as well as implement a termination condition.

In our implementation, we’ll be using the number of steps as our termination condition. The following code closely follows the instructions we provided: it creates a 0-filled grid with a target size, finds the center of the grid and creates the initial seed (a square of length 3 here) then starts producing and moving particles. The direction for the particle’s movement is chosen at random at every iteration for its movement, so this is a random / stochastic process.

Here’s our code, annotated with comments:

publicint[,] GenerateMap(Vector2Intsize_map, intnb_steps){int[,] grid =newint[size_map.x, size_map.y];// create a tracker for allocated points for the diffusion process List<Vector2Int> recorded_points =new();// Diffusion process moves from a given point to another point in a one cell movement so we're setting the directions here as a reusable elementVector2Int[] directions =newVector2Int[4] { Vector2Int.left, Vector2Int.up, Vector2Int.right, Vector2Int.down };// set a initial seed, a cluster of tiles at the center of the room Vector2Int center_map =new( size_map.x /2, size_map.y /2 );for (int i =-1; i <2; i++) {for (int j =-1; j <2; j++) {Vector2Int temp = center_map +newVector2Int(i, j); grid[ temp.x, temp.y ] =1; } }// The diffusion process consists in firing from a random point in a random direction until we hit a previously allocated pointSystem.Random rng =new();for (int i =0; i < nb_steps; i++) {// choose a random point Vector2Int origin_point =new( rng.Next(size_map.x), rng.Next(size_map.y) );// move in a random direction until we hit something, or get out of boundswhile (true) {// choose a directionVector2Int direction = directions[rng.Next(4)];Vector2Int new_point = origin_point + direction;// check if the new point is in the grid. If it isn't, go to next stepif (new_point.x <0|| new_point.y <0|| new_point.x >= size_map.x || new_point.y >= size_map.y) {break; }// check if this is not a previously visited point// if it is a visited point, we can add the "origin_point" to our grid if (grid[new_point.x, new_point.y] ==1) { grid[origin_point.x, origin_point.y] =1;break; }// else we update origin point and continue moving our particle origin_point = new_point; } }return grid;}

And we’re done! The Diffusion Aggregation algorithm is quite simple to implement but the results are quite interesting, let’s take a look:

In our implementation we used the number of steps as the termination condition and I think the results are pretty neat. Still, there are a couple of other termination conditions you could use:

Aggregate size, don’t stop the algorithm until it reaches a given size

Connectivity level, the maps generated by this algorithm are usually branching which may mean a dead-ends and backtracking for the player. You can keep running the algorithm until cells have at least N connections on average, or inject corridors or other shapes in the grid.

How to subdivide or partition a 2D grid with the diffusion aggregation algorithm

It’s also possible to modify the diffusion aggregation algorithm to use it as a partitioning / subdividing algorithm, which can then be used to define game elements such as biomes.

In this case, we want to divide a grid into multiple subsections, each with its own ID. We can accomplish this in a few steps:

Create a grid

Create initial points for each subsection, write them to the grid and store them in a tracker

For each subsection, choose a stored point

Choose a random direction

Get the neighbouring cell of the stored point using this direction

If this point in the grid is unallocated (i.e. has a value of -1), set the id of the subsection in the grid at the point’s location and add the point to the tracker

Continue from 3 with the next subsection

Repeat until the full grid has been filled

This algorithm will split a grid between different subsections and ensure that subsections are fully connected (no isolated child for any subsection).

publicint[,] GeneratePartitionedMap(Vector2Intsize_map, intnb_subsections){int[,] grid =newint[size_map.x, size_map.y];// fill with -1s to get the initial state for (int i =0; i < size_map.x; i++) {for (int j =0; j < size_map.y; j++) { grid[i, j] =-1; } }// create a tracker for valid points by subsection for the diffusion process List<List<Vector2Int>> recorded_points =new();for (int i =0; i < nb_subsections; i++) { recorded_points.Add(new()); }// create a counter to keep track of the number of unallocated cells int nb_free_cells = size_map.x * size_map.y;// set up the initial points for the process System.Random rng =new();for (int id_subsection =0; id_subsection < nb_subsections; id_subsection++) {while (true) {// find a random point Vector2Int point =new( rng.Next(size_map.x), rng.Next(size_map.y) );// check if it's free, else find another pointif (grid[point.x, point.y] ==-1) {// if it is add it to tracking and grid then proceed to next subsection grid[point.x, point.y] = id_subsection; recorded_points[id_subsection].Add(point); nb_free_cells -=1;break; } } }// Diffusion process moves from a given point to another point in a one cell movement so we're setting the directions here as a reusable elementVector2Int[] directions =newVector2Int[4] { Vector2Int.left, Vector2Int.up, Vector2Int.right, Vector2Int.down };// now we can start filling the grid while (nb_free_cells >0) {for (int id_subsection =0; id_subsection < nb_subsections; id_subsection++) {// check if there are tracked points for this subsection if (recorded_points[id_subsection].Count ==0) {continue; }// choose a random point from the tracked points int id_curr_point = rng.Next(recorded_points[id_subsection].Count);Vector2Int curr_point = recorded_points[id_subsection][id_curr_point];// choose a direction at randomVector2Int new_point = curr_point + directions[rng.Next(4)];// check if the new point is in the gridif (new_point.x <0|| new_point.y <0|| new_point.x >= size_map.x || new_point.y >= size_map.y) {continue; }// next check if the new point is already occupied and skip this direction if it isif (grid[new_point.x, new_point.y] !=-1) {continue; }// else we can record this new point in our tracker and set it in the grid grid[new_point.x, new_point.y] = id_subsection; recorded_points[id_subsection].Add(new_point); nb_free_cells -=1; } }return grid;}

And here’s the result:

As I mentioned previously, a prime application of this type of algorithm is to create biomes. And actually we can compare the result to another algorithm that is commonly used for this kind of purposes: Voronoi Diagrams.

From these visualisations we can see that both algorithms allow us to subdivide a grid which we can use to defined game elements such as biome. The main difference here is that the shapes generated by our algorithm are much less regular than what’s created by the Voronoi algorithm. In my opinion, this makes our modified Diffusion Aggregation algorithm an interesting alternative to Voronoi Diagrams.