How does Dwarf Fortress keep track of so many entities without losing performance?

Question

In Dwarf Fortress you can have hundreds of Dwarves, animals, goblins, etc in game at any one time, each with their own complex AI and pathfinding routines. My question is how does this not produce noticeable slowdown? Does each Dwarf run in its own thread?

Answer 1

Any system which had a thread for each of so many characters would run out of resources very quickly. Threads may give you access to extra processor cores but they don't make anything intrinsically more efficient, and they come with overhead.

The simple answer is just to be efficient about processing each entity in the game.

• Don't process every entity each frame.
• Split processing into stuff that needs doing often and stuff that does not need doing often.
• Spread long-running algorithms across multiple frames so that they don't block processing in other systems.
• Ensure that efficient algorithms and data structures are used.
• Cache the results of expensive calculations if they are likely to be used again.

Answer 2

Dwarf Fortress is not open source, and while there is a lot of conjecture and reverse engineering that can go into how that all works, I will instead focus on some basic techniques for optimizing a 3D (not 3D graphics, 3D world) roguelike of the same type.

As is the case with all video games there are a lot of smoke and mirrors that are creating the illusion of complexity from simple rules and systems. These range from using simple random numbers for aimless movement all the way out to pre-baking a high-level mesh of nodes for pathfinding.

Movement

Speaking of pathfinding, this can often be a very difficult problem to solve for large spaces like a DF map can be (as much as 768x768x64 IIRC) however the problem can be simplified and sped up in these ways:

• Pre-baked node network: When the map is created the world can be broken into chunks, and each chunk can have its exits and entrances mapped. When a chunk is updated, such as when a wall is built, only that chunk's network needs to be updated.
• Staged Pathfinding: Running a path over the whole map, cell for cell, would take a lot of time, instead you would pathfind over the larger chunk network, which maps all the connection between chunks, and then only run an intra-chunk path when moving from chunk to chunk. This does 2 things for you. It speeds up the pathfinding by breaking it up over many smaller pieces, and it also enables the unit to change direction part way along the path when a chunk updates. It would re-path across the large network if any of the nodes it needs to cross update.
• Random steering: When not moving to a goal, the unit need only walk aimlessly. Many roguelikes just move the unit in a random direction, which feels unnatural. Various steering techniques can be used, simple ones are favoring to move in a straight line and having less and less chance to move in the directions radiating to the back, which would have only about a 1% chance. So the unit would sometimes reverse direction entirely, but only rarely.

I won't cover the basics of pathfinding. Most roguelikes use A*, but there are other methods to skin the cat. Mmmm Cat leather..

Personal Tasks

One of the major things that makes DF units pop and feel alive is their personal goal list. In truth many roguelike games have this on a basic level. Essentially each unit has a list of desires (and for your dorfs, tasks they might pick up that you're asking to be done) and they will pick from them based on their personality (stats.)

Some tasks have requirements. Making a leather skirt requires the dorf be in such-and-such a shop that has X items. So those all are checked and added as tasks to their list. Simple as that.

Since most of the time a unit will be in transit, the checks for what units are doing can be very fast, only a few units will be making a choice at any given moment, and so overall there is no slow down even for hundreds or thousands of units. And remember, in DF everything from bees to troglodytes to trees are units.

---

In doing some additional research it is clear that, hilariously, DF is doing a terrible job of pathfinding in general. It isn't breaking the map into chunks, it is breaking the map into segments or areas that are connected, (which is better than nothing for sure) so my above assessment is even less an example of how DF works than I thought. :) Which is not to say that DF is anything less than amazing for a million other reasons.

It goes to show that what is important in a game is the game play. Not graphics, not great programing, not great writing, not great music, not even the interface; nothing else is even 1% as important as the game itself.

Answer 3

From this page:

Well [the pathfinding] 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.

I don't know if this is definitely how he prevents "flooding the map", but the usual way to do this in games is using an alteration to A* called Hierarchical Path-Finding A*, or HPA*. The idea is to break the grid into many fewer but larger chunks, then use A* to find the best path from each chunk to its neighboring chunks. You can use this to build a much smaller graph over which to run A* for each unit over.

You can also group those chunks into even larger chunks, which is where the "hierarchical" comes from.

This algorithm only finds near-optimal paths, but for games like Dwarf-Fortress that is usually ok. It is still guaranteed to find a path if one exists; and when there is no path, it will only flood-fill the smaller graph, saving an enormous amount of time.

There is also an abstraction of HPA* that deals with units which can go over some terrain but not others (such as cliffs, which air-units can traverse over but ground-units can't). It's called HAA*, and there is a very accessible article explaining it here.

You can read more about various pathfinding algorithms here.

Answer 4

If anything, it's the opposite - the whole thing runs on one thread and it's now hitting the point where that is becoming the blocking factor (last time I checked!)

The reason it's fast is that there's no fancy graphics. It's deceptive, but the main thing that slows stuff down is drawing things (think upwards of two thirds of a frame in AAA titles). Since dwarf fortress is quite basic, it devotes the rest of that time to doing interesting things.

Answer 5

I don't know how DF is coded but the amount of AIs doesn't really impress me because what people often oversee it that AI doesn't need precision. It's perfectly viable to do most stuff only every few seconds. It's also viable to use imprecise calculations. Imperfection saves a lot performance. You can run the decision making routine of 100 units every 100 ms, or you can run it for 1000 units every second, it will take the same amount of CPU time but well... you have 10 times the units.

Here is a simple example how one could handle a lot units:

int curUnit;
Array<Unit> units;
[...]
while([...]) // Game Loop
{
  [...game logic...]
  // process 10 AIs per Frame
  for(int i=0; i++; i<10)
  {
    curUnit++
    if(curUnit == units.length()) curUnit=0;
    if(curUnit < units.length())
      units[curUnit].processAI();
  }

  // Update the position of all units, this should be as optimized as possible
  foreach(Unit& unit in units){ unit.move(); };

  [...graphics...]
}

The AI will become less and less responsive the more there are, but the player probably will only notice it in extreme cases.