Terrain Generation Tutorials, Part 1: Generating a Simple Grid

### Introduction

Terrain Generation has been an important component of games for a long time now, as is even more prevelent and important as technology has advanced and gamers have responded well to open, expansive worlds and universes they can explore. However, generating these worlds at the hands of an art team is expensive and time consuming. At a point, it becomes unfeasable or even impossible. Luckily, as programmers, we can create terrain programatically using a few different techniques, like perlin noise.

This series of blog posts will act as a tutorial, in part, and will go over the process of generating terrain in DirectX11. This first tutorial will cover the basics of generating a grid in a project I had previously built here. I will try and explain any of my engine-specific features to avoid confusing anyone following this tutorial, so that you can account for them and work around them where required.

### Theory

Terrain is most typically represented as a 2D grid with any number of cells that then have their y values manipulated by a height map or noise-generating algorithm. This grid will be generated programatically with each vertex being placed at an equal distance from each other. Considerations must be made to DirectX being a left-handed coordiante system, as it means that it the ordering of the vertices are important.

The manipulation of the y values will be explained in later tutorials, such as the Height Map Tutorial.

The construction of the grid must be split into two sections: The generation of the grid vertices, and the generation of the grid indices. The vertices can be created simply by stepping along each row and adding them at a spacing equal to the desired cell width [Figure 1]. To calculate the indices, we need to consider vertices on two rows to construct the polygons that make up the grid [Figure 2]. Figure 1 - A few vertices that make up a simple 1x3 grid. Figure 2 - A simple 1x3 grid where the numbers represent the draw order of the vertices.

The index list for this grid would be something like this: { 0, 1, 2, 0, 3, 1, 2, 5, 4, 2, 1, 5, 4, 7, 6, 4, 5, 7 } (For an array starting at 0).

### Code

With the basic theory covered, it's time to implement a grid builder into our application. We will start by creating a class called, conveniently enough, `GridBuilder`.

class GridBuilder { private: ID3D11Device* _device; static vector<Vertex> BuildVertexList(Box gridSize, XMFLOAT2 cellCount); static vector<unsigned short> BuildIndexList(XMFLOAT2 cellCount); ID3D11Buffer* CreateVertexBuffer(unsigned long long vertexCount, Vertex* finalVerts) const; ID3D11Buffer* CreateIndexBuffer(int indexCount, unsigned short* indices) const; public: GridBuilder(ID3D11Device* device); ~GridBuilder(); Geometry* Build(Box gridSize, XMFLOAT2 cellCount) const; };

The `Box` class being passed into some of the methods is simply a data transfer object containing a width and height. We have a few things of note here. Firstly, the class uses a tiny bit of dependency injection by holding a reference to the `ID3D11Device`, passed into the constructor at initialisation. Then, we have the main `Build(...)` method, which takes a grid size and cell count as parameters.

We also have some helper methods to assist us and make our code a little cleaner, which are the private `BuildVertexList(...)`, `BuildIndexList(...)`, `CreateVertexBuffer(...)` and `CreateIndexBuffer(...)`. Their jobs should be fairly self-explanitory, but the logic inside each method will be explained in detail shortly.

#### Constructing the Vertices

First, let's look at the `BuildVertexList(...)` method.

vector<Vertex> GridBuilder::BuildVertexList(const Box gridSize, const XMFLOAT2 cellCount) { const int halfWidth = gridSize.Width / 2; const int halfDepth = gridSize.Height / 2; const XMFLOAT2 cellSize = XMFLOAT2(gridSize.Width / cellCount.x, gridSize.Height / cellCount.y); vector<Vertex> vertices = vector<Vertex>(); for (int row = 0; row <= cellCount.x; row++) { for (int column = 0; column <= cellCount.y; column++) { Vertex vertex; vertex.position = XMFLOAT3(column * cellSize.x - halfWidth, 0, row * cellSize.y - halfDepth); vertex.texture = XMFLOAT2(row * (cellCount.x / gridSize.Width), column * (cellCount.y / gridSize.Height)); vertex.normal = XMFLOAT3(0, 1, 0); vertex.tangent = XMFLOAT3(0, 0, 1); vertex.binormal = XMFLOAT3(1, 0, 0); vertices.push_back(vertex); } } return vertices; }

The important part of this method is the calculation of the position and texture coordinates for each vertex. But before we do that, note the first three lines. The first two lines will find half the width and depth, which is used later so that the center of the grid in centered at local coordinates (0, 0). This third line will determine the cell spacing between vertices.

