Angled Random Walks for DLA-like Terrain Generation

2024-08-03

I watched this excellent video, Better Mountain Generators That Aren’t Perlin Noise or Erosion by Josh’s Channel. It discusses generating mountain heightmaps using a technique called Diffusion-Limited Aggregation. The structures produced by this process are known as Brownian trees.

In DLA, we start with a seed typically placed at the center. At each step, we randomly place points on the grid and then random-walk them until they hit an existing particle, at which point they are frozen there. This is, of course, very inefficient. The video describes a good technique to get it to be faster, by starting with a small grid and doing a crisp upscale​  (This upscale isn’t done directly on the pixels — instead, we keep track of which pixel sticks to which, and use that graph to populate a larger grid.)  after the grid is filled to a certain degree, and repeating the process until we get to the desired size.

But my immediate thoughts after the video were that surely this would be faster the other way round — by generating outwards from the initial seed. After experimenting with a lot of approaches, I found a way that yields fairly DLA-like results with much less computational cost.

Approach

We have a number of random walkers on the grid. Each of them has these properties:

1. Age: How many pixels it travelled since it was spawned.
2. Generation: How many parent walkers it has.
3. Angle: What angle the walker aims towards.
4. Type: Is it a long or short walker. Short walkers don’t split into more walkers when they end.

The algorithm for generation is:

1. Start with a grid of zeros.
2. Place a number of walkers at the centre, all aimed at different angles.
3. While there are any walkers:
   • If it is a long walker and its age module some frequency parameter is zero, spawn a short walker at that position.
   • If its age is greater than some maximum age, it dies, and…
     • If its generation is less than some maximum generation, and it is a long walker, spawn some number of long walkers where it stopped, each aimed slightly offset from the parent’s angle.
   • Else, the walker moves in a random direction, chosen via weighted sampling where the weights are smaller the larger the angular distance between that direction and the target angle, and the most opposite direction is removed​  (Otherwise, the walkers wind back on themselves and fail to spread apart sufficiently. An example of what that looks like: )  by subtracting its weight from every weight. The point it moves to is filled in on the grid.

Implementation

I’ve written a Rust implementation of this algorithm.

• Repository: bharadwaj-raju / angled-random-walker
• Crates.io: angled-random-walker
• Documentation: angled_random_walker on docs.rs

Heightmap

By filling each walked pixel with the cumulative age of its walker, and blurring the result, we get a simple heightmap. But this just gives you mountain-like smooth blobs.

To get more interesting terrain, we superimpose a clamped and lightly-blurred version. This preserves the smaller and sharper details generated in the process. The effect is — in my estimation — close to the sought-after erosion look.

Demonstration

This is a live demonstration. Play around with the sliders to immediately see your changes. To make it easier to isolate the effects of varying parameters, the seed is held constant — click “Randomize Seed” to generate from a new seed.

Similar Stuff

Planet Eleven Games posted about Using drunken walk for height maps. They were inspired by the exact same video, but the approach they use is different, involving an unbiased random expansion with each new pixel having a chance of dropping in height. Check out their demo.