Autotiling adventures

So, we have a procedurally generated biome map, where each pixel is an individual biome. If we zoom in, it’s obviously quite pixelated. If we add sprites, it just doesn’t look right (besides the lighting and colors)

We have reasonably detailed sprites on a single-colored squares. It’s just ugly. We need to add some texture/detail.

Auto-tiling

 

Enter auto-tiling (or transition tiles): a method to automatically place tiles with texture so that each tile matches perfectly with their neighbours. It’s a bit of a wild west out there in terms of approaches, so here are some resources (or resource lists) that I found useful:

https://pixelation.org/index.php?topic=9865.msg107117#msg107117
https://gamedevelopment.tutsplus.com/tutorials/how-to-use-tile-bitmasking-to-auto-tile-your-level-layouts–cms-25673
http://www.cr31.co.uk/stagecast/wang/blob.html
https://www.codeproject.com/Articles/106884/Implementing-Auto-tiling-Functionality-in-a-Tile-M

https://gamedev.stackexchange.com/questions/32583/map-tile-terrain-transitions-with-3-4-different-types
https://www.gamedev.net/forums/topic/606520-tile-transitions/
https://gamedev.stackexchange.com/questions/26152/how-can-i-design-good-continuous-seamless-tiles
http://allacrost.sourceforge.net/wiki/index.php/Video_Engine_Visual_Effects#Transition_Tiles
https://web.archive.org/web/20161023185925/http://www.saltgames.com/article/awareTiles/
https://www.gamedev.net/search/?q=tile%20transitions&fromCSE=1#gsc.tab=0&gsc.q=tile%20transitions&gsc.page=1
https://www.gamedev.net/articles/programming/general-and-gameplay-programming/tilemap-based-game-techniques-handling-terrai-r934/
http://www-cs-students.stanford.edu/~amitp/gameprog.html#tiles
http://playtechs.blogspot.co.uk/2007/04/tileset-design-tip.html
https://opengameart.org/forumtopic/auto-tiling-standardization
https://forums.tigsource.com/index.php?topic=21237.0
http://www.pascalgamedevelopment.com/showthread.php?22862-Tilemaps-and-autotiles
https://gamedev.stackexchange.com/questions/125284/what-is-the-term-for-a-3×3-tile-set-used-to-create-larger-areas/125285
https://forum.unity.com/threads/2d-tile-mapping-in-unity-demystified.441444/

Quite a few.

There are two main ways to consider art when using autotiles: using masks, or using premade textures. A good example is shown here:

Autotiling example

https://i1.wp.com/allacrost.sourceforge.net/wiki/images/1/19/Autotileex.gif?w=630

Blend masks example

https://i0.wp.com/allacrost.sourceforge.net/wiki/images/3/34/Blendmaskex.gif?w=630

The premade tiles have the obvious benefit that they can be very nicely done, but of course they are tied to the content they represent.  The blend masks do not look as good, but are easier to develop, and they are more flexible in terms of what textures we want to seamlessly mix. I decided to use masks as I want transitions between any biome: for 16 biome types, that’s 120 unique combinations. It’s not an option to ask an artist to develop 120 different autotiles, that needs quite a bit of money and time. And also, that would have no variation; each autotile would be replicated all over the place, so it would be easy to distinguish patterns.

 

Grid shifting

The first naive thought that comes to mind (and I went with it for a while actually) is “ok, we have a tile, it is neighbour to 4 or 8 other tiles, so generate masks according to that relationship”. Example here. As one can see, the 4-connected version is less interesting than the 8-connected version (and we don’t want less-interesting), but the 8-connected version results in a lot of combinations! So what do we do? Well, we shift the grid. This way, we always have 4 potentially different tiles (quarters of them anyway)

Below, we shift the whole grid top-left by half a tile. Now, each grid cell (red) always contains parts of 4 tiles.

While this is mentioned in a few articles, it’s demonstrated perfectly in a non-technical article, here. That’s what sold me, as I find the results amazing!

 

Reducing unique combinations

So, that’s what I mostly found so far in reference material. Now, a 2×2 grid as described can contain 4 different biomes. That’s 4 bits, therefore 16 possible total combinations/arrangements. Here’s how they look like (source):

 

In the “16 most basic tiles” above, we can observe the following:

  • No 16 can be expressed by transforming 15 (180 deg rotation)
  • No 11,13,14 can be expressed by transforming 10 ( 90,180, 270 deg rotation)
  • No 3,9,7 can be expressed by transforming 1 ( 90,180, 270 deg rotation)
  • No 2,6,8 can be expressed by transforming 4 ( 90,180, 270 deg rotation)
  • No 5,12 contains no spatially varying data

This implies that the only unique tiles are 1,4,10,15,5,12. Furthermore, the only unique tiles with spatially varying data are 1,4,10,15. So, that is 4 tiles instead of 16. We can arrange such a mask of 4 tiles like this:

This has a nice continuous shape, if for example we want to ask an artist to draw some of those. Note that with this arrangement, the transformation will differ, as now the masks are already transformed compared to what I showed above. What’s really important is that the amount of white vs black at the borders that contain both needs to always match, so that tiles are seamlessly combined. In my case above, I’m splitting them at 50%, but that’s of course configurable. What I’m not going to cover, as I’ve given it some thought and gets very complicated, is to support variable black/white border percentages, ensuring that they match There are many more complications involved and I’m not sure if it’s worth it in the end.

