DLA - A Naive Approach

Jump to the demo!

Generative landscapes have always been a topic I’ve wanted to learn. Like many of my peers, I originally got into programming because of Minecraft! That said, making a world like Minecraft takes a lot of maths, and can be a lot to take in without proper schooling, so it’s always been out of my grasp. The closest I’ve ever gotten was this attempt at generating “clouds” using a noise-like process, or my cellular automata caves.

I was kicked back into gear, though, after watching this great video, Better Mountain Generators That Aren’t Perlin Noise or Erosion by Josh’s Channel. In this video, a very nice cartoon dog explains various ways of generating mountainous terrain, and the pros and cons of these methods. One of the methods discussed, and the main focus of the video, is DLA, or Diffusion-limited Aggregation. This method comes to us from chemistry, and more specifically from how certain compounds will diffuse out of a solution. The video explains the process much better than I can, so please do go watch it, but I’ll explain my approach below.

I’d also like to give a shout-out to Jason Webb for his article, Simulating 2D diffusion-limited aggregation (DLA) with JavaScript, which I checked out after I had finished my implementation. This was definitely a good benchmark to compare my work against.

Going For A Walk

In its simplest form, DLA takes a grid of units, here called “cells”, that are either “stuck” or not. In the implementation below, we start with one stuck cell right in the middle of the grid. There is then another active cell that’s not stuck, and that’s the “walker”. The walker will move through the grid randomly until it touches a cell that is stuck. Here, touching means that either the stuck cell is to the left, right, above, or below the walker. Once the walker touches a stuck cell, the walker will then stick where it is, and a new walker will be generated. Over time, a fractal pattern will emerge.

Some Specifics

For my implementation, I chose to have the simulation stop once the grid has at least 33% of its cells stuck. While this sounds like a surprisingly small percentage, I’ve found over time that this leads to nice looking patterns for the small-scale grids used here.

Though the description of the process says that a new walker is generated each time, my implementation actually only uses one walker. Once the walker because stuck, the cell at its position in the total grid is marked as stuck, and then a new empty position is chosen at random for the walker to continue. This does have some implications that I discuss later in the Post Mortem section.

Post Mortem

As I admit in the title of this project, this is a naive approach to implementing DLA. That’s not to say it’s not thought out, or that I didn’t work hard on it, but there are certainly some things I look forward to optimizing or implementing in future attempts.

The first and foremost improvement I want to add in the future, is dynamic grid resizing. Part of this implementation’s issue is that, due to the walker’s random movement, on larger grids it can take a very long time to reach a stuck cell. A more optimal approach would be to start with a small grid, say an 11x11 grid, and then expand that grid once a certain threshold has been met. This should significantly reduce the amount of time it takes to get a large, pretty looking pattern.

Another issue with this approach is the random placement of the walker. The issue with this is that there is no bias to where it could pop up. On large grids, it might show up at the border of the grid, and then take 30 minutes inching its way to the next stuck cell. Alternatively, in a mostly complete pattern, it could spawn in an empty space near the center of the pattern. In my opinion this creates an artificially dense middle, with sparse details on the outer edges. Ideally there should be a bias for spawning the walker a certain radius from the center of pattern. This method would pair very well with the gradually increasing grid size mentioned in the previous paragraph.

Stretch Goal

I’m far from done with this project, but the ideal end for me would be to use this to then actually generate a 3D terrain map using the pattern generated. I say this here because I’m not confident I’ll get there any time soon, but at the very least maybe writing it down here will remind me later that it’s on the to-do list.