Procedural generation: grid basics

15

Next part:

Two dimensional number grid can help when you deal with procedural generation in graphics and game development. It can be used to generate textures, landscapes, dungeon maps, etc. In this group of articles we'll discuss and implement several useful algorithms with numeric grids.

Some grid algorithms can be generalized to work on 1, 3, or higher dimensions. However from the educational point of view 1 dimension has lack of visualization while 3 and higher are too complex. 2 dimensions look like the best compromise of complexity and visualization. Still, eventually we will discuss some of algorithms on other dimensions.

In this article we will implement basic operations on a number grid. We will use HTML5 canvas and JavaScript. It's simple and well-known programming language and you don't need to mess with compilers to play with article examples — everything works right in the browser. However in real life it's not good for procedural generation due to lack of performance. The goal of these articles is to give you an idea, not the ready-to-use library. Moreover, even high performance programming language like C++ might be bad choice due to the same reasons. Procedural algorithms could do a huge amount of calculations and the best way to implement them might lie in GPU calculations, not CPU. Let me know in comments if you want me to give you OpenCL implementation of our Grid class. But now let's get back to the JavaScript. In any case, I believe you won't find it hard to rewrite our examples into any other language you're familiar with.

HTML canvas

First, let's create a very simple HTML page:

<!DOCTYPE html>
<html>
    <head>
        <style type="text/css">
            body
            {
                background: #333;
                display: flex;
                align-items: center;
                justify-content: center;
                margin: 0;
                width: 100vw;
                height: 100vh;
            }

            canvas
            {
                image-rendering: pixelated;
                image-rendering: crisp-edges;
                width: 1200px;
                height: 800px;
            }
        </style>
    </head>
    <body>
        <canvas id="canvas" width="120" height="80"></canvas>
    </body>
</html>

canvas attributes width and height specify the size of the internal image while CSS properties width and size specify the size of the HTML element. So in our page HTML element canvas is 10 times bigger than its internal image. It means that canvas image will be upscaled when drawn. We did this to make pixels bigger so we could see what's going on very precisely. By default canvas image is upscaled with interpolation which leads to a blurry image. That's not what we want. That's why we added CSS property image-rendering — it keeps the image sharp upon upscale.

Grid class

Basically our Grid class is one dimensional array of numbers which is wrapped into two dimensional access interface. Most of grid operations are implemented on top of this 2D access. A grid which has A values in width and B values in height should contain a total of A×B values. Let's take a look at our brand new grid class:

class Grid
{
    constructor(width, height)
    {
        this.resize(width, height);
    }

    // Index of the value in (x, y) coordinates
    indexOf(x, y)
    {
        return y * this.width + x;
    }

    get(x, y)
    {
        return this.values[this.indexOf(x, y)];
    }

    resize(width, height)
    {
        this.width = width;
        this.height = height;
        this.values = new Array(width * height);
    }
};

OK, we can resize our grid and access its values with two dimensional coordinates. Now let's add another member function into our class which fills underlying array with random numbers from (-1; 1) interval. White noise is starting state for many procedural content generation algorithms.

noise()
{
    for(let n = 0; n < this.values.length; ++n)
    {
        this.values[n] = Math.random() * 2 - 1;
    }
}

Display the image

Now we need to display our grid somehow. We're going to use HTML5 canvas for that. We will draw positive values with green color and negative values with red color. Also let's set pixel brightness proportionally to the value modulus — values having bigger modulus should be brighter and values around zero should be darker. So let's add draw member function:

draw(canvas)
{
    const context = canvas.getContext("2d");
    const imageData = context.createImageData(this.width, this.height);

    for(let y = 0; y < this.height; ++y)
    {
        for(let x = 0; x < this.width; ++x)
        {
            const value = this.get(x, y) * 255;

            // imageData.data is array of RGBA values, four values per pixel
            let n = this.indexOf(x, y) * 4;

            if(value >= 0) // Positive value: fill with green
            {
                imageData.data[n++] = 0;
                imageData.data[n++] = value;
            }
            else // Negative value: fill with red
            {
                imageData.data[n++] = -value;
                imageData.data[n++] = 0;
            }
            imageData.data[n++] = 0;
            imageData.data[n] = 255;
        }
    }

    context.putImageData(imageData, 0, 0);
}

