Print

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

[rucksackjack]

In the past, I've always designed my fortresses with small walled-off stockpiles, each workshop in a different room, etc. Recently I tried using a new strategy of putting all the workshops in a big, wide-open room, and doing similarly for stockpiles. I also made the halls very wide (5 tiles), which I've never done in the past.

Now, this is the odd thing: I've never had framerate issues in the past, but this layout seemed to cause large amounts of stuttering, even with only seven dwarves running around. I thought it might just be some feature of the landscape that was doing it and not my layout, so I restarted in a different place. Nope--the fortress layout still seemed to cause lag.

This is completely contradictory to what I've heard about improving framerates, so what gives? Does the game hate it for some reason when I create very big rooms with many stockpiles/workshops, even though this should ease pathfinding issues? Am I just going insane?

[Oldin]

Large hallways, huge rooms, these all increase the number of possible paths your dwarves may take when walking from a to b, thereby increasing the calculations needed to optimize the path. While it is likely they will get to their destination faster in game time, chances are it will take longer in real time.

[rucksackjack]

But http://www.dwarffortresswiki.net/index.php/Maximizing_framerate says this: "Narrow paths and bottlenecks cause the pathfinding algorithm to repeatedly recompute a faster route for each dwarf (and pet) as the paths empty and clear. Use large hallways and multiple stairways to connect any two spots where lots of dwarves will want to be."

I'm being whipsawed. Which is it? Are large areas good or bad for framerate?

[uioped1]

Think about it this way:

Consider a very small labyrinth with a one-tile wide passageway shaped like a donut.  A thirsty dwarf is there, a few steps away from a barrel of booze.  He could go the long way around or the short way, so the game has to check which way will be better.  Once Mosus has figured out that he should go the short way, he sets off, and doesn't have to search for paths to the booze anymore.  He takes a step though, and all the sudden  a kitten drops through a hole in the ceiling ahead of him.  Now he has to reconsider.  Should he try to crawl under the kitten or should he go the long way around?  Supposing he decides to take the long way, he'll have to reconsider again if the kitten steps across the barrel.

If the passageway was 2 tiles wide, here's how the scenario would be different:  The initial search would be more difficult, because for every one step down the passageway, Mosus has to decide if he should go diagonal, or straight ahead.  Once he's decided on a path, however, it's really easy to find a new one once there's an unexpected obstruction: The search algorithm can be optimized to notice that there's a readily available path one diagonal step away from the chosen path.  Since a diagonal step is just as quick as a step straight ahead, Mosus knows it's not going to take him any longer to get there than the way he was going, and since he knew the way he was going was the best available, he doesn't have to keep searching.

Notice what happens if we then add cross passageways to turn our donut into a spoked wagon wheel.  Instead of deciding from two original directions he must choose whether to cross the wheel at each spoke, and if so, whether to go straight across, or turn at the center (and which way?)  What you've done with the big open rooms is essentially keep adding spokes until there's no more rock.  This means that each dwarf taking a step has to make choices.  A lot of choices.

Granted, you can eliminate many of those choices without fully investigating them, but the fact remains that there are a lot of possible ways to get from A to B.  Another problem is that by increasing the scale of your passageways, you've also probably made the distance between things larger, which means the paths are longer, and the difference between a near miss and a hit doesn't get discovered until you've spent more time looking.

Basically, what you need to do is provide some assistance to the initial search by saying don't look for a path form here to there, that's just stupid.  (do this by placing a wall or channel or something.)  Just don't create bottlenecks where all the dwarves get funneled through one small set of tiles, because this sets all of them looking for new routes.

So anyway, that's pathfinding in a nutshell.  I know that was a complicated answer to a simple question, but hey, I'm a computer scientist.  If you want to know even more, look up A* on wikipedia.

[rucksackjack]

Thank you! That is a much more helpful response than my question probably deserved. I'll stick some walls in here and see if things improve, as I'm sure they will.

Thanks again.

[Jude]

Whoa! Very interesting explanation, although hard to understand for a computer ignoramus. (although it probably isn't helping that I took some Ambien for my insomnia and it's finally beginning to kick in)

So in general, what would you say is the best layout for good FPS? Two-wide passageways and medium-size rooms?

[Core Xii]

Another possibility is to use traffic designations. Low-cost designations cause dwarves to consider them first, contributing to not having to explore pointless tiles.

[Tcei]

I find 2-3 tiles wide are  the best options. I use 3 wide hallways leading to my main  high traffic areas like workshops, stockpiles, and dinning room. This way there's plenty of room for the dwarves to maneuver around each other and not get ran-over by a legendary especially at higher populations. I'll use 2 for those areas that dont see alot of traffic. All my workshops are hosed in 3x3 rooms with one side completly open to the hallway. I'm still experimenting with sizes of stockpiles...

[iskurthi]

Another possibility is to use traffic designations. Low-cost designations cause dwarves to consider them first, contributing to not having to explore pointless tiles.

I had a fortress layout with 3-tile wide central hallways and a loose grid of rooms. I just tried setting all the main hallways high-traffic and some of the grid doorways as low-traffic and there was an immediate framerate improvement just from that.

