Terrain in Unity: Infinite Streaming 2D Side-scroller

In previous tutorials, we generated and smoothed a mesh-based, 2D terrain in Unity, using floating-point heightmap data to dictate how our mesh would be generated.

This tutorial will focus on infinitely scrolling our terrain, as found in e.g. endless runner games.

Building blocks: Deterministic PRNG & Streaming

When a function is deterministic, it means that we will always get the same outputs for a specific set of inputs.

In our case, the function we're speaking of is a pseudo-random number generator (PRNG), of which Unity's Random.Range() is the PRNG in question; we've used it up till now, to generate heightmaps:

        for (int i = 0; i < LENGTH; i++)
        {
            heightmap[i] = UnityEngine.Random.Range(MIN, MAX);
        }

Thus far, our heightmap has been different every time we've hit Play, i.e. non-deterministic, but in fact, the Random class allows us to pre-seed it with a specific value, such that when Random.Range() is called thereafter, we will get the same numbers in sequence. Same numbers means same terrain, every time we run the program. The seed is a crucial input for the deterministic PRNG function.

Streaming is a fairly simple concept that you might know from your favourite video-on-demand provider: Instead of having the whole movie's data on a disc, right from the start, you instead start receiving your movie as a data transfer from your VoD provider, and begin watching straight away - before you have the whole thing on your device. Indeed, you may never be storing the entire movie on your device at one time, as the VoD system may already have started discarding bits you've already watched, by halfway through (ever notice how it can take some time to rewind? It's because you have to reload those discarded bits.) Indeed, this idea of never storing the whole thing at once is the definition of streaming that we will be using here today.

Toward deterministic terrain generation

Let's look at how we can make our existing code generate the same sequence of values no matter how many times we hit Play in Unity, and no matter who is running our code, when, or where.

Grab the final state of the project from last tutorial. Then all we need is to open our script SideTerrain and add a single line at the in Awake() to seed our PRNG:

        UnityEngine.Random.seed = 0; 
        for (int i = 0; i < LENGTH; i++)
        {

The seed value can be anything: just as long as it is the same each time we run our code, it will continue to generate the same sequence of values in Random.Range(), which is exactly what is happening in the loop below: if we add a Debug.Log() therein:

        UnityEngine.Random.seed = 0;
        for (int i = 0; i < LENGTH; i++)
        {
            heightmap[i] = UnityEngine.Random.Range(MIN, MAX);
            Debug.Log("heightmap["+i+"]="+heightmap[i]);
        }

Then you will get these exact same values as I got for a seed value of 0:

and so on, to infinity: no matter how many values we generate, the sequence that you, I, and Bob Green living on Mars, will all get the same sequence of values, provided we all use the same seed.

Let's test the theory further. Try setting the seed differently:

        UnityEngine.Random.seed = 21983;

And once again, you and I (and Bob) will get the same sequence for a seed of 21983:

We could go on this way, with different seed values, and I could show you a million or more console logs generated, but it is a mathematical certainty that the sequence of values that you generate, and the sequence of values that I generate, will be the same for any seed we share, provided we have gone through the same number of Random.Range() calls after setting the seed.

Let's prove this statement. Reduce Awake() to:

    void Awake()
    {
        Camera.main.transform.position = new Vector3(LENGTH / 2, LENGTH / 2, -LENGTH);
        
        mesh = new Mesh();
        mesh.name = "Terrain mesh";
        meshFilter.mesh = mesh;
        
        UnityEngine.Random.seed = 0; 
    }

Our new Update():

    void Update ()
    {   
        if (Input.GetKeyDown(KeyCode.Return))
        {
            GenerateHeightmap();
            BuildMesh();
        }
    }

And the new method:

void GenerateHeightmap()
{
    for (int i = 0; i < LENGTH; i++)
        heightmap[i] = UnityEngine.Random.Range(MIN, MAX);
    
    for (int s = 0; s < SMOOTH_COUNT; s++)
        Smooth();
}

In this new Update(), smoothing works differently. Instead of hitting spacebar repeatedly, in GenerateHeightmap(), we smooth the terrain a fixed number of times, so we need this:

    public const int SCAN_RADIUS = 2; //Old
    public const int SMOOTH_COUNT = 3; //New!

See how we set Random.seed = 0, just once, in Awake()? We've bound the return (enter) key to call GenerateHeightmap(), but without resetting the seed each time. Hit Play, click on Game view.

The first time we hit enter to call GenerateHeightmap(), it looks thus:

The next time we hit enter to call GenerateHeightmap(), it looks so:

Why are they different? Because we do not reset the seed on pressing enter. If you move UnityEngine.Random.seed = 0; out of Awake() to GenerateHeightmap(), before the for loop begins using Random.Range(), then you will get the first image, both times - no change.

If you do reset the seed to the same value as before, then both runs of GenerateHeightmap() do the 1st LENGTH=100 (1-100) generations, relying on the seed itself, which is say 0 in both cases, for their starting state, with identical results. Hence, the two ranges look the same.

If you don't reset the seed to the same value as before, then the first image consists of the 1st LENGTH=100 (1-100) generations, while the second image consists of the 2nd 100 generations (101-200). The 101st, 102nd generation and so on - i.e. the leftmost heights in the second image above, are a sort of continuation on the 100th value - i.e. the final, rightmost height of the first image. Hence, the two ranges look different.

Why? Each call to Random.Range(), after seeding, changes Random's internal state and affects the next result. So after generating the first 100 values, we have changed the internal state of our PRNG Random 100 times over, so that by the time we start the second GenerateHeightmap() call i.e. the 101st Range() call, Random is in a completely different state than if we had re-seeded it with 0. Remember the function inputs I mentioned? One of those is the internal state of the Random class.

Determinism requires us to generate the same sequences of numbers in the same circumstances, so do not forget to make all inputs the same, by re-seeding your PRNG if you want determinism!

Shifting about the world: part 1

We have a heightmap array with LENGTH of 100, so why not stream into that? That way, we don't have to pre-generate some massive array: we keep the small memory footprint of our application, the same as it has been thus far.

As we move forward and back in the world, we can generate new values, one at a time, in the direction we're moving, while discarding older values from the other end of the array, so as to always keep to exactly 100 elements. This is like a pair slide-rules moving together, always keeping the same space (LENGTH=100) between them. This way, we can see a small window into any part of a world of any size, no matter how large.

Let's begin! Our Awake() method is updated to:

    void Awake()
    {
        Camera.main.transform.position = new Vector3(LENGTH / 2, LENGTH / 2, -LENGTH);
        
        mesh = new Mesh();
        mesh.name = "Terrain mesh";
        meshFilter.mesh = mesh;
        
        GenerateHeightmap();
        BuildMesh();
    }

Update() gets a complete overhaul; you can gut and replace your existing Update() code with:

    void Update ()
    {   
        int scroll = 0;
        if (Input.GetKeyDown(KeyCode.LeftArrow)) scroll--;
        if (Input.GetKeyDown(KeyCode.RightArrow)) scroll++;
        
        if (scroll != 0)
        {
            offset += scroll;
            
            GenerateHeightmap(offset);
            BuildMesh();
        }
    }

And we will also need:

    float[] heightmap = new float[LENGTH]; //Old
    int offset = 0; //New!

Now let's go through Update():

1. is setting up a temporary variable, scroll, to determine whether we've scrolled -1 (back), 0 (no change) or +1 (forward) on this game tick / update. Notice that if we hit neither arrow key, this remains 0.
2. checks whether the left arrow key has been pressed, and if so, indicates to later code via scroll, that we are moving backward.
3. checks whether the right arrow key has been pressed, and if so, indicates to later code via scroll, that we are moving forward.
4. checks if we have scrolled per se, and if so:
5. update our world position, offset, as we use the arrow keys to walk through the world; that's why we're adding scroll to it.
6. pass our world position into GenerateHeightmap().
7. build (and smooth) the new mesh, using this updated heightmap data.

offset is how far we have moved in the world, along the x-axis (positive being right). It is used to offset how far into the world we are generating heights - and by world, I mean the results of our global PRNG function.

Think of offset like this: where before the left hand side of our heightmap was always position 0 in the world (meaning the 1st Random.Range generation after seeding), now it is offset. We draw our onscreen heights, as follows: offset + 0, offset + 1 ... etc. to offset + LENGTH - 1.

GenerateHeightmap() just needs our random seed put in at the start:

void GenerateHeightmap()
{
    UnityEngine.Random.seed = 0;
    for (int i = 0; i < LENGTH; i++)
        heightmap[i] = UnityEngine.Random.Range(MIN, MAX);
    
    for (int s = 0; s < SMOOTH_COUNT; s++)
        Smooth();
}

Oops. Hold up. There's a problem: this version of GenerateHeightmap() isn't remotely what we need, because it has no concept of scrolling through our world.

A brief interlude: offsetting generation

First off, let's consider what our LENGTH really means. In our original application, it meant both that we have say 100 heights in our heightmap, and it also meant that the highest number of generations we'd ever do with our PRNG was 100, thus, position 0 was the lowest world position (and we were always standing at 0) and 99 was the maximum world position, leading us to count 100 elements.

In the scrolling approach we are now implementing, this will no longer be the case. We are now going to shift any distance (rightward) into our world, and when we come back again (leftward), we need to see exactly the same features as we did before. Our world position, offset, will change at the player's whim.

Whereas heightmap was previously a fixed piece of the world landscape representing locations 0-99, it is now a pair of slide-rules, that can just as easily surround demarcate positions 0-99 as it could 10101-10200. The heightmap now holds a range of the total world space as generated by PRNG.

So our process every time we move, will be more like:

1. seed the PRNG; this also resets its state so it will start a brand new generation sequence. So if we were at position 43 earlier, and after moving about to various other positions, we have come back to position 43 again, then we will generate the same sequence here.
2. generate LENGTH=100 heights - but these are no longer always world positions / generations 0-99 after we seed the Random generator. Instead, they typically have to be a later 100 generations, because we no longer always start at world offset 0, as in earlier tutorials, but rather at whatever offset / position we have moved to in the world: We have to generate those 100 heights starting at that offset.

How do we get to a later series of 100, after seeding the Random generator? Here's the Big Kick in the face: we have to keep on generating values until we get to that range. This means even if we're at position 14850 in the world - a long way from Kansas! - we'd still have to generate 14850 throw-away values, before we get to the 100 that we actually need (up to index 14949). Costly, yes?

The reason for this was already suggested: the PRNG bases its next value on the last Random.Range()'s results (or at least on the process of getting that result), and so on down the line.

While flawed, the approach we're taking is simple; so for learning purposes, let's complete it.

Shifting about the world: part 2

Knowing what's wrong with the old GenerateHeightmap(), let's go to a new, improved version:

    void GenerateHeightmap(int offset)
    {
        UnityEngine.Random.seed = 0;
        for (int j = 0; j < offset + LENGTH; j++)
        {
            float rnd = UnityEngine.Random.Range(MIN, MAX);
            if (j >= offset)
            {
                int i = j - offset;
                heightmap[i] = rnd;
            }
        }
    }

1. seeds our generator, and in doing so, also resets so it can start generating a fresh sequence for this seed value.
2. loops no longer just from 0 to LENGTH, but rather from our world offset, to offset + LENGTH.
3. generates a random float value, rnd, for each step of the for loop.
4. checks if we're at an offset in the world where we will need heightmap values, i.e. where i is greater than or equal to offset, and if so,
5. gets us array index i that will work safely with heightmap, as j - offset puts us back in the 0-99 index range - heightmap is still only 100 elements long, even if the world is infinite!
6. stores the just-generated random value in our heightmap, using safe index i. (Note how, if j is less than offset, we don't use this value, and it gets discarded: it's not onscreen.)

First example:

We are standing at offset=25 after using the arrow keys. In the for loop above, we are on the 19th element (j=18). What has happened for each element up until now, is that the random value rnd is generated, and then discarded: but we needed to do this in order to at least advance the internal state of our PRNG Random.

Second example:

We are standing at offset=25 after using the arrow keys. In the for loop above, we are on the 41st iteration (j=40). In this iteration, the random value rnd is generated as always, and because we are within LENGTH=100 elements after offset (40 is greater than or equal to 25), we don't discard the value, but store it in the heightmap, because it's one of the 100 we presently need to display onscreen.

And, at the end of GenerateHeightmap(), after the for loop's closing brace }:

    }
    
    for (int s = 0; s < SMOOTH_COUNT; s++)
        Smooth();
}

