Gotta Go Fast

Pathfinding in RimWorld has a weird bug: the faster you move, the worse your pathfinding gets. This patch fixes that. Best case scenario, your super-fast pawns will pick routes that are up to 3× as efficient! It also fixes a suboptimality in Vanilla Expanded Framework that causes pawns immune to terrain costs to pathfind as though they were affected by terrain. This lets your pawns with Glidewings (or any other "ignore terrain" effect that uses the same functionality) fly over shallow lakes instead of pathing around them. Also fixes a vanilla bug involving flying creatures and snow.

Do you know how movement speed works in RimWorld? I thought I did, and I was surprised by how wrong I was. The RimWorld wiki (as of the time of upload) is completely wrong about terrain movement penalties!

Under the hood, before your pawn moves, her move speed is converted to "game ticks necessary to move one grid cell." The penalty from terrain is an integer that’s added to the ticks it takes to move from one cell to the next. You know how it says that soil is 87% speed? That’s kind of a lie. Normal pawns with no bonuses or penalties have a 4.6 cells/sec move speed, meaning their ticks/cell is 13. The terrain penalty for soil (2) is added on top of that, raising the ticks/cell to 15. 13/15ths is 87%, and that’s where that number rimworld shows you actually comes from.

BUT if you follow this logic out, you’ll realize that the faster your pawn is, the more the terrain penalty hurts. Let’s say you’ve got a pawn right at the speed cap of 60 cells/sec. Her ticks per cell is 1. That means after you add soil’s movement penalty, her ticks per cell is 3. She’s literally moving at 1/3rd speed. Here’s an animation to illustrate. Lenka is fast. But notice how much faster she moves over the road than over the soil. That soil’s causing a huge penalty, way worse than the stated 87%.

So obviously, when I found this out, I built a spidery network of concrete roads over my entire map so that my speed-60 haulers could clean up all the drops from raids on the far side of the map much faster.

But there was a problem: my haulers were ignoring the roads I’d made, and were literally walking through the soil right next to the road and taking huge speed penalties. You can see that in the animation above. When I told Lenka to move horizontally, why didn’t she take the road?

So I looked into the code. RimWorld uses A*[theory.stanford.edu] for pathfinding, which is pretty much a perfect algorithm. A* is faster than other pathfinding algorithms because it uses something called a heuristic, which is basically a way to tell the algorithm "don’t bother searching this path; it’s not going to get you anywhere useful." The problem is that RimWorld’s heuristic assumes that the pawn has 4.6 speed, no matter how fast the pawn actually is! In computer science terms, the heuristic is "inadmissible," meaning it breaks A* and keeps it from finding correct paths. This means that pathfinding basically forces your pawn to find paths as though she had a speed of 4.6, meaning she grievously underestimates how bad soil is, because she thinks it’ll only slow her by 13% instead of 67%. That’s why, in the image above, Lenka tromps through the soil when I tell her to move instead of taking the road; veering off course just isn’t worth it to her because her pathfinding algorithm literally can’t see the savings.

This mod fixes the heuristic so it’s admissible, which turns the A* pathfinding back into a "perfect algorithm," where your pawns, no matter their speed, will find the correct fastest path, even if it’s unintuitive. Here’s that same movement route I showed above, but this time with this mod applied.

See how she runs along the road now when moving to the right? That’s because the pathfinding algorithm now correctly detects that veering off to the north to take the road is a better route than trekking through the soil. Same movement commands. Much faster pawn.

Here’s another example: Lenka hauling 15 pieces of slag. Top is vanilla, bottom is with this mod added. Note how much she uses the roads in the bottom animation to speed herself up.

This patch also fixes a suboptimality in Vanilla Expanded Framework that causes pawns immune to terrain costs to pathfind as though they were affected by terrain. This lets your pawns with Glidewings (or any other "ignore terrain" effect that uses the same functionality) fly over shallow lakes instead of pathing around them.

It also fixes a bug in Alpha Genes VFE that prevented waterstriding pawns from pathfinding over water.

This patch also fixes a vanilla bug. In Vanilla, flying creatures (Like Odyssey’s Locusts) fly slower over snow than they do over normal ground, even when it’s not snowing! This bug caused some problems in my fix to VFE, above, and it turned out that fixing the vanilla bug was faster than fixing VFE while preserving the bugged behavior, so enjoy faster winter locusts!

This is a bit of a performance hit. A test with 250 colonists with speeds randomly assigned from 2 to 60, all pathfinding simultaneously, reduced TPS by 17% compared to vanilla in a testbed environment… but then, that’s 250 colonists, which is a worst-case situation. Other performance notes:

• This patch only activates for fast pawns, and it adapts to your pawn’s speed. The patch’s effect on performance will be heaviest when your pawn has a move speed of 60. It will only be negligibly heavier if her speed is 5.2 or something else close to baseline.
• It doesn’t get applied to animals. I guess they’re just too dumb to figure out where to move. Sucks for Legendary Thrumbo-legged Thrumwolves, but it’s worth it to keep herds of animals from tanking TPS when they’re doing nothing but milling around uselessly.

The picture shows two of my favorite pawns in my most recent playthrough: a Hisa named Mills and a Revia named Lenka in a footrace, both bragging about the various equipment, bionics, genemods, and racial traits they’re using to go fast, each trying to one-up the other. Lenka’s a nudist, but you can hardly tell, can you? That’s because the Light Tribalwear from VFE – Tribals (basically a loincloth) doesn’t count as clothing, and neither does the Janissary Cuirass from VFE – Empires for some reason. TLDR: if you ever need a SFW/stream-safe nudist, that’s how you do it! Her eyes are weird because she’s part Narai for their ridiculous unclothed speed buffs.