Sunday, 12 February 2017

DoodleBob - xygine game released on

Somehow I've managed to not post about this project whatsoever in the last few months I've been working on it. DoodleBob is a virtual pet type game which I worked on over the christmas holidays, using completely hand drawn artwork - hence the name DoodleBob.

The game is built on xygine and is open source for anyone who wants to dig around - or if you just want to try it the game is available for windows (linux users will have to build from source) on the page.

I admit there are a few places which could do with some polish - but overall I'm pretty pleased with it. Perhaps at some point I'll write some posts about how the path finding and decision making work. For now though I'm happy to hear any suggestions or opinions through the comments below.

Thursday, 19 January 2017

tmxlite - 1.0.1 Released

I've released a bugfix update to tmxlite, my lightweight Tiled/tmx parser for C++.

Fixes include:
  • Fixed typo in FindTMXLITE file
  • Made render order property optional for backwards compatibility with older map versions
  • Fixed colourFromString() not properly removing preceeding #
  • Fixed Parsing of image property of collection of images tilesets
  • Fixed missing image size property for collection of images tilesets

There are also a couple of new / update features:
  • Added an OpenGL example using SDL2
  • Moved the SFML example to its own project folder
  • Updated the CMake file to allow compiling libtmxlite as a dependency of another project

The latest relase has been tested to work on Windows, linux and OS X. Thanks, as ever, go to the community members who have contributed via the Github page.

You can grab the source here and Visual Studio 2015 builds here.

Thursday, 24 November 2016

Procedural 2D Terrain - Part 4: Making Some Noise

So far I've not covered precise noise generation techniques I used for the terrain, mostly because I've not really settled on any one 'perfect' technique. I have finally begun to refine it, however, particularly as I'm now adding detail textures to the generation so I thought I'd share what I have so far.

A Quick Recap
If you've not seen how I'm currently rendering the terrain, it's probably worth reading part 1 of this series first, as I'll be referring to some of the rendering methods used. I'm currently using a noise generation library named FastNoiseSIMD which is highly optimised for x86/x64 processors, as well as being wonderfullly lightweight, requiring only a few source files to be added to the project. My old 2.1Ghz Core2Duo chomps through chunk generation with no problems at all as a testiment to the quality of the library.
    Noise generation for each chunk is performed in a series of steps using a variety noise patterns. I'll cover the settings of each as they currently are at the time of writing - although the source code may well have changed significantly by the time anyone reads this. I shall also point out that there is currently no generation of rivers or roads (although I plan to work on at least roads at some point), just everlasting terrain interspersed by large bodies of water. If you're on Windows and using FastNoise there is a binary in the releases section of the github repository, which allows previewing the different noise types. This has been incredibly useful while testing different noise parameters for quick visual feedback. While the FastNoise library itself is cross platform (at least, I have it working in xubuntu) the preview executable appears to be Windows only unfortunately, due to its dependence on .net. Perhaps if you're sadistic enough you might get it running with Mono...

The Data Structure
The underlying data array of each chunk has been modified since I wrote part 1. In that part I stated I use a 64x64 array of std::uint16_t, each value holding a bitmask of parameters which are sent to the shader. I've now increased the data size to std::uint32_t, so that more information my be included per value (each value represents a tile within the chunk). I could probably change the texture type used to store the array to RGBA 8-bit so that each channel is accessable in the shader without having to use bitwise operations to extract the data GPU side, and I may still do that, but for now it remains a single unsigned red channel. The format of each value looks like this (where F represents 4 used bits):
  • 0x000000FF - Tile ID. This is used by the shader to look up the index of a tile.
  • 0x00000F00 - BiomeID. There are 9 biomes, which fits nicely in 4 bits
  • 0x0000F000 - Depth value. This isn't the same as the height value, rather it is used by the shader to darken tiles to give some illusion of 'depth'. This is most noticeable in the water.
  • 0x00FF0000 - ID of a detail tile. Details are drawn on top of existing tiles, and exist within each biome tile set, so that each biome has a unique set of details
