Randomly Generated Terrain

I took a break from programming for a little bit and to get back into it, I decided what I wanted to do was get started on learning how to create terrain tools using Unity's new system. I had two goals for this: 1. Create procedurally generated terrain, and 2. figure out how to create my own texture painting brush that limits itself based on the slope and height, for things like snow on the top of mountains.

The second one took a while, not because the math or algorithm was particularly challenging, but because I spent a lot of time going over Unity source code and figuring out how exactly to create custom texture painting shaders and use them in code (there are no tutorials for this out there that I could find). What took the longest amount of time was figuring out how to get the height and normal data to the shader itself; I eventually figured out how to use PaintContext objects and what to do to deal with a crummy nullreferenceexception that was being thrown by Unity's code when I used PaintContext.GatherNormals (turns out you need to make sure that Instanced Drawing is checked in the terrain settings, otherwise when GatherNormals tries to get the normal map from the terrain, it will get a null value). Other than these complications, I'm skipping over the second goal because the math in it was incredibly simple and therefore not that interesting.

For the first goal, my first step was learning how to make my own Terrain Tool. I decided not to get into custom heightmap modifying shaders just yet; instead, just for the purpose of proof of concept, I decided to just make my brush into a render texture, on which would be generated the height map. Then, I could just paint the heightmap onto the terrain using the built in "stamp" pass. If I was to make this into a real, useful tool, I would find a more usable method than just stamping it onto the terrain, but this would work for now, just to test my ability to implement the algorithm.

My plan was to use the Diamond Square Algorithm of generating heightmaps, a simple and effective algorithm to start with. It's a procedure where you start with a grid with height and width 2^n+1, and you iterate over the pixels as shown, with each step generating points with values averaged from the points around it (either diagonally or vertically and horizontally), plus or minus a random value (with the max/min of that value decreasing exponentially with every iteration).

To speed this up I decided to generate this with a compute shader. But first, I needed to set up my GUI. I spent the first couple hours (this was my first time with both custom terrain tools and using compute shaders) figuring out how to set this up, and setting up my compute shader to simply fill our render texture with 0.5 values:

[numthreads(8, 8, 1)] void Clear(uint3 id : SV_DispatchThreadID) { write[id.xy] = 0.5; }

("write" is our RWTexture2D<float> output texture)

Of the variables shown, Roughness is the max random deviation; the max starts at 1 and is multiplied by Roughness every iteration. You can get weird results from this if you set it to something too much lower or higher than 0.707 but I thought it would be good to give the user control over this variable regardless. Resolution Magnitude controls the width and height of the texture; the width and height are equal to 2^r + 1 where r is the resolution magnitude. I know this is a very bizarre resolution for a texture but it's necessary for the algorithm we're implementing.

Random Seed should be self explanatory, you just set it to any value within the range 0 to 10000000 and it generates a unique fractal specific to that combination of seed and resolution magnitude. (I limit the seed to this range because if the value gets too high, the pseudo-random number generator breaks down).

(Right now I've made the Brush Size able to scale up to over 1000; this allows me to stamp an entire terrain at once easily. This spams the console with warnings when hovering over the entire terrain with a brush this large, but we're going to leave it in until we think of a better way to implement the tool.)

Next thing I needed to do was find a pseudo-random number generating algorithm. I spent a little while looking around online until I found one that worked for me. It returns a random float between 0 and 1. It originally used a float2 as input (intended to be the UVs of an input texture), but I edited it a little bit to work with a single uint input instead so that it was easier to implement a seed, and wrote a few functions in my compute shader to test it.

inline float rand_float(uint input) { return frac(sin(dot(float2(input / 65536.0, input / 65536.0), \

float2(12.9898, 78.233)))*43758.5453123); }

inline uint pixel_to_seed(uint x, uint y) { return randomSeed + x + widthMinusOne * y; }

(randomSeed is a uniform int passed into the shader from our tool.)

[numthreads(8, 8, 1)] void RandomTest(uint3 id : SV_DispatchThreadID) { write[id.xy] = rand_float(pixel_to_seed(id.x, id.y)); }

This worked rather well.

So to create our fractal, first we start with the corners. There are only 4, so there's really no need to multithread this.

[numthreads(1,1,1)] void StartCorners (uint3 id : SV_DispatchThreadID) { write[uint2(0,0)] = rand_float(pixel_to_seed(0,0)); write[uint2(0, widthMinusOne)] = rand_float(pixel_to_seed(0, widthMinusOne)); write[uint2(widthMinusOne, 0)] = rand_float(pixel_to_seed(widthMinusOne, 0)); write[uint2(widthMinusOne, widthMinusOne)] = \

rand_float(pixel_to_seed(widthMinusOne, widthMinusOne)); }

widthMinusOne is simply the texture width - 1, or 2 ^ r, where r is the resolution magnitude.