So, now we have 4 unique combinations. These can be nicely stored in an RGBA texture (one mask per channel) by converting the above 1×4 tile image. In the shader, given a mask value in [0,15], we effectively do the following:

mask = ... // obtain mask value from 4 underlying biome map tiles. Value in [0,15]
(mask_unique, transform) = get_transform(mask); // use a lookup table to get the unique mask index [0,3] and the transform needed
uv2 = apply_transform(uv, transform); // transform the texture coordinates
mask_rgba = sample_mask_texture(uv2); // sample the mask values
mask_value = -1;
switch(mask_unique)
{

    case 4:  mask_value = 0; break; // whole mask is empty
    case 5:  mask_value = 1; break; // whole mask is full
    default: mask_value = mask_rgba[mask_unique]; // get the component that we need
}

Most of the above can be done in the vertex shader, whereas the last two steps (sampling the texture and getting the component) need to be done in the pixel shader. So, it’s quite cheap.

Rendering tiles

So, we have a method to render tiles given a very small number of masks. How do we render the tiles? Here’s the naive approach, for a 512×512 biome map:

  • We have 16 biome layers, so I assign each a priority. E.g. shallow water covers coast. Water covers shallow water and coast. Deep water covers water, shallow water and coast. And so on.
  • For each layer, we generate tile render data as follows:
    • For each tile corner in the biome (513×513 grid of points)
      • Sample the 4 adjacent biome types (clamp to border if out of bounds)
      • Create the mask where we set 1 if the layer is equal or higher priority than current, or 0 if the layer is of lower priority than current
      • Based on the mask value, calculate unique mask index and transform, and store in this tile’s render data

So, now we have a list of 513x513x16 tiles = 4.21 million. That’s quite a lot. But as I said, that’s the naive version. Observations:

  • When the unique mask index corresponds to constant 0 (mask_unique index == 4), we don’t need to consider the tile for rendering.
  • When all of the four biome values in a tile are of higher priority than the  current layer, this means that the tile will be completely covered by higher priority layer tiles, and therefore we don’t need to render it.

By applying these two, for my test map I reduced the number of tiles to 0.4 million, which is 10x better. Of course, that’s still a lot, but it doesn’t take into account any spatial hierarchy and other optimisations that could be done.

Here are some examples using the above un-nice mask. Zoomed-out:

Zoomed-in

Ok, so my mask looks bad, and there’s little to none variation, so you can see patterns everywhere.

Increasing variation

Using 256×256 masks, a single RGBA texture needs 256K of memory. We can have a texture array of such masks, using however many layers we can afford memory-wise. In runtime, we can select the layer based on various conditions. E.g. some texture layers could contain transition masks for particular biomes, or more generally, we can select a layer based on a function of the tile coordinates.

Next…

Next post will be about procedurally-generating lots of masks, using distance fields versus using binary masks, and also determination of locations for placement of props.

Shader variables

Since the game will utilize graphics quite a bit in the style of old SNES-era games (multiple layers, lots of sprites), that means using a rendering engine which is above trivial level. Additionally, since much of rendering will be based on procedural techniques, that means lots of shaders. Lots of shaders requires configurability of said shaders using uniform variables. And this is the topic of this post.

A shader variable (ShaderVar) is an abstraction for such uniform variables. The abstraction allows manipulation of the value via ImGui (using optional minmax ranges for integer/float variables and vectors) and updating the values in the OpenGL state. These variable abstractions can also be used to solve the problem of automatic binding of textures, as in OpenGL it can be a bit of a pain to manage. Finally, we can add stat gathering functionality to identify at a rendercall if there are any variables which haven’t been set, which can be quite useful for debugging. A brief overview is the following:

Effect loading. Inspect loaded effect (program) for uniform variables that are used by the shaders. Make two lists: one for textures/buffers and one for other values. The index in the sampler list is set as the texture unit location that we should be binding any texture or sampler

ShaderVars class.  An abstraction for a group of ShaderVar objects. Each object has a name and value, and a uniform location for an arbitrary number of effects. That means that we can do the following:

SetShaderVar<float>( shaderVars, "g_Speed", 0.5f); // Set the value 0.5f to the variable g_Speed
...
UpdateShaderVars( shaderVars, fx1);// If g_Speed exists in fx1, it's set as 0.5f
...
UpdateShaderVars( shaderVars, fx2);// If g_Speed exists in fx2, it's set as 0.5f

It’s not really complicated underneath, but it serves as a nice abstraction to not deal with strings in the underlying implementations, as we’re dealing directly with uniform locations and vectors of such locations. At the moment I’m using strings for setting values, but this can (and will) be changed to use other forms, such as properties

Global and local ShaderVars. When we’re about to render, we can update the shader using several such blocks. For example, one block could be globals for the whole application (window width,height), others could be globals for the current frame (current time) or also more specific, such as common values for overworld rendering ( The grid section that is currently in view, etc). These globals can be stored in the registry and fetched using a handle. After the globals are set, we can update the effect using any local shader variables. In case of a clash, we override with the most local version of the variable. Such overwrites can also be detected, warning for any misuse of the system.

Here’s how a few sections look like in the config files:

// Some shadervar blocks
"ShaderVars" : [
    { "GlobalPerApplication" : {
        "@factory" : "ShaderVarsSeparate",
        "ShaderVars" : [ 
        ]
    }},
    { "GlobalPerFrame" : {
        "@factory" : "ShaderVarsSeparate",
        "ShaderVars" : [ 
            {"Name" : "g_TotalTime", "@factory" : "ShaderVarFloat"}
        ]
    }},
    { "GlobalOverworld" : {
        "@factory" : "ShaderVarsSeparate",
        "ShaderVars" : [ 
            {"Name" : "g_HeightScale", "@factory" : "ShaderVarFloat", "Values" : [0.0], "Min" : 0, "Max" : 4},
            {"Name" : "g_BiomeMap", "@factory" : "ShaderVarTextureStatic", "Values" : ["biome"]},
            {"Name" : "g_SpriteOffsetY", "@factory" : "ShaderVarFloat", "Values" : [0.5], "Min" : 0, "Max" : 1},
            {"Name" : "g_TileMapRects", "@factory" : "ShaderVarTextureBufferStatic", "Values" : ["dcss_rects"]},
            {"Name" : "g_TileMap", "@factory" : "ShaderVarTextureStatic", "Values" : ["dcss"]},
            {"Name" : "g_ResourcesMap", "@factory" : "ShaderVarTextureStatic", "Values" : ["resources"]}
        ]
    }},
    { "GlobalFlashing" : {
        "@factory" : "ShaderVarsSeparate",
        "ShaderVars" : [ 
            {"Name" : "g_FlashMinIntensity", "@factory" : "ShaderVarFloat", "Values" : [0.5], "Min" : 0, "Max" : 1},
            {"Name" : "g_FlashMaxIntensity", "@factory" : "ShaderVarFloat", "Values" : [1.0], "Min" : 0, "Max" : 1},
            {"Name" : "g_FlashPeriod", "@factory" : "ShaderVarFloat", "Values" : [2.0], "Min" : 0, "Max" : 5}
        ]
    }}
],
... 
// Some renderers. They can use shadervar blocks
{"OverworldDense" : {
    "@factory" : "RendererGrid2Dense",
    "Fx" : "OverworldDense",
    "ShaderVars" : ["GlobalPerFrame", "GlobalOverworld"],
    "DepthTest" : true
}},
{"GridSparseHighlight" : {
    "@factory" : "RendererGrid2Sparse",
    "Fx" : "GridSparseHighlight",
    "TextureSamplers" : { "g_TileMap" : "nearest_clamp" },
    "ShaderVars" : ["GlobalPerFrame", "GlobalFlashing","GlobalOverworld"],
    "DepthTest" : true
}},
....
// A renderable. They can use local shadervar blocks
{ "griddense" : { 
    "@factory" : "RenderableTileGrid2Widget",
    "Renderer" : "OverworldDense",
    "ShaderVars" : {
        "@factory" : "ShaderVarsSeparate",
        "ShaderVars" : [
            {"Name" : "g_Color", "@factory" : "ShaderVarColor", "Values" : [[255,255,255,255]]}
        ]
    }
}},

Note: The reason I’m using an additional ShaderVars abstraction is because in the future I want to consider having uniform buffer objects for many shader variable blocks, as it’s more optimal. But of course, this will only happen when the slowdowns begin, which is not now.

So, that’s it for this time. I’m also currently toying with introducing framebuffer objects in the system (so that renderers and renderables can be configured via script to render to an offscreen surface) so that we can have more flexible render paths. And also what’s coming is an autotiling implementation, using all these.

Automatic pixel art from photos

Disclaimer: Properly authored pixel art is awesome. Automated pixel art is fast food: great when you don’t have enough money (to hire) or time (to author). And does the trick when you’re starving.

I’m not an artist, I love pixel art, and frequently I want something here and now. So, how do I get copious amounts of pixel art without bugging a pixel artist or becoming one myself? Software of course. The style that I’m after is retro 90’s look: slightly pixelated and with a limited, painterly color palette. A few examples:

Old game art, fantastic colours, painterly look:

Pixel art, great mood and selection of colours

 

Great tile design (sprites are sometimes too “cute” for me unfortunately) and great colours. I bought them as I love them! 🙂

So, while I don’t hope to automatically generate stuff of quality like the above from photos, I made a tool to convert landscape photos to pixel-art style.  There are two components to the process:

  • Palettization (Mapping full colour range to a limited palette)
  • Pixelation (Downscaling the image to look a bit retro)

My approach is quite simple, and is as follows:

  • Load the source image
  • Select a color difference function (I used code from here)
  • Convert image pixels to color space used by the difference function
  • Select a palette. I got some from here. Additionally, I got all the unique colors in Oryx tileset and made a palette out of them too (the largest palette: about 1000 colors)
  • Convert palette pixels to color space used by the difference function
  • For each pixel, select the palette entry that minimizes the color difference between itself and the source pixel.
  • Downscale the image by a factor. For each block of pixels NxN that corresponds to 1×1 pixel in the downscaled image, fetch the palette color that appears the most times.

And that’s it! So, I tried the above on a few images (found in google, none of them is mine), and I got … very mixed results. Below I’ll show the original image and a few good/bad/quirky results.

Mountain/River

Cie94 w/ Oryx, downscaled 2x. Good

Cie2000 w/ famicube, downscaled 2x. Not good

Cie94, GraphicArts w/ psygnosia, downscaled 2x. Lo-spec but good!

Atlantis

Cie94 GraphicArts w/ Oryx, downscaled 2x, good

Cie94 GraphicArts w/ famicube, downscaled 2x, good. Sharks are a bit of a problem as the sea water bleeds in

Cie1976 w/ Endesga-16, downscaled 2x, bad.

Euclidean distance w/ Oryx, downscaled 2x, bad

River

Cie2000 w/ oryx, downscaled just 1x, it’s way too realistic.

Cie94 GraphicArts w/ Oryx, downscaled 3x, a bit better, but still a bit realistic

Cie2000 GraphicArts w/ Endesga-32, downscaled 3x. Not as realistic, but a bit worse quality.

Castle

Cie1976 w/ oryx, downscaled 1x. A bit too realistic

Cie1976 w/ famicube, downscaled 1x. A bit too damaged and noisy.

Mexico

Cie2000 w/ oryx, downscaled 1x. A bit too realistic. Additional downscale would destroy the geometrical details.

Cie2000 w/ famicube, not good.

Cie94 Textiles w/ psygnosia, quite bad.

Underwater ruins

Cie2000 w/ oryx, downscaled 2x. This looks great! Good for a change.

Cie2000 w/ famicube, not so great.

Cie2000 w/ psygnosia, not great either. the water is gray and the shark is bluish. Well … no.

Sahara

Cie2000 w/ oryx, doable

Cie2000 w/ endesga, quite bad, but at least is good in making the JPG artifacts very very visible.

Cie2000 w/ psygnosia, not that bad actually! Even if quite lo-spec.

Yucatan

Cie94 Textiles, w/ aap64, downscaled 3x. A bit too damaged, but I like it

Cie2000 w/ oryx, downscaled 3x. It’s good, but a bit too realistic

 

So, the experiment was a failure, but I learned a few things from it:

  • Most important: The visual appeal of the results greatly depends on the colours used in the original. A grayish brown image won’t magically transform to colourful, just because the target palette is. And a simple color distance doesn’t solve the issue. We need a more sophisticated color transfer
  • Distinguish between surface texture and geometric silhouettes: surface texture colours need to be somewhat flattened, while silhouettes need to be preserved
    • could use a bilateral filter, and edge detection
  • Consider dithering. Can reduce color error, but do we want that? It certainly helps with the blotches/banding.
  • When using a palette with lots of colours, doesn’t mean we should strive to use all of them. The color distance metric tries to preserve the original colours, which would be realistic. We don’t want that.
  • Pick the brains of pixel artists for their approach (Duh)
  • Use high quality images, with minimal JPG compression artifacts. (Duh, but I was too lazy for this one)
  • Use Photoshop/GIMP/etc. The more sophisticated the algorithm gets, the more tedious it is to write/update a custom tool to do that.

Front-end: Camera

We currently have overworld maps that can be visualized with a color per pixel, depending on the pixel’s biome data.
In the actual game, each of these pixels will be a tile, on which we’ll map textures, and we can also even put geometry. There are many ways to view such maps, for example various configurations of perspective and orthographic projections.

So far I’ve been using a top-down view for the ease of implementation. As I wanted to experiment with several visualizations, I changed the implementation to support a fully configurable camera, as well as tile highlighting and edge scrolling as before. Here are some examples of an overworld map, visualized with a few cameras (orthographic top-down and 3 perspective cameras, zoomed in and out) :

The art that I’m going to use will possibly be just 2d sprites. The beauty of 2d sprites is that they can be used both in 2D and 3D views, in the latter, as billboards. The challenge is to make them look good when integrated in a 3D environment. Here are some examples of a basic, naive integration of some DCSS tiles in the map:

So, these are the tiles rendered to the top-down view – nothing special so far. Below, we try the billboard rendering, before and after, using a side-camera:

When using such cameras, it’s clear that sprites look much better as billboards rather than flat mapped onto the terrain. Some more billboard examples using more cameras (1 isometric and 3 perspective):

(Note: Any sprite overlaps are due to my laziness; the positions for the billboards are generated randomly and therefore sometimes overlap)

I think it’s safe to assume that it works well, but they don’t integrate perfectly. I’m not an artist, so I need to get some informed opinions on how to improve the visual result by just processing the sprites and data that I have (e.g. using specific, shared color palette for both overworld and sprites, process sprite boundary, add some fake environment lighting, etc). Also, DCSS sprites occasionally have integrated shadows, which funnily enough works for many of the views, but it’s baked in the sprite, so not really controllable.

Here is a video of a perspective/ortho cameras using billboard version, to showcase the 3D look.

While the 3D effect works, the visuals can be massively improved. For example:

  • Actual textures for the overworld, including rivers and sea (tileset hunting plus procedural should do it for now)
  • Vegetation and mountain sprites on the tiles (I need tilesets for that)
  • better sprite integration with the map (shadows? silhouettes? env lighting?)
  • Optionally, a basic elevation visualization, with lighting (mutually exclusive with mountain sprites, but this is easy to do)

Of course I’ll need an artist for sprites and textures, so at the moment I have to make do with my mad (bad?) pcg skills. And for even later, there’s also animated fog of war, particle systems and other bells and whistles, because graphics programming is fun 🙂

Generating overworld resources

Cities and civilizations need resources to survive and thrive. Our case is no different. So, before placing any cities, we need to generate the resources that the world uses. I’ve decided to split the resources into 3 groups: food, basic materials and rare materials: the first two are found in varying quantities pretty much everywhere. Civilizations can immediately use such resources. Rare materials, on the other hand, are not easily found, they need to be discovered first, and they also need to be mined. On the plus side, there will be enough incentive to explore, discover and mine such materials (wealth, influence, advanced structures and items, etc).