The top byte is not currently used, but will probably be involved in rendering the road systems.

Creating Tile Indices
To calculate the tile ID I use two maps. The first is a simplex fractal set, using the default FastNoise settings. The value is normalised then multiplied by 4 to provide 4 variations of tiles, where 0 is water and 1-3 are land varieties. This creates a 'lumpy' lanscape with pools of water and patches of hills. Then I set the the frequency of the noise generator to a much lower 0.003 to create a simplex set (note no fractals). This is used to create large open areas of water, such as seas and oceans by adding it to the first map before it has been normalised. The low frequency means that large areas of 0 value IDs are created during normalisation, which are interpreted as large bodies of water. It also produces nice looking  coast lines, and islands in shallower areas.
Potential real estate for a harbour?
These two maps are actually produced one tile larger in width and height than the chunk size - 65x65 values, starting at the position of the current chunk. This is so that once the values are normalised and converted to the 0-3 range they can be passed through the marching squares algorithm I talked about in the last post. Each tile needs to consider its neighbour, which is why the noise sets have the extra values. Once the final tile ID has been calculated it is OR'd into the bottom byte of the chunk's data array.

Biome Generation
To calculate the biome ID I use three noise maps:
  • Rainfall, which is a simplex fractal set with 3 octaves and a frequency of 0.005
  • Average temperature - a gradient fractal set with a RidgedMulti fractal type
  • Height data, created from a value fractal set with 2 octaves and a frequency of 0.002
I also create a 'latitudinal variance' which is a linear gradient in the Y direction which decreases with distance. This is used to decrease the average temperature the further north or south the chunk appears, and also slightly increase the rainfall value. The height map is also applied to the rainfall and temperature maps, decreasing temperature linearly with height,  and reducing the average rainfall to near zero after a certain limit. The rainfall and temperture values are then used as x/y coordinates in the biome lookup table, detailed in the last post, to find the biome ID. This is then shifted and OR'd into the lower half of the second byte of the chunk data array.

Biomes by the sea...

Depth data is also calculated at this point, by taking the terrain data map, normalising it, and multiplying it by 15, to fit it in to the top half of the second byte.

Adding Detail
Finally the values of detail tiles are calculated, although not with a noise map. Details, in this case, are tiles which may contain non-interactive vegetation, stones/rocks or items floating in the water, and are scattered as evenly as possible. To get a good distrubution I use a poisson disc function (based on this article, and added to xygine) which scatters the locations nicely. The side effect of not being noise based is that the result of the function is non-deterministic and varies every time it is run as it is not seed based - but for non-interactive details such as these I don't regard it as a real problem, particularly as chunks are written to disk after generation anyway, rendering the positions fixed. Details are based on the depth value of the current tile, of which the deepest value over open water is ignored. The remaining values are divided by 4 to determine which of the four tile types the current tile is a member of, before then being randomised between one of the 3 variations of detail for that type. These are stored in order in the biome tile set texture starting at index 90: 0A, 0B, 0C, 1A, 1B, 1C... and so on, where the number is the tile type, and letter the detail variation.

That pretty much sums up the noise generation as it stands - there is still a lot to do including laying out roads and adding cities and other interesting places for the player to visit and explore, but I am pleased with the progress so far.

Terrain Generation Repository.

Previous Parts:
Part 1
Part 2
Part 3

Thursday, 17 November 2016

Procedural 2D Terrain - Part 3: Texturing

Continuing from part 2 of the blog series, it was time to start texturing the terrain.

The Technique
At this point the terrain was rendered  by reading an index value stored in an integer texture and using it to choose a colour to be displayed. I modified the shader, based on this article, to look up the corresponding fragment in a tile set, and use the result to colour the current tile. Temporarily I used a texture which looked like this to see which indices were being rendered (warning crude programmer art ahead!):

