Fun with pathfinding

I’m currently debugging a fun pathfinding error. Here’s a view of it; I’m asking the game to generate the path that a subscriber would take if they were to try to travel from a point in the right of this image to the left of the image (basically, they’re trying to get from one end of the red line to the other); the white line is the path that they’re taking.

The interesting thing here is that while it successfully makes it across the region boundary, immediately after traversing the mountain pass the pathfinding appears to decide to go overland, rather than take the bending path that goes through the little village, visible above.

I get this same problem in both directions; it’s not that people are falling off the road system after going through a mountain pass; they’re refusing to get on this specific road no matter which way they’re travelling, unless you start pretty much directly on top of it. Everybody else completely skips it for some reason.

No idea what’s causing it yet. But it’s an interesting puzzle. (This pathfinding debugging tool is actually accessible in the current testing version of the game; it’s incongruously lurking under the ‘Town’ tab. Note, don’t delete paths after playing with it; that’s liable to cause a crash because it’s not yet cleaning up after itself. I have a fix for that, but it’s not up on Steam yet)


…and found it.

So here’s what happens: In MT2’s pathfinding system, there are two main processes interacting. One piece is an exploration agent which builds a graph of nodes of potentially interesting places where a subscriber might want to walk to, while travelling from one place to another.

(For the technies out there, I’m doing a standard A* search across this graph, but I’m building the graph at the same time that I’m doing the search, instead of the more traditional approach of having a static, pre-built graph that searches are then run across)

For example, the explorer typically begins by creating points where the subscriber is now, at the eventual destination, at the nearest point on a road to the starting point, at the nearest point on a road to the finish point, and several other spots. As it starts evaluating how much it wants to reach each of these spots, it starts picking where it might want to go to next, from whichever point it’s evaluating right now. For example, if it’s standing in the middle of a road, it adds a point for each end of the road, and also for the nearest point on the road to the destination.

The second main part in the system is involved with deciding how much it wants to consider each of those positions that the explorer has noted. It assigns a “cost” to each. The eventual path that’s chosen by the subscriber is the path which will get from the starting point to the desired destination using the lowest “cost”. This is why subscribers prefer to take roads; taking roads has a lower “cost” than walking the same distance across normal terrain, and so they’re willing to travel further, if it means they can take a road. (Right now, travelling on a road is considered to be one tenth the cost of travelling across terrain. That’s absurdly low; players in MMORPGs typically don’t stick to roads that strongly. I should really make it closer to half, or even two-thirds.)

Anyhow. The bug was in the logic around traversing across an intersection. The explorer would say “I’m at the start of this road, therefore I’m on its start intersection, and therefore I will consider traveling to the far end every road which also meets this intersection.” Which is just fine, except that the system which is deciding how much each move costs looked at that move and said “Oh, you’re going to travel from the start of this road to the end of that road? Let me just check if that’s movement along a road. Hey, wait a minute, those two points aren’t remotely close to each other, and aren’t even on the same road; that would just be traveling across regular ground, so I’m not giving you the on-road bonus”. And so subscribers were effectively losing that road bonus, when crossing that intersection. Really, the explorer shouldn’t have been adding the far end of the connecting road, it should have been adding the near end of the connecting road, so that the costing agent could correctly realise that yes, we’re still traveling over a road.

So that explains why players don’t want to use that road. But it doesn’t explain why they’re happy to use every other road; why they only broke with this specific road.

Well, it turns out that I’m an idiot. It just so happens that this is a bug I’d noticed before, back in August. And I fixed it for the case where the explorer agent was traveling over the end of a road, but forgot to do it when it was traveling over the start of a road. (Roads have both a ‘start’ and an ‘end’, based upon where you started drawing them from. This makes no difference, in general, except for this specific bug). It just so happens that getting onto that one winding road here involved traveling over the “start” of the mountain pass, or over the “start” of that circular street on the left, and so was failing in both these cases, but not in the other cases.

It’s all now fixed, finally. Debugging is fun!


i like these posts they are very intresting look into game development. :slight_smile:


I should post these things more often. I’d love to do development livestreaming, but my usual internet connection just can’t upload fast enough to do it.

The trick is always in finding a bug which I know in advance is going to be interesting enough to talk about, and this one definitely qualified, because its behaviour was just a slight weirdness. That it didn’t result in a flat crash also made it a really good candidate. I sort of liked that I posted this one before I’d figured out what was going wrong; usually when I post about bugs it’s after the debugging has been completed and I know that I have something interesting to talk about. This time… I had no inkling what the problem was going to turn out to have been. I actually suspected that it was just that I was loading a really old save file, and maybe there was something wrong in the save data which wouldn’t happen if I was to rebuild the road fresh. I’m sort of glad that didn’t turn out to be the case; this was a much more interesting solution!

(Even though it did turn out to be a bug that I’d apparently found once before, several months ago, and only half-fixed at the time.)