Print

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

[shadow_slicer]

A general tip to improve pathfinding for people who don't want to make use of the in-game traffic zones.  Open up the init.txt and change the weighting on the "normal" zone from 2 to 1.  This will basically double the effectiveness of all your pathfinding, but make high traffic zones meaningless.

That should not make a difference. A grid of cost 2 squares should behave the same way as a grid of cost 1 squares. Its the interaction between different costs that makes the difference. Such is theory, anyway, if you have done any testing then let us know.

It actually should make a difference. The heuristic function employed by the A* algorithm to determine the lowest possible cost to the destination from a given point has to use the lowest cost possible for each tile which is 1. This means that if every tile has a cost of 2, it will end up exploring areas that actually aren't very promising just because they could *possibly* connect to a high traffic zone to the destination. By setting the normal tile cost to 1 you avoid that extra overhead.

Even if you do use the zones, it may be better (framerate-wise) to swap the costs of normal and high-traffic zones. Then you can still designate highways: just paint "high-traffic" in the areas around the highways you don't want dwarves to go through.

[Thief^]

The heuristic could use 2 as the tile cost.

Which would cause it to explore high traffic zones which head in almost the right direction in preference to a normal priority route which heads in exactly the right direction. The resulting paths wouldn't be the shortest possible, but they would be close enough.

[Yagrum Bagarn]

It actually should make a difference. The heuristic function employed by the A* algorithm to determine the lowest possible cost to the destination from a given point has to use the lowest cost possible for each tile which is 1. This means that if every tile has a cost of 2, it will end up exploring areas that actually aren't very promising just because they could *possibly* connect to a high traffic zone to the destination. By setting the normal tile cost to 1 you avoid that extra overhead.

While it's been some time since I had Data Structures and Algorithms, I believe that is correct.

[Retro]

I don't think the door trick's been mentioned here - build a door somewhere useless or something, then just quickly lock and unlock it every now and then. Pathfinding gets reset. Annoying, but a workaround.

[Lemunde]

I don't think the door trick's been mentioned here - build a door somewhere useless or something, then just quickly lock and unlock it every now and then. Pathfinding gets reset. Annoying, but a workaround.

I'll keep that in mind.  I noticed this happened when I toggled wall grates on and off but it didn't seem reliable.

[PencilinHand]

A general tip to improve pathfinding for people who don't want to make use of the in-game traffic zones.  Open up the init.txt and change the weighting on the "normal" zone from 2 to 1.  This will basically double the effectiveness of all your pathfinding, but make high traffic zones meaningless.

That should not make a difference. A grid of cost 2 squares should behave the same way as a grid of cost 1 squares. Its the interaction between different costs that makes the difference. Such is theory, anyway, if you have done any testing then let us know.

It actually should make a difference. The heuristic function employed by the A* algorithm to determine the lowest possible cost to the destination from a given point has to use the lowest cost possible for each tile which is 1. This means that if every tile has a cost of 2, it will end up exploring areas that actually aren't very promising just because they could *possibly* connect to a high traffic zone to the destination. By setting the normal tile cost to 1 you avoid that extra overhead.

Even if you do use the zones, it may be better (framerate-wise) to swap the costs of normal and high-traffic zones. Then you can still designate highways: just paint "high-traffic" in the areas around the highways you don't want dwarves to go through.

No, it won't, not if every tile costs the same.  Each tile's travel cost is 1*weight, where weight is set by the traffic zones  and normal is weight 2, high is weight 1, etc. Giving normal a weight of 1 will just nullify the usefulness of high-traffic zones. The ratio of the weights for valid tile paths is what is important, not the absolute value of the weight of any given tile.

Picture a Y split where either path is equally valid to reach the destination but give one path a per tile weight 3 times that of the other be it 1:3, 2:6, or 333:999 it doesn't matter.  The path with the lower weight will be preferred at a rate of 3 tiles to one tile of the path with the higher weight.  Giving all paths the same weight(including the path to reach the Y) be it 1:1, 2:2: or 1000:1000 won't matter because there is no advantage for going with one compared with another.

The only way an advantage could be achieved would be by picking weight numbers that either simplify the mathematics, and we don't really know enough to do that, or by using a little understanding and being smart about laying down high and low traffic zones.  There is a fringe case where a really, really, REALLY long path(path length of over 16000 tiles minimum for normal weight of 2) might conceivably exceed the size of its container.  Realistically we aren't going to see that kind of case(a long path in DF is a few hundred tiles), read up on how int variables work if you are interested.

[andrewas]