While this went mostly without trouble I did discover that on some AMD cards there were occasional rounding errors, which led to the wrong tile being rendered. I fixed this by adding a small offset to coordinate values before rounding (which can be seen as the variable 'epsilon' in the shader source).

Smooth Transitions
The reason the above tile set has 120 tiles is because of what I had planned for the next part; now that I knew any tile could be rendered from within a set simply by using its index I wanted to create smooth transitions between the different textures in the set, rather than the harsh square edges of the tiles. I'd come across this article on using the marching squares algorithm to process the edges of transitions, so I implented it within the Chunk class's tile creation function. First the noise values are generated via FastNoise as before - but then the final tile indices are calculated using the marching squares algorithm. Using the above tile set again, I could check the correct tiles were being displayed. As you can see there was a minor problem:

Tile number 60 would not render...

After some amount of head scratching, and a lot of probing with renderdoc (thanks Aster!) I discovered that once again this was a rounding error - a position value which should have been 0 was in fact 1, causing tile 60 to render the last column of fragments from tile 74. A quick fix was to enable wrapping on the tile set texture so that the incorrect coordinate wrapped back around to tile 60 - but of course the proper fix was to correct the rounding error with the epsilon value once again. With a hastily scribbled tile set created in Pyxel Edit (I love this program) testing the terrain now displayed pleasing terrain transitions.

Texturing Biomes
At the end of the last post I wrote about how I included generating biome data. While the output is still far from refined the terrain was, by this point, generating biome IDs which were stored in the second byte of the array value, and therefore accessible to the shader. Using the ID my plan was to use a GL_TEXTURE_2D_ARRAY containing a tile set for each biome, and use the biome ID in the shader to select the correct texture when rendering. The index in the first byte of the lookup value would then select the correct tile from within the tile set.

More programmer art was needed to test this - I wanted a tile set (based on the above template) for each biome, but each tileset also needed to be different enough that it was visibly outstanding when rendered. The biome IDs are based on Whittaker's biome graph so using <searchengine> image search I found some reference images of real-world biomes and, coupled with Paletton, created a set of palettes which represented each biome.

Palettes for Cold Desert, Shrubland, Boreal Forest, Savanna Forest and Seasonal Forest
Eventually I'll use these palettes to make a series of complete tile sets, but for now they are enough to make coloured templates. Implementing the rendering didn't go entirely smoothly, however, as although it is possible to modify the OpenGL properties of SFML textures, it is not possible to use any format other than GL_TEXTURE_2D. This was a shame and, although I could have reimplemented the entire rendering setup in OpenGL, meant that I had to reconsider my options. Eventually I settled on building a texture atlas at run time, combining all of the tile sets in to a single texture. The biome ID was still valid, but in the shader was now used to calculate a position within the atlas at which the tile set started, rather than act as an index into a texture array. To combine the textures I took advantage of the sf::Image class, as not only could I validate that all the textures were the correct size, I could also compensate for load failures by replacing the images with a solid colour. The final atlas texture would still be valid if images on the disk weren't - although would not render correctly of course.

void TerrainComponent::loadTerrainTexture()
    m_terrainTexture.create(width * texturesPerSide, height * texturesPerSide);
    for (auto i = 0u; i < biomeCount; ++i)
        sf::Image img;
        if (!img.loadFromFile("assets/images/tiles/" + std::to_string(i) + ".png"))
            img.create(width, height, sf::Color::Magenta);
        if (img.getSize().x != width || img.getSize().y != height)
            img.create(width, height, sf::Color::Magenta);
            xy::Logger::log("Image " + std::to_string(i) + " was not correct size.", xy::Logger::Type::Warning);

        auto xPos = i % texturesPerSide;
        auto yPos = i / texturesPerSide;
        m_terrainTexture.update(img, xPos * width, yPos * height);

    m_terrainShader.setUniform("u_tileTexture", m_terrainTexture);