Run this, move around using the left and right arrow keys. (moving left from position 0 shows only flat terrain - this is expected behaviour.) Sped up vid of repeated right arrow keypress:

Final code is as follows:

using System;
using System.Collections.Generic;
using UnityEngine;

public class SideTerrain : MonoBehaviour
{
    public const int MIN = 20;
    public const int MAX = 50;
    public const int LENGTH = 100;
    public const int SCAN_RADIUS = 2;
    public const int SMOOTH_COUNT = 3;

    float[] heightmap = new float[LENGTH];
    int offset = 0;
   
    public MeshFilter meshFilter;
    public Mesh mesh;

    void Awake()
    {
        Camera.main.transform.position = new Vector3(LENGTH / 2, LENGTH / 2, -LENGTH);
        
        mesh = new Mesh();
        mesh.name = "Terrain mesh";
        meshFilter.mesh = mesh;
        
        GenerateHeightmap(offset);
        BuildMesh();
    }
    
    void Update ()
    {   
        int scroll = 0;
        if (Input.GetKeyDown(KeyCode.LeftArrow)) scroll--;
        if (Input.GetKeyDown(KeyCode.RightArrow)) scroll++;
        
        if (scroll != 0)
        {
            offset += scroll;
            
            GenerateHeightmap(offset);
            BuildMesh();
        }
    }
    
