Print

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

[Martin]

Wait...

Reducing the path value shouldn't have an effect. Adding 1's isn't any faster than adding 2's. What *would* have an effect for A* algorithm is giving a limited number of high traffic areas that eliminates paths from the priority set.

The way A* works is by taking the starting point and checking the cost of neighboring points (the cost is the distance times the tile cost, which is the traffic value) and maintaining a list of all path options (nodes) that are ranked by cost. It then expands each path, checking the neighboring tiles for each one, recalculating the cost, resorting the list, and so on. It estimates the cost from each node to the destination and culls the list as appropriate. If it estimates that a given node is so far/expensive from the destination that it can't be cheaper than the top ranked node, it stops calculating for it.

The reason that high traffic areas (and restricted areas moreso) works is that it more quickly shoves nodes into the 'too expensive' category and keeps them from being calculated. A simple pathing algorithm expands geometrically with the size of the map, but by weighting the cost of each tile moved and estimating the cost to reach the end, most paths can be ruled out as too expensive. If you lock a room off, once the algorithm hits a node containing the door, every tile inside the room is infinitely expensive and never gets calculated. If you have a 4x4 map with normal travel cost of 2, the minimal cost to travel the map is 48x4x2 = 384 (I assume diagonal movement is cost 1, doing otherwise is computationally stupid if geometrically wrong). In that case, making your restricted tile cost 384 would effectively stop pathing on every node bordering the restricted area unless every other path hit a restricted tile. It'd be as effective as putting in a wall, except that dwarves would cross it in a worst case situation. Making your normal travel cost 4 and high traffic 1 would much more rapidly knock down nodes and reduce path costs while preventing dwarves from taking totally stupid (merely moderately stupid) paths. There should be a happy medium in there somewhere.

If you want to further lighten the computational overhead a bit, make all the costs a factor of 2: 1,2,4,8,16,32,64, etc.

I don't think that pets/animals respect the traffic costs, so adding them into the experiments shouldn't make any difference at all.

You might see lower FPS with high traffic areas if they cause more immediate interactions. More dwarves bumping into each other means that the paths need to be recalculated. That's why traffic jams suck so badly. Again, there's a happy medium here.

[Ignoro]

EDIT:
What the next guy says.

The following is all guesswork:

On a 3x3 with 1:2:10:25, you got 75 fps.
On a 3x3 with 10:10:10:10, you got 90 fps.  I don't see any explanation for this behavior, and the difference between these two (15 fps) IS statistically very significant.

1:1:10:25 & 10:10:10:10 get the same results because hightraffic=normaltraffic areas I think. It's like I designated high traffic, but better because the lowest values compared to the other values is smaller which = lower cost by relative ratio. For 10:10:10:10, everything was lowest pathfinding cost of 1 by ratio. Not entirely sure. Note that giving them the equal values within a set had the same performance.

They both use a path cost of '1' designated everywhere, and I don't see any explanation in the current theory (high numbers = slower) for why this would happen.

It would appear to me the actual values you enter mean nothing. That's what I said when they're relative to each other. It's actually ratios you enter for the pathfinding weight. Entering them all as the same value should give them all a pathfinding weight of 1.

10:10:10:10 = cost of 1
1:2:10:25 = cost of >1, as the higher traffic designation takes the designated cost by 2x.
1:2:10:25 High traffic ratio is vanilla. It's the smallest number of the set, but the ratio compared to the others is not as small as the next.
1:99:999:9999 High traffic ratio is infinitesimally small compared to others.

Pathfinding cost is relative to the other values. Of course the 1:9:99:999 setup makes the normal and low traffic areas worth basically as much as restricted tiles for their ratio.

[Martin]

*foams at the mouth*

I can't argue with experimental evidence!

I have to question some of the results though.

On a 3x3 with 1:2:10:25, you got 75 fps.
On a 3x3 with 10:10:10:10, you got 90 fps.  I don't see any explanation for this behavior, and the difference between these two (15 fps) IS statistically very significant.

Also, I'm very confused why
3x3 1:2:10:25 (80 FPS)
3x3 1:99:999:9999 (125 FPS)

They both make some sense to me.

In the first test, (1,2,10,25/10,10,10,10) all paths were equal weight, so the same number of nodes got calculated in both tests, but in the first case, there was a possible weighting factor to the each node. It never got put into effect, but the algorithm didn't know that. In the 2nd case, all traffic values were the same, so it could skip the weighting factor and just add them up. This assumes that Toady checks for that situation, but given that pathing is wicked expensive, my guess is he does.