and the fragment shader:

void main()
    uint value = texture(u_lookupTexture, v_texCoord).r; 
    float index = float(value & 0xFFu); 
    vec2 tilesetCount = u_tilesetCount * biomeCount;
    vec2 position = vec2(mod(index, u_tilesetCount.x), floor((index / u_tilesetCount.x) + epsilon)) / tilesetCount;

    float biomeID = float((value & 0xf00u) >> 8u); 
    vec2 biomePosition = vec2(mod(biomeID, biomeCount.x), floor(biomeID / biomeCount.x)) / biomeCount; 

    vec2 texelSize = vec2(1.0) / textureSize(u_lookupTexture, 0);
    vec2 offset = mod(v_texCoord, texelSize); vec2 ratio = offset / texelSize; offset = ratio * (1.0 / u_tileSize); 
    offset *= u_tileSize / tilesetCount; 

    colour = texture(u_tileTexture, biomePosition + position + offset); 

Things are (rather colourfully) now coming together.

After I've finished creating more detailed tile sets it will be time to tackle terrain details, such as foliage, as well as further refining the noise generation technique. For now though the full code can be found in the repository.

Part 1
Part 2
Part 4

Tuesday, 15 November 2016

tmxlite - A lightweight Tiled map parser for C++14

One of the biggest problems with the SFML tmx map loader is its dependency on not only SFML but zlib, which can be a pain to set up correctly on many platforms. A while back I stumbled upon miniz which is a drop in replacement for zlib in a single source file. I used it when adding tmx map support to xygine, and was so pleased with the result that I've spun off the parser in to its own library. tmxlite is small, supports all compression formats, and can be compiled in to a static or shared library on any platform which supports CMake (probably even on mobile!), without any of the fuss of linking to external libraries. It also offers (in my opinion) a far cleaner API to the map structure of Tiled maps than the SFML map loader, so that any graphics library can be used with it, not just SFML. If you're intrigued, or just want to try a different library, you can find it on Github here.

Thursday, 10 November 2016

Procedural 2D Terrain - Part 2: Creating Chunks

In my last post I wrote about how I set up rendering of chunk data in the TerrainComponent class of my procedural terrain experiment. Once I had this working it was time to start creating chunks on the fly, and then caching the data to be used when a chunk was revisited.

