About Trollskog

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.

  • View media
  • View media
  • View media
  • View media
  • View media
  • View media
Post article RSS Articles

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...

Suitability map 1

... 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

Suitability map 2

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

Generating the voronoi diagram

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.


Making connections

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.

Generating vegetation

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...

Putting the pieces together

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:

The result

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

Villages or megalopolis?

Villages or megalopolis?

News

An issue that has come up repeatedly during Trollskog’s playtests is the question of settling multiple smaller cities versus growing one massive city...

News from the forest

News from the forest

News

Dev update: I've been tying together loose ends, collecting yarn, leaving a trail of breadcrumbs, and avoiding minotaurs.

Comments
AndreilGame
AndreilGame

It's fun that your game has a lot in common with one of my old game (town management + empire management + exploration based)
While it's a completely different kind of game (mine was an RPG)
it's pioneerz : Andreilgame.itch.io

I'd love to see how your game evolve, you've gain a new follower ^^

Reply Good karma Bad karma+1 vote
Post a comment
Sign in or join with:

Only registered members can share their thoughts. So come on! Join the community today (totally free - or sign in with your social account on the right) and join in the conversation.

Follow Report Profile
Icon
Trollskog
Platforms
Windows
Creator
OftenABird
Engine
Custom
Contact
Send Message
Homepage
Trollskog.net
Release date
Game watch
Follow
Share
Style
Theme
Fantasy
Project
Indie
Boxart
Boxart
Twitter

Latest tweets from @oftenabird

This town might be excessively defended. It's certainly not an easy target... #screenshotsaturday #indiedev T.co

Dec 8 2018

Every castle starts with a wall. (Don't quote me on this, I haven't actually studied the lifecycle of castles)… T.co

Dec 1 2018

Exploring your neighborhood can be dangerous... Best leave these skellies alone for now 💀#screenshotsaturday… T.co

Nov 24 2018

Working on my latest and greatest invention: Procedurally generated exceptions

Nov 17 2018

GUI images on #screenshotsaturday is always exciting right? A villager's inventory slot is now also a progress indi… T.co

Nov 10 2018

Embed Buttons
Link to Trollskog by selecting a button and using the embed code provided more...
Trollskog
Statistics
Last Update
Watchers
11 members
Articles
3
You may also like
SpellForce 3
SpellForce 3 Real Time Strategy
Warcraft III: Reforged
Warcraft III: Reforged Real Time Strategy
Stronghold Legends
Stronghold Legends Real Time Strategy
King under the Mountain
King under the Mountain Real Time Strategy
Black & White 2
Black & White 2 Real Time Strategy
ParaWorld
ParaWorld Real Time Strategy