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.

Back to homepage

More posts from the development blog of Trollskog...

The roadmap to v0.9

Since the early access release, I've had my nose buried in my keyboard, fixing bugs and not posting too much about upcoming updates and features - in part because there's been a major backlog of bugs to work through, and because future features have a tendency to change. Now, with the game rapidly approaching a stable state, and with a clearer view of the updates ahead, it's time to share the future roadmap with you.

Pathfinding fix

I'd say the bulk of my development efforts since the early access release has been iterating on the pathfinding, but at last, it is just around the corner. In the dev branch (and in a few days, on the steam build), units no longer get stuck on terrain or buildings. I’m still dissatisfied with group steering, especially in combat - fighting units tend to trip over each other and struggle to get into melee range. I'm looking to resolve this before releasing the next patch.

Improved AI - Attacking, expanding, trading

This is being worked on. As far as rabbit holes go, this one is deep. I’ll be making incremental improvements rather and releasing them together with other new features. Expect the AI to become a little more competent and engaging with every new patch.

New units

There’s some new combat mechanics waiting in the wings, such as buffs and debuffs, auras, armor and damage types. I’ll be unrolling these together with new units that make use of these mechanics in interesting ways. The new units in the pipe are the Slinger (a tier 1 ranged status caster), as well as the Seider, Skalder and Noaidi (Tier 2 and 3 aura-casters)

Food rework

As I’ve mentioned in a few other places, the food mechanic needs some love. I’ll be adding more food engines (rather than the dummy simple “put grain in bakery”) and adding a survival mechanic.

Tier 3 rework

It’s no secret that the last tier is a bit of a placeholder still. This will be fleshed out with more resources, buildings and units.

Harvesting rework

The current harvesting mechanic - specifically, the dotted line around each city - was not really intended to be in the game for this long. The new design will revolve around building specific structures to collect different resource types, such as granaries and lumber mills. I’m not entirely finished with the design on this one, so the dotted harvest radius line will remain for a while longer.

Main Quest Chain

Not going to spoil the plans for this one, but there will be group of procedurally generated “main quests” that can be completed to achieve sweet victory.

Save rework

Currently, every patch breaks existing save games, and each save file is on the order of several megabytes. This makes autosaves an unappealing concept. To fix this, I’ll be replacing the current serialization layer (Protobuf) with flatpak, and separate the serialized gamestate from the data-model that’s used in-game.

Future roadmap from 0.9 to 1.0

With the above features in place, the game will be in a good spot to be taken from Early Access to released. It's too early to give specific details here, but in all likelihood, when we get past 0.9, I’ll start marketing the game again, focusing on a Mac and Linux build, as well as the holy grail - Multiplayer. The big roadblock for this one (on a technical level) is the “Save rework” bullet point mentioned above. As it looks today, the serialized gamestate is a bit too cumbersome to be transmitted over the wire. Hopefully those pieces will fall into place as the patches roll out.

Want to share your thoughts? There's a discussion thread on the steam forums or you can hit me up via any of the social media links in the page header.

Early access on August 19!

For the first time, Trollskog is swinging open its doors and inviting you to share in the experience. On August 19th, the game will be available world-wide on Steam for Windows PC.
This is an early access release, which means the game is not yet content complete, but it is in a stable and playable state.
If you would like to participate in the community as the game continues to grow, you are welcome to join us!

Unit showcase - The berserker

The berserker is a new addition to the earlygame, capable of quickly engaging ranged enemies and delivering solid damage.
Equip him with a blunt club for an immobilizing stun, or an axe for maximum damage.

Steam store page opens up!

Some time ago, Trollskog was greenlit on steam. Finally, the store page has been published.

There'll be more details to come on this site, but we're open for wishlisting!
Additionally, the next test release will be moving on to the Steam platform, so the alpha accounts on this site will be replaced by steam beta keys.
If you registered an account here previously, you should be expecting an email within a few weeks.
If you didn't register, well, it's not too late...

To the walls

Walls and towers are a staple of real-time-strategy games, and Trollskog wouldn't be complete without them.
Here's a sneak preview of this latest feature:
(Click the image for full-res)

Placing archers on the walls will help keep those frontier settlements well-defended.