Procedural 2D Terrain - Part 1: Rendering
There comes a time in every programmer's life when he or she decides to create their own vast, explorable, procedurally generated world. I don't know why, it's as if it's some rite of passage all enthusiastic game programmers must go through. I've been delving in to it myself in recent weeks, and this post is going to attempt to document some of my experiences. Much of what I've done is merely a reimplementation of other works, based on blog posts scattered about the web (and linked where possible), although I like to think I've managed to apply some of my own ideas to the technique.
In part 1 I'll skip over any particular data generation details. Procedural terrain is generally created via a combination of noise maps, and there are many resources out there covering how height, temperature and rainfall data are combined with landscape details to create a convincing (or at least attractive and interesting to visit) world. Instead I want to outline how I store and manipulate that data once it is accrued, and how it is rendered to screen. Part 2 will cover how the terrain data is split in to chunks and streamed to and from disk. If I ever get around to it part 3 will cover texturing the terrain, including the marching squares algorithm and biome texture selection.
Setting Up
As always my experiment begins with my framework, xygine. This takes care of most of the boilerplate code, so I can dive straight into the terrain generation. The terrain itself is constructed around two main classes. The TerrainComponent which implements xygine's Component interface, so that the terrain can be drawn as any other drawable within a Scene. The TerrainComponent manages the resources needed to draw the terrain, as well as a series of instances of the Chunk class. The Chunk class is used to calculate and draw a section of terrain and is where all the actual data is located. The repository for the terrain experiment is available on Github, so you can pick the source apart in all its gory detail. The noise maps used to generate the data are most commonly created via perlin or simplex fractal algorithms. There are other resources out there covering the topic, so I'll skip the details beyond stating the requirement of some sort of noise map generation code. As I'm too lazy (and, quite frankly, too ignorant) to write my own, I use a library called FastNoise. In general libNoise appears to be the most commonly recommended library, but I've found that a FastNoise variation, FastNoiseSIMD, is lightweight, and very performant. As its name suggests it uses SIMD optimisations to dramatically speed up the time it takes to generate noise maps, which is important if I want to generate them in real time as the player wanders around the world, but has the drawback of being compatible only with x86/x64 CPUs. It is still cross platform, however, I have it working on both Windows and linux - and, if I gave a fig about Apple, I'm sure it'd work on OS X too.
Data Design
At its core the data required to render a terrain is just an array of bytes which represent a grid. In this case, to try and keep the array as small as possible, I use an array of std::uint16_t - unsigned short if you prefer - to store the tile IDs of the texture used to draw a chunk. IDs themsevlves never actually exceed 255 and so could be stored in a single byte, but I also store other metadata per tile. As the terrain is split in to biomes, for example forest, desert or tundra, only the bottom byte is used to store the tile ID - the top byte contains the ID of the biome to which the tile belongs. This means that biomes can be represented with different tile sets - the tile ID itself merely represents a tile within that set. I find this is more flexible as biomes can be added more easily by creating a new texture from a template, as well putting a cap on the maximum tile ID.
A single chunk is made of 64 x 64 tiles, which totals 4096 values. As each tile value is 2 bytes in size the entire array is a mere 8kb in total. This is useful not only because of the small memory footprint, but because at some point I'll want to read and write the chunks to disk and the smaller the amount of data required the faster the operation will be. The array of data is also maintained within the Chunk class so that, should I chose, the player can interact with and modify the terrain which ultimately comes down to updating one or more tile values. The updated chunk data can then be saved, so player modifications to the world are persistent, and automatically loaded next time the chunk is visited.
Creating Data
To begin with I was only interested in getting something displayed on screen, refining the map generation and calculating biome data would come later, as well as managing multiple chunks of terrain. When drawing tile maps with SFML (the library powering xygine) the most common technique is to use a vertex array. This usually involves some complicated wrangling of vertex data, tile positions, texture coordinates and so on, and also often suffers the pixel offset problem. More recently, based on a post by Mickaël Pointier (known as the venerable _Dbug_ on #sfml) I implemented GPU side tile mapping for xygine's tmx/Tiled map renderer component, and so decided to extend the technique to the terrain renderer. To first get the map data from the noise generator in to a suitable format I populated the chunk's array, mapping the -1 to 1 floating point values to 0 - 3 integer range. This would represent 4 initial tile IDs which could be drawn on screen. FastNoise generates three dimensional data and it can be slightly confusing retreiving a 2D plane, as it reverse iterates the noise set starting with the z axis.
float* noiseData = noise->GetSimplexSet(0, 0, 0, 64, 64, 64);
for(auto z = 0; z < 64; ++z)
{
for(auto y = 0; y < 64; ++y)
{
std::size_t idx = z * 64 + y;
std::uint16_t value = static_cast<std::uint16_t>((noiseData[i] * 0.5f + 0.5f) * 3.f);
m_data[i] = value;
}
}
This is a simplified example of noise creation - it doesn't cover calculation of biome data, but provides enough to get started on visualisation. Notice how the range of the noise value is first normalised, then multiplied by 3 - the maximum tile ID for this example. From here I wanted to move the values in m_data to the GPU so that they can be used as a lookup table. In theory I could pass the array as a uniform to the shader, although in this case I opted to create a texture. Textures are fundamentally an array of data in video memory, so creating a texture from the chunk data means it is only uploaded to VRAM once, until the next time it's updated. SFML provides a nice clean API, hiding away the details of OpenGL, but unfortunately this means that, by default, the texture format is not optimal. SFML expects textures to be 8bit RGBA, whereas the tile map data is 16bit. However SFML does expose the underlying OpenGL texture ID so with a little work I can modify the texture format to suit my needs. In theory I could split the 16bit data in to 2 8bit RG channels (which I may eventually do to reduce the amount of bitwise operations performed) but for now I've taken advantage of the R16UI format.
texture.create(64, 64);
glBindTexture(GL_TEXTURE_2D, texture.getNativeHandle());
glTexImage2D(GL_TEXTURE_2D, 0, GL_R16UI,64, 64, 0, GL_RED_INTEGER, GL_UNSIGNED_SHORT, m_data.data());
glBindTexture(GL_TEXTURE_2D, 0);
The texture is created as normal, but then I use the native handle to bind the texture, and modify its format. glTexImage2D() sets the format of the texture to GL_R16UI (red channel only, 16 bit unsigned integer), its size to the chunk size, and takes a pointer to the array of data created from the noise function as a final parameter. The Chunk class can update its texture at any time with glTexSubImage2D(), so if the data is modified, say by a player at run time, the modified data can quickly be uploaded to the existing texture. This also proved to be very flexible when splitting the terrain into multiple chunks as a set of textures can be pooled and reused between chunks. As far as the CPU side of things go this was pretty much all that was needed to render a chunk - no vertex arrays, no wrangling of multiple data buffers. Now it was over to the GPU...
Displaying the Data
Drawing the chunk requires a shader to take advantage of the lookup texture, but preliminarily is pretty simple. The draw function of the Chunk class merely binds the texture and the shader, and draws it as a single quad via a vertex array (OK so I still need a vertex array, but 4 fixed points are far easier to manage).
void Chunk::draw(sf::RenderTarget& rt, sf::RenderStates states) const
{
m_shader.setUniform("u_texture", m_chunkTexture);
states.texture = &m_chunkTexture;
states.shader = &m_shader;
rt.draw(m_vertices.data(), m_vertices.size(), sf::Quads, states);
}
It is important to set the states texture as it allows SFML to internally set up the texture coordinates of the vertex array. The vertex array is also sized so that the quad is 4096 x 4096 pixels in size, making each tile 64px square (though this may change at some point). All the grunt work is done in the fragment shader but, as it requires version 1.3 of GLSL, I also had to use a custom vertex shader. The vertex shader can be seen here, and the first revision of the fragment shader is listed below:
#version 130
uniform usampler2D u_texture;
in vec2 v_texCoord;
in vec4 v_colour;
out vec4 outColour;
vec3[4] colours = vec3[4](vec3(0.0,0.0,1.0), vec3(1.0,1.0,0.0), vec3(0.8, 1.0,0.0), vec3(0.0, 0.9,0.1));
void main()
{
uint index = texture(u_texture, v_texCoord).r;
outColour = vec4(colours[index], 1.0);
}
The texture sampler is of type usampler2D - because the lookup texture contains unsigned integer values, as opposed to default floating point type. The shader then takes the value from the current fragment and uses it as an index in to the colours array, to colour the final output. Eventually this lookup will be done within a tile set texture, but for now this is enough to check that it was working.
In summary: the tile information of a terrain chunk can be stored as an array of integer values, representing the ID of a tile. This array is stored in a texture on the GPU which is used by the fragment shader to look up the ID of the tile to be drawn, moving as much of the image processing from the CPU to the GPU as possible.
Part 2
In part 1 I'll skip over any particular data generation details. Procedural terrain is generally created via a combination of noise maps, and there are many resources out there covering how height, temperature and rainfall data are combined with landscape details to create a convincing (or at least attractive and interesting to visit) world. Instead I want to outline how I store and manipulate that data once it is accrued, and how it is rendered to screen. Part 2 will cover how the terrain data is split in to chunks and streamed to and from disk. If I ever get around to it part 3 will cover texturing the terrain, including the marching squares algorithm and biome texture selection.
Setting Up
As always my experiment begins with my framework, xygine. This takes care of most of the boilerplate code, so I can dive straight into the terrain generation. The terrain itself is constructed around two main classes. The TerrainComponent which implements xygine's Component interface, so that the terrain can be drawn as any other drawable within a Scene. The TerrainComponent manages the resources needed to draw the terrain, as well as a series of instances of the Chunk class. The Chunk class is used to calculate and draw a section of terrain and is where all the actual data is located. The repository for the terrain experiment is available on Github, so you can pick the source apart in all its gory detail. The noise maps used to generate the data are most commonly created via perlin or simplex fractal algorithms. There are other resources out there covering the topic, so I'll skip the details beyond stating the requirement of some sort of noise map generation code. As I'm too lazy (and, quite frankly, too ignorant) to write my own, I use a library called FastNoise. In general libNoise appears to be the most commonly recommended library, but I've found that a FastNoise variation, FastNoiseSIMD, is lightweight, and very performant. As its name suggests it uses SIMD optimisations to dramatically speed up the time it takes to generate noise maps, which is important if I want to generate them in real time as the player wanders around the world, but has the drawback of being compatible only with x86/x64 CPUs. It is still cross platform, however, I have it working on both Windows and linux - and, if I gave a fig about Apple, I'm sure it'd work on OS X too.
Data Design
At its core the data required to render a terrain is just an array of bytes which represent a grid. In this case, to try and keep the array as small as possible, I use an array of std::uint16_t - unsigned short if you prefer - to store the tile IDs of the texture used to draw a chunk. IDs themsevlves never actually exceed 255 and so could be stored in a single byte, but I also store other metadata per tile. As the terrain is split in to biomes, for example forest, desert or tundra, only the bottom byte is used to store the tile ID - the top byte contains the ID of the biome to which the tile belongs. This means that biomes can be represented with different tile sets - the tile ID itself merely represents a tile within that set. I find this is more flexible as biomes can be added more easily by creating a new texture from a template, as well putting a cap on the maximum tile ID.
A single chunk is made of 64 x 64 tiles, which totals 4096 values. As each tile value is 2 bytes in size the entire array is a mere 8kb in total. This is useful not only because of the small memory footprint, but because at some point I'll want to read and write the chunks to disk and the smaller the amount of data required the faster the operation will be. The array of data is also maintained within the Chunk class so that, should I chose, the player can interact with and modify the terrain which ultimately comes down to updating one or more tile values. The updated chunk data can then be saved, so player modifications to the world are persistent, and automatically loaded next time the chunk is visited.
Creating Data
To begin with I was only interested in getting something displayed on screen, refining the map generation and calculating biome data would come later, as well as managing multiple chunks of terrain. When drawing tile maps with SFML (the library powering xygine) the most common technique is to use a vertex array. This usually involves some complicated wrangling of vertex data, tile positions, texture coordinates and so on, and also often suffers the pixel offset problem. More recently, based on a post by Mickaël Pointier (known as the venerable _Dbug_ on #sfml) I implemented GPU side tile mapping for xygine's tmx/Tiled map renderer component, and so decided to extend the technique to the terrain renderer. To first get the map data from the noise generator in to a suitable format I populated the chunk's array, mapping the -1 to 1 floating point values to 0 - 3 integer range. This would represent 4 initial tile IDs which could be drawn on screen. FastNoise generates three dimensional data and it can be slightly confusing retreiving a 2D plane, as it reverse iterates the noise set starting with the z axis.
float* noiseData = noise->GetSimplexSet(0, 0, 0, 64, 64, 64);
for(auto z = 0; z < 64; ++z)
{
for(auto y = 0; y < 64; ++y)
{
std::size_t idx = z * 64 + y;
std::uint16_t value = static_cast<std::uint16_t>((noiseData[i] * 0.5f + 0.5f) * 3.f);
m_data[i] = value;
}
}
This is a simplified example of noise creation - it doesn't cover calculation of biome data, but provides enough to get started on visualisation. Notice how the range of the noise value is first normalised, then multiplied by 3 - the maximum tile ID for this example. From here I wanted to move the values in m_data to the GPU so that they can be used as a lookup table. In theory I could pass the array as a uniform to the shader, although in this case I opted to create a texture. Textures are fundamentally an array of data in video memory, so creating a texture from the chunk data means it is only uploaded to VRAM once, until the next time it's updated. SFML provides a nice clean API, hiding away the details of OpenGL, but unfortunately this means that, by default, the texture format is not optimal. SFML expects textures to be 8bit RGBA, whereas the tile map data is 16bit. However SFML does expose the underlying OpenGL texture ID so with a little work I can modify the texture format to suit my needs. In theory I could split the 16bit data in to 2 8bit RG channels (which I may eventually do to reduce the amount of bitwise operations performed) but for now I've taken advantage of the R16UI format.
texture.create(64, 64);
glBindTexture(GL_TEXTURE_2D, texture.getNativeHandle());
glTexImage2D(GL_TEXTURE_2D, 0, GL_R16UI,64, 64, 0, GL_RED_INTEGER, GL_UNSIGNED_SHORT, m_data.data());
glBindTexture(GL_TEXTURE_2D, 0);
The texture is created as normal, but then I use the native handle to bind the texture, and modify its format. glTexImage2D() sets the format of the texture to GL_R16UI (red channel only, 16 bit unsigned integer), its size to the chunk size, and takes a pointer to the array of data created from the noise function as a final parameter. The Chunk class can update its texture at any time with glTexSubImage2D(), so if the data is modified, say by a player at run time, the modified data can quickly be uploaded to the existing texture. This also proved to be very flexible when splitting the terrain into multiple chunks as a set of textures can be pooled and reused between chunks. As far as the CPU side of things go this was pretty much all that was needed to render a chunk - no vertex arrays, no wrangling of multiple data buffers. Now it was over to the GPU...
Displaying the Data
Drawing the chunk requires a shader to take advantage of the lookup texture, but preliminarily is pretty simple. The draw function of the Chunk class merely binds the texture and the shader, and draws it as a single quad via a vertex array (OK so I still need a vertex array, but 4 fixed points are far easier to manage).
void Chunk::draw(sf::RenderTarget& rt, sf::RenderStates states) const
{
m_shader.setUniform("u_texture", m_chunkTexture);
states.texture = &m_chunkTexture;
states.shader = &m_shader;
rt.draw(m_vertices.data(), m_vertices.size(), sf::Quads, states);
}
It is important to set the states texture as it allows SFML to internally set up the texture coordinates of the vertex array. The vertex array is also sized so that the quad is 4096 x 4096 pixels in size, making each tile 64px square (though this may change at some point). All the grunt work is done in the fragment shader but, as it requires version 1.3 of GLSL, I also had to use a custom vertex shader. The vertex shader can be seen here, and the first revision of the fragment shader is listed below:
#version 130
uniform usampler2D u_texture;
in vec2 v_texCoord;
in vec4 v_colour;
out vec4 outColour;
vec3[4] colours = vec3[4](vec3(0.0,0.0,1.0), vec3(1.0,1.0,0.0), vec3(0.8, 1.0,0.0), vec3(0.0, 0.9,0.1));
void main()
{
uint index = texture(u_texture, v_texCoord).r;
outColour = vec4(colours[index], 1.0);
}
The texture sampler is of type usampler2D - because the lookup texture contains unsigned integer values, as opposed to default floating point type. The shader then takes the value from the current fragment and uses it as an index in to the colours array, to colour the final output. Eventually this lookup will be done within a tile set texture, but for now this is enough to check that it was working.
 |
| The three smaller images on the right are there to help visualise some of the other data such as biome coverage, which I'll explain more about that in the next post. |
In summary: the tile information of a terrain chunk can be stored as an array of integer values, representing the ID of a tile. This array is stored in a texture on the GPU which is used by the fragment shader to look up the ID of the tile to be drawn, moving as much of the image processing from the CPU to the GPU as possible.
Part 2
Comments
Post a Comment