Print

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

[rephikul]

From there, you're halfway to an elaborate spiral stair.

Thanks for all the help but I'm going back to good old staircases

[Theodis]

Well to understand how having a bunch of extra stairs will affect it you have to understand a little about how the pathfinding works.  A* is a slight addition to Dijkstra's algorithm.  With Dijkstra's algorithm the search starts from the source and evenly looks outward in all directions until it hits the destination.  This would be a bit inefficient because as you can probably imagine the paths leading in the opposite direction are most likely not going to lead to the best path(unless a lot of backtracking is the only way to get to the target).  So A* adds in an extra estimated distance to target factor into the search.  So it prioritizes tiles closer to the target in the search to those farther from it when picking tiles to check.

So then if there is a straight open path it's quite fast to find one as it'll just keep searching tiles closest to the destination and pretty much draw a line to the target.  However if that path is blocked it'll start checking the tiles closest to the target which were dead ends which'll probably be all the nearby tiles.  If there was only a minor obstruction it'll quickly get around it and still be good.  However imagine a U shaped barrier and your start of the path is at the top of the open end and the target is behind the bottom closed portion.  Well the A* pathfinding routine will first dart towards the target but bump into the wall.  Then it'll gradually fan out checking all the other nearby tiles which also happen to be the U and will end up searching the entire inside of the U before spilling out the edges and then darting towards the destination because now the path is mostly clear if no other obstructions were present.

Now let's apply it to stairs.  If you have one main pillar of up/down stairs and a dwarf is trying to path  from inside the fortress to the surface and the tile is roughly at the same location just mainly differing plane and the stairs are far off then from a pure distance perspective the dwarf is already near and walking in any direction on its plane is moving away from the target however to get to his destination the dwarf has to get to the stairs.  So then the search pattern will just fan evenly out from the dwarf sorta like Dijkstra's algorithm until it gets to the stairs in which case going up a level will get the dwarf closer than fanning out further so the searching moves up a level.  Now depending on how the search prioritizes vertical to horizontal movement after going up it may start searching the current floor by darting in the direction of the destination over moving up again.  If this is the case it'll dart to the x/y position nearest to the destination and fan out yet again before spilling up a level until it finally finds the path.  If the hallways were a bunch of up/down stairs then the dwarf would be able to dart towards the target both horizontally and vertically and waste much less time fanning out on each floor or in the better case with vertical movement prioritized just the one floor.

And since path weights were mentioned let's go over that.  If you have normal tiles weighted at 4 and high priority ones at 1 that means that the pathfinder will prefer moving on up to 4 high priority tiles over a single normal one and 16 high ones over 2 normal ones.  That's going in any direction so to get around 1 normal one that is at a choke point it might add many more than just 4 tiles.  This is why the configuration warns against excessively high values.  If you make restricted 60,000 and block off a region with it and a dwarf is trying to get in this region it will not stop them.  It just means that the pathfinder will probably search the entire accessible map before evaluating all the restricted tiles and finally finding a path.  However it can also work positively.  If a dwarf is trying to find a path and it isn't behind a restricted area you've effectively blocked off a region from being checked at all.  Similarly it can be used positively to guide the pathfinding.  Since I typically have one major hallway stemming out from the stairs leading to major sections I set it to high so that the pathfinding prioritizes getting there and searching along the main path rather than searching all the minor sublet areas which likely do not lead anywhere unless they are the destination.  By setting high and normal to the same you're just making them equal and removing functionality from yourself.  Better to just keep them different and not use one or the other leaving yourself with the option to use a high priority section if the need comes up.

Ok so in short.  The more possible paths the better.  The pathfinder doesn't evaluate them all just uses the first it finds(which is always the best given how A* works).  So if you turn your fortress into a big block of stairs pathfinding will run super fast it just won't be aesthetically pleasing.  Structuring main hallways which connect the fortress's segments and setting it to high priority will also aid the pathfinder and speed things up and will have a less negative impact on the look of the fort.  Plus it makes sense .

[Urist Da Vinci]

And since path weights were mentioned let's go over that.  If you have normal tiles weighted at 4 and high priority ones at 1 that means that the pathfinder will prefer moving on up to 4 high priority tiles over a single normal one and 16 high ones over 2 normal ones.  That's going in any direction so to get around 1 normal one that is at a choke point it might add many more than just 4 tiles.  This is why the configuration warns against excessively high values.  If you make restricted 60,000 and block off a region with it and a dwarf is trying to get in this region it will not stop them.  It just means that the pathfinder will probably search the entire accessible map before evaluating all the restricted tiles and finally finding a path.  However it can also work positively.  If a dwarf is trying to find a path and it isn't behind a restricted area you've effectively blocked off a region from being checked at all.  Similarly it can be used positively to guide the pathfinding.  Since I typically have one major hallway stemming out from the stairs leading to major sections I set it to high so that the pathfinding prioritizes getting there and searching along the main path rather than searching all the minor sublet areas which likely do not lead anywhere unless they are the destination.  By setting high and normal to the same you're just making them equal and removing functionality from yourself.  Better to just keep them different and not use one or the other leaving yourself with the option to use a high priority section if the need comes up.

Let's assume a 1-dimensional case where normal pathing cost is 2 and high pathing cost is 1:

Code: [Select]

        A             B
9  8  7 6 5 4 3 2  1  0  distance from B
6  4  2 0 2 4 6 8  10 12 normal pathing cost from A
15 12 9 6 7 8 9 10 11 12 tile total cost (if normal)


Code: [Select]

        A            B
