Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[helf]

This is what I plan on doing in a few months when I have some spare cash I will pst my results when I do it. heh.

Call me a dork but I'm actually considering doing this myself. UNfortunately I'm not an overclocking genius so please do post your results!!

Sure thing. It's going to run me around $600 for the project, so I'm /hoping/ to have the monies by May. Being a broke college student kinda blows

[ral]

Maybe I'll get this to save some money:

http://www.itworld.com/hardware/138740/asus-motherboard-box-doubles-a-pc-case

[Niseg]

Don't overclock a Pentium 4!  it's just stupid today because other than the fact it's an oven,  it's performance per clock is about half of core 2 . It's better to just get a new pc . Sandy bridge is a good choice especially K series with good cooler so you can push the CPU - I heard 4.5GHz is easy to do on air.

Sandy bridge also has better per clock performance (about 17%) than previous gen and I think previous gen did better than one before it. I'm guessing at  25% better per clock performance compared to my core 2 . so If I'm getting 32-33 fps with 208 dwarves and a "big basement" 10k+ items and 225 animals (not sure if they are all caged). On a 2500@4.5  you should get about 56 FPS if not more due to lower overhead on memory access.

[Quift]

If you really want to minimize OS cycles you should of courserun a smaller linux. XP is still windows, thus something of a resource hog.

[rephikul]

I believe dual core architect and up has resolved that problem.

[ahonek]

With regard to the overclocking idea:

I currently run an AMD hex-core 2.8ghz. The multiple cores aren't important for DF so I'll ignore that. At 2.8ghz, I notice low fps around 50 dwarves, and by the time I get to 100 dwarves I don't want to play the fort anymore due to sluggishness.

I've overclocked to 4.0ghz (about a 40% increase) and now I can get to about 70 dwarves before I notice the fps, and around 100 dwarves again I stop playing due to speed. How could this be? Wouldn't a 40% increase in speed increase my playable dwarf cap by 40%?

The answer is no, because the complexity of the algorithms in this game is not linear with dwarves, or even linear with the number of items on the map. It probably grows by at least n*log(n), given that there is definitely sorting involved (and sorting is minimum n*log(n)).

My point is that no matter how fast your CPU is, you will eventually die a framerate death because there just does not currently exist a personal computer that can run DF at high framerates near the default dwarf cap. So don't waste money trying to build a fast computer if its only purpose is Dwarf Fortress - you will be disappointed.

The best ways to avoid FPS deaths are documented earlier in this thread. The biggest (and fastest-growing) CPU burden is pathfinding, so the best way to keep your FPS high is simply to reduce the "magnitude" of your fortress. By "magnitude" I am referring to amount of earth dug (more possible paths -> longer pathfinds), the amount of items created (more items -> longer pathfinds), and the amount of animals and dwarves (more pathfinds -> more pathfinds).

When in doubt, atom-smash all the stone you don't need. Even just that will speed things up a lot.

[helf]

If you really want to minimize OS cycles you should of courserun a smaller linux. XP is still windows, thus something of a resource hog.

Myth. Mostly.

I run lightweight linux distros (vector, arch, custom debian installs, etc) and a stripped xp install isn't any more of a resource hog, honestly. At least 20mb difference in ram usage isnt going to make any difference when you have 2-4gigs and you also get to more easily run all the assorted DF accessory apps.

Yes, you could get all anal and make a custom linux install that uses 5MB of ram on bootup and still manages to run DF, but thats more hassle than most people wish to go through You can have XP using 45-60mb of ram on bootup with ease.

[Quift]

Also, on maximizing FPS. The biggest impact on FPS is normally pathing. So minimizing pathing is a worthwhile pursuit. This means that you wish to shorten travel as much as possible. The most common way to do this is by making your fort as compact as possible, and heavy use os Z-levels.

But there are quite a few seldom used ways of doing this. The biggest one is minimize the number of dwarves who do travel at all. Workshop dwarves should more or less eat and sleep in their workshop, with each having a separate burrow, with his own workshop, bedroom, and diner. I usually make it a nice "house" with appartments, in the cellar there is the stockpile, above is the workshop, and on top is the bedroom and dining room.  If you plan this out correctly dedicated haulers are then bringing in all supplies. Haulers should also be specialized, in separate burrows for separate production chains. So that they stay in their wing of the fort, and look for jobs there. This is intended to avoid dwarves taking jobs on the other side of the map and heading over there. Plan this out from the start to get a nice production chain going on, since even then it is a pain to set up. You could also add separate communal rooms in each wing, meaning that dwarves from different wings interact less. One of the points of that is that when they marry, they hopefully stay in the same wing. It also feels more thematic with dwarves living in private dwellings on top of their workshop, and associating only with their guild, instead of dwarves living in vast residential complexes, and working in factory style production complexes.

The point here is that paths are recalculated every tile. So the longer (in time) a dwarf has to travel, the more dwarves will path at the same time., and since paths are more complicated the longer they are, shorter paths are really having an impact on FPS.