Let's put our Grid class into grid.js file and update our HTML page. Now we can include grid.js into the page, create an instance of the Grid class, fill it with noise and draw. Oh, and also let's put page CSS styles into the file style.css so we could keep the page clean:

<!DOCTYPE html>
<html>
    <head>
        <link rel="stylesheet" type="text/css" href="style.css" />
    </head>
    <body>
        <canvas id="canvas" width="120" height="80"></canvas>
        <script src="grid.js"></script>
        <script>
            const grid = new Grid(120, 80);
            grid.noise();
            grid.draw(document.getElementById("canvas"));
        </script>
    </body>
</html>

And finally, let's refresh the page in our browser and look at the result:

Grid noise

Pretty easy so far, huh?

Now we're going to take this noise and run it through different algorithms. But before that we need to do a couple of additional things.

Tiled seamless access

From the perspective of two dimensional access our grid should look endless, seamless and tiled. Like a tiled texture in graphics. We will need this property in several algorithms we're going to deal with. To do so all we need is to modify indexOf member function:

indexOf(x, y)
{
    x = x >= 0 ? (x % this.width) : (this.width + (x % this.width));
    y = y >= 0 ? (y % this.height) : (this.height + (y % this.height));
    return y * this.width + x;
}

Now we can pass any values for x and y, including negative ones, and their values will be modified in such a way so the grid will look endless and tiled in all directions.

Normalization

After different transformations values in our array could grow out of (-1; 1) interval. Or they could become too small and the picture will go black. To avoid all these we should rescale values so they fit (-1; 1) interval in the best way. We will do that with normalize member function. We will find a value which has the biggest modulus and divide all values by this modulus:

normalize()
{
    let max = 0;

    for(let n = 0; n < this.values.length; ++n)
    {
        if(Math.abs(this.values[n]) > max)
        {
            max = Math.abs(this.values[n]);
        }
    }

    if(max)
    {
        for(let n = 0; n < this.values.length; ++n)
        {
            this.values[n] /= max;
        }
    }
}

Gaussian blur

And it's time to add the first interesting algorithm which is Gaussian blur. In fact Gaussian blur is a bit more complex, however we'll do the most simple implementation. It works like that: we should iterate over each pixel on the grid, and replace it with the arithmetic mean of this pixel and its neighboring pixels. Repeating this operation over and over we will get deeper and deeper blur effect.

blur(depth)
{
    for(let n = 0; n < depth; ++n)
    {
        // Create additional buffer for the next blur step
        const buffer = new Array(this.values.length);

        for(let y = 0; y < this.height; ++y)
        {
            for(let x = 0; x < this.width; ++x)
            {
                // Fill this buffer with the arithmetic mean of 3x3 pixels
                buffer[this.indexOf(x, y)] =
                   (this.get(x - 1, y + 1) + this.get(x, y + 1) + this.get(x + 1, y + 1) +
                    this.get(x - 1, y    ) + this.get(x, y    ) + this.get(x + 1, y    ) +
                    this.get(x - 1, y - 1) + this.get(x, y - 1) + this.get(x + 1, y - 1)) / 9;
            }
        }

        // Replace the current grid buffer with the filled one
        this.values = buffer;
    }
}

Notice that we've already got use of tiled access to our grid. Coordinates (x ± 1, y ± 1) are going out of [0; width) and [0; height) intervals when you run along the grid border, so tiling the grid is already helpful here.

All right, let's see how does it work! Let's update our page. You should play around with blur depth to see different levels of blurring.

<script>
    const grid = new Grid(100, 50);
    grid.noise();
    grid.blur(8); // Change this and see what happens
    grid.normalize();
    grid.draw(document.getElementById("canvas"));
</script>

Let's see the results of blurring of the same noise with different levels of depth:

Notice that if you tile the same blurred image then you'll see a picture which is seamless in all directions. This happens because of tiled 2D access which we've implemented earlier. That's lovely!

Tiled blurred noise

Summary

All right, we've implemented a grid and its basic operations: tiled two dimensional access, filling values with random noise, values normalization, and of course displaying of the grid. Now we have everything we need so we can focus on grid algorithms entirely.

Full source code for this article: source.zip. Unzip the archive and open page.html in your web browser.

Next part:

Share this page: