Level Generator Part 2: Island

This is the second part in a series going over how we generate levels for our game. The previous post¬†went over the generation of the high-level layout structure. In this post, we’ll take a step towards being able to generate some triangles for the terrain, and we’ll generate some useful information for water rendering and object placement.

The island generation stage creates a number of world-maps which will be used further down the pipeline for various tasks. A world-map is simply a floating point image, projected onto the world from above. Along with the map data, it holds its world-space origin and texel/meter ratio. This extra information allows us to easily convert between world-space and image-space.

Terrain height world-map

The island generation stage is partly inspired by the work done for Horizon: Zero Dawn for their real-time GPU object placement system. In our case, we don’t need to generate this data on the fly, so our implementation is all CPU-based since it’s a bit more flexible, and easier to implement and debug.

As mentioned previously, we don’t use the world-maps for just object placement, but we also use them for terrain generation, water placement, navmesh generation and transforming the layout graph information into something that’s less ‘graphy’. A typical level will generate around twelve or so world-maps at various resolutions. Some of these are cached inside the island for efficiency (since they’re sampled in a few places), while others may just be used once, so we just generate the pixel samples when they’re needed.

There are two world-maps that are always created during the island generation step. The first is the layout mask which details which areas of the world should remain relatively open to allow space for combat to occur. The second is an obstacle mask which will hold coarse collision information.

Layout Mask

We could just rasterize the high-level layout graph directly into the layout mask, but this would leave us with perfectly circular gameplay areas with straight-line paths between them – not so interesting. Instead, we’ll use a couple of 2D procedural generation methods – random fills and random walks.

Layout mask
Nodes

For the nodes, we’ll perform a random fill of the layout mask, starting at each node center. We maintain a list of active cells (a world-map texel), which is initialized at first with the cell that contains the node center. From there, we’ll repeatedly pick a random ‘seed’ cell from the active list, then try to fill in one of its neighbors. If we fail to find a neighboring cell to fill too many times then the seed cell will be removed from the active list. Once we find a cell to fill, we’ll set that layout mask value to one and add the new cell to the active list.

The termination condition for the random is fill is simply when the area of cells filled for each node exceeds the area of the circle chosen during the layout stage. Performing a random fill like this ensures that we keep the areas roughly the correct size for gameplay purposes, while adding some irregularity to the shape.

Edges

For the layout edges, we’ll do something similar. This time we’ll start at the center of the first node, and we’ll do a semi-random walk to get to the second node.

The semi-random walk is essentially a modified path-finding algorithm. First we look at the Manhattan distance from the cell containing the source node to the cell containing the destination node. This is our minimum path length. We’re then going to multiply this by a factor (say, 1.75) to choose how many steps we’d like to have in the path.

The path-finding works similarly to normal A* path-finding through a grid, except we’re not trying to choose the grid cell that will get to the goal the quickest, instead we’re trying to stay as close as possible to the ideal path-length.

We always use the most recently added cell as the chosen cell for the current loop. We then look at how many steps it took to get to that cell and add the inflated (by the same factor as before) Manhattan distance from each of the neighboring cells to the goal as the estimate of the total number of steps required to reach the goal along that path. The final cost for each of the neighboring cells is based on how close that number of steps is to the ideal number of steps at that iteration.

This method allows the path to temporarily move away from the goal, but it will always end up deviating back towards the goal cell as each iteration goes by. This is a step of the level generator I’d like to spend more time on to really fine-tune, but it generally works. It produces non-straight paths, though sometimes the paths end up being forced into being straight towards the end due to being too far below the ideal path length.

When filling a path cell, we actually use a ‘stamp’ pattern comprising of a 5 x 5 cell pattern. This means that the paths always have a decent width to them. Again, I would like to work on this part more at some point.

Obstacle Mask

The island also allocates an empty obstacle mask at creation time. This mask is used to store very coarse-level collision information for obstacles. During the later obstacle placement stage, the convex hull of the 2D projection of the collision shape for each collidable object is rasterized into the object mask.

Obstacle mask

Level-Specific World-Maps

Each level can generate an arbitrary number of world-maps and use them for object placement and terrain generation. A world-map is generated using a graph of simple image filters defined in script. This is a very flexible system that is easy to modify

