Deeper Details

Anyway, let's move on to what I expect was one of the biggest challenges in developing the game: the amazing pathfinding.

TA: Is it amazing? It's creaky and slow.

Well it looks amazing from my end, since there's a metric ton of characters all doing it at once.

TA: The dwarves themselves mostly move around with A*, with the regular old street-distance heuristic. The tricky part is that it can't really call A* if they don't know they can get there in advance, or it'll end up flooding the map and killing the processor.

(Ed. note: see here)

Sometimes in commercial projects the developers do a bit of cheating, and predefine travel paths.

TA: Yeah, that's the hard part. We can't really predefine areas beyond very basic notions because fluids can zip by and block them off, or they can mine a floor out. All it does now, and this isn't ideal, is keep connected component numbers. So if a dwarf is standing in "2", they know they can't get to "3" and don't bother trying. However, they assume they can get to any other "2", and will A* those paths. There are still a few failures, but it's fixable.

There's a price to pay for that though, on a few levels. First, it's a pain to maintain. If a fluid occupies a square, it has to update. If a fluid flows through a passageway and cuts it in half, it has to reindex one or both sides. There are other ways to think about handling it, like keeping track of some sort of rectangles or something, and pathing on those, but the memory cost is too great.

The memory cost here is large, and it's also a speed burden. There are probably a ton of better ways to do it, it's just a very hard problem.

And all of this taking place over potentially many Z-levels too.

TA: In a 480x480xZ map. Or even a 768x768xZ at max settings.

And there's another huge downside to it that I have to cope with, and that's the mode of travel. A dwarf walks; a dwarf does not fly. For a flying creature, the path components are meaningless. So flying creatures are much dumber than dwarves, and dwarves are already kinda dumb.

I still stand by the adjective "amazing" though, based on how watching a dwarf make his away around the world, then suddenly disappear because he took an unforeseen shortcut over a hillside, is a cool experience.

TA: Yeah, it's nice that they can solve an arbitrary labyrinth of your own design, and they'll pick the best possible path, generally. There are some exceptions, like mining where they can mine from multiple sides, and don't try them all.

At its most complex, running Dwarf Fortress is like having an ant farm. You look in, and these little bearded guys are roaming all around, each with his own agenda. It's fascinating to watch for its own sake.

TA: Somebody modded their dwarves into antmen [laughs]. I even have a few people that went as far as donating, and they don't even play. They just like to check out the stories.