Hello there,

I just took a short walk around the block to get some inspiration for the Friday Facts (it has been one of those weeks where many things that are not really worth talking about took majority of our time). And it doesn't feel like winter at all outside. More like the beginning of the spring. This has been the case for past couple of winters actually here in Czech Republic. It seems like there is some truth to the global warming. This triggers interesting associations with Factorio in my head. Things like: "Hmmm, so maybe all this warm weather is really caused by us (as a society) producing too much pollution. We should switch to Solar energy ASAP before nasty creatures start attacking us". Professional deformation I suppose=))

Path finder challenges

Speaking of nasty creatures attacking. They need to find their way first to do so. This is one of the areas that we decided to work on in the 0.13. Basically with large factories the path finder tends to suffocate with too many requests. The result is that there are groups of biters which appear non-responsive even if the player is walking near them or if there are player turrets attacking them.

Path finder can handle only a constant amount of nodes per tick. This is so to avoid FPS glitches in times of intensive path finding. However this also leads to mentioned unresponsiveness. The approach we took here (namely Ondra who is in charge of the task) was to start with analysing couple of big saves where this is happening. So he has made a script to collect and plot path finding data. Below are these data for a fairly large save.

• Top left: Each dot represents one path. X axis is path length and Y axis is steps it took to calculate. Not saying much. Dots over dots.
• Top right: Histogram of paths by steps to calculate. X axis is steps to calculate. Y axis is number of paths that needed this many steps. This shows that majority of paths take <= 50 steps to calculate.
• Bottom left: Sum of the Top left one. For each path length on X axis we get on Y axis the amount of steps needed to calculate all paths with that length. Now this is intersting. The red circled are shows some crazy activity for short paths.
• Bottom right: Histogram of the Bottom left one. The X axis represents path lengths split to intervals of 50 (same as top right). The Y axis then gives total amount of paths for that path length interval.

So the major observation based on these graphs is that there are a LOT of requests for short paths. This can be further divided into:

• requests for very short paths of length less or equal to 5. This is the first spike in red circled area.
• requests for the rest of the short paths of length between 5 and 50.

The goal is to avoid path finding whenever possible for short paths. This would speed the game quite a bit - or rather allow other entities to use the path finder and avoid path finder suffocating and unresponsiveness. One of our advantages in this quest is that we can afford "suboptimally" looking behavior when biters are not anywhere close to the players factory. What the eye doesn't see the heart doesn't grieve over comes to mind. Another reason to avoid using path finder for short paths is that there is a constant amount of time necessary to setup and start the path finding / put together the results / etc. As an obvious consequence, it would take effectively longer time to calculate many short paths than a few long paths even if the sum of steps would be the same. And that is not mentioning all the black magic like cache locality=)

The solution

Based on the data and observation we (well Ondra=)) have figured that the cause for overflow of requests for very short paths ( length <= 5) are issues with avoiding the obstacles when following a given path. For example let's say that a biter follows a given path which runs across another biter nest (very common) there he bumps into a friendly biter just standing there or wandering around. After some bumping time it would fallback to searching for a path that would reconnect him to the next waypoint on his path. This new path would typically be very short (<= 5). The solution was to introduce a so called avoidance logic. If a biter bumps into another biter on the path it asks him to "make way". This biter (that has been bumped into) then moves away and allows the other one to pass. This turned out to work quite well (see below).

The main cause for requests for path of length between 5 and 50 turned out to be twofold. First, it is biters travelling into group meeting points. These are triggered by pollution and get created close to spawners. Over the course of time, biters from nearby spawners are collected here and after some period of time the group is send to attack the factory (following the pollution path). Another case are biters which wandered too far away from their spawners. In that case they would request the path back to the spawners vicinity. Both cases produce short and relatively straightforward paths that are almost never observed by the player. Hence the solution here would be to actually don't use pathfinding but a straightforward algorithm when the biter just goes directly to the goal and if it encounters the obstacle it performs obstacle avoidance (trying to get around the obstacle from one specified side). Only in cases when this fails do we fallback to regular pathfinding. This is computationally very cheap and actually based on observation (and data) produces very good results.

Conclusion and next steps

So in the second set of graphs we can see (bottom left diagram) that the number of steps to compute very short paths (length <= 5) dropped from almost 10000 to about 1000. In other words 10 fold improvement=). And short paths request in general (length <= 50 - see bottom right diagram) dropped from almost 1000 paths to little bit over 200. So about 4 fold improvement. This concludes our optimization efforts for dealing with short paths for now.

However we are not done with path finder optimizations. Another big issue is that path finder struggles with long paths. Especially when searching for path around big lakes. Typically pollution spreads from the factory across the lake and triggers biters to attack, however they need to search for the path around the lake which is VERY expensive. Here we have decided to start by optimizing our path cache mechanism (so once the path is actually found we will make sure to reuse even parts of it in the future) and shorten the final path searched for (we will not search for the path into the middle of a big factory but rather in the outskirts where the attack usually ends at the defenses anyway). If this is not sufficient then we might dive into implementing a variation of hierarchical path finding. All this is a near-future work and we will keep you up to date with progress=))

Mods board cleanup

Ssilk has done some cleanup and reorganization in the mods section on the forums. So if you are a modder please check out the following thread for details. On a similar note, originally we thought we will have the external mod database ready for the 0.13 however the external development (in Python) of the mod portal went silent in the past month so at the moment the status of that is unclear. So we might need to hold onto the current forum-based solution a little longer=/.