Minimize stockpiles to limit the amount of stuff lying around. This ties into the former point. If you set everything up correctly you should have small and very specilized stockpiles. So that less stuff travels, and travels less far. This also helps.

[Vastin]

Ok, so as noted previously, Pathfinding is generally the biggest killer in older forts.

Each dwarf needs to find paths every time they want to go somewhere or get something. The costs here are (roughly):

1) Determine what object you want to get.

In forts with thousands of pieces of stone or other objects this can take a while, but people tend to make this out to be a bigger problem than it really is - large list searches can be quite fast. Nevertheless, designating a lot of your loose junk stone and other trash to be (F)orbidden can speed this up a bit.

2) Find a path to the object you want.

Ok, this is where things get really expensive. Anyone familiar with A* path routines knows that the bigger and more complex the search space, the uglier this gets, quickly. For those unfamiliar with A*, it works a little like filling the map with water, starting from the spot your dwarf is now, spreading out along every available path until it the flow finally reaches the ONE spot you are looking for. Think about how you would restrict the flow of water flooding your fort, and do the same for pathing (ok, except this 'pathing' water flows up, down and in all directions).

Dwarf Fortress is actually pretty good about segmenting its pathing spaces to reduce costs - IF you help it out a bit. Pathing does not search through locked doors, or outside of burrows that a dwarf is assigned to.

- Don't create too many different ways to get to the same place. A* will tend to search ALL of them to try and get there. Think in terms of efficiency - if your dwarves can get there efficiently, then A* will also tend to run more efficiently.

- Think vertically. A lot of players have a tendency to build huge, sprawling horizontal labyrinths that take forever to get anywhere. Think in terms of building in a CUBIC format and you'll compress a 200x200 fortress that can take up to 300 steps to get from point A to point B, and reduce it to a 34x34x34 space that takes a maximum of about 50 steps to get anywhere. That's huge savings both for your Dwarves and A*. It's also an interesting challenge to force yourself to think in completely 3-dimensional terms.

- Make your corridors wide enough to prevent congestion, but not any wider. 1-space corridors are fine for any infrequently travelled space, and 2-spaces fine for all but the most heavily trafficked. Wider than that just increases pathing costs without much benefit. I'll admit I often use 3-wide corridors for aesthetic reasons, but I know that I pay for that.

- Isolate any unused sections of your fortress. And by that I mean your mines and storerooms. Most fortresses will choke to death the moment you start MASS MINING operations underground, digging tunnels through miles of rock in all directions. This is just terrible for the poor pathfinder - but of course, you need to mine. Divide your mines into sections and seal those tunnels off with locked doors as you finish exploring and exploiting them. This will make a huge difference (it also puts all those loose rocks out of play). If your dwarf can't get there, it's off the grid and you no longer pay the pathing costs for it.

- Isolate Caverns. Opening caverns adds a huge new pathing space all in one go when you penetrate them. When you breach a cavern, create a walled and door-sealed section that your Dwarves are restricted to save for when you are actively exploring it. This knocks most of the cavern space off the path map, and also helps keep the giant monsters from reaching your fortress. Note that flying monsters eat up vastly more pathing time inside caverns because there is so much cubic volume for them to consider, but you can't do anything about that.

- Doors, Doors, Doors Locked doors isolate useless rooms, seal off expensive alternate routes, and generally allow you a great deal of fast control over pathing. Use them. A lot.

Other Mechanisms

Using the traffic designation tool causes the pathing 'flow' to spread much faster through your high traffic designations, and much slower through low traffic or restricted designations. This is good for reducing the cost increases that can be caused by creating alternate routes, but using them effectively requires a more robust understanding of A*, so again I suggest door management for most cases.

Burrows are a similarly powerful pathing restriction tool, as dwarves supposedly will try not to search for paths outside of them, but there are two problems, first, burrow assignment is still confusing as hell, and second, I'm not really sure that it restricts pathing enough to really make as much of a difference as doors or walls do. I just don't know enough about that system to judge it properly.

[Vastin]

To give you a slightly better sense of the costs involved in an A* search and how they proliferate when spaces are open rather than confined, imagine that you are trying to reach a rock 10 spaces north of your current position, but in three completely different spaces:

1) You are at the end of a 1-space wide, 10-long corridor. At the other end is the item you want. In this case A* will find the object in exactly 10 steps, which is as good as it is ever going to get.

2) You are at a 4-way intersection with the corridors going off 20 spaces in all directions. The item is 10-spaces north. In this case you are going to find the object in about ~40 steps (A* has to search down all 4 corridors at once - it usually doesn't make any assumptions about what direction the object is in!)

3) You are standing on the surface, with nice green grass in all directions. The item is 10 spaces to the north. In this case basic A* is going to find the object in approximately ~400 steps - it has to search the entire square volume around you in concentric fashion before it finds the object! This is why a large starting embark area can have such dire consequences for pathing. Srlsy. 0_o;