const height_terrain: Filter =
{
    name = "height_terrain"
    description = "height_terrain"
    root = Max 
    { 
        a = Constant { value = -3 }, 
        b = Subtract
        {
            a = Add
            {
                a = Max
                {
                    a = SampleNoise { octaves = 6, frequency = 0.01, amplitude = 3.0, bias = 0 }    // Low frequency hills
                    b = Constant { value = -0.3 }   // Allow shallow areas of water
                }
                b = SampleNoise { octaves = 2, frequency = 0.5, amplitude = 0.2, bias = 0 } // High frequency detail
            }
            b = Max
            {
                a = Multiply
                {
                    a = SampleNoise { octaves = 6, frequency = 0.01, amplitude = 25, bias = -5 }    // Low probability dips can produce lakes
                    b = Threshold { threshold = 15, smooth = 15, source = topo_layout } // But not on or near layout areas
                }
                b = Constant { value = 0 }
            }
        }
    }
}

It’s advantageous to implement some kind of image-filter visualizer or debugger when using a system like this. It’s often not clear when something isn’t as you expect, why it is so. It’s especially useful to be able to view the results of sub-branches.

Image filter debugger

For any world-map that is cached inside the island (and therefore fully rasterized), the game supports running a post-process on the resulting image to convert it into a distance field. This is done using the O(n) algorithm described here. I believe that the algorithm described in that post is Fast Raster Scan Distance Propagation on the Discrete Rectangular Lattice, F. Leymarie and M. D. Levine.

Obstacle distance field

Distance fields are used by our game to place objects, alter terrain, as a navmesh, for water properties, and more! They’re very useful and pretty quick to generate. Most of the time we don’t need the signed distances, so we usually just generate one side of the distance field.

Example Level

Here’s a quick overview of some of the world-maps we cache in the island stage for our forest level.

Distance to Layout

Distance field that gives the distance from the current cell to any cell that is part of the layout mask.

Terrain Heights

Generate the heights for the terrain using a combination of noise, but ensures that the areas on and around the layout are above water and relatively flat.

Obstacle Distance Field

This one is a bit special since it will get regenerated after each object placement pass. It’s the distance to the nearest point inside the obstacle mask. This is mainly used to prevent large objects from overlapping each other.

Distance To Water

This reads the terrain heights and fills in all values below zero, then generates the distance field. It’s used later for object placement and navmesh generation.

Foliage Placement Weight

Uses noise to generate vary density foliage areas, but uses the layout and water distance fields to prevent foliage from being placed on or very near to those areas.

Rock Placement Weight

Similar to the foliage placement weight, but allows placement in water and is more clumped up but sparse.

Trap Placement Weight

Dictates areas where mines or other traps could be placed.

Summary

The island is used to cache world-space information that later stages will use to to generate the terrain, place objects and more.

The next post will go into how we use the terrain information to generate collision and render meshes.

 

Level Generator Part 1: Layout

This is the first of what will be a number of posts that go into how we generate the levels for our game.

A typical level in the game is somewhere in the region of 400 x 400 meters at the moment. Each level takes about two seconds to generate (all on the CPU), and the generator places somewhere in the region of 50,000 meshes to fully populate the world.

Fully populated Swamp level

Keep reading

Quick Peek: Ambient Occlusion

We use vertex coloring for all our meshes, and this presents a bit of a problem when rendering ambient occlusion since it’s very easy to see the interpolation artifacts.¬†Another issue which adds a kink to dealing with AO is that we use a faceted ‘low-poly’ look. We generate the face normals on at run-time so that we can have just one vertex in each position (rather than one per face). Generating face normals in the geometry shader saves us both space and time since the transform cache gets better utilized.

No ambient occlusion

If we just have one vertex at each position, then it’s not obvious in which direction the AO normal should point to get smooth occlusion. Most modeling packages will split the normals and AO based on a certain smoothing or ‘hard edge’ value. Even if forcing all edges to be smooth, it requires some hand tweaking to get the AO to look ok. Maya LT in particular is a nightmare to get nice looking AO with. Keep reading

Hello world!

Welcome the development blog for our upcoming game! We’ll be posting snippets detailing some of the tech, design and art decisions that went into the making of the game.

We’ll keep each post short and keep ’em coming! There’s so much that goes into making a game that we can’t cover everything, but we’ll try to cover the interesting parts.

Here’s what the game looked like just over a year ago.

Today, although it’s far from complete, it looks quite a bit different. Want to find out how we got here? Then stay in touch! Follow us on Twitter for updates and the grand unveiling of the name of our first title.