In the 2nd test, (1,2,10,25/1,99,999,9999), the cost estimate for reaching the end would be the 2nd value. The algorithm would assume that the cost for each unknown tile is the normal cost, so in the 2nd case, the algorithm would reject nodes much faster than the first one, because it would assume all future unknown nodes cost 99 rather than 2, so they get knocked out faster.

[Martin]

Pathfinding cost is relative to the other values. Of course the 1:9:99:999 setup makes the normal and low traffic areas worth baisically as much as restricted tiles for their ratio.

Pretty close. If a node is 100 tiles from the destination, it'd assume that the remaining cost is 9 (unknown cost) * 100 (distance) = 900. If a neighboring tile is low traffic and one closer to the destination, that node would be 9 (unknown cost) * 99 (distance) + 99 (known cost) = 990. The first path could go 10 normal traffic tiles without getting any closer to the destination before the low traffic node calculated again. If a neighboring tile was instead restricted and one tile closer, that would cost 9 (unknown cost) * 99 (distance) + 999 (known cost) = 1890. The first path could go 50 tiles away from the destination on normal traffic and turn back toward it before the restricted node calculated again. What really matters is the cost ratio to *normal*, not really to each other. The algorithm assumes normal for all future tiles.

[Ignoro]

What really matters is the cost ratio to *normal*, not really to each other. The algorithm assumes normal for all future tiles.

EDIT:

1:9:99:999 Avg 125 FPS
1:999999:1:1 Avg 80 FPS
1:999999:1:1 Avg 75 FPS

Eh-wahhh?
Can someone else test this? I'm not all that certain on my method anymore.

[Martin]

What really matters is the cost ratio to *normal*, not really to each other. The algorithm assumes normal for all future tiles.

EDIT:

1:9:99:999 Avg 125 FPS
1:999999:1:1 Avg 80 FPS
1:999999:1:1 Avg 75 FPS

Eh-wahhh?
Can someone else test this? I'm not all that certain on my method anymore.

Well, you're running into some other things, I think. The 999999 value means that it's multiplying that large number rather a lot which is expensive. You don't need to go any higher than the largest distance on your map * the normal cost. If it's 4x4, that 384*2. Basically, any node that hits one tile that costs more than normal, assuming a normal path exists would never get calculated again. Oh, and sticking to powers of two helps eliminate some of the math assuming that Toady has optimization turned on in any way.

The last two tests could be averaging issues or some small particular of the algorithm where branching on restricted is faster than on high, that kind of thing. 5 FPS out of 80 is insignificant, IMO.

[Martin]

I'll add a corollary to this. A* can be abstracted further, which I think Toady has in mind. If you consider a typical underground fortress with rooms, there are some significant speedup opportunities if you can cache subpaths. An example would be a room with one door. The cost from any point outside the room to any point inside the room is the cost to the door + the cost from the door to the spot inside the room. You can eliminate all the path options within the room if you know to just calculate to the door and to do the smaller pathing inside.

Imagine a room with 2 doors. The cost from one door to the other is essentially fixed. If you save that cost (say a 10 tile distance with a normal cost of 2 = 20 cost to go across the room) the you can path to one door, add 20 to the cost, and you jump to the other door and resume your pathing, skipping the interior of the room entirely.

For a fortress comprised of rooms like this, you can cache the cost from any door to any other door (or bridge, floodgate, hatch cover) and if you start calculating from the start and hit a door, stop, start calculating from the end and hit a door, stop, and just add in the known costs between the doors. You can cut out a TON of calculating if you bother utilizing things that Toady decides will cache pathfinding costs. Now, you need triggers to recalculate costs, but those are pretty well known - jobs, mostly.

The downside to this is that it can get expensive in memory. I've had fortresses with 2000 doors and hatch covers. That's potentially 2000x2000=4,000,000 paths to cache. Now, that can be cut down a LOT because most of those paths went through other doors so most of those paths don't need to be retained, you just string together cached values, which is still plenty fast, but it's a non-trivial thing to organize and implement. The advantage to this approach is that the player can know what will and won't hurt pathfinding. Don't leave open doorways and stairs, for example, that kind of thing.

[numerobis]

The 999999 value means that it's multiplying that large number rather a lot which is expensive.

*headdesk*

Multiplying any n-bit number by any other takes exactly the same amount of time on the vast majority of commercially available chips.  And with values of just a million, there's basically no chance of integer overflow there (which would cost all sorts of lovely behaviour).

Assuming A*, the heuristic must be admissible for the algorithm to be correct; otherwise we're just hosed, forget the FPS, your dwarves are taking longer paths than necessary.  So, it can't assume the normal traffic cost, but has to assume high-traffic, or 1.  The empirical data seem to indicate the current code uses high-traffic as the base cost.

