Over the last few weeks, the bfme2-patcher grew quite a bit. What started as a small dll that redirects a few DNS queries and skips a certificate check (if you missed it, that’s what my first blog post is about) now applies a whole list of patches to the running game: a 60 fps mode, a handful of crash fixes, AI fixes, tooltip improvements, and more. Most of them are small, but two areas turned out to be much more interesting than I expected: the performance of the pathfinder and the delayfix for multiplayer matches. This post is about those two.

A quick note before we start: many of the other patches, such as the 60 fps mode, most of the AI and tooltip fixes and some of the crash fixes, are derived from patches of pySAGE. Some of them work a bit differently in the patcher, but the groundwork was done there, so credit where credit is due.

Part 1: Faster pathfinding for big armies

Why big armies make the game stutter

Anyone who has played a late game with a few hundred units on the map knows the problem: you select your army, click somewhere, and the whole game freezes for a moment. With a big enough army, a single order stalled the game for hundreds of milliseconds, and I wanted to know where that time goes.

The culprit was the pathfinder. To find a path, it runs an A* search over a grid of cells, and every cell the search opens gets a price. Part of that price is what I call the crowd cost: the pathfinder walks a small window of cells around the cell it’s pricing and, for every unit standing in that window, asks three questions:

  1. How does the moving unit relate to this unit (ally or enemy)?
  2. What’s the priority of both units?
  3. How fast can this unit move?

None of these questions are cheap, and since a unit stands in the windows of many neighboring cells, a single search asks the same questions about the same unit over and over again. On top of that, the game recomputes the world position of the cell’s center for every unit in the window - four floor calls and a terrain height lookup each - even though the result is the same for all of them. In a slow frame, that adds up to about 200,000 calls computing the exact same two floats.

Remembering the answers

The fix for the cell center was simple: compute it once per call and reuse it. The other three questions needed a bit more thought.

The answers only depend on the units, their modifiers and the terrain, none of which change while a search is running. So within a single search, the same question always gets the same answer. That makes it a perfect candidate for memoization. The patch redirects the calls to those three functions to small hash tables keyed by the arguments, and only calls the original function on a miss.

There’s one catch, though: the game is a lockstep simulation. Every player runs the exact same logic, and if a single result differs on one machine, the match desyncs. Between two searches, units move and their modifiers change, so an answer from an earlier search can be outdated. On top of that, not every search runs on every machine. The UI, for example, asks the pathfinder whether the location under your cursor is reachable, which only happens on your computer. If the cache outlived a search, your game could pick up an outdated answer that no other player has, and the match would desync.

Luckily, every search in the game ends in the same cleanup function. The patch hooks it and increments a counter there, and each cached answer remembers the counter value it was stored with. An answer from an earlier search no longer matches the current value and is treated as a miss, which makes every earlier entry stale at once, without having to clear the tables.

Rewriting the crowd cost

With the memoization in place, I went one step further and rewrote the crowd cost function itself. In the end, all three questions boil down to one of three outcomes per unit:

  1. The unit is ignored.
  2. The unit adds a fixed cost.
  3. The unit adds a cost only if it reaches the cell before the moving unit does.

The rewritten function works out which of these applies once per unit and search, and then simply reuses that result for every cell window the unit shows up in.

This is where it got tricky. The original function does its math on the x87 FPU (floating-point unit), the part of the processor that old x86 programs use for calculations with fractional numbers. How precisely it rounds the results depends on a setting called the FPU control word. Being “almost the same” is not good enough in a lockstep game, so the rewrite reproduces the rounding for 24- and 53-bit precision and falls back to the game’s own function for everything else, including any value it can’t reproduce exactly:

int __fastcall crowdCost(void *self, void *, int mover, int node, const int *cell, int radius, int extent, int flag) {

    const auto original = reinterpret_cast<CrowdCost>(CROWD_COST);

    const int mode = precision();
    if (mode < 0) {
        return original(self, mover, node, cell, radius, extent, flag);
    }
    bool ok = true;
    const int result = mode == 0 ? crowdCostOf<false>(self, mover, node, cell, radius, extent, flag, ok)
                                 : crowdCostOf<true>(self, mover, node, cell, radius, extent, flag, ok);
    if (!ok) {
        return original(self, mover, node, cell, radius, extent, flag);
    }
    return result;
}

The full version of the code can be found here.

Bonus: collision detection

While I was at it, I also found a second bottleneck that shows up with big armies: the collision detection. Before the game checks whether two objects actually collide, it first narrows things down by finding all pairs of objects whose bounding boxes overlap. It keeps track of those pairs in a hash table, and on every logic frame it looks up pairs in that table over and over again.

The problem is the size of that table. It only has 11,131 buckets, but with a big army clumped together, there can easily be more than 200,000 pairs. Every bucket then holds a long list of pairs, so a single lookup has to walk through ten or more entries before it finds the right one. The collision check took about 12 ms of every logic frame, and most of that time was spent on these lookups.

The patch gives the table 262,139 buckets instead, which keeps those lists short and brings the time down to about 4 ms. That number isn’t random: it’s the largest prime below 218. The game picks a pair’s bucket by taking the remainder of a division by the table size, and with a prime number as the table size, pairs whose ids follow a regular pattern still end up in different buckets instead of piling up in the same few. With about 200,000 pairs, that’s less than one pair per bucket on average, so more buckets wouldn’t gain much and would only cost more memory.

Since the game only uses that table to look pairs up and never walks through it in order, every lookup still finds exactly the same pair as before. Just like the pathfinder patches, it doesn’t change the outcome of the simulation in any way.

