Hello
time is flying by and we have started some serious preparations for the Steam release. Martin and Kuba are making sure that we have the Steam compatible builtds as soon as possible. This basically means that out automated build process time will be doubled (the Steam binaries are different because of linkage against Steam libraries). We haven't yet figured if all the experimental updates will go to Steam, or what exactly will be the model, but we are working on that. Albert is wrapping up the new gameplay trailer and based on the testimony of couple of "unbiased" testers you have something to look forward to. The trailer will be released when we launch on Steam.
Ondra (Oxyd) has been working hard on the Pathfinder improvements. This time it is mainly connected to how our path cache works. He wrote the following to give you an idea of what he has been up to.
In FFF #117, we talked about improving Factorio AI performance by avoiding pathfinding as much as possible. These changes have helped cut down on work done each tick significantly -- but there are still many cases where pathfinding is still necessary: The simple movement heuristic can easily get stuck in a corner and may need the pathfinder's help to reach the intended destination -- and we don't even attempt to use the naive heuristic for traversing any kind of long distance -- it is a short-distance-only optimisation.
Pathfinding is therefore still very much needed, but we have other heuristics in our arsenal to help improve AI performance in those cases where we do actually run the pathfinder. The main heuristic for this purpose is the path cache. Often, we want to find a path very similar to a path we already found previously -- if a biter gets stuck on its way back to its spawner and requests a path to get back on track, chances are there will be another biter getting stuck in a similar location wanting to go to that same spawner. Caching is the obvious answer for this problem.
Path cache is a storage for a fixed number of calculated paths. Whenever a path is calculated, it is added to the cache, along with an information on how difficult it was to find the path. If the cache has no more room for another path, we use the difficulty-to-compute information to decide which path to remove from the cache in order to make more room. Later, when we need to find a path from one place to another, we check whether the cache already has a similar path -- if it does, we can use it in order to save some work processing the new request.
Path caching has been in Factorio for longer than I have been on the team -- so, as far as I'm concerned, it's been there forever. Over the years, Factorio has changed, including its enemies and their pathfinding needs. The caching code, however, hasn't. So, in our optimisation work for 0.13, we've decided to give it an overhaul as well.
The old way to use the cache is very simple: If we want to find a path from point A to point B, we go through each path in the cache and see if it starts somewhere near point A and ends somewhere near point B: We would require that the respective starting and ending points align rather closely with each other -- basically, we'd try to find an already-made solution to the current problem.
The starting and ending points don't always align so nicely, however. An example of this is a bunch of biter bases in a similar-ish place but still quite some distance apart, all wanting to attack a similar place -- the player's factory. The path for each attack group is very similar, so we wanted to make a use of that. Instead of only considering the cached paths' endpoints, we now go through the entire cached path to see if we can use any part of it. Also, instead of requiring the cached path to be close to the start and destination, we now allow greater distances. Together, this means that in order to find a path from point A to point B, we can go from A to the middle of a previously-found path, follow this pre-existing path for a bit, and then depart it and go to B. This reduces the -- possibly quite large -- pathfinding job of "Find path from A to B" to two smaller jobs: "Find path from A to X" and "Find path from Y to B", where X and Y lie on some known path in the cache, and so no pathfinding is needed between X and Y.
The above image shows the new path-joining logic quite well. The player's factory is to the northwest. A biter raid from the southeast already took place and used the red path to reach the factory. Then a new group of biters from the spawners in the centre of the image wants to attack the factory as well -- instead of finding a completley new path to pretty much the same place, they simply joined the pre-existing red path via the yellow path.
A second improvement to the caching logic was the introduction of the negative path cache: Sometimes, a biter will ask for a path that doesn't exist -- it may be blocked off either by water or by other entities, such as spawners. Determining that there is no way to get from one point to the other can take quit a considerable amount of time as well. Once the pathfinder has determined that a certain place is unreachable, we can cache this information as well. Next time we get a similar request, we can again serve the answer directly from the cache instead of looking for a path that doesn't exist.
In the picture below, we see a lonely biter on a peninsula in the bottom left part of the frame. It can't leave the peninsula because the two spawners are blocking the exit. It still wants to join its friends up north, so it asks the pathfinder for a path -- once we've determined that the biter can't go there, we remember the fact: The dashed magenta line is a "negative path" stored in the cache. Next time the biter wants to see its friends up north, we can tell him right away that it's not possible.
In one of the previous editions we have mentioned that we are looking for someone for our "jack-of-all-non-dev-slash-gfx-trades" position. This includes taking care of user support, community interaction, PR & marketing, bits and pieces of administration and whatknot. Well, we have received quite a few applications for the position including a few directly from people in the community. Things went quite fast and I am happy to announce that Scott (also known as Klonan on the forums) will come to work at this position with us here in Prague starting in February. He has spent last week here on probation and we feel it will be a mutual fit. At the moment his main priority is the Steam PR campaign obviously=)
If you have anything to remark on the path finding improvements, please let us know at our forums.