Resource Management
To handle the generation of chunk data the TerrainComponent is put in charge of ownership of the Chunk class instances, as well as any resources they require. When creating and destroying objects frequently memory fragmentation can be a concern, and repeatedly loading / saving assets from storage can also bottleneck performance. Chunks are allocated on the heap using std::unique_ptr, so to address the first issue xygine (my game framework within which I'm currently experimenting) provides an ObjectPool class, designed to manage allocated memory and efficiently recycle it, preventing any fragmentation. Depending on where the player is in the world up to 4 chunks are visible at one time, and generally 9 chunks are active at any time (the current chunk containing the player and 8 surrounding chunks) so a fixed allotment of memory can be used, from which the TerrainComponent can draw upon as it creates new chunks. When chunks are destroyed the memory is marked as free and automatically reallocated by the ObjectPool.
    Chunks also require at least one shader when being drawn (other shaders may be used for effects like water) and continually creating / destroying shaders is time consuming. The TerrainComponent has a single shader as a member, compiled on start up, a reference to which is passed to each new chunk as it is created. As outlined in part 1 each chunk requires a specially formatted texture which is used as a lookup table and, again, to keep creating and destroying these would be both time consuming and quite possibly cause memory fragmentation. The TerrainComponent therefore manages a pool of textures so that they may be reused rather than recreated. This is done by creating a ChunkTexture alias

using ChunkTexture = std::pair<sf::Texture, bool>;

and creating a vector of ChunkTexture. Textures are paired with a bool flag which marks whether or not the texture is currently in use by a chunk. The vector has to be initialised in the TerrainComponent constructor so that the textures are in the correct format and the flags have an initial value of false.

for (auto& tp : m_texturePool)
    tp.first.create(64, 64);
   glBindTexture(GL_TEXTURE_2D, tp.first.getNativeHandle());
    glTexImage2D(GL_TEXTURE_2D, 0, GL_R16UI, tp.first.getSize().x, tp.first.getSize().y, 0, GL_RED_INTEGER, GL_UNSIGNED_SHORT, 0);
    glBindTexture(GL_TEXTURE_2D, 0);
    tp.second = false; //texture not yet used

As m_texturePool is a std::vector a utility function can quickly find the first unused texture:

ChunkTexture& TerrainComponent::getTexture()
    return *std::find_if(std::begin(m_texturePool), std::end(m_texturePool),
        [](const ChunkTexture& ct)
        return !ct.second;

A reference to a free texture is then passed to a Chunk, along with the shader, when it is created (I'm aware of the assumption that the above function will always return a free texture - this is because the ObjectPool for the Chunk instances is a fixed size, which is the same size as the texture pool. If, at any point, I'm trying to create more chunks than I have free resources then I've got a bigger problem on my hands...). This takes care of the resource handling, but the TerrainComponent has a second job: to monitor the player's position in the world, and update the corresponding world chunks.

Creating Chunks On The Fly
Two things needed to be done to the Chunk class then. Firstly a chunk needs to have some positional data. It needs a position in world space, and a size. This is done by providing an sf::FloatRect which represents the global bounds of the chunk. The bounding rectangle can be used to test if it contains the player position, and compare it to the position from the last frame. If the current chunk differs from the previous chunk then the player has moved from one chunk to another, triggering a chunk update. Each active chunk is tested, via its global bounds, to see if it contains one of 8 points surrounding the current chunk (which contains the player). If the test fails the chunk is removed, the ObjectPool automatically freeing the memory, and the destructor of the chunk marks its texture as being free. The surrounding points are again tested to see which chunks do not yet exist, and any missing chunks are created in the active chunks list.
    Secondly a chunk has to be able to update its texture with an array of tile data. This is done by giving each chunk a unique ID based on a hash of its 2D position. When a chunk is created it looks to local storage for a file with the same name as its ID. If it is found the file is loaded and the contents copied to the chunk array. As the data is only 8kb in size I've found that this loads fast enough to not visibly block the execution of the program - although I have yet to implement any error checking. If a matching file is not found, however, then the chunk must be generated from scratch using the noise library. This, I have found, did cause some visual stutter, so the chunk creation function is called in its own thread. Some care is required for syncronisation, but an atomic bool flag is enough to tell the chunk when the data is ready to be uploaded to its texture. The chunk's position is needed here too as the noise function which generates terrain data does so based on a coordinate system. Once new chunk data has been created it is saved immediately to a file, so it can be reloaded next time the chunk is visited.

The Result
By this point I had a smooth, seemingly endless terrain generating on screen, with nice, tightly managed resources. I was able to leave a weight on the arrow keys of my keyboard for about 20 minutes so the 'player' kept on walking in a single direction, with absolutely no problems at all (don't worry the video isn't 20 minutes long...).

Now that the chunk system was working it was time to start working on generating biome data. Biomes, as I am sure many people are familiar with, describe the differences in terrain, such as forest areas, deserts or mountains. Using this post as a guide I set about generating further noise maps when a chunk was created for the first time, which create data that can be used to look up a biome ID from a static table of data. This ID is then OR'd into the data array value at that coordinate. This will eventually be used to select the correct texture for that biome, although currently I feel the noise generation part could do with some tweaking. In the above video the middle view of the minimaps on the right displays the different biomes, with which I am currently not personally happy. Some fine tuning will be required, before moving on to texturing...

Part 1
Part 3