    void GenerateHeightmap(int offset)
    {
        UnityEngine.Random.seed = 0;
        for (int j = 0; j < offset + LENGTH; j++)
        {
        	float rnd = UnityEngine.Random.Range(MIN, MAX);
            if (j >= offset)
            {
                int i = j - offset;
                heightmap[i] = rnd;
            }
        }
        
        for (int s = 0; s < SMOOTH_COUNT; s++)
            Smooth();
    }
    
    void Smooth()
    {
        for (int i = 0; i < heightmap.Length; i++)
        {
            float height = heightmap[i];
            
            float heightSum = 0;
            float heightCount = 0;
            
            for (int n = i - SCAN_RADIUS;
                     n < i + SCAN_RADIUS + 1;
                     n++)
            {
                if (n >= 0 &&
                    n < heightmap.Length)
                {
                    float heightOfNeighbour = heightmap[n];

                    heightSum += heightOfNeighbour;
                    heightCount++;
                }
            }

            float heightAverage = heightSum / heightCount;
            heightmap[i] = heightAverage;
        }
    }
    
    void BuildMesh()
    {
        mesh.Clear();
        List<Vector3> positions = new List<Vector3>();
        List<int> triangles = new List<int>();
        
        int offset = 0;
        for (int i = 0; i < LENGTH - 1; i++)
        {
            offset = i * 4;
            
            float h = heightmap[i];
            float hn = heightmap[i+1];
            positions.Add(new Vector3(i+0,0,0)); //lower left - at index 0
            positions.Add(new Vector3(i+1,0,0)); //lower right - at index 1
            positions.Add(new Vector3(i+0,h,0)); //upper left - at index 2
            positions.Add(new Vector3(i+1,hn,0)); //upper right - at index 3
            
            triangles.Add(offset+0);
            triangles.Add(offset+2);
            triangles.Add(offset+1);
            
            triangles.Add(offset+1);
            triangles.Add(offset+2);
            triangles.Add(offset+3);
        }
        
        mesh.vertices = positions.ToArray();
        mesh.triangles = triangles.ToArray();
        mesh.RecalculateNormals();
    }
}

