Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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?

share|improve this question
6  
Interesting question. Though I don't like the way it's phrased, since it would just be speculation to answer this question as worded. Anyway, you may have seen this article talking with Tarn Adams. Where they briefly cover path finding. –  Byte56 Jul 23 '12 at 13:45
14  
It absolutely produces noticeable slowdown once you have a complex tunnel topology and 100+ dwarves. –  Russell Borogove Jul 23 '12 at 17:48
3  
Yes, DF in my experience is incredibly slow in the scenario you describe. –  airza Jul 23 '12 at 17:48
2  
Destroy a primary stairwell and watch your framerate drop like a rock for a moment while every dwarf suddenly repaths at the same time. –  Mooing Duck Jul 23 '12 at 20:13
1  
I'm going to chime in and agree that DF is not the best example; in fact DF is well-known to suffer performance issues. –  Robert S. Feb 25 '13 at 21:13
add comment

5 Answers 5

up vote 83 down vote accepted

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.
share|improve this answer
    
+1 for this, for actually explaining what's going on, rather than wittering on about graphics like me. :) –  Matt Kemp Jul 23 '12 at 13:33
4  
To be fair, I gave you +1 too because I forgot about that aspect, and it's very true - take gfx out of the equation and it's like making computers 2x or 3x faster instantly. –  Kylotan Jul 23 '12 at 13:36
    
I've heard that DF is now multithreaded, but at least until recently, it was all done in a single thread. (It may still be, not sure) –  Mooing Duck Jul 23 '12 at 20:11
    
@MooingDuck It still isn't. –  Tharwen Jul 24 '12 at 10:01
add comment

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.

share|improve this answer
6  
+1 for cat leather –  LordScree Jul 23 '12 at 15:12
1  
1024X1024X32? Vertical is 128 or 256 I believe. Its far bigger than 32. –  Lawton Jul 24 '12 at 3:09
    
@Lawton I believe I am incorrect about the the max size, but the height is not that incorrect. I'm correcting it. I loaded the game and the embark I am on is only about 45 levels high. More might be 'simulated' but I don't have access to them for digging or building. –  DampeS8N Jul 24 '12 at 4:49
    
@DampeS8N I just loaded up an unmodded, medium map and was able to view from +16 to -156, around 180 levels. 40 level maps are the exception, not the rule. Even if you are only able to dig 40 of them due to being blocked by an aquifer or lava, its not relevant, because the area underneath is still populated with simulated fun. –  Lawton Jul 24 '12 at 13:03
    
@Lawton, my map only allows me to page through 45 levels. They are absolutely variable but I wasn't easily able to find numbers on how many each map has accessible. It also may depend on what version of the game we are using. In the end it isn't all that important for my answer. –  DampeS8N Jul 24 '12 at 13:05
add comment

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.

Hierarchical pathfinding

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.

share|improve this answer
5  
+1 Sweet info, and nice answer. –  Matsemann Jul 23 '12 at 18:07
add comment

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.

share|improve this answer
7  
One data point in favour of this is the OpenGL rewrite from a while back which I remember brought a massive frame rate increase. So even doing the simple sprite graphics that DF has efficiently made an impact. –  millimoose Jul 23 '12 at 15:13
3  
+1 Strip graphics = massive amount of spare time for gameplay computing –  Laurent Couvidou Jul 23 '12 at 16:52
1  
It is worth noting that DF's graphics are about as demanding as any modern indie 2D game. There are many textures, even if they are small and simple, and they can be spread over full HD monitors of real-estate. There aren't any flashy particle effects or what have you, but the raw "paint all these pixels" work is still present and due to the number of draw calls needed for the tiny tile sizes is actually a pretty big challenge to make performant. –  DampeS8N Apr 28 at 19:11
add comment

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.

share|improve this answer
    
There is a lot to be said for stepping through stacks of tasks that are not frame-level precise. AAA games often explicitly time-box each individual department in percentages of frames so that one department can't step on the toes of other departments. If the method for animating tree sway based on wind speed and direction is slow, fewer trees will be processed rather than eating up the budget of other teams. –  DampeS8N Apr 28 at 19:04
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.