Hello,
Make Way for the Pentapods!
Last week (FFF-424) we announced two entirely new enemies coming to Factorio: Space Age: Stompers and Strafers. This week, we're going to take you on a behind-the-scenes tour of some of the features, systems, and optimizations that brought these adorable monsters to life. We'll also talk about the techniques we used to prepare last week's announcement. We've got a lot of ground to cover, so let's dive right in.
From the very beginning, we knew we wanted Pentapods to reuse the code that drives Spidertron legs, but we also knew that Spidertron had some performance issues. If we could not solve the issues, then adding Pentapods to Factorio would really harm UPS. Even though premature optimizations are usually a bad idea, we had very little choice in the matter; in order to bring Pentapods to life, I first needed to optimize Spidertron.
The most obvious performance problem with Spidertrons happened when they navigated over obstacles. In 1.1, you can observe a noticeable slowdown by commanding a squad of Spidertrons to cross a wide river. In some saves, as few as 10 Spidertrons could affect UPS.
The first culprit that I found was the algorithm that searched for an empty space to place each leg. In 1.1, the algorithm scans in an outward spiral, checking every 1/5 of a tile for collisions with a tile (i.e. water) or entity in that location, in an area of up to 16x16 tiles. In the worst case where there are no empty spaces, this algorithm conducts around 6400 collision checks ((8 [tiles radius] × 2 ÷ 0.2 [distance between checks])²).
All of the positions a Spidertron's leg checks for collisions. This example shows 1600 checks, but this isn't even the worst possible case.
Also not illustrated is the fact that every single leg on the Spidertron is performing this check every single tick.
The trick for solving this was realizing that the scan precision is very small (0.2 tiles). Tiles are 5× this size, and most entities are at least 10× this size. Therefore, the algorithm often checks the same tile or entity over and over again. Instead, if the algorithm finds a collision, it should immediately advance past the edge of the collider's bounding box. And if we remember every collider's bounding box, we can potentially skip scanning entire rows and columns.
The Spidertron's leg checks far fewer positions now. This example shows about 70 collision checks.
Also, note the new scan pattern, which produces better results compared to the spiral.
This change alone significantly improved Spidertron performance, but the job was not done yet. We'd need to free up many more compute cycles before Pentapods were feasible.
The second performance culprit was that every single Spidertron leg in a group was performing the same empty space search in roughly the same area. Even if each individual leg was conducting fewer collision checks, multiple nearby legs would still duplicate this work. This naturally raises a question: can spider legs work together to perform fewer searches?
The trick to making this work was realizing that the algorithm scans outward from the center until the first empty space is found. That means if we find an empty position some tiles away from the search origin, we know that the inside square is completely blocked. If we mark this inner square as a "search exclusion zone" and put it in a list, future leg searches can check that list and skip collision checks that fall within that zone.
After searching an area for empty space, that area is logged as a "search exclusion zone" for the remainder of the tick. Other Spidertron legs will skip over this entire zone when they also search for an empty space.
Honestly, I had little hope for this to work. The implementation is very naive and the exclusion zones are only valid for tick they are added. But to my surprise, this little hack cut down a ton of time! After a few more adjustments and other optimizations, Pentapods were now feasible and could be added to the expansion.
The final performance culprit that we'll discuss involves the algorithm that selects which Spidertron leg gets to move. You see, for all the improvements made to the empty space search algorithm, there was still a glaring inefficiency: every leg — no matter if it was already moving or waiting on a moving neighbor — was searching for an empty space every tick while the Spidertron was walking. Each leg was assigned a score based on how far the leg needed to step, and only the one leg with the highest score was chosen to move. If that leg was already busy moving, then the results were simply thrown away.
Obviously this resulted in many wasted searches, but it was necessary to ensure that the Spidertron always made progress towards its destination. Without this scoring system, legs that needed to take a big step would often get stuck because one or both neighboring legs were busy taking small, repeated steps. What we needed was an efficient way to ensure that every leg had an equal opportunity to move.
The solution to this problem came about months later while the Pentapods were in early development. When the 5-legged Pentapods were added, the old algorithm for scoring and moving legs was no longer adequate. Earendel wanted complete control over the order in which legs moved so that we could give these alien creatures a unique and organic walking pattern. This gave me the excuse I needed overhaul the Spidertron walking algorithm and implement the final major optimization.
How should a creature with 5 legs walk? We don't have many examples on Earth, but Earendel still came up with a good design. To maintain balance and stability, Pentapods step in a 5-pointed star pattern.
After all legs in group 1 have finished stepping, legs in group 2 can start stepping. Afterward, group 3, then 4, then 5.
Some Pentapods however prefer to count backwards.
To implement this, every leg on a Pentapod or a Spidertron is assigned a numbered "walking group". When walking, one or more legs from the current walking group are selected to move. These selected legs search for a clear destination, and then begin moving there. No more wasted searches. After all of the legs of the current walking group have finished stepping (or at least moved past some specified threshold which I won't be able to cover today), the process repeats for the next walking group. This new system significantly cuts down on the number of collision checks while giving designers unprecedented control over Spidertron and Pentapod walking animations.
After these three large optimizations, and several other smaller ones we don't have time for, Spidertrons are now far less taxing on UPS. In a test save designed to stress Spidertron mobility, I measured an average of 53.56% fewer milliseconds per update (approximately 2.15× faster). So in Factorio 2.0, players should now be able to command larger armies of Spidertrons without obliterating their UPS (results may vary).
With new enemies comes new behaviors! And with new behaviors comes new engine features. We'll now discuss the game design decisions that influenced the Pentapod designs and the system changes we built to implement them.
We knew early on that enclosing your Gleba factory in walls was going to be a real drag on gameplay. So we designed an enemy that didn't care about our puny walls. Instead, players must fend off Pentapod attacks with raw firepower and the new rocket turret.
To make this work, we needed the pathfinder to support gaps and produce paths that ignored obstacles. Luckily, I was able to extend the existing Biter pathfinding system (FFF-317) with a few new features.
When performing the abstract (or chunk-level) pathfinding, it is no longer sufficient to only record the traversable tiles that touch the chunk's perimeter. In addition, non-traversable tiles along the chunk's perimeter need to record the distance to the nearest traversable tile (of up to 2 different components). We later use this information to connect multiple components between chunks.
The distance between two tiles is calculated as the greater value of either delta-X or delta-Y.
Traversable tiles within a chunk are grouped together if their distance is less than the maximum allowable gap. Tiles along each chunk's border remember the distance to the nearest traversable tile within the chunk.
(Note: this screenshot does not show an example of an edge tile that is within range of more than one component.)
Next, when performing the base (tile-level) pathfind, every node must remember if it is traversable and always point back to the last known traversable node. This allows the algorithm to scan deeper into untraversable areas (water, walls, and other entities) to find paths that would otherwise be impossible for biters to traverse.
Nodes search some distance into untraversable terrain, always pointing back towards the last known traversable tile. A typical pathfind searches many more nodes than this illustration shows.
Discontiguous pathfinding will be available via the modding API in Factorio 2.0, even though nothing in the base game currently makes use of it.
Now that walls can't keep Pentapods out, the player has another problem: Pentapods could still attack any part of your factory from any direction! What is an engineer to do except surround the factory with more turrets and weapons? This was still not the strategy we wanted for our players, so we needed to make this strategy unnecessary. To accomplish that, we changed how pollution works on Gleba.
Enemy units (Biters and Pentapods alike) typically choose attack targets based on pollution. When an attack party is formed, they pathfind towards the nearest chunk with a locally maximum level of pollution and attack the entities in that chunk that are emitting pollution.
Pollution works differently on Gleba than on other planets. Some machines that produce high amounts of pollution on Nauvis should emit no pollution on Gleba while machines that produce high amounts of pollution on Gleba should emit no pollution on Nauvis. How can we make Pentapods prioritize specific parts of your factory without changing Biter behavior?
Factorio 2.0 introduces pollutant types. Mods can add different types of pollution. Machines, plants, spawners, and tiles can each be configured to emit or absorb different amounts of each pollutant type. However, for performance reasons, only one pollutant type can be enabled per surface. "Pollution" is the default pollutant type for new and existing surfaces that have pollution enabled. In Factorio: Space Age, Spores replaces Pollution on Gleba. Each pollutant type can have its own name, absorption and emission rates, chart color, and more.
Armed with this new tool, we were able to tune Gleba so that Pentapods focus their aggression on a few specific buildings while functionally ignoring the bulk of the factory. That is, as long as they are not provoked.
Finally, Pentapod legs needed a rework. Being an organic creature, we wanted to minimize the amount each leg stretched and squished, and instead emphasize bending at the knee and hip. This makes the creature look and feel more believable and less robotic.
We even made the legs update their sprites based on their orientation relative to the body. This was difficult to get right due to Factorio's perspective and the weird angles, but Fearghall and Earendel did an amazing job. The final effect makes these creatures feel more real by keeping the lighting angle consistent and by accounting for the player's perspective at all times.
Stomper and Strafer legs attempt to flex at the hips and knees before stretching. Sprites change based on orientation.
Because Spidertrons and Pentapods share a lot code, Spidertrons now also have a slightly new look. The legs are less stiff, more bendy, and frankly a little more creepy. They are still clearly robotic entities, so I believe we've managed to preserve their iconic look while also giving them a small facelift.
Left: Spidertron walking animation in 1.1. Right: Spidertron walking animation in 2.0.
When we were trying to decide what to do for this week's FFF, and I made the joke that I could make a FFF on the making of the last FFF. Well... people really seemed to like that idea so here we are.
It makes sense, fans like seeing behind the scenes. Showing how the videos are made is a nice way to show you behind the scenes content without needing to reveal game secrets.
Most FFF, (like this one) are made the week of their release. Usually I try to have mine done an extra week in advance, it's less stressful that way. For the enemies FFF though, I started working on it many weeks in advance trying to eliminate all of the "unknowns" from the production process.
I took some of the randomly generated terrain as a "combat arena", placed some enemies, and exported it as a scenario (the same way anyone can from the map editor).
From previous videos I already had some performance capture code for capturing player input for character running and tank controls (turning, acceleration, etc). I extended that system to also capture player weapons input, which is mostly which weapon is selected, firing or not, and the target position.
Here's the character loadout. Weapon damage upgrades are at level 8.
I recorded a performance of fighting the enemies in the arena, and then I applied that performance back to the scenario, ran it again, and... it played out differently.
All of the player input was the same, but the enemies didn't do the same things. Some wandered to different positions so attacked at different times. In the original captured version there was one Strafer on the map and another one spawned just before the egg raft died. In the version with the script-controlled character, instead of spawning a 2nd Strafer an extra Wriggler spawned. The Stomper joined the combat much earlier for some reason. The character got slowed by gliding Wrigglers hitting at different times so the movement was off-track and eventually the character got stuck running into a tree and was quickly stomped to death.
So, not an ideal start. Running the scenario again did at least cause things play out exactly the same way with the character getting stomped into a tree, so at least it's not rerolling the entire outcome every time. I started trying to figure out what exactly would or would not cause the outcome of the scenario to be randomised.
After some testing I realised that it's just not possible to have the scenario play out the same way as the input recording, because both the recording code and application code themselves are enough to change the outcome and there's no way around that. It's a bit annoying but not a huge setback because I knew that a lot of the landscape was going to change around the arena anyway. It made the most sense to add some other more reliable tools to keep the new simulation more stable.
The biggest thing to sort out was the player getting off-track. It was obvious that this sort of thing can happen easily because if a gliding Wriggler hits it slows movement. When dodging the gliding Wrigglers there are a lot of near-misses so it results in a lot of variability. Any changes to player movement also affect where the enemies go, so the whole combat could get dragged off to an unexpected direction.
Some new terrain assets were added to the map as they were completed, but this "rerolled" the enemy behaviour, slowing the character at different times, so everything played out differently and the character's final path looks very different.
Left: Original movement path. Right: Movement path with the same input but being slowed at different times.
My fix for this was to measure how far the character is from the intended path, and if it strays too far then they are just forced to run in a direction to correct it. They're still slowed by whatever effects they have, but it means that they can cut corners or skip dodge manoeuvers to get back on track.
Tracking the player movement in this way also gave me a nice way to replace our camera system. Unlike previous videos where the camera is panning smoothly over the landscape, this video would follow the character's erratic movement. Our old bezier control point system for camera movement would be a nightmare to match the character movement, especially if it ever needed to be re-recorded, which is almost guaranteed.
My new system takes the logged character positions from the performance capture and smooths out that path with a few passes of a relax filter, essentially making each point the average of the point before and after.
Actual character movement in white. Smoothed path for the camera in blue.
This gives nice smooth camera movement, but it doesn't follow the action very well because it's always centred on the character. Then I added a secondary target system where an imaginary point could move to a targeted enemy and the camera would stay some % between the smoothed path and the secondary target point. It uses an imaginary point and not the enemy itself so if the enemy dies and a new target is chosen the camera doesn't suddenly jump, instead the imaginary point moves to the new target with a limited speed. An extra layer of controls can determine how strongly the camera is pulled to the 2nd target. At the start of the video the secondary target is the egg raft but the influence is set to zero.
All our debug data enabled: Smoothed primary camera path in blue. Secondary target path in orange. Actual camera result in white.
The purple squares are the camera bounds.
All the positions and timing are more important than usual because everything in the combat is choreographed to the music. The egg raft dies just before the beat kicks in. The Strafer dies when there's a melancholic tone and the music starts to sound a bit more unhinged. And the Stomper needs to die at a specific time too (more on that later).
Along the way I got to learn what would change the scenario result and how enemies would be affected.
Enemies behave consistently as long as NOTHING changes. Swapping out a graphic is fine, but changing the graphics shifts is not. Moving an enemy, adding or removing a tree, changing a tile, adding some ammo to the character, even adding a decorative, all break the result. It can break in a lot of different ways too.
The spawner (egg raft) may or may not spawn a unit, or if they do it could be a different type of unit. One time it randomly spawned a Stomper so there were 2 Stompers. That didn't go well. The scenario is part of a mod with a set of scenarios for videos, so to fix this problem I updated the scenarios mod so that spawners can only spawn Wrigglers.
Any of the pentapods could wander off in a random direction, so if combat starts they might be out of range of the "call for help" and just never show up in the combat.
I tried to teleport the enemies to the correct spot just before they'd be in camera view, but I quickly found that you can't teleport the leggy enemies, they rubber-band back to their previous position in 1 frame.
Instead I had to spawn the pentapods to the correct position via LUA script just before they're in camera view. This kept positions more consistent. Buuut....
Script-spawned leggy pentapods had a 50-50 chance of having a left or right strafing bias, meaning they'd go in a random direction. As with other things, the direction was only consistent as long as nothing changed. This was the most awkward problem because their direction impacts so much of the fight. There was never a great solution to this, but there are only 8 outcomes of left-right combinations for the 3 leggy enemies, but really the most significant direction is the first Strafer. With the other consistency safety nets it was enough to make sure that the first Strafer has a consistent direction by subtly adjusting its starting position until it re-rolled the direction I wanted.
It wasn't until much later that I discovered the worst offender of messing up the scenario simulation outcome: Even the change in camera script code to go from preview mode to render mode for saving screenshots, is enough to break the scenario output. That means that all the time spent previewing what would happen was useless because it didn't work out the way the preview showed. This catch didn't get noticed immediately because the first few times I went through the process the render result wasn't noticeably different, but inevitably at some point it became a huge problem. Fortunately I found that I could leave rendering on all the time but reduce the capture size to 1px by 1px, so even though it's still saving files, they're so tiny that it's really fast and that's good enough for a preview.
The weapons input capture records the time to fire, the position to fire at, and the gun to use. For Wrigglers it's ok, the aim assist chooses nearby enemies so inaccuracy still works. For rockets vs Strafers though, the position would be so wildly wrong that the rockets would usually target a Wriggler, often not fire at all, and only very occasionally attack the intended target. To fix that I edited the input data to remove all rocket firing and instead used my events system to fire a rocket at a Strafer directly, and in a way where it's easier to change the times to make sure there's a Strafer in range.
With the flamethrower there's no target locking but for the first use vs Wrigglers it always worked just fine. It's near the start of combat so it's more consistent and they're all being led into a kill funnel anyway. In the last use against the Stomper, the Stomper position was very unreliable. It would always be somewhere near the character but the angle could be in any direction. Firing based on its original position looked very wrong in most cases because the flames would be going in a seemingly random direction. Once the flame dance had started it got more consistent because I stayed in a small area abd just spreading flames in a circle made more sense. To fix the start of this sequence though, I added a script to make the flamethrower target the Stomper's position for the first 2 seconds and then switch back to captured input. Just a bit of smoke and mirrors.
The next problem is the timing of when the final Stomper dies. The Stomper needs to die before the end of the music, but not so far before that nothing is happening for a few seconds. For the egg raft it's easy, just shoot it at the correct time. With the Strafers it's down to the rocket timings, but sometimes they're out of range but if that's delayed by a few seconds it's ok. For the Stomper the death time is really hard to control. In the performance capture I got the timing just right (with some practice), but in playback the timing is always off. It's usually too late because extra Wrigglers get in the way, or the flamethrower misses more. The final fix for this is just to multiply the thing's health by 10x and use a script to insta-kill it at the correct time. Health bars are hidden anyway. The approximate damage inflicted by that point is still roughly enough for it to die if it had the correct health so it doesn't look wrong. That's actually part of the strategy for spinning round with the flamethrower at the end. It ensures that there's some fire doing damage so that it doesn't die while not taking damage.
The same scene as the original combat video but enemy healthbars are shown and it's day for clarity over atmosphere.
The Stomper death time is not scripted so this time it dies slightly too early, but re-rolling things could make it die too late.
The character happens to survive this time, but that doesn't always happen.
The final problem is the character dying. In the original performance I got to the end alive but a lot of that was to do with dodging. When playing back the scenario, even when not running into a tree, the character only had a 25% chance of getting to the end because it'd dodging feet that are in different places and running straight into damage sometimes. This could have been solved just by upgrading the quality of the armour or equipment, but I went with the faster approach of just keeping character health up with a script.
Just for fun, let's see what happens with some larger enemies.
The same scene again, but this time the enemies are more evolved. It plays out a bit differently...
Thank you for joining us on this journey! We hope that we offered a glimpse into what it takes to create a new enemy, and the kind of effort goes into producing exciting announcements like last week's FFF.
I now too have a greater appreciation for games with a wide enemy variety. Even though I had the benefit of building upon existing systems, I still had to learn the capabilities, limitations, quirks, and bugs of each one, and then figure out how to make them play together nicely. Each change needed to be carefully tested so that other parts of the game didn't break or become unbalanced. Along the way were plenty of refactors, cleanups, bug fixes, and many pages of notes. Even so, it's obvious that the previous programmers built these systems with extensibility, performance, and (sometimes) code health in mind.
Anyway, I think I've seen enough of these creepy-crawlies to last a lifetime. I'll leave Gleba to the Pentapods for now. They can have it! Besides, it's about time I check on my Vulcanus factory. I've been getting a bunch of alerts from there, so I sure hope nothing is disrupting my foundries...
As always, reliably and repeatably wander over to the usual places and comment at exactly the right time, which is now.