Problems with this solution

• We perform an unbounded number of Random.Generate()s before actually being able to get the LENGTH number of values we need to put into our heightmap, as already described. This is not just costly, it is untenable.
• As our character moves (quickly) over the terrain in an endless runner, we are making incessant calls to GenerateHeightmap() and RebuildMesh(). This can be very costly, especially given the constant transfer of mesh data across the system bus from CPU to GPU; if nothing else, it is wasteful of CPU cycles we could be using for other things, like AI or game logic.
• You'll notice that the leftmost and rightmost points of the heightmap tend to jump a bit as you are moving about. This is because the smoothing function needs to go out of the range of offset + 0 to offset + LENGTH to get a correct average, but it can't - recall the little hack we included in Tutorial 1, to prevent it from doing so. Instead it only gets a correct average when it is closer to the middle of the view, where there are enough neighbours to "feed off" of.

Caveat emptor. Working code is not necessarily good code, though this has served to demonstrate a simple, deterministic, streaming terrain generator.

Conclusion

In this tutorial, we learned much about deterministic generation of terrain. It is amazing to see that, from the same mathematical function (in this case's Unity's built-in PRNG), we can retrieve and re-display values we had previously discarded, thought gone forever.

Next time, we will greatly improve on this solution by implementing terrain chunks while continuing to perform deterministic data streaming magic.