[RogerN]

Has Toady ever said that he's using A* for pathfinding?  I've heard him mention that his pathfinding could use some more optimization, but never any mention of the exact algorithm.

Assuming that Dwarf Fortress uses A* or something similar, it's not necessarily a big performance hit to create large open areas.  If that were the case then you'd expect to see huge framerate problems on almost all above-ground fortresses.  The A* algorithm does not consider every possible route to the destination unless it has to.  In fact, by open areas you actually reduce the number of iterations that A* must perform before finding the optimal path.

The thing that will really kill your pathfinding performance is having a bottleneck (door, stair, etc...) between two points in an unexpected location.  For example, consider a dwarf who wants to go to the dining room.  The dining room is west of his position and two levels up.  The A* algorithm will try to "guess" the best route to the dining room by assuming that he needs to go west.

But what if the staircase is actually east?  That can slow down the pathfinding in a big way, since it won't even try going east until it has exhausted most of the possibilities on the west side.  Centralized staircases, despite their popularity, are a good example of how to drive the A* algorithm nuts.  Fortunately most forts which use centralized staircases tend to use only a small area on each level.

Note that if Dwarf Fortress does NOT use A* then all of the above is moot, and open areas may indeed cause pathfinding lag.

[Great Cthulhu]

DF does use A*, according to Toady in the the gamasutra interview.

Interestingly, he also states that he uses the street distance heuristic in combination with A*. If that means the Manhattan Distance, and my understanding of A* is correct, then this is not optimal. Dwarves are able to move diagonally and not just at right angles. This means that the actual optimal distance may be less than the distance according to the heuristic. (A dwarf can go NE in less time than it takes him to first go E and then N.) This breaks the optimality guarantee of A* (as the heuristic is not admissible), which in practical terms means that performance will suffer. Euclidian distance would be more appropriate. Or the maximum of the X and Y distance, if taking a diagonal step takes no more time than a step in the X or Y directions. (Movement in one axis is "free" as it can be combined by moving along the other axis by going diagonally.)

If what I said above is correct, then I would expect performance to suffer when dwarves can move both diagonally and in straight angles. That would explain the performance hit in areas with large open spaces. It wouldn't be an issue if dwarves can only go diagonally or at straight angles.

Anyone see any flaws in my logic? I could be spouting nonsense due to sleep deprivation.

[chris_acheson]

This breaks the optimality guarantee of A* (as the heuristic is not admissible), which in practical terms means that performance will suffer.

A* can be used with non-admissible heuristics, which will cause it to sometimes choose a longer-than-ideal path.  However, this means that it's ending the search early, so it ends up being more computationally efficient.

[Great Cthulhu]

Ah, crud. I mixed up suboptimal cost performance and suboptimal computational performance. I knew I made a mistake somewhere. Thanks for pointing it out!

More thought on this is required after I get some sleep.

[Great Cthulhu]

One more sleep-addled observation. (To be consumed with copious amounts of salt.) If DF uses A* and the Manhattan heuristic in open spaces (as well as everywhere else), then why is there a framerate drop in such areas? The algorithm should find a straightforward path without having to backtrack at all. At worst, the path will be suboptimal due to the heuristic not favoring diagonal movement over movement in straight angles.

Also, now that I think of it, I've often seen dwarfs move diagonally in open areas. A* with the Manhattan heuristic should have dwarves move in straight angles a lot. Unless ties are resolved by preferring diagonal movement. Hmmm. Food for thought...

Edited to be less stupid. (Hopefully.)

[Fringe_Worthy]

One other possibility could also be related to failed A* paths.

Lets say there is no path from a -> b.  This is a global problem. On the other hand, A* (And pretty well all other algorithms) are local searches.  A* is not a god who can gaze down from on high and say "Hey, there is no way from here to there!"

So, A* will keep on exploring until it reaches an abort situation (Hey, if any path is more then 1000 tiles... stop) Or it completely explores the entire reachable area and it no longer has a list of tiles to explore.

Your blind dwarf is standing in front a door. The door is locked. Behind the door is some beer that is begging to be drunk.  Why not  stop early?  Someone mentioned that if you go to the bottom of the map, through that maze, you'll find a pillar of stairs up to a sky cloud maze construction that leads over to that side of the map, which runs through a vertical maze, and finally to a tunnel  that goes above that locked room, and low there is a set of stairs down into that room.   Oh, there is a savage bear in that room that will eat the dwarf, but that's just too bad.

Wouldn't you imagine all routes possible to get to your beer if you needed to have that beer?

(Note, sometimes you can do the reverse. Go from the beer to the dwarf. That handles the case of the beer being locked up.  Of course, if the dwarf is in prison, you're just as messed up.)

Build your fortresses for dwarves whose legs below the knees are torn off and whose eyes have been plucked out, and who will crawl any distance for that beer. 

---
One thing to maybe look at is: How do we know to get item X into stockpile A B or C? (Though, I think we've had people complain about it just doing: If stock pile wants a stone, go through the item  list picking the last stone created? If it does anything .. clever.. you might have fun issues?