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?
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.
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:
The AI will become less and less responsive the more there are, but the player probably will only notice it in extreme cases.
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.
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:
I won't cover the basics of pathfinding. Most roguelikes use A*, but there are other methods to skin the cat. Mmmm Cat leather..
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.
From this page:
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.
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.