Now, there are A* optimizations that can allow for much faster searches in some conditions like the open field, such as favoring steps that move towards the object, and making ones that move away from it more expensive, for example - but those search optimizations are making assumptions that might make other searches much MORE expensive, so there are usually trade-offs for this kind of thing.

There are also multi-layer A* concepts where the entire search space is broken up into large sections of 'geometry' that can be stepped through extremely quickly to get close to where the target is, but these implementations are quite complex and can take up a fair amount of memory to boot, so I have no idea if they are used in DF.

In a game like DF where the paths are frequently convoluted, I suspect that A* makes relatively few assumptions - but you'd have to ask Toady about the details.

[Vastin]

The point here is that paths are recalculated every tile....

Is that really the case? They certainly shouldn't have to!

As long as the target isn't moving/gone and the dwarf doesn't hit an unexpected obstruction in its planned path, there really isn't any reason they can't remember a path once they've searched it - and storing a dwarf's path in memory is way, way less expensive than reserving the memory (not to mention CPU) for them to recalculate every step.

On the plus side, if they ARE doing that it means there is a hella lot of easy optimization that Toady could still do for pathing. <shrug>

[Granite26]

If you want to know how often a dwarf updates it's path, watch it chase a goblin.

You will often see the dwarf run 3-5 steps in the wrong direction after the goblin moves.  Alternately, lock a door and see how long it takes to get the job cancelation.

As far as A*, I've been under the impression that it does prefer to move straight towards the item, but I'm not sure.  Maybe that's just the top of the 'X moves or less' pile.

I'm a big fan of separating out the above ground pathfinding from the below ground.

[Vastin]

If you want to know how often a dwarf updates it's path, watch it chase a goblin.

You will often see the dwarf run 3-5 steps in the wrong direction after the goblin moves.  Alternately, lock a door and see how long it takes to get the job cancelation.

Yeah, that was my impression as well - that paths were recalculated, but only occasionally.

In a highly optimized system, each target object would hold a list of anyone currently pathing TO it, and on moving or changing state it would inform those interested parties, telling them they need to reconsider their path or job.

Once you do this you remove the need for the pathing entity to EVER re-calculate their paths unless they are told to do so, or they hit an unexpected obstruction (another moving enemy, recently locked door, etc). They can also this flag to cancel build/pickup/kill orders the moment they are invalidated instead of having to wait until they get there to figure out there is a problem.

[JmzLost]

Another good test for repathing is digging a grid of 1-tile wide corridors (I used to use 1 tunnel every 10 spaces for exploration).  It looks like the dwarfs will generate a path to their destination, and then break it up into a series of way-points.  At each waypoint, they check that the path to the next point is clear.  If it's not, they recalculate their path to the waypoint, not to the final destination.  I've had dwarfs take the long way around at the end of their path and approach their destination from behind, walk past it, and turn around to go from the last waypoint to the final destination.  Between waypoints, they only check to see if the next tile is blocked, which is why you'll get dwarfs walking over each other, and why they'll occasionally "run away" right through a goblin ambush.

Posted by: Vastin
In a highly optimized system, each target object would hold a list of anyone currently pathing TO it, and on moving or changing state it would inform those interested parties, telling them they need to reconsider their path or job.

I think DF does this, items that move will cause immediate cancellations of any jobs associated with them, and as above, I don't think the dwarfs recalculate their entire path at every step.

As for flyers in the caverns, the best bet is to wall off the caverns right at the opening, so random critters can't get into them.  Then treat the rest of the cavern as part of your fort, and wall off any unused spaces to reduce dwarf pathfinding.  Of course, this gives a temporary hit to FPS while your dwarfs path to the stone, then to where they need to build the wall, etc.

Multiple small booze/food/dining hall areas near where dwarfs are working/sleeping can also help, since they won't need to search the entire fort for the one stockpile that's 200 tiles away.  May be some negative impact from the stockpiles searching for items, though.  I'm not entirely sure how those are generated, and when the game checks for a path between an item and the stockpile it belongs in.

JMZ

[Lemunde]

If you want to know how often a dwarf updates it's path, watch it chase a goblin.

You will often see the dwarf run 3-5 steps in the wrong direction after the goblin moves.  Alternately, lock a door and see how long it takes to get the job cancelation.

Yeah, that was my impression as well - that paths were recalculated, but only occasionally.

In a highly optimized system, each target object would hold a list of anyone currently pathing TO it, and on moving or changing state it would inform those interested parties, telling them they need to reconsider their path or job.

Once you do this you remove the need for the pathing entity to EVER re-calculate their paths unless they are told to do so, or they hit an unexpected obstruction (another moving enemy, recently locked door, etc). They can also this flag to cancel build/pickup/kill orders the moment they are invalidated instead of having to wait until they get there to figure out there is a problem.

That's definitely the way it should be. However it wouldn't work for pathing to other creatures since they tend to change position constantly. There's plenty of room for optimization all around and I think it's something Toady should seriously consider before moving on to newer features.