Part 2: Less delay in multiplayer matches

Where the delay comes from

The second topic is one that every BfME player has complained about at some point: the delay between issuing a command and the units actually executing it in multiplayer. Interestingly, it’s not the same for every player. The host barely notices it, while off-host players (everyone who isn’t hosting) do.

To find out why, I wrote a small patch that logs when each of the local player’s commands is created, sent and executed, as well as how every logic frame started, into a CSV file. The numbers were pretty clear: commands of the host were executed after about 0.12 seconds, while commands of an off-host player took about 0.92 seconds.

To understand where the difference comes from, it helps to know how a command travels in a multiplayer match. Since every player has to execute every command in exactly the same logic frame, it’s the host that decides which frame that is. When you give an order, your game sends it to the host, and the host schedules it for its own next logic frame.

That would work great if everyone were always at the same point in the match, but they aren’t. The host starts running the match while the other players are still loading, so every off-host player starts about 4 logic frames (roughly 0.8 seconds) behind the host. When the host schedules your command for its next frame, your own game only reaches that frame about 4 frames later. The host doesn’t have that problem, because its next frame is the one it’s about to run anyway.

And off-host players never catch up. They can’t run a frame before the host has sent it to them, so the best they can do is keep the host’s pace, but never get ahead of it. On top of that, EA built in a network slowdown that deliberately slows an off-host player down until 3 frames are buffered beyond the one they’re currently on. So even if the gap closed a bit on its own, the game would slow that player down again, and the lag stays for the entire match.

What the 2.02 patch does

The community’s 2.02 patch already ships a delayfix, so I wanted to understand how it works before building my own. The game spreads the work of a logic frame over several client frames; let’s call them phases. The stock game runs 6 phases per logic frame at 30 fps, which comes down to about 198 ms per logic frame. The 2.02 delayfix runs the first two phases in the same client frame, for every player, which makes it 5 client frames (about 165 ms) per logic frame.

In a multiplayer match, that speed-up mostly turns into waiting. The host’s network still only allows one logic frame every 200 ms, so the host finishes its 5 client frames early and then waits for about one client frame per logic frame. Off-host players, on the other hand, now try to run a logic frame every 165 ms, which is faster than the host. That’s what lets them close the gap: they run faster until they’ve caught up with the host, and from then on they simply wait whenever the host’s next frame isn’t there yet.

The 2.02 delayfix also disables EA’s network slowdown for every player, but more by accident than on purpose. The game recalculates the slowdown in the first phase of a logic frame, and since the delayfix merges that phase into the second one, the recalculation never happens anymore.

That works, but it comes at a price. The delayfix is always active, not just in multiplayer, so single player, skirmish and even replays run about 20 % faster than they’re supposed to. It also makes some animations look a bit funky: because the first phase is never drawn, moving and turning units take a step twice as large as usual once per logic frame, about six times a second, which makes their movement look slightly jerky. On top of that, it doesn’t work together with my 60 fps patch. That’s why I decided to build my own delayfix.

Catching up instead of running faster

My approach targets the actual problem: off-host players trailing behind. Instead of making everyone faster all the time, only off-host players speed up, and only while they’re behind.

Like the 2.02 delayfix, it runs two phases in the same client frame, but only when there’s a reason to. To stick with the numbers from above, let’s look at the game at 30 fps, where a logic frame consists of 6 phases:

  • If an off-host player has one frame buffered beyond the current one, phases 5 and 6 run in the same client frame. The logic frame then takes 5 client frames instead of 6, which is the same pace as the 2.02 delayfix.
  • If two or more frames are buffered, phases 3 and 4 are paired as well, and the logic frame takes only 4 client frames.
  • If nothing is buffered, the player has caught up, nothing is paired, and the game runs at its normal pace.

Phase 1 is never paired, since parts of the game expect to see it in every logic frame, which is exactly what the 2.02 delayfix breaks. In reality, the game runs with the 60 fps patch (derived from pySAGE), where a logic frame consists of 12 phases and up to three pairs are merged, but the idea is the same: the game is only sped up when necessary.

The pairing happens through the game’s own catch-up loop, so every phase still runs exactly once per logic frame and in the same order. Only the pace changes, never the logic, which keeps the game deterministic. For off-host players, the patch also disables the network slowdown on purpose, so they only wait when a packet actually arrives late, just like the host. The patch has no effect when hosting a game, playing single player or watching replays.

Sending commands earlier

While going through the CSV files, I noticed another source of delay: the game only hands your commands to the network once per logic frame. That means a command waits for 100 ms on average before it even leaves your computer (the measured median was 99 ms). For the host, that wait doesn’t matter, but for off-host players it does.

So there’s one more patch: off-host players now send their commands every client frame instead of once per logic frame. This is still deterministic, because the sender never decides in which frame a command is executed. The host still assigns the frame to every command it relays, exactly like before. This cuts another 100 ms off the delay on average.

2.02 delayfix vs. my delayfix

Here’s a quick overview of the differences:

  2.02 delayfix my delayfix
Who is affected every player, always only off-host players, only while they’re behind
Single player, skirmish and replays about 20 % faster unchanged when compared to vanilla
Commands sent once per logic frame every client frame for off-host players

What’s Next?

There’s still plenty left to look at. On the performance side, big armies are still far from free, and the game’s rendering logic also offers a few opportunities for performance gains - for example in the part that renders shadows. On the multiplayer side, part of the remaining delay comes from the host putting every command into its next logic frame, which neither the 2.02 delayfix nor my patches change.

If this blog post sparked your interest, the source code is available on GitHub.