fff-317

New pathfinding algorithm Oxyd

Last week we mentioned the change to make biters not collide with each other, but that wasn’t the only biter-related update we released this past week. Somewhat coincidentally, this week’s updates have included something I’d been working on for a few weeks before – an upgrade to the enemy pathfinding system.

Pathfinding

When a unit wants to go somewhere, it first needs to figure out how to get there. That could be as simple as going straight to its goal, but there can be obstacles – such as cliffs, trees, spawners, player entities – in the way. To do that, it will tell the pathfinder its current position and the goal position, and the pathfinder will – possibly after many ticks – reply with a path, which is simply a series of waypoints for the unit to follow in order to get to its destination.

To do its job, the pathfinder uses an algorithm called A* (pronounced 'A star'). A simple example of A* pathfinding is shown in the video below: A biter wants to go around some cliffs. The pathfinder starts exploring the map around the biter (shown as white dots). First it tries to go straight toward the goal, but as soon as it reaches the cliffs, it 'spills' both ways, trying to find a position from which it can again go toward the goal.

Webm/Mp4 playback not supported on your device.

In this video, the algorithm is slowed down to better show how it works.

Each dot in the animation represents a node. Each node remembers its distance from the start of the search, and an estimate of the distance from that node toward the goal – this estimate is provided by what's called a heuristic function. Heuristic functions are what make A* work – it's what steers the algorithm in the correct direction.

A simple choice for this function is simply the straight-line distance from the node to the goal position – this is what we have been using in Factorio since forever, and it’s what makes the algorithm initially go straight. It’s not the only choice, however – if the heuristic function knew about some of the obstacles, it could steer the algorithm around them, which would result in a faster search, since it wouldn’t have to explore extra nodes. Obviously, the smarter the heuristic, the more difficult it is to implement.

The simple straight-line heuristic function is fine for pathfinding over relatively short distances. This was okay in past versions of Factorio – about the only long distance pathfinding was done by biters made angry by pollution, and that doesn’t happen very often, relatively speaking. These days, however, we have artillery. 長距離砲 can easily shoot – and aggro – massive numbers of biters on the far end of a large lake, who will then all try to pathfind around the lake. The video below shows what it looks like when the simple A* algorithm we've been using until now tries to go around a lake.

Webm/Mp4 playback not supported on your device.

This video shows how fast the algorithm works in reality; it hasn’t been slowed down.

Contracting Chunks

Pathfinding is an old problem, and so there are many techniques for improving pathfinding. Some of these techniques fall into the category of hierarchical pathfinding – where the map is first simplified, a path is found in the simplified map, and this is then used to help find the real path. Again, there are several techniques for how exactly to do this, but all of them require a simplification of the search space.

So how can we simplify a Factorio world? Our maps are randomly generated, and also constantly changing – placing and removing entities (such as assemblers, walls or turrets) is probably the most core mechanic of the entire game. We don’t want to recalculate the simplification each time an entity is added or removed. At the same time, resimplifying the map from scratch every time we want to find a path could quite easily negate any performance gains made.

It was one of our source access people, Allaizn, who came up with the idea that I ended up implementing. In retrospect, the idea is obvious.

The game is based around 32x32 chunks of tiles. The simplification process will replace each chunk with one or more abstract nodes. Since our goal is to improve pathfinding around lakes, we can ignore all entities and consider the tiles only – water is impassable, land is passable. We split each chunk into separate components – a component is an area of tiles where a unit can go from any tile within the component to any other within the same component. The image below shows a chunk split into two distinct components, red and green. Each of these components will become a single abstract node – basically, the entire chunk is reduced into two 'points'.

Allaizn’s key insight was that we don’t need to store the component for every tile on the map – it is enough to remember the components for the tiles on the perimeter of each chunk. This is because what we really care about is what other components (in neighbouring chunks) each component is connected to – that can only depend on the tiles that are on the very edge of the chunk.

Hierarchical Pathfinding

We have figured out how to simplify the map, so how do we use that for finding paths? As I said earlier, there are multiple techniques for hierarchical pathfinding. The most straightforward idea would be to simply find a path using abstract nodes from start to goal – that is, the path would be a list of chunk components that we have to visit – and then use a series plain old A* searches to figure out how exactly to go from one chunk's component to another.

The problem here is that we simplified the map a bit too much: What if it isn’t possible to go from one chunk to another because of some entities (such as cliffs) blocking the path? When contracting chunks we ignore all entities, so we merely know that the tiles between the chunks are somehow connected, but know nothing about whether it actually is possible to go from one to the other or not.

The solution is to

Bye bye TOGoS TOGoS

Hi everybody!

I'm going to be resigning from official Factorio staff after today to start a new job closer to home.

The main reason for this switch is that working entirely remotely turned out to be something that I wasn't able to handle all that well. But also, my primary contribution to the project, the programmable map generator, is complete, stable, and pretty well understood by at least one other person, so timing-wise this seemed a good point for me to move on. To working in a cube farm writing Android applications for treadmills, apparently.

We'll see how that goes!

It's been an honor to be part of this awesome project and to leave my imprint on it. And working on a large and pretty well-managed C++ codebase, full of things done just a bit different than I had ever thought to, has been mind-opening.

I also want to thank the community for your continual patience, honest feedback, and the occasional bit of pressure that you put on us to make the game as good as it can be.

I'll continue to read the Friday Facts every week, lurk on the forums, and probably update documentation here and there. Hopefully I'll find time to crank out some terrain-altering mods of my own. And I'm looking forward to seeing what else y'all do with it, too. (Which includes working through a backlog of mods -- I have yet to get to the space exploration part of Space Exploration!)

Peace out for now.

Community spotlight - 13x9 Micro Factory Klonan

Over 100 Friday Facts ago we covered DaveMcW's 9x14 Micro Factory (FFF-197). While it may have taken over 2 years, he has improved his design even further, and the result is just as impressive as before.

He offers some more explanation of his Micro Factory in this forum post.

As always, let us know what you think on our forum.

Discuss on our forums

Discuss on Reddit

Subscribe by email