Greetings Golems
We have been working hard on 1.0 and we're making some great progress. Today I want to share with you what I (Jasson) worked on last month. Overall, I think that AutoForge (currently as of 0.7), performs quite well even with larger factories, but I fully admit that it begins to struggle in the late game with some frame rate loss. This performance drop is largely due to all of the items moving around in transport tubes and how the game handles that. This has been known for some time now, but addressing it was going to be a significant undertaking. With other priorities taken care of and us now pushing towards the 1.0 release (and the factory demands therein), it was finally time to tackle reworking the item transportation.
This update will be much more in-depth and technical than previous posts, so I hope you like it!
Sneaky peaky at all of the new transport tube graphics - including some new tiers!
High-level Design
Over time, I have done my best to squeeze out as much performance as I could with the original item transportation system. However, it was becoming apparent I had reached the limits of possible optimization, and truly the path forward to a better running game would be to rebuild item transportation from scratch. So, that's exactly what I have done! To better understand the details of the new system implementation, let's quickly cover how the original system worked.
The previous implementation was in most ways very simple. All items in transport were stored in a large list, and every simulation update would trigger the game to check for each item to see if it could move forward to the next transport tube that the current tube was pointing at. However, because this was so naive, we actually had to go through this list twice. An item could be blocking another item at first but then moved out of the way making room for the next item. This meant that we had to update every single item every single simulation update not just once, but twice. Needless to say, this does not scale well!
Each one of these items get updated twice every frame - even if it isn't moving
Years ago, I remember reading this excellent Factorio FF post that detailed how they worked on optimizing item transportation in Factorio. I always thought it was very clever and it immediately popped into my head when I started the redesign. How it works is that transport tubes (conveyor belts in Factorio) that are connected are logically put together into a "segment". Items in a segment move only in one direction and they move at a constant speed. This means that the spacing between items stays constant until the item hits the end of the segment or another item.
With segments in practice, we only have to track the distance between one item to the next, with the first item tracking the distance to the end of the segment. Then, we can reduce the distance of the first item, and it will move all of the items in the segment since we track their relative distances rather than absolute positions. With this design we can update dozens of items (potentially even more) by only updating a single item. Additionally, this opens up the potential to optimize full segments to not even have to update a single item. Performance-wise, this is a HUGE win.
All of these items are updated together in a segment and it is not updated at all when no movement
Segmenting Challenges
One of the first tasks that I set out to do was to develop a system to calculate the transport tube segments themselves. I thought this would be a simple enough task but was I ever wrong. Initially, I designed it so that the system was recalculating segments as placed tubes changed, but as I neared completion, I realized that I was overlooking a fundamental aspect to the design. Segments needed to be preserved, due to there being a significant amount of data associated with them (such as the items moving in them). This required starting the design of the entire segment calculation over.
Now that I knew I needed to preserve segments, I had to handle all of the scenarios that a segment could potentially change. Transport tubes can be added, removed, rotated and have the tier change. Any one of these structural changes could result in a segment changing. The challenging part came with handling each of these properly; depending on the tube change, it might be appending the tube to a segment, or that a segment would need to split in two, or that two segments needed to merge.
Each of these lines is a different item segment - rotating the middle tube in the + changes multiple segments
With all these factors to consider, Implementing the transport segment handling took all of nearly two weeks with multiple rewrites. I have been programming for over 20 years, and this was by far the most challenging code I have ever had to write. I have glossed over much of the complexity, but needless to say, I was extremely relieved to finish it.
Additional Complexities
Speaking of glossing over complexities, there are many other aspects of item transportation that required consideration to bring it all together. One such thing was structures collecting items from nearby transport tubes. This is surprisingly a very costly task and with the changes to how items are stored (in segments) it became a slightly more complex one too.
With the original system it was fairly trivial to check if an item was in tile or not. With the new system we don't know exactly where an item is without having to go through every single item before it and adding up the distance from each one. Doing this allows us to determine which tile in the segment the item is on, however, if we did this every single update for every single item for every structure collecting items then we would absolutely destroy any performance gains we gained so far. Fortunately, there are a few neat tricks I was able to employ to optimize this.
Oftentimes a segment will run through multiple tiles that a structure will be collecting from, so instead of checking every tile we can, we instead check a range within the segment. If the item falls within the range, then we know the structure can collect it. We can calculate this segment range and store it so that we only have to recalculate it when the segment or structure changes (which is not that often). Now that we're tracking segment ranges, we can also track the range that items moved within the segment - if there was no item movement for a segment within the collector's range then that means no items moved. There are sometimes when we have cases where we need to force a check such as when a structure is first placed, but that is easily done.
Structure collection ranges in red
There are, also a fair few more complexities and considerations, such as handling bypasses, splitters, item dispensing and multiplayer to consider... Of these, bypasses are the most interesting one. Previously bypasses would transfer items out of the item transport system into a special state to track their 'movement'. This was done because items were attached to tiles and so only one item per tile was supported. Now, with the segments it was possible to integrate bypasses into the item transportation. This ends up being a huge optimization. The bypasses are now much lighter to process - especially now that they use the greatly optimized item segments.
All of these aspects of item transportation took some time to truly think through and implement but in the end, we now have a greatly optimized solution that will support much larger factories without frame rate issues.
Quality of Life Fixes & Changes
When I set out to work on the new system, I was not only looking to improve performance but also looking at making improvements to other issues that are more player-facing. I'm happy to say that I was able to accomplish every task I had set out to solve and then some.
Fixed issue where structures would sometimes stop dispensing/collecting items.
Splitters now interact with structures as players expect (i.e. dispense directly without tubes).
Splitters' priority is now observed correctly - always pushing into prioritized tube unless it is truly full.
Bypass outputs can now be rotated.
Items coming out of a bypass no longer appear to be stacked on another item that is moving out of it.
Item merging in tubes is now deterministic with round robin (taking turns).
[Multiplayer] Fixed item transportation for clients that would often break.
Results
In order to stress test the game, I replaced the sky islands with thousands upon thousands of structures and transport tubes to simulate an endgame factory.
The stress test world sky was littered with hundreds of these little factories
With the previous system this stress world was running at a whopping 10fps on my machine... Using the same world, I tested the new item transport system, and I watched as the numbers climbed. Right out the gate it was at about 30fps - with the item transportation being an amazing x4 faster. It's important to note that this test was always gauging while factory was fully active, I imagine factories that have items backed up will easily be x20 faster. The 30fps was nice a nice start but not going to cut it for me. So I rolled up my sleeves and got back to work.
Firstly, I worked on optimizing the hot spots in the item transportation and squeezed out all of the juice I could. From that alone I was able to get the stress test world running at 40fps. With thousands of structures in the world, I could see that other systems were being also being stressed. One by one I worked on optimizing them - shaving off those precious milliseconds. When I was done finished optimizing where I could, it was running at a beautiful 50+fps.
Before any changes you can see how painfully slow item transportation was
Huge gains with item transportation after all of the changes
Overall, this is amazing progress and I'm thrilled that players will have a much better play experience in later game worlds. Technically there is still some work to be done, such as tackling the Fabricator system and wrangling the LUA garbage collector which causes unpleasant lag spikes. I hope to get to these fixed before release but for now I must shift my determined gaze upon the new content that we are adding in...
Stay Tuned
We have some exciting news coming up next week that we are beyond excited to share.