Tile resources

From a macro point of view, each tile of the overworld has a the following resource information:

  • Food: Used to feed population. Obtained from sources such as vegatation and wildlife. Value: [0,255]
  • Basic materials: Used for buildings and construction of everyday items. Obtained from environment. Encompasses materials such as stone/leather/wood/iron. Value in [0,255]
  • Rare materials: Special, difficult to find/mine materials, used for magic and/or construction of advanced buildings/items. Examples include silver, gold, mithril, crystal, gems, etc.  A value of [0,1] per rare material type.

So, each tile resource can be represented with a 32-bit value: 8 bits for food, 8 bits for basic materials and 16 bits for rare materials (for a maximum of 16 rare materials). Several rare materials can co-exist at the same tile.

Rare material traits

A rare material, with regards to generation of a map that contains them, has the following main traits:

  • BiomeSuitableRange: This is a collection of ranges per biome parameter, e.g. temperature, humidity, elevation, water type, etc. So, for example, some materials can be spawned only in high altitude areas of extreme cold, etc.
  • Chance: This is the chance of a rare material spawning at a suitable tile. So, the effective spawning chance is chance multiplied by the probability of a tile being suitable.

Tile resources map generation

In order to generate this “tile resources” map, we need to have calculated the biome map first.

The first step in the process is to calculate all the candidate tiles per rare resource type. At this stage, we also calculate the food and materials per tile, as a function of the biome. I’m currently using an extremely naive mapping of wildlife density to food and vegetation to materials, but that should change later on.

We then shuffle the candidate list and pick the N first points, where N = max(chance * totalCandidateNum, min(1,totalCandidateNum)). So, if we have no candidates, we won’t generate any. If we have at least 1 candidate, we should generate at least one point. And that’s it, really! Pretty simple, but does the job. Here’s an example of a rare material’s distribution; there only tens of them in the whole map, so it could be a quite coveted material to be able to mine and get access to.

Overworld map generation

My goal is to generate an overworld map, where each tile would cover an area of about a hundred square km (On normal terrain, a regular unit would need a day to cross a regular tile). The overworld needs to contain islands, continents and biomes. The output of this process is a 2D “image”, with data per pixel (32 bits, like an RGBA PNG file) that completely describe how is the environment of a tile like. I’m going for plausible rather than realistic: I want to be able to create maps that are fun to play. Below, I’m going to go through the various steps of the process that I use.  All but the landmass labeling and river generation passes are generated using the GPU, as the calculations are typically parallel. The whole process takes about 60 milliseconds for 512×512 maps, so we can tinker all sorts of parameters and see the results in real-time.

Continent mask

The first step is the creation of the seed continents. These are not necessarily the final continents, but they help construct the base for the big landmasses. The continents start off as a small set of scaled and rotated ellipses. Everything about these ellipses is randomized: number, scale, rotation, eccentricity.

The next step is to distort the boundary of the ellipse using perlin noise. Effectively, we’re warping the point we’re on before testing whether it’s inside or outside one of the ellipses. There are two parameters for this: warp frequency (how much can the warp differ between 2 adjacent pixels) and warp magnitude (how far the warped point can get from the original). Some examples of increasing frequency:





For the rest of the post, let’s choose the one before last. At the end of this stage, we have a map that stores if we’re inside or outside big continent-like landmasses

Continent mask distance field

This step calculates a limited distance field around the coastline of the continents: this will be useful for the actual heightmap generation. We calculate distances from the coastline (d = 0) up to a number of pixels away from it (e.g. d = 32) and we map the values 0-1 to this clamped distance range.

Heightmap

This step calculates an 8-bit heightmap with values [-1,1], positive numbers representing land. We don’t care about it looking too realistic, as the heightmap will only be used implicitly, as an input to other parts of the generator.

Landmass mask

This step creates the final landmasses. We’re just using the heightmap to generate this, comparing the height values against 0.

Landmass distance field

This step does the exact same process as the continent mask distance field, but on the landmass mask.

Landmass labeling

This step does a floodfill over the heightmap, detects landmasses, classifies them in terms of size (rocks, islets, islands and continents) given user-defined area thresholds. There can be a maximum of 63 continents given the current bit budget, but of course that’s flexible. The continents are also uniquely labeled at this step (this means that all the tiles that belong in continent 2, store the value 2 somewhere — see below, Biome data section). Additionally, bodies of water that are completely enclosed by landmasses are marked as part of the landmass, so that they can correctly be identified as lakes later on.

Rivers

This step generates the rivers in the overworld. Effectively, give some parameters such as minimum river proximity to each other and river min/max length, we generate rivers. The way this is done is by sampling random points on the map and testing if they can be appropriate starting locations (e.g. on or by a mountain). If a point satisfies the conditions, then a path is attempted to be generated, with branching; the path follows a downward path in terms of heights till it reaches a lake, the sea, reaches maximum length, or can’t go further due to any reason. Below two examples with different density:

Humidity

This step generates the humidity for each tile. It takes into account outline, heights and freshwater. The basic map is calculated with perlin noise, but it is also adjusted based on if a tile is water or land: areas in and near water are more humid. It is also affected by the the freshwater mask, which gets heavily blurred and added as extra humidity; this guarantees that there almost never are rivers in the desert, or swamps without a body of water nearby.