Actually, no, I was wrong and they were right. The problem is that, while the heuristic is assuming a base cost of 1 (Which it must, or it becomes possible to return an 'optimal' path which takes no account of a high traffic zone) but most tiles cost at least 2, then the algorithm has to consider many more tiles than if the basic tile cost matched the heuristics expectations.  If the destination is to the west, then every tile to the west increases the path cost by two and the heuristic cost decreases by 1. The increased path cost will force the algorithm to search one square east for every two squares west, even before all paths to the west have been exhausted.

[PencilinHand]

Actually, no, I was wrong and they were right. The problem is that, while the heuristic is assuming a base cost of 1 (Which it must, or it becomes possible to return an 'optimal' path which takes no account of a high traffic zone) but most tiles cost at least 2, then the algorithm has to consider many more tiles than if the basic tile cost matched the heuristics expectations.  If the destination is to the west, then every tile to the west increases the path cost by two and the heuristic cost decreases by 1. The increased path cost will force the algorithm to search one square east for every two squares west, even before all paths to the west have been exhausted.

You are forgetting that the heuristic is updated from every tile.  It doesn't matter if the cost function is calculating the cost to reach the current position as one per tile and 2 for the heuristic distance and is over estimating the distance*.

Code: [Select]

AXXXX
X468X
X6D8X
X881X
XXXX1

A is the destination, D if the current position, the 1's represent the path so far, the other numbers are the estimated distance left to travel if diagonal movement costs the same as cardinal movement.  The cost to get where D is now is 2, the heuristic still works as intended.


*We can't say for sure this is how it works because Toady hasn't given us the exact code.  It may be that the cost to reach the current position is the weight per tile(what I am assuming) or it might only cost one. see edit

EDIT: So there is no misunderstanding, I am assuming the cost from the start to the current position INCLUDES the weighted value of the tiles so far AND that the estimation for the distance cost remaining is also weighted.  If the former is true(that is the cost to "here" is weighted) then the distance estimation would benefit from considering the weighting in the distance cost(that is the "how far do we have to go" is weighted = less tiles need to be searched).  However, the estimated distance doesn't HAVE to be weighted to be deterministic(meaning it always reaches the goal, if possible) and can be valued at 1 though this would be less efficient.

However, if you assume that the cost to the current tile("here") is always the same per tile regardless of traffic designation then you have to lock the heuristic to either 1 or whatever the built in cost is per tile and ignore weighting or you aren't always deterministic.  However, if you do this then traffic designations would do NOTHING because they would have no impact on the cost to "here" nor the estimated distance left( that is the total cost of the path).

[qwertyuiopas]

There is a fringe case where a really, really, REALLY long path(path length of over 16000 tiles minimum for normal weight of 2) might conceivably exceed the size of its container.  Realistically we aren't going to see that kind of case(a long path in DF is a few hundred tiles), read up on how int variables work if you are interested.

First, that assumes a signed int, second, many compilers use 32 bit integers. It is just 16 bits minimum.

Note 2 of that exact same wikipedia article.

"On compilers for 32 bit and larger processors (including Intel x86 processors executing in 32 bit mode, such as Win32 or Linux) an int is usually 32 bits long and has exactly the same representation as a long."

[PencilinHand]

There is a fringe case where a really, really, REALLY long path(path length of over 16000 tiles minimum for normal weight of 2) might conceivably exceed the size of its container.  Realistically we aren't going to see that kind of case(a long path in DF is a few hundred tiles), read up on how int variables work if you are interested.

First, that assumes a signed int, second, many compilers use 32 bit integers. It is just 16 bits minimum.

Note 2 of that exact same wikipedia article.

"On compilers for 32 bit and larger processors (including Intel x86 processors executing in 32 bit mode, such as Win32 or Linux) an int is usually 32 bits long and has exactly the same representation as a long."

All of which only makes the fringe case even more unlikely to the point of almost not being worth mentioning.  I figured I would state the worst possible case(a signed 16-bit int or "short") under the default configuration(weight = 2) in the possibility that Toady was using a compiler that doesn't use a 32 bit int. For a 32-bit int you would need to path over 1.07 or ~2.15 billion tiles depending on if it was signed or unsigned respectively.

[shadow_slicer]

A general tip to improve pathfinding for people who don't want to make use of the in-game traffic zones.  Open up the init.txt and change the weighting on the "normal" zone from 2 to 1.  This will basically double the effectiveness of all your pathfinding, but make high traffic zones meaningless.

That should not make a difference. A grid of cost 2 squares should behave the same way as a grid of cost 1 squares. Its the interaction between different costs that makes the difference. Such is theory, anyway, if you have done any testing then let us know.

It actually should make a difference. The heuristic function employed by the A* algorithm to determine the lowest possible cost to the destination from a given point has to use the lowest cost possible for each tile which is 1. This means that if every tile has a cost of 2, it will end up exploring areas that actually aren't very promising just because they could *possibly* connect to a high traffic zone to the destination. By setting the normal tile cost to 1 you avoid that extra overhead.