9  8  7 6 5 4 3 2 1  0 distance from B
3  2  1 0 1 2 3 4 5  6 high pathing cost from A
12 10 8 6 6 6 6 6 6  6 tile total cost (if high)

In the normal case, doesn't the pathfinding function consider the tile to the left of starting point A because it has a total value of 9, whereas tiles closer to B have the values 10, 11, and 12? If B is farther away, it checks a sphere around point A even if there is a straight line path to B. In the high case, it never looks in the wrong direction unless it encounters an obstacle.

[Trouserman]

By setting high and normal to the same you're just making them equal and removing functionality from yourself.  Better to just keep them different and not use one or the other leaving yourself with the option to use a high priority section if the need comes up.

It does remove functionality, but since the normal pathing cost of 2 allows more backtracking even when there is a direct path to the destination, setting normal pathing cost to 1 can make searches more efficient if you're not using high traffic designations.  Since it is always possible to set the weights back to normal, the functionality can be regained at any time if the need does come up.  Most of the time, I just don't want to be bothered setting and maintaining invisible traffic designations as I expand my fort.  However, you make a good point about prioritizing finding the right level before scanning the halls, so a high traffic designation for just the stair well might help more...  Though neither one makes a lick of difference in my current fort.  Oh well.

[therahedwig]

To dumb the A* stuff down even more:

Asume each step a dwarf will take in a high-traffic area will cost him 1 coin.
Each step in a normal area will cost him 2 coins, in a low-traffic area 3. Restricted areas will require him to pay 25.

Ofcourse, the dwarf wants to pay as little as possible, therefore it'll try to move through a high-traffic above low-traffic areas, so he'll have to pay less.

However, NO MATTER WHAT, HE HAS TO GET TO HIS DESTINATION.
That means that unlike burrows, if a dwarf is isolated from the rest of the fortress through a strip of restricted traffic area, he will move through that area none the less if he has to be on the other side no matter what the cost. Of course, in actual dwarf fortress your dwarf won't really have to pay money for his traveling.

How is this useful? Well, for starters you can make hospitals, private quarters and tombs restricted. This'll stop the dwarfs from sleeping in beds in the hospital for example. You can then assign the big hallways you made with high-traffic, so your dwarves will prefer them to that little thin hallway you dug to get you trapped miner out.

As for the staircases... I guess it would improve the speed because there's shorter paths, but on the other hand there's more paths calculated...

[Zidane]

I don't know if dwarf fortress is filled with geniuses or gigantic nerds.

I should probably stop worrying and love the magma.

[Theodis]

As for the staircases... I guess it would improve the speed because there's shorter paths, but on the other hand there's more paths calculated...

A* stops as soon as it has found a path and doesn't evaluate all potential paths.  If there is a short direct path it'll take it and it won't take much time finding it.  The less obstacles, less required backtracking, and the more direct paths the faster it's going to go.  Stair cases likely just add in more edges to the graph and doesn't generate more paths to get from A to B across several height levels.

[Theodis]

In the normal case, doesn't the pathfinding function consider the tile to the left of starting point A because it has a total value of 9, whereas tiles closer to B have the values 10, 11, and 12? If B is farther away, it checks a sphere around point A even if there is a straight line path to B. In the high case, it never looks in the wrong direction unless it encounters an obstacle.

First off there are a number of ways to come up with an estimated distance and how optimistic the guess is will vary the node selection.  An optimistic guess where the estimate is at the minimum cost(like your example) will favor searching nodes going in the direction of the target.  An pessimistic guess where the estimate is assuming maximum cost will end up favoring low cost edges more often than ones in the direction of the target.  The guess of course can lie anywhere inbetween or even off the scale or even negative(in which case the pathfinder will stupidly favor checking nodes that go in the opposite direction of the target and will probably search the whole graph).  I have no idea what Toady is using for the estimate or if it's even been mentioned but it would definitely have an impact on how influenced the pathfinding is based on the weight values of the edges.

But in your example yeah if that's how it does the distance estimate then it would check the opposite direction some however by making normal and high equal you spoil your chance at helping the pathfinder by prioritizing areas that are more likely to connect a multitude of closed off areas that don't directly connect to each other with the exception of a main tunnel.

[Brisk]

Well, I did the experiment. First I built a fort with a central staircase. 125 fps. Then I built stairs in the main hallways. 145 fps. They are certainly taking less steps to go up/down a floor if they what they want is just one z-level down.

However, I just now realized that my fps increase might be due to me using stones to build the stairs.

For me the deciding factor is not really fort design but number of objects. Once I get above a certain number of dorfs and objects it doesn't seem to matter how my fort is laid out my fps just grinds to a halt. What I do is set a population limit, I am careful not to overproduce food or trade goods, and I only mine out what I need to.

[Trouserman]

First off there are a number of ways to come up with an estimated distance and how optimistic the guess is will vary the node selection.  An optimistic guess where the estimate is at the minimum cost(like your example) will favor searching nodes going in the direction of the target.  An pessimistic guess where the estimate is assuming maximum cost will end up favoring low cost edges more often than ones in the direction of the target.

In order for A* to guarantee finding you a shortest path, the cost heuristic must not exceed the best path cost.  Therefore, for correctness it must assume a minimum cost path could be available.

Also, a heuristic which assumes maximum cost would not favor low cost edges; it would make apparent distance to the target more important.  To favor low cost edges more, you need an even more optimistic heuristic.  And when you favor edges of any cost over apparent distance to the target, you get the behavior Urist Da Vinci described.

[gtmattz]

I don't know if dwarf fortress is filled with geniuses or gigantic nerds.

Isnt that statement a bit redundant?  I would think that genius intellect would come with an extremely high risk of 'nerdus giganticus'.