Temperature

This step generates the temperature for each tile. It takes into account outline, heights and freshwater as well. The basic map is calculated with perlin noise, but it is also adjusted based on if a tile is water or land: when on land, we sample from a heavily blurred heightmap and reduce the temperature based on that regional average height. This reduces temperatures in regions where there are a lot of high mountains. Additionally, the regional existence of water reduces temperatures a bit.

Biome data

At this point, we’re almost done! This step samples all maps and packs them into a 32-bit output map. These 32 bits encode the biome detail in a coarse way.

Here’s the breakdown:

  • Temperature: 3 bits
  • Humidity: 3 bits
  • Elevation: 2 bits //  Height or depth, dep. on water type
  • Water type:  2 bits // none, river, lake, sea
  • IsCoast: 1 bit
  • Vegetation density: 3 bits
  • Wildlife density: 3 bits
  • Continent ID: 6 bits
  • Landmass size: 2 bits
  • Biome type: 4 bits // one of the 16 predefined biomes
  • Padding: 3 bits

For many of the above (temperature, humidity, elevation), we quantize the (typically 8-bit) data that we already have to the bits above. The biome type is calculated from the rest of the values (temperature, humidity, etc), and is one of the following:

Sea Coast, Shallow Water, Sea, Deep Sea, Abyssal Sea, Tundra, Alpine, Desert, Boreal Forest, Temperate Rainforest, Tropical Rainforest, Temperate Deciduous Forest, Tropical Seasonal Forest, Temperate Grassland, Savannah, Wetland

Some of the values are calculated in this step:

  • WaterType: Calculate based on if it’s a river tile, landmass ID and height.
  • IsCoast: Calculate based on if we’re on land, and sample all neighbours for any sea tile
  • Vegetation density: More perlin noise, adjusted by humidity, temperature and height
  • Wildlife density: More perlin noise, adjusted by humidity, temperature, height, freshwater and vegetation

Here’s a visualization of the vegetation density:

… and the wildlife density:

Depending on the biome type we can distribute flora, fauna, resources, civilisations, etc.

Here’s a video of the GUI tool in action!

Other examples here:

Closing notes

The format might get adjusted in the future, in order to use those padding bits to encode some extra information, for example freshwater direction in river tiles (2 bits). There is also a dynamic magic map which specifies, in areas of high magic, special happenings such as rifts, summons, portals, etc. Additionally, there’s tile resource generation which will be covered next time.

More messaging and shader parameterisation

Last time I gave a brief description about how messaging (and my dirt simple implementation) can help with decoupling. But of course that was just scratching the surface. So, in this post, a bit more information on how the whole system is put together

Messaging changes

The messages now can also store an explicit message handler. In terms of the example I used last time, the new message would be as follows:

class cEntity;

struct cEntityCreated : public cMessage
{
    explicit cEntityCreated( const cEntity& zEntity, const cMessageHandler * handler = nullptr)
    :cMessage(msType,handler),mEntity(zEntity){}

    const cEntity& mEntity;

    static const int msType = 2;
};

So, a slight change allows cases where we’d like to target a message to a particular handler. This would be useful in the cases where we want to directly affect something from another part in the code that we don’t want coupling with, but we don’t want to introduce abstraction layers. Example:

My test rendering app needs to modify a renderable directly, by setting a bunch of tiles. One option is to introduce a new message, TilesChangedInRenderable( tiles, renderable), but then we have a TilesChanged(tiles) message AND a TilesChangedInRenderable(tiles, Renderable). To avoid doing the same thing with classes other than Renderables, and since the Renderable is a MessageHandler anyway, I decided to make the above adjustment where we can always optionally provide an explicit handler; if one is provided, the message is only handled by message propagators (e.g. a System) and the handler in question, otherwise it is handled by everybody who is registered to listen to those types of messages.

Shader parameters

Disclaimer: Rendering is always in flux – I’m trying to get something generic, extensible and easily editable working together, and it’s no easy feat.

Summary of rendering so far:

  • The currently running application state renders its root widget
  • Each widget contains body and margin renderables (2 different)
  • Each widget can contain a modal widget, or if it’s a container widget, other widgets
  • Some widgets add more renderables: e.g. textbox also has a text renderable
  • Renderables are pretty much rendering configurations, and store a reference to a renderer and to their widget owner
  • Renderers use shaders and contain rendering logic
  • A renderer renders a single renderable type, a renderable can be rendered by several renderer types

Before, the configuration was via explicit parameters in an inheritance chain. While it’s explicit, it’s a PAIN to add parameters, as it’s compile-time. So I ditched that approach, and used a far more generic approach. Now every renderable stores, among other things:

  • A list of references to textures
  • A list of dynamic textures, along with a message updater for each
  • A list of texture buffers, along with a message updater for each
  • A reference to a blending configuration
  • A list of shader variables, organized as:
    • a vector of (name, value) pairs, for every common shader type (int, float, int2, float4, etc)
    • a vector of (name, texture_buffer_index)
    • a vector of (name, texture_index)
    • a vector of (name, dynamic_texture_index)

So far, this is looking flexible and I like it. Of course it’s far from optimal, but it is optimal for prototyping, and that’s what matters now. For performance, variables could be organized in uniform buffer objects of varying frequency of updates, etc, but that’s far down the line.

