Generating the maps of Trollskog
Generating terrain for a strategy game is a fascinating topic to me, because it challenges the developer to describe the ideal map in mathematical terms. The ideal map naturally depends on the mechanics and design of the game, which should be done before we can ask the question: what properties are we looking for in a good map?
Randomness doesn't get us very far by itself, but it can be a great starting point if we add certain constraints and parameters, such as:
- The player always starts near a river
- The area immediately adjacent to the player’s start location is free of enemies.
Not too complicated, yet. These requirements could be met with some simple math and distance checks.
But what if we want to spawn quest providers - entities in the game world that issue quests to the player - and place them in such a way that the player should encounter the quest provider before finding the quest objective?
For example, a troll tribe might recruit the player’s help in finding a magical artifact somewhere in the forest: This quest would suffer if the world is generated in such a way that the player stumbles upon the artifact before finding the troll tribe, or worse; if the artifact spawns in some inaccessible location that can’t be reached from the quest provider’s location.
It becomes clear that we need a smarter way to plan the world and the placement of things within it.
The new terrain engine in Trollskog generates 64 by 64 tiles of terrain at a time (lovingly referred to as a chunk), by performing these steps:
Start with the rivers...
... because these are tricky to generate using noise functions. Instead, we start off with spline interpolation using two edge points with the lowest elevation as control points.
The image shows the chunk we’ve started generating. Since this is the first chunk and has no neighbors to worry about, we can freely place the river anywhere. Future chunks will be more limited in their river placement options.
Within the chunk, all subsequently generated entities must interact with the river: Villages should be placed near rivers, and bridges should be placed in logical locations. Therefore, rivers are placed early on in the generation process.
Generate the encounter graph
It’s time to place the player’s starting units. We observe a few simple rules when choosing a suitable location: The image above is shaded accordingly - the image is darker further away from rivers and edges. Picking the best spot for a town is as simple as selecting the darkest pixel in the image above. The same placement rules apply, except now we also wish to avoid already placed nodes.
When we reach the edge of this chunk, store the state of the edge nodes, we will be needing them when we generate this neighbor.
Ensure connectivity
First, create a voronoi diagram by iteratively growing each point that we have placed so far.
This helps us plan discrete areas of the map to place enemies, and makes it easy to see which parts of the map should be connected.
Connections are generated between neighboring regions. There are a lot of clever ways to go about this, depending on your needs.
The visualization on the left attempts to ensure all regions are connected as a spanning tree - after all, content that can't be reached is wasted content.
Bridges are useful for gating content and need to be carefully placed. For example, it might be a good idea to close off a difficult part of the map by blocking off a bridge until the player has the tools they need to deal with the enemies in that area.
Vegetation and forest
Using our favorite continuous noise function, generate some organic-looking data which we will use for a range of terrain features. There's a lot of great material written on the topic of noise, so if you don’t yet know about the usefulness of this tool in procedural generation, check out some awesome posts on the subject.
Here, we can combine the voronoi region data with our noise output to create nice-looking forested with clearings around paths and spawn nodes.
And repeat...
Each chunk propagates its boundary conditions to its immediate neighbors, which in turn use this data to plan their large-scale features.
In general, as long as the rivers and roads line up right, some tricks can be employed to cover up potential seams resulting from generating these chunks one at a time.
The result
Here is what a generated map with 3x3 chunks, containing 3 towns, with highlighted connections typically looks like:
This algorithm makes it easier to plan and structure procedural content. In particular, structuring the terrain as a graph helps the AI navigate the world and understand tactical concepts like chokepoints.
The quest engine (which will no doubt be the subject of a future post) can request terrain features to ensure that quest providers and their objectives are arranged in a way that makes sense for the flow of the game.
Perhaps most importantly, we get to use smart-sounding terms like “arborescence” and “spanning forests” to describe and reason about the terrain generation algorithm... Seriously though, there’s a vast amount of articles, libraries and tools on the topic of graph theory that are invaluable resources for a programmer.
The next steps to improve this algorithm would be generating mountains by individually elevating specific voronoi regions to make cities on hills, or elevating the edges between regions to mountains dividing the map.
Spots where multiple rivers meet would be good spots to place lakes, and why not islands?
There’s a lot of room for improvement and creativity, and the terrain generator is a feature I hope to be able to revisit in a future update. Until then, keep your ears to the forest floor and consider signing up for the trollskog alpha to get a first-hand view of these updates.
/Andreas
