Two years to find a path

I'd been playing around in Unity for about a decade before we started on Empire Builder. Game development always felt like the ultimate creative outlet for someone who also happens to write code.

Back when Windows Phone was a thing, I even released a holiday-themed endless runner. You played a snowman racing through a frozen world, bouncing from ice block to ice block and dodging spikes and campfires. To this day, it's unclear where all the negligent campers were.

A tool already in the bag

RimWorld has been a huge inspiration for me. It's incredibly complex under the surface, but it has a visual simplicity that makes game development feel approachable. Top-down, simple artwork, a world full of little characters finding their way around it. I started (and abandoned) a lot of prototypes loosely based on that look.

I don't know that RimWorld uses A* for its pathfinding, but there's a good chance. Either way, those prototypes meant I'd implemented simple versions of A* several times. It was already a tool in my bag.

If you haven't run into it: A* finds the cheapest route between two points on a graph. It explores outward from the start, but instead of searching blindly in every direction, it always looks next at the option with the lowest combination of "what it cost to get here" and "a guess at what it'll cost to reach the goal." With a sensible guess, it finds the cheapest path without exploring most of the map.

And an Empire Builder map is a graph. Every milepost is a node, and every legal step between neighboring mileposts is an edge. So A* was the obvious choice.

What I'd never done was build a feature-rich pathfinding system: one with real costs and weights, special cases, and rules that change depending on what you're trying to do. It turns out that was the hard part.

Two jobs, two kinds of hard

We use pathfinding for two very different things.

Building: what will this cost me?

When you build track in Empire Builder, you're spending money, and the price depends on where you build. Open terrain is cheap. Mountains cost more. Alpine mileposts cost more still. Building into cities has its own costs, and so does crossing a river or other waterway.

So the building pathfinder's job is to find the route that costs the least money. Not the shortest route; the cheapest one. This is by far the most complex part of the system.

At release, it worked... okay. But it had enough issues that players who trusted it, without double-checking that it had actually found the cheapest route, were putting themselves at a disadvantage. In a game about money, that's a real problem.

My favorite example: more than six months after release, we found that the pathfinder wasn't properly accounting for crossing waterways. It would happily suggest a route that zig-zagged across the same river several times, at $2 million per crossing.

It was a bad route that looked perfectly reasonable on screen until you added up the bill.

It turned out to be two bugs stacked on top of each other.

The first: when the search decided which step to explore next, it was going by distance instead of by what the route would actually cost. Fixing that helped well beyond rivers. Building through the Alps, for example, where there are lots of expensive mileposts packed together, got noticeably better.

But even with that fix in place, rivers still weren't being handled properly. When I dug in, I found that the code pricing each step was calculating the cost of crossing water. It just never added it to the total.

Both were head-smackingly obvious once I found them. But I didn't find them until I sat down and focused on that one problem and nothing else.

I put that down to moving at speed. When you're trying to sprint all the time, you're going to make some mistakes. Some of them will sit quietly in your code for months, costing your players $2 million at a time.

Today, the building pathfinder produces a predictably efficient path.

Moving: what did you mean to do?

Moving trains is simpler math, but it's complex in a different way.

Moving along your own track is free. But Empire Builder also lets you pay to use another player's track for the turn. So when you move your mouse across the map, the pathfinder isn't just finding a route. It's guessing your intent. Did you mean to stay on your own line, or did you mean to pay to cut across someone else's?

Even at release, we didn't have this quite right, and players complained about accidentally using (and paying for) another player's track.

Today, a dedicated piece of code interprets what the player is trying to do. It really boils down to one question: does the player want the fastest path using only their own track, or the fastest path regardless of whose track it uses?

The last annoying case was a player hovering over a major city milepost they aren't directly connected to. Is that a destination they're trying to reach on their own line, or an invitation to rent someone else's track to get there because it's cheaper (in movement terms)?

With our most recent major release, I believe movement is finally in a good spot.

The better part of two years

If I'm honest, getting all of this right took nearly two years. Not two years of constant work, but it was almost two years before I felt there were no outstanding bugs and I could call it feature-complete.

That's a long time for an algorithm I already "knew." The lesson I took from it: knowing the algorithm is maybe 10% of the job. The rest is the rules of your game, every edge case they create, and how much your players can trust the answer you give them.

The guy who owns pathfinding

I wrote most, if not all, of the building and movement code. I started on it before we'd even signed our agreement with Darwin's Toys; I'm not sure Derek had even installed Unity yet. Ever since, it's simply been easier for me to take pathfinding issues and let Derek work on something he knows better.

That's how it goes across the codebase. I wrote the very first versions of the networking and lobby code, but Derek has been on point for both ever since. I own much of the core building and movement code, and I wrote nearly all of the code that supports our DLC maps.

This is a weakness of small teams. Domain silos aren't just inevitable; they're necessary.

We could probably move faster if both of us knew every line of code in the game. But the time and mental load it takes to build that knowledge, and keep it current, is very costly when there are only two of you. It's easier to define clear areas of ownership and cross those boundaries when we need to swarm a feature or a problem together.

But "necessary" doesn't mean permanent. The networking code started as mine and became Derek's. Ownership shifts when the work demands it. The silos are there to keep us fast, not to keep us apart.