Trollskog is a desktop city-builder strategy game for Windows due to be released in 2017, and draws inspiration from the real-time-strategy classics, while combining the best aspects of city-builders with the clever design of modern boardgames.
Will you spread peace and prosperity throughout the lands, help those in need, and protect defenseless villages with your armies? Or will you send those armies to conquer the wilderness and colonize the far reaches of the forest?
Each city is both a puzzle and a piece of your sprawling empire. Plan your buildings with care to suit your needs, manage your foreign policy and establish trade routes with your allies, or plunder those of your enemies.
Visit the website to find out more and follow the development 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:
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:
... 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.
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.
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.
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.
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.
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.
An issue that has come up repeatedly during Trollskog’s playtests is the question of settling multiple smaller cities versus growing one massive city...
Dev update: I've been tying together loose ends, collecting yarn, leaving a trail of breadcrumbs, and avoiding minotaurs.
No articles were found matching the criteria specified. We suggest you try the article list with no filter applied, to browse all available. Post article and help us achieve our mission of showcasing the best content from all developers. Join now to share your own content, we welcome creators and consumers alike and look forward to your comments.