We then generate an amount of vertices equal to the `(cellCount.x + 1) * (cellCount.y + 1)`, which is done via the nested for loops. For each vertex, we calculate it's position using the following formula:

`XMFLOAT3(column * cellSize.x - halfWidth, 0, row * cellSize.y - halfDepth)`

We can see how this code constructs the vertices with the following gif [Figure 3] Figure 3 - Gif explaining how the code constructs each vertex.

The texture coordinate code ensures that the entire grid contains texture coordinates between 0 and 1, which is calculated using the provided cell count and grid size.

`XMFLOAT2(row * (cellCount.x / gridSize.Width), column * (cellCount.y / gridSize.Height))`

#### Constructing the Indices

Constructing the indices is a slightly different beast, but is fairly simple if we approach it in the correct way. First, let's look at the code in `BuildIndexList(...)`:

vector<unsigned short> GridBuilder::BuildIndexList(const XMFLOAT2 cellCount) { vector<unsigned short> indices = vector<unsigned short>(); for (int row = 0; row < cellCount.x; row++) { for (int column = 0; column < cellCount.y; column++) { unsigned short topLeftIndex = row * (cellCount.y + 1) + column; unsigned short topRightIndex = topLeftIndex + 1; unsigned short bottomLeftIndex = topLeftIndex + cellCount.y + 1; unsigned short bottomRightIndex = topLeftIndex + cellCount.y + 2; indices.push_back(topLeftIndex); indices.push_back(bottomRightIndex); indices.push_back(topRightIndex); indices.push_back(topLeftIndex); indices.push_back(bottomLeftIndex); indices.push_back(bottomRightIndex); } } return indices; }

This code will go through each square in each row of the grid, and get the index for that vertex. Because the vertices on a higher row will have much higher indexes, we need to add the cellCount to the index to move us up to the next row. Once this has been done, we can push 6 indices to the index list that represent the two polygon faces making up the square.

NOTE: This is the part where it is important to consider that DirectX uses a left-handed coordinate system. Make sure that you are drawing these polygon faces in a counter-clockwise direction, otherwise you are going to end up with some weird issues later down the line.

#### Preparing the Buffers for DirectX

If you are familiar with any object loading in DirectX, you should know that the vertex and index buffers need to be pushed into an object of type `ID3D11Buffer` to later get passed to the GPU. The last two helper methods, `CreateVertexBuffer(...)` and `CreateIndexBuffer(...)` do exactly this, and should be quite familiar to you.

ID3D11Buffer* GridBuilder::CreateVertexBuffer(const unsigned long long vertexCount, Vertex* finalVerts) const { D3D11_BUFFER_DESC bd; ZeroMemory(&bd, sizeof(bd)); bd.Usage = D3D11_USAGE_DEFAULT; bd.ByteWidth = sizeof(Vertex) * static_cast<UINT>(vertexCount); bd.BindFlags = D3D11_BIND_VERTEX_BUFFER; bd.CPUAccessFlags = 0; D3D11_SUBRESOURCE_DATA InitData; ZeroMemory(&InitData, sizeof(InitData)); InitData.pSysMem = finalVerts; ID3D11Buffer* vertexBuffer; _device->CreateBuffer(&bd, &InitData, &vertexBuffer); return vertexBuffer; } ID3D11Buffer* GridBuilder::CreateIndexBuffer(const int indexCount, unsigned short* indices) const { D3D11_BUFFER_DESC bd; ZeroMemory(&bd, sizeof(bd)); bd.Usage = D3D11_USAGE_DEFAULT; bd.ByteWidth = sizeof(WORD) * static_cast<UINT>(indexCount); bd.BindFlags = D3D11_BIND_INDEX_BUFFER; bd.CPUAccessFlags = 0; D3D11_SUBRESOURCE_DATA InitData; ZeroMemory(&InitData, sizeof(InitData)); InitData.pSysMem = indices; ID3D11Buffer* indexBuffer; _device->CreateBuffer(&bd, &InitData, &indexBuffer); return indexBuffer; }

The only thing left to do is to call all these methods in the right order and pass the geometry data back to the code that requested it! This call would be made to the publically avaliable `Build(...)` method by passing it the desired grid size and cell count. Then, slap on a texture and draw the grid, and it should look something like Figure 4 & 5. Figure 4 - 10x10 cell grid with 100x100 size. Figure 5 - 10x10 cell grid with 100x100 size.

In the next tutorial, we will investigate how to manipulate the y values on this grid using a height map.