Above there’s a screen from the modification of the A* visualizer to operate on graphs — just minimal changes needed from existing infrastructure:

  • There is a new renderer instance of the type GridSparseSelectionRenderer — it’s used for rendering lines.
  • There are a few renderables: for the node points, for the start point, for the goal points (of course horribly inefficient, I might as well draw all points at once and assign per-instance colors, but that’s not the point here), for the edges and for the edges that are part of the output path.
{ "gs_nodes" : { 
    "@factory" : "RenderableTileGridWidgetSelection",
    "Renderer" : "GridSparse",
    "TextureBuffers" : [
        {
            "first" : {"format" : "rg16i", "usage" : "DynamicDraw", "Flyweight" : false, "max_elements": 2000}, // let memory be initialized at first update
            "second" : "TileSelectionChangedToTextureBuffer"
        }
    ],
    "ShaderParams" : {
        "g_Color" : {"type" : "color", "value" : [0,0,255,100]},
        "g_Tiles" : {"type" : "texture_buffer", "value" : 0}
    }
}},
{ "gs_edges" : { 
    "@factory" : "RenderableTileGridWidgetSelection",
    "Renderer" : "GridSparseLine",
    "TextureBuffers" : [
        {
            "first" : {"format" : "rg16i", "usage" : "DynamicDraw", "element_size" : 2, "Flyweight" : false, "max_elements": 2000}, 
            "second" : "TileSelectionChangedToTextureBuffer"
        }
    ],
    "ShaderParams" : {
        "g_Color" : {"type" : "color", "value" : [128,128,128,255]},
        "g_LineThickness" : {"type" : "float", "value" : 1.0},
        "g_LinePoints" : {"type" : "texture_buffer", "value" : 0}
    }
}},
{ "gs_edges_path" : { 
    "@factory" : "RenderableTileGridWidgetSelection",
    "Renderer" : "GridSparseLine",
    "TextureBuffers" : [
        {
            "first" : {"format" : "rg16i", "usage" : "DynamicDraw", "element_size" : 2, "Flyweight" : false, "max_elements": 2000}, 
            "second" : "TileSelectionChangedToTextureBuffer"
        }
    ],
    "ShaderParams" : {
        "g_Color" : {"type" : "color", "value" : [128,255,128,255]},
        "g_LineThickness" : {"type" : "float", "value" : 2.0},
        "g_LinePoints" : {"type" : "texture_buffer", "value" : 0}
    }
}},
{ "gs_start" : { 
    "@inherit" : "gs_flashing",
    "ShaderParams" : {
        "g_Color" : {"type" : "color", "value" : [255,0,0,255]}
    }
}},
{ "gs_goals" : { 
    "@inherit" : "gs_flashing",
    "ShaderParams" : {
        "g_Color" : {"type" : "color", "value" : [0,255,0,255]}
    }
}},

Messaging

Prelude: the reason for the existence of this post, while I should be testing A* solving on graphs and rendering, is because of the coupling between rendering and logic. In the logic, I had to manually,explicitly set the data that the renderable  – an object that has a description of a render configuration, e.g. textures, buffers, parameters – would use. I disliked that part, so I wanted proper decoupling, via messages/events.

In the original version of the engine, I was using entityx that provided an Entity-Component-system implementation, along with some event handling. I ended up changing the whole thing as it was not suitable anymore, except the event handling. Alas, the event handling needs to go now too, as it unfortunately was implemented too rigidly for my taste: example follows.

  • System (being an event receiver) subscribes to an event type (e.g. CollisionEvent)
  • System implements a void receive( CollisionEvent ) that is mapped as the receiver function
  • Entities can emit an event, system can handle it directly

Now that looks fine, but then I got into scenarios as follows. The game logic says “Hey, I finished with some pathfinding result, in case anybody’s interested”. Event sent. Now we should have receivers that could handle that. For example, our rendering system could listen to that event. The rendering system then needs to know which renderables would be interested for this event and could update some render data with it. That’s the point where I realized I’d have to make serious changes to the event handling code to manage this sort of freedom adequately. So, as the library wasn’t that big, I stopped using it, and I introduced my own solution, which is supposed to be lightweight, and custom to my needs.

Messages

Messages are simple structs of strictly reference variables, generated from a python script. For example:

"EntityCreated" : [
    ('cEntity', 'Entity', 'class')
],

generates the following:

class cEntity;

struct cEntityCreated : public cMessage
{
    explicit cEntityCreated( const cEntity& zEntity)
    :cMessage(msType),mEntity(zEntity){}

    const cEntity& mEntity;

    static const int msType = 2;
};

All messages derive from a base “cMessage” class.

There’s some global function to emit messages, that passes the messages to all systems, and each system stores a list of message handlers per message type – so, every time a system needs to post a message, it grabs the appropriate list of message handlers, and sends the message to every one of them. So, the message handlers need to be able to handle a generic message.

Example: a renderable stores, among other things, a list of texture buffers and dynamic textures, which could optionally be used for updating gpu data useful for rendering. Example: we have a path that we want to render, represented as a set of integer points (x,y), stored in a texture buffer. Another example: we want to visualize the results of a grid search, by putting the gscore values in a dynamic texture.

But we don’t want to hard-code anything, so we specify the format in the configuration file. What I’m looking forward to would look like in json:

"texture_buffers" : [
    { 
        "config" : {
            "format" : "rg16i",
            "memory" : 8192,
            "usage" : "DynamicDraw"
        },
        "updater" : { "@inherit" : "MessageUpdaterSearchGridPathToTbo" } 
    }
]

In the above partial definition of a renderable, we say that it will have a single texture buffer, with the specified format, a maximum memory of 8Kbytes and it will update its contents automatically using “MessageUpdaterSearchGridPathToTbo”. So, what’s the latter? It’s a very simple polymorphic interface, that defines a function:

template<class Source, class Target>
class cTransformer
{
    virtual void Transform(Target& obj, const Source& msg) const = 0;
}

Using the type family machinery for easily specifying factories in JSON, we can define classes as follows:

//! SearchGridPath:Path to Tbo
class cMessageUpdaterSearchGridPathToTbo : public cTransformer<msg::cSearchGridResult, gfx::cTextureBuffer>
{
public:
    void Transform(gfx::cTextureBuffer& obj, const msg::cSearchGridResult& msg) const override;
};

//! SearchGridPath:Visited to Tbo
class cMessageUpdaterSearchGridVisited : public cTransformer<msg::cSearchGridResult, gfx::cTextureBuffer>
{
public:
    void Transform(gfx::cTextureBuffer& obj, const msg::cSearchGridResult& msg) const override;
};

So, what do we achieve in the end? Proper decoupling! The C++ code does not specify what will be rendered – it will just send messages “my grid search was completed” or “my graph search was completed”. The C++ code won’t specify in the game code how something will react to a message – this will be done by interfaces, which are assigned based on json. In json, renderables specify who’s listening to what, and what actions will be taken upon receipt of the messages. So, json acts like a bunch of cables, and the game logic, the rendering, and the updater specification are all independent black boxes, not knowing of each other. I expect to have this working by next week hopefully, even though things are looking quite busy.

Pathfinding and visualization

 

The core libraries are now done (or so I thought), so I’m slowly refactoring the game libraries, one component at a time. But because nothing escapes my refactoring extravaganza, I discovered another victim in the core libraries, ready to be refactored mercilessly: the grid/graph pathfinding. So, my original idea is to make the pathfinders objects that keep some state and run one iteration at a time, as I envisioned that I might interrupt an A* calculation halfway through. Well, thinking about it, that’s nonsense, so … refactor away.

Now the pathfinding routine is just a function with 3 arguments:

  • A config struct which, as the name implies, provides configuration/setup for the search execution: start point, goals, heuristics, search space etc.
  • A state struct which maintains the algorithm state: fscore/gscore maps, the priority queue, etc.
  • An output struct which stores the output from the search, such as the path, path costs (optional), visited nodes (optional), etc.

To aid debugging, I’ve added a conditionally compiled part that records state and output at every search iteration. After this semantic separation in these structures, recording the state is now a breeze! I just keep a vector of states/outputs per iteration to see their “history” and how they evolve.

So, with the nicely modularized grid pathfinder function and the newly refactored rendering system, we can implement an application that visualizes pathfinding (inspired by Amit’s super awesome A* page, among others). I’ve made an application that uses ImGui and my widgets (the tilegrid one to be precise), so that I can dynamically modify weights on the map, as well as start and goals, heuristics, 4 or 8 connectivity, etc. Additionally, several visualization options are provided as overlays: visited cells, gscore, fscore, the calculated path, start/end points, etc, all as layers: gscore, fscore and weights exist for all cells, so they are rendered using a dense tile renderer, while start, goals, visited cells are rendered using a sparse tile renderer. The tilegrid widget uses a group renderer, tha renders all the layers specified. Way too much text and way too little action, here’s a video capture of the visualizer:

 

Next thing to do is make sure the graph pathfinder works well, and then continue the refactoring quest, which is totally worth it.

Widget-based rendering back end

(Using Dear ImGui to dynamically configure my own widget framework)

 

During the last few months, I’ve also redone how rendering should work. The crux is still the same though: rendering is widget-based. It’s all OpenGL 3.3, as that’s all that my decrepit laptop can handle.

An application state controls a root widget. The root widget is the root of a hierarchy of containers, buttons, text boxes, list boxes and tile grids. Each widget stores “renderables”: the description of how to render themselves. Typically, one for widget body, one for widget margin, and one for the text layer. So, when an application state needs to be rendered, it asks from the root widget to be rendered, and the rest happens organically.

Renderers and Renderables in the framework

A renderable is a description of how something should be rendered. Like a “material” in UE/Unity. It stores a reference to a renderer that knows how to render it. Widget renderables have access to the widget for vital parameters, and also know where they should be rendered. For example, tilegrid and tilegrid selection renderables both use the tilegrid widget to access the size of the grid displayed, the pixels per cell, etc.

A renderer is the object that contains the logic for rendering a single type of renderable. A renderable type can be rendered from many renderers, while a renderer type can process a single renderable type. For example, a basic renderable can have information about a texture and a colour, and we could have several renderers that can generate an image using different shaders and parameters.

There is also a group renderable with the associated group renderer: A group renderable contains a map< layer , renderable> and the associated renderer processes the layers in order. This allows adding multiple passes, for example for post processing effects or multiple render layers for the tilegrid.

Now what?

Well, what I’m doing with the above is effectively preparing a rendering framework so I can easily write tile grid based shaders at will, to try all sorts of different effects and visualizations 🙂 But there’s still framework work to be done (obviously)