Even if you do use the zones, it may be better (framerate-wise) to swap the costs of normal and high-traffic zones. Then you can still designate highways: just paint "high-traffic" in the areas around the highways you don't want dwarves to go through.

No, it won't, not if every tile costs the same.  Each tile's travel cost is 1*weight, where weight is set by the traffic zones  and normal is weight 2, high is weight 1, etc. Giving normal a weight of 1 will just nullify the usefulness of high-traffic zones. The ratio of the weights for valid tile paths is what is important, not the absolute value of the weight of any given tile.

Picture a Y split where either path is equally valid to reach the destination but give one path a per tile weight 3 times that of the other be it 1:3, 2:6, or 333:999 it doesn't matter.  The path with the lower weight will be preferred at a rate of 3 tiles to one tile of the path with the higher weight.  Giving all paths the same weight(including the path to reach the Y) be it 1:1, 2:2: or 1000:1000 won't matter because there is no advantage for going with one compared with another.

The only way an advantage could be achieved would be by picking weight numbers that either simplify the mathematics, and we don't really know enough to do that, or by using a little understanding and being smart about laying down high and low traffic zones.  There is a fringe case where a really, really, REALLY long path(path length of over 16000 tiles minimum for normal weight of 2) might conceivably exceed the size of its container.  Realistically we aren't going to see that kind of case(a long path in DF is a few hundred tiles), read up on how int variables work if you are interested.

I think you are missing a very subtle issue with A*. It won't affect the end result of the calculation, but does impact the number of tiles considered. The problem with A* is that the heuristic must generate a cost that must be greater or equal the actual cost. This means that the heuristic will need to assume that all of the remaining tiles have the minimum weight.

Now let's do an example:

Spoiler: spoilered for length (click to show/hide)

We allow tiles with weights 1, 2, and 5. We are finding the path from S to D in a completely open space with normal traffic designation.

Code: [Select]

S2222
22222
22222
22222
2222D
The cost+heuristic A* sees looks like:

Code: [Select]

S6
65

   D
First A* would expand the node south-east of S since it has a cost of 2 and heuristic of 2 = 4 total cost.
The cost+heuristic A* now sees is:

Code: [Select]

S68
6*7
876
 
    D
Then A* can either explore south or east of S or continue south-east again. If it goes south or east, we are exploring more nodes than we would if 2 was the lowest allowable weight. If it goes south-east again, we have:

Code: [Select]

S68
6*79
87*8
 987
    D
Then A* MUST explore south or east of S, since they could potentially be shorter. Since we already know that there are no tiles on this specific area of a cost less than 2, this is not necessary. We can't use a weight of 2 for the heuristic because this is also possible:

Code: [Select]

S2111
22221
22221
2222D


It is important to make the normal cost the lowest, because that makes it optimal for the most common case. Since we don't know how the DF determines the lowest cost for the heuristic function, we should make the normal cost 1 in case it is hardcoded to that.

Of course, if the player decides to add traffic designations which may reduce the efficiency of the pathfinder, they can. They can even add them intelligently to minimize this effect. This is different than the current case, where everything is suboptimal by default.

[The Grim Sleeper]

I've heard a rather unsubstantiated rumor that having multiple equal-length paths causes the path-finding to get confused, trying to find the shorter of those routes over and over. Could anyone of you mathemagicians shine a light on this?

[immibis]

Having multiple equal-length paths will make the algorithm find both of them. Although it isn't actually very different in speed from having multiple paths with unequal lengths or having only one path. And no, it doesn't get confused.

[Phwoar]

Mark the entrances to all bedrooms, meeting rooms and personal dining rooms with a Restricted square.  People who want to go in them still will, but nobody else will try to path through them.  This is a simple one that requires no additional thought.  Just do it.

The same can be done for entrances to dead-end corridors that contain only rooms of the above type.


I still want Toady to add a setting that allows all friendly things to walk through each other for free.  No more having to re-path around every other unit every single tick.  Sure, less 'realism', but for a good cause, when required.

[decius]

Not a compsci major myself, but the explanations for why A* is faster when the path that it ends up choosing is cost 1 than when it is cost 2 make sense to me.

Does anyone have any comparative numbers for "I had X dwarves and everthing designated a normal traffic zone. When I changed the cost of the normal traffic zone from 2 to 1, my FPS changed from A to B."?

On a 4x4 embark with flowing water, I typically end up with 6-7 FPS in the late early game; I tend to have about 40 dwarves pathing at that point, and I can't figure out how to keep doing anything without producing a lot of hauling jobs. Any way to bump that up that doesn't involve buying a computer from this decade would help a lot.