Before I start on the diamond and square passes, a few inline functions I wrote:

inline float rand_offset_with_variation(uint x, uint y) { return (rand_float(pixel_to_seed(x, y)) - 0.5) * variation; }

This one just takes the x and y value of the pixel and adds a random value up or down, scaled by variation. "variation" is a uniform float passed in by the

Now is where things get a bit trickier.

First we create an "average4" inline function. This will prevent code reuse and come in handy if we need to change the way we're averaging points.

inline float average4(float a, float b, float c, float d) { return (a + b + c + d) / 4.0; }

This is our "Diamond" step:

[numthreads(8, 8, 1)] void Diamond(uint3 id : SV_DispatchThreadID) { int units = widthMinusOne / (1 << iteration); uint2 newXY = uint2(id.x * units * 2 + units, id.y * units * 2 + units); float average = average4(sample_read(newXY.x - units, newXY.y - units), \ sample_read(newXY.x + units, newXY.y - units), \ sample_read(newXY.x - units, newXY.y + units), \ sample_read(newXY.x + units, newXY.y + units)); write[newXY] = average + rand_offset_with_variation(newXY.x, newXY.y); }

This is our "Square" step:

[numthreads(4, 8, 1)] void Square(uint3 id : SV_DispatchThreadID) { // To achieve a "diamond pattern" we multiply the x value by 2 and then add 1 to the x value for every other row int units = widthMinusOne / (1 << iteration); int rowShift = (id.y + 1) % 2; uint2 newXY = uint2(id.x * units * 2 + units * rowShift, id.y * units); float average = average4(sample_read(newXY.x - units, newXY.y), \ sample_read(newXY.x + units, newXY.y), \ sample_read(newXY.x, newXY.y - units), \ sample_read(newXY.x, newXY.y + units)); write[newXY] = average + rand_offset_with_variation(newXY.x, newXY.y); }

"iteration" is a uniform int passed into the shader from our tool. "1 << iteration" is a quick way to generate powers of two using bitshifting, and results in 2 ^ iteration.

This might require a bit of visual explanation. We're starting with only the left half of our grid filled in (that's how many we're planning on passing into the pass):

First we multiply every x value by 2:

Then we shift every other row over, starting with the first:

This gives us our diamond pattern.

You may realize that we've been relying on our graphics card to know how to read and write out of bounds; on most modern systems, this is defined behavior: reading out of bounds gives you a 0, writing out of bounds does nothing. However, I realize that this might not be the case for all systems. If I was writing a finished product, I would implement a separate set of functions with bounds checking, for systems on which reading or writing out of bounds causes problems; however, since this is just proof of concept, I'm not going to bother with that just yet, especially since bounds checking means putting in if statements, which creates warp branching and drastically slows down the performance.

Here's the code for the algorithm I'm using to run these passes. It's the actual C# code but with the unimportant parts of it abstracted into made up functions so you can get the general gist of what I'm doing without it becoming to unreadable:

// Generate resolution

// bitshift to get 2 ^ the resolution magnitude int resolution = 1 << _resolutionMagnitude; resolution += 1;

_renderTexture = CreateMainRenderTexture();

// Create our "reading" render texture so we aren't reading and writing to our render texture at the same time (we don't need to do this but it makes debugging easier)

CustomRenderTexture renderTexture2 = CreateRenderTexture2();

// Initialize compute shader variables _computeShader.SetInt("widthMinusOne", resolution - 1); _computeShader.SetInt("randomSeed", _seed);

// Use the compute shader to clear our render texture to 0.5 int kernelHandle = _computeShader.FindKernel("Clear");

_computeShader.SetTexture(kernelHandle, "write", _renderTexture); // We have to add 1 extra line on the x and y to account for our strange resolution _computeShader.Dispatch(kernelHandle, resolution / 8 + 1, resolution / 8 + 1, 1);

//initialize the corners kernelHandle = _computeShader.FindKernel("StartCorners"); _computeShader.SetTexture(kernelHandle, "write", _renderTexture); _computeShader.Dispatch(kernelHandle, 1, 1, 1); // Copy to our readable render texture Graphics.Blit(_renderTexture, renderTexture2);

float variation = 1;

// MAIN LOOP for (int i = 1; i <= _resolutionMagnitude; i++) { _computeShader.SetInt("iteration", i);

// Diamond Pass int numBlocks = 1 << (i - 1); // bitshift to get 2 ^ (i - 1) int threadgroups = Mathf.Max(numBlocks / 8, 1);

variation *= _roughness;

_computeShader.SetFloat("variation", variation); kernelHandle = _computeShader.FindKernel("Diamond"); _computeShader.SetTexture(kernelHandle, "write", _renderTexture); _computeShader.SetTexture(kernelHandle, "read", renderTexture2); _computeShader.Dispatch(kernelHandle, threadgroups, threadgroups, 1);

Graphics.Blit(_renderTexture, renderTexture2);

// Square Pass int numBlocksX = numBlocks + 1; // Always 1 more than our previous pass int numBlocksY = numBlocks * 2 + 1; // How many blocks we need vertically int threadgroupsX = Mathf.Max(numBlocksX / 4, 1); int threadgroupsY = Mathf.Max(numBlocksY / 8, 1);

variation *= _roughness;

_computeShader.SetFloat("variation", variation); kernelHandle = _computeShader.FindKernel("Square"); _computeShader.SetTexture(kernelHandle, "write", _renderTexture); _computeShader.SetTexture(kernelHandle, "read", renderTexture2); _computeShader.Dispatch(kernelHandle, threadgroupsX, threadgroupsY, 1); } RenderTexture.active = null; renderTexture2.Release();