Using the usual heuristic on a grid of just computing the euclidean distance times the minimal possible cost, the heuristic would be more accurate when routing over a map that is entirely high-traffic than over a map that is entirely normal-traffic.  When the heuristic isn't as tight, bad paths are followed that shouldn't have been followed.  According to this, I predict that pathfinding should generally get faster as the ratio of the most common cost to the base cost gets smaller.

tl;dr : Yes, it makes sense that the game will be faster if everything is designated high-traffic, or if you change the raws to make normal- and high-traffic have the same cost.  And if you designate dead-ends as low-traffic, it should speed up yet more.

[numerobis]

This, by the way, is indeed a pretty cool discovery.  Maybe the default raws should be 9:10:50:500, so 'high' is preferred, but only a little bit, and the heuristic over normal-designated terrain is only 10% off.  (For those of us for whom dwarf-based pathfinding is the main cost, which is not the case in my current fortress apparently)

[Ignoro]

You don't need to go any higher than the largest distance on your map * the normal cost.

So there is some fine tuning to be had with relation to map size?
Does this mean you can get better FPS on a square map of the same area compared to a very rectangular map of the exact same area if you optimize the pathfinding costs?

EDIT:

*headdesk*

So ...no?

MORE TESTING! But I don't have anymore time to do so. Sorry.

[ZeroGravitas]

This, by the way, is indeed a pretty cool discovery.  Maybe the default raws should be 9:10:50:500, so 'high' is preferred, but only a little bit, and the heuristic over normal-designated terrain is only 10% off.  (For those of us for whom dwarf-based pathfinding is the main cost, which is not the case in my current fortress apparently)

4:8:64:256, maybe, if you want to stick with powers of 2.

[numerobis]

What's the advantage of powers of two?

[Baughn]

There isn't one.

Power-of-two math can sometimes be a little faster (though on modern chips it's mostly dwarfed by memory lag), but only when the compiler knows in advance it's power-of-two; it has no effect if it doesn't, or as in this case if it sometimes isn't.


Oh, and good catch on the pathfinding. It does make some sense that, if you don't actually designate traffic costs, the pathfinder works better if everything has cost 1 - I'd need to confirm that for myself, but it sounds like a bug. The solution would be to have the A* pathfinder assume the cost is (whatever the default cost is with current settings), not always 1.

Hm. The way this works... skip to the lasst paragraph if you don't understand A*, I'm just thinking out loud.

A* adds up the euclidian (or manhattan, don't know which toady picked) distance from all possible next steps on the current set of paths to the destination. It then picks the lowest-cost path (previous cost + euclidian distance) to check, and.. adds the traffic cost for that cube to the path cost. Right..

When A* is working right, extending the path directly towards the destination should not alter the path cost (sunk cost + remaining distance) at all; it's plus 1 minus 1. But with the traffic cost of that cube above 1, it'll be plus (traffic cost) minus 1, which will suddenly make the most direct path *not the best path* as far as the algorithm is concerned, so it'll go ahead and try lots of other paths (that won't get anywhere either, since the traffic cost is just as high for those) before getting back to the first, and hopefully best one. Lots of extra, unnecessary work.


So, test, that I'd like you to try (too; I'll be testing myself, of course):
You should get ideal behaviour by setting all path costs to the same value in init, and to the specific value that the pathfinder assumes is in effect. This may be 1, or 10; I'd have to read the code to find out. Try different values, see what gets you highest FPS.

[Sowelu]

So, it can't assume the normal traffic cost, but has to assume high-traffic, or 1.

OH HELL YOU'RE RIGHT, HOW DID I MISS THAT.

All high-traffic SHOULD improve pathing immensely in flat open areas!  I wouldn't expect it to hurt anything indoors, but it wouldn't give nearly the same speedup.

Wow, I fail pretty hard.  Yeah.

The clear solution is to default all zones to 'high traffic', and only allow the player to manually place lower-traffic regions.  This is a huge deal.

Heck I'd go so far as to say that if you DIDN'T get a huge improvement by moving everything to high traffic, there might be something wrong with the algorithm!

Just goes to show that the conclusion of a fallacious argument is NOT necessarily false!  I stand by my statements.  If people hadn't been all distracting with "it's faster to calculate 1+1 than 2+2" this might have been seen earlier.  >.>

[Akhier the Dragon hearted]

another thing you should look at. it was mentioned that there was 100 cats. now if they where all trying to do the same thing every time you did the test it would be reliable but what if one test the cats just mostly stood still and another they kept trying to walk through the dwarfs. you would need many tests using save scumming from the same moment with atleast 10 or so trials on each setting to account for the cats.