Generating the maps Trollskog

An article on the procedural generation engine was recently featured on IndieDB:

Read the full article here.

Homage to the classics

Trollskog owes a lot to the old-school RTS legends that pioneered the genre, and the forest is filled with loving homages for you to discover... You'll know them when you find them!

Villages or megalopolis?

An issue that has come up repeatedly during Trollskog’s playtests is the question of settling multiple smaller cities versus growing one massive city (a megalopolis). I'd like to talk a bit about the problem, and my solution to it.

I should explain what I mean when I say city, first - In Trollskog, most buildings can only be placed inside a city’s borders, and built using the resources available in the town hall structure. Each city can support a population of inhabitants depending on its food supply and housing infrastructure.

As players explore the world they’ll find resource nodes to claim and defend, and a lot of the mid- and endgame content revolves around managing multiple specialist cities, and the choices the player makes to balance each city’s strength and weaknesses.

When testers discovered a new resource node in the world, however, they would oftentimes begin harvesting this resource in the simplest way: sending workers from their capital city to trek all the way to some distant corner of the world where they might have discovered a new silver mine or rock deposit, have the worker harvest as much as it could carry, then walk all the way back home.


Gold- and silver mines are an example of a resource node that players can find while exploring the world.

Initially, I didn’t think much of this: surely players wouldn’t continue “long-distance mining”[1] resource nodes in this way once they became more comfortable with settling new cities?
After playing around with it myself, though, I was vexed by how this simple move allowed the player to grow their capital city to an enormous size while not having to make any of the interesting choices[2] involved in managing multiple cities, essentially skipping a lot of gameplay content.
Worse, many new players fell into this behavior by default, finding it simpler to just wait for their harvesters to complete their distant journeys rather than settling a new city.

I tried a few different mechanics to mitigate this. Initially, I experimented with giving each city a limited inventory. If each city could store at most 4 different resource types, progressing past a certain point in the tech tree becomes impossible without founding new towns.


The town hall command card in the lower right shows the city’s 4 inventory slots (2 occupied by wheat and wood, the other 2 empty)

This gave me some variables to tweak: the number of slots and how many resources each slot could hold. However, setting these variables in such a way that prevented a megalopolis made this mechanic extremely punishing for new players, who often take a very exploratory approach to resources and tech, while being trivially avoidable by players more familiar with the tech tree. Since I did like the decisions that came from having to manage a city’s limited inventory size, a nicer variant of this remains in the game, but a limited inventory was not a powerful enough tool to prohibit megalopolis formation.

So I looked to other strategy games for inspiration, trying to remember what’s worked well and what hasn’t. Now, most RTS games don’t actually have cities - In games like StarCraft, Age of Empires and Command & Conquer there’s really just different types of buildings - a player can consider a collection of buildings of cities if they want, but the game itself has no such concept. Certain buildings function as resource drop-off points, and this drives the player to expand out into the map.

Of the games I could remember having a well-established city concept, Anno 1404 impressed me the most with its solution. The game allows the player to settle new islands, which function similarly to cities in Trollskog, each having its own collection of resources. Each island having limited fertilities forces the player to settle colonies in order to advance their capital. The game holds the player’s hand through this process the first time around, encouraging the player to settle an oriental island to secure spice production, required to progress to the next tier.

In the end, I decided to utilize both these mechanics to a varying degrees. Resource nodes that are too far away from a drop-off point simply cannot be harvested. The player can decide whether to build a full city near the resource node, or to build a resource outpost and transfer the raw materials to a nearby city for further processing.


The inner border represents the city limits, the outer (dotted) border represents the city's harvesting range. Full cities have both these borders, while resource outposts only emit a harvesting range.
The inner border can be expanded by purchasing more tiles with gold, the outer border remains more or less static. The tradeoff: Resources will not replenish inside the inner border - harvesting a tree there means it stays harvested.

With these mechanics in place, I hope the issue is resolved. Players should still be able to build large cities, but doing so shouldn’t be something players blindly stumble into, it should be an interesting challenge that requires tradeoffs and support infrastructure in the form of smaller villages surrounding the capital.

I’m testing these changes internally first, and unleashing it on my alpha testers sometime next week.

[1] “Long-distance mining” being the Starcraft (and perhaps general RTS) term for harvesting resources far away from your cities.
[2] Thank you Sid Meier for not patenting this phrase

Fireside devlog

In these balmy summer temperatures, my code flows like molasses. But as the nights get longer and cooler, development thaws.

I'm currently investigating some glitches related to saving and loading: the world coming up ever-so-slightly different each time you load it is enough to make one question one's sanity.

When I've resolved this I intend to ship a new build and send out a new wave of alpha invites. I know there are some people who have been waiting for months - you will absolutely get your invite before the game's release, and the game will be better for it. Thank you for your patience!

And a glad midsummer to you!

Summer solstice is here! Development of the game will be on hold this weekend, as there are certain rites and rituals that must be observed to guarantee a good harvest.

So we wish you a merry midsummer, and if you'd like to read more about Trollskog, check out the devlog. Meanwhile, life in the village continues...

Trade route established

A trader's caravan moves brings goods from the blue city to the orange. A profitable endeavor, but sure to attract raiders.

Naptime

Sleepy times in the forest. A new unit "Idle" visual communicates to the player when their villagers are slacking off!

Pathfinding in an infinite world

One of the most important aspects in a strategy game lies in its pathfinding algorithm. This determines how the game’s entities move around in the world, which greatly affects the feel of the game.
As a player, you want the entities in the world to feel like an extension of yourself, and to watch your villagers struggle to carry out basic tasks due to a poor pathfinding algorithm is a frustrating experience.

I prototyped the pathfinding system using A* - this is the canonical pathfinding algorithm, which unfortunately isn't a viable solution in a game like Trollskog, no matter how much you dress it up, A* ends up having to explore huge areas of the world to provide search results, and we can’t be waiting around longer than 100ms for a path request without it negatively impacting the game experience.

The first serious attempt was Jump Point Search (JPS). In the same way that A* is an optimized variant of Dijkstras that assumes all edges have a non-negative length, JPS is an optimized variant of A* that assumes the traversed graph is a grid. I first encountered the algorithm in this whitepaper by Daniel Harabor and Alban Grastien.
Since the terrain in Trollskog certainly is a grid, the algorithm seemed like a good fit.

While JPS was orders of magnitude faster than A*, it wasn’t the performant silver bullet I’d hoped for, and it didn’t help at all with steering behaviors - A single entity following a path worked fine, but having a large group of entities all navigating together, bumping into each other and other entities along the way resulted in a lot of edge-cases, sometimes requiring path recalculation. I kept piling on band-aids for a while, trying to fix new strange behaviors as they arose, but eventually made the decision to try another algorithm.


The lit area indicates a route calculated by the JPS pathfinder. The yellow squares indicate jump points. Path-smoothing is applied to the route, as JPS tends to generate straight routes that take as few 45 degree turns as possible.

Some research into my problems led me to flowfields. These are great because they practically solve pathfinding and steering using the same algorithm. This GameAIPro chapter by Elijah Emerson is still the best writeup I’ve found on the subject.

Flowfields work quite differently from graph-traversal algorithms like A* and its variants. To summarize, it works by calculating a vector to the goal from each tile on the map, then each entity just has to follow the average vector of the four tiles around it to find the goal. This makes the algorithm scale very well with multiple entities;
Filling the entire world with vectors for every move command would be crazy inefficient, so instead we break the world up into sectors, and only fill the sectors that contain moving entities.


Here we see a 64x64 chunk of Trollskog’s world, divided into 8x8 sectors.

These sectors play two roles, one as a convenient bound for our vectorfield floodfill (to avoid having to fill the entire game world with vectors) and also for the first-pass hierarchical pathfinding. We can let the pathfinding system do an initial, broad-strokes search by traversing whole sectors at a time before we run a finer search on a tile-level, letting us break up a potentially large request into many smaller ones.

We need to keep these pathfinding sectors up-to-date by recalculating them, individually, whenever an entity that blocks a tile is placed or removed. And naturally, we want to generate these pathfinding regions as late in the terrain generation process as possible - An average 64x64 chunk of terrain in Trollskog contains about 2000 trees, and keeping the pathfinding regions up-to-date during the generation process while those trees are being placed would be a pointless waste of resources.

The advantages to this approach were immediately apparent. In the worst-case, A* and JPS explored most of the world before concluding that, yes, this unreachable spot surrounded by trees is, in fact, unreachable. The hierarchical flowfield approach can often rule out destinations which are not connected to any portal instantly, or at worst rule them out during the initial portal traversal stage.


Above, two entities are pathfinding between two sectors, with debug display enabled. Here is a larger group with a lower individual collision radius.

The result works a lot better than the previous (JPS) implementation, with a lot of tweakable variables (like collision radius, repelling force, etc) that I can play around with to make the end result look and feel the way I want.

Lit Green

Trollskog has been greenlit! This means the game will be available for distribution on the Steam platform. The whole process went faster than expected, so thanks to everyone who voted! And a special thank you to the awesome folks at valve.

I'm back in the lab, working on getting the next alpha build out there into the ether. Stay tuned!

On greenlight!

This week saw Trollskog appear on Steam Greenlight! In case you missed it, here is a link.

The response to the trailer has been great! I've enjoyed hearing from so many people who share my enthusiasm for the game, and getting feedback and criticism on the progress so far has been very valuable.

If you have any thoughts, I'd love to hear from you! Leave a comment on the greenlight page, send me a tweet @OftenABird, or a mail at trollskoggame@gmail.com! The options are endless. Since the game is still in alpha, there's still plenty of time to polish the some of the rougher edges based off your feedback.