The main loop works down the iterations, running a diamond pass and then a square pass each time.

So now we have what looks like a functioning fractal generator!

No, not quite. Here's what it looks like when applied:

I knew from the beginning this was going to happen, and what I needed to do to fix it. The edges of all square passes average all 4 adjacent points, including ones that are out of bounds, which means they're factoring 0s into the averages on the left and top (from out of bounds operations), and either 0 or 0.5 on the bottom and right (the textures "real" size is actually almost twice as large as the part we're working on, since all textures are stored in memory with height and width as powers of 2, and the "clear" pass sets the values of the pixels for a slightly larger section than what we're working on to 0.5. The first few iterations will sample far out of that range and get 0, and the later ones will sample within that range and get 0.5, resulting in the ridging you can see in the image.)

To fix this, we need to add a pass for each side of the texture, making them average together only the 3 sideways points that are in bounds. To do this we need another average function:

inline float average3(float a, float b, float c) { return (a + b + c) / 3.0; }

After that, the four passes were easy to write.

[numthreads(1, 8, 1)] void SquareLeftSide(uint3 id : SV_DispatchThreadID) { int units = widthMinusOne / (1 << iteration); uint2 newXY = uint2(0, id.y * units * 2 + units); float average = average3(sample_read(newXY.x + units, newXY.y), \ sample_read(newXY.x, newXY.y - units), \ sample_read(newXY.x, newXY.y + units)); write[newXY] = average + rand_offset_with_variation(newXY.x, newXY.y); }

[numthreads(8, 1, 1)] void SquareTopSide(uint3 id : SV_DispatchThreadID) { int units = widthMinusOne / (1 << iteration); uint2 newXY = uint2(id.x * units * 2 + units, 0); float average = average3(sample_read(newXY.x - units, newXY.y), \ sample_read(newXY.x + units, newXY.y), \ sample_read(newXY.x, newXY.y + units)); write[newXY] = average + rand_offset_with_variation(newXY.x, newXY.y); }

[numthreads(1, 8, 1)] void SquareRightSide(uint3 id : SV_DispatchThreadID) { int units = widthMinusOne / (1 << iteration); uint2 newXY = uint2(widthMinusOne, id.y * units * 2 + units); float average = average3(sample_read(newXY.x - units, newXY.y), \ sample_read(newXY.x, newXY.y - units), \ sample_read(newXY.x, newXY.y + units)); write[newXY] = average + rand_offset_with_variation(newXY.x, newXY.y); }

[numthreads(8, 1, 1)] void SquareBottomSide(uint3 id : SV_DispatchThreadID) { int units = widthMinusOne / (1 << iteration); uint2 newXY = uint2(id.x * units * 2 + units, widthMinusOne); float average = average3(sample_read(newXY.x - units, newXY.y), \ sample_read(newXY.x + units, newXY.y), \ sample_read(newXY.x, newXY.y - units)); write[newXY] = average + rand_offset_with_variation(newXY.x, newXY.y); }

Just add those passes to our C# code and we have a terrain generator!

And yet... something's not right about this. The mountains here have a conical look to them. Not realistic at all. I know I must have gotten something about the algorithm wrong:

I didn't have to think about it very long before I realized the problem. My current system of averaging surrounding points does what can be seen on the left; I wanted the behavior on the right.

This wasn't hard to reprogram:

inline float average4(float a, float b, float c, float d) { //return (a + b + c + d) / 4.0; return (max(max(a, b), max(c, d)) + min(min(a, b), min(c, d))) / 2.0; } inline float average3(float a, float b, float c) { //return (a + b + c) / 3.0; return (max(max(a, b), c) + min(min(a, b), c)) / 2.0; }

The terrain now forms ridges in a much more realistic fashion:

Now that I was done with that, I spent some time making the tool I mentioned earlier, which paints textures with limits based on height, and slope. Once I was done with that, I downloaded some free assets for the textures and skybox, baked some lights, and made this image: