Print

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

[Evile]

Now we have 4 designations = high/normal/low/prohibited

Now what if designations had also preferred directions of travel, that way one could possibly create 2 way traffic where dwarves would never face opposing traffic flow.

I think this should and would postpone FPS deaths to some extent.

Thoughts?

[10ebbor10]

This would probably require an pathing engine rewrite.

Though that one may need to be rewritten anyway.

[NW_Kohaku]

Yes, one-way traffic pathing is impossible given the modified A* pathfinding that this game uses. 

In fact, the current traffic designations are basically terrible for pathfinding as it stands unless you are one of the very few people who actually set high priority to every hallway and low or restricted priority to every dead-end room, as the game basically requires you manually optimize your traffic patterns, unless you just manually set "normal" priority to 1.  (And even then, you should probably paint your dead-ends in low and restricted traffic.)

[King Mir]

Logically, crowded hallways should be bad, and dwarves should be slowed down or have to route around tight crowds.

But practically, any implementation of crowding would be a major FPS hit. Based on the apparent effectiveness of traffic designations, DF works better with slim hallways, and single tile stairs. This way dwarves only have one possible path to consider, and so the algorithm is fast. Traffic designations could speed up a fort with wide hallways by making all the dwarves travel via the middle of the hall.


Setting Normal priority to 1 should have no effect. The cost of a tile only matters if different tiles have different costs. It just impacts the importance of high traffic zones. Personally, I set normal traffic areas to 3 and high to 2, when I bother with it, but I've done no science on he effectiveness of this.

[NW_Kohaku]

Setting Normal priority to 1 should have no effect. The cost of a tile only matters if different tiles have different costs.

No it doesn't.

That's not how A* works.  A* tries to path directly into the direction of its destination first, but when it sees that the tile it is trying to enter has a weight of "2" (and "seeing" that takes an entire memory fetch routine, which is THE thing slowing the game down), it then decides to try testing all the other possible tiles going anywhere near the right direction to see if there is a path that involves a weight of 1.  The game ONLY takes the shortest route without checking other routes when you have a weight of 1.  And checking other routes is, again, the thing slowing pathfinding down. 

[King Mir]

Setting Normal priority to 1 should have no effect. The cost of a tile only matters if different tiles have different costs.

No it doesn't.

That's not how A* works.  A* tries to path directly into the direction of its destination first, but when it sees that the tile it is trying to enter has a weight of "2" (and "seeing" that takes an entire memory fetch routine, which is THE thing slowing the game down), it then decides to try testing all the other possible tiles going anywhere near the right direction to see if there is a path that involves a weight of 1.  The game ONLY takes the shortest route without checking other routes when you have a weight of 1.  And checking other routes is, again, the thing slowing pathfinding down.

I agree that alternate routes is the thing that slows A* down. Not the rest though. A* will always look at all adjacent tiles to the path it considers. Then it picks the one with the lowest cost (This is actually fast, because it keeps the possible paths sorted). The cost in this case is tied to the distance to the target, and to the traffic cost. If all the traffic costs are the same, then only the distance matters. If the costs per tile are different, then it will prefer the high traffic areas, resulting in fewer alternatives considered, but at the expense of a potentially longer path.

Smart placement of high and low traffic tiles could result in an FPS speedup without making dwarves take longer paths.

[kaenneth]

I was thinking simple, automatic traffic laning.

Such as, even numbered columns are preferred for north to south, odd columns for south to north, even rows for east to west, odd rows for west to east.

that way any two tile wide hallway would automatically organize into two lanes.

or a version of the 'left hand rule', where dwarfs would try and keep a wall to their left side when pathing.

[King Mir]

If two paths are potentially equal distance, A* will pick the one it looked at most recently. This allows some technical optimizations, that aren't central to the algorithm. Preferring the left path instead would prevent those optimizations.

[JanusTwoface]

Setting Normal priority to 1 should have no effect. The cost of a tile only matters if different tiles have different costs.

No it doesn't.

That's not how A* works.  A* tries to path directly into the direction of its destination first, but when it sees that the tile it is trying to enter has a weight of "2" (and "seeing" that takes an entire memory fetch routine, which is THE thing slowing the game down), it then decides to try testing all the other possible tiles going anywhere near the right direction to see if there is a path that involves a weight of 1.  The game ONLY takes the shortest route without checking other routes when you have a weight of 1.  And checking other routes is, again, the thing slowing pathfinding down. 

But for it to actually be A*, it has to use an "admissible heuristic" meaning that it cannot overestimate the distance to the goal^[1]. If distance is the number of steps to get to the square and the weighting is directly used as the heuristic, doesn't this mean that all values other than 1 break this guarantee? (and thus inspect far more of the map than they need to)

(Note: Since Toady's the only one that's actually seen the pathfinding code, so my assumptions could easily be completely off base.)

[NW_Kohaku]

But for it to actually be A*, it has to use an "admissible heuristic" meaning that it cannot overestimate the distance to the goal^[1]. If distance is the number of steps to get to the square and the weighting is directly used as the heuristic, doesn't this mean that all values other than 1 break this guarantee? (and thus inspect far more of the map than they need to)

(Note: Since Toady's the only one that's actually seen the pathfinding code, so my assumptions could easily be completely off base.)

It's not technically A*, it's a modified A* and it works in a 3d grid with 26 possible moves, and testing also proves it weights diagonal upwards movement (that means ramps) ahead of direct vertical movement (that means stairs).  Because of this, the game will actually test for ramps existing before it tests for stairs, and spiral stariways of ramps are actually more efficient, and testing has proven this.

Likewise, I remember seeing testing of simply turning traffic designations "off" by editing the init.txt file to make traffic weights 1:1:1:1, and it sped up the game by spending less time looking for alternate paths because it will follow the heuristic without having to check for alternate paths on reading a weight of 1. 

So yes, that is exactly what you and I are saying: a weight of 1 makes for far faster pathfinding with far fewer alternate tiles checked.

[King Mir]

But for it to actually be A*, it has to use an "admissible heuristic" meaning that it cannot overestimate the distance to the goal^[1]. If distance is the number of steps to get to the square and the weighting is directly used as the heuristic, doesn't this mean that all values other than 1 break this guarantee? (and thus inspect far more of the map than they need to)

(Note: Since Toady's the only one that's actually seen the pathfinding code, so my assumptions could easily be completely off base.)

It's not technically A*, it's a modified A* and it works in a 3d grid with 26 possible moves, and testing also proves it weights diagonal upwards movement (that means ramps) ahead of direct vertical movement (that means stairs).  Because of this, the game will actually test for ramps existing before it tests for stairs, and spiral stariways of ramps are actually more efficient, and testing has proven this.

Likewise, I remember seeing testing of simply turning traffic designations "off" by editing the init.txt file to make traffic weights 1:1:1:1, and it sped up the game by spending less time looking for alternate paths because it will follow the heuristic without having to check for alternate paths on reading a weight of 1. 

So yes, that is exactly what you and I are saying: a weight of 1 makes for far faster pathfinding with far fewer alternate tiles checked.

Ramps could be checked ahead of direct vertical movement because they are in fact faster to climb. Even if ramps where given special precedence outside the distance function, the effect would be pathing not finding the shortest route. It wouldn't change the core of the algorithm though. The algorithm will still always queue every branch (except when it would immediately pop the branch off and try it).

Testing FPS is an imprecise task. Without an understanding of how a change might speed up the game, I would doubt the perceived speedup. Either rigorous testing or a good explanation would be needed. That's why I doubt your claim that changing all traffic costs to 1 leads to speedup. It doesn't make sense given Toady said that he uses A*, even if it is slightly modified A*. 


It is the case that poor use of traffic areas, could actually hurt FPS.

EDIT: Setting the normal traffic cost to 1 has the effect of halving the tile cost in all calculations used in the heuristic. Nothing else. It doesn't change the relative cost of any two paths, and therefore doesn't change the number of paths considered.

EDIT2: Apologies for incessantly editing the formatting of this.

[Evile]

It is a pity that I can't simply contribute to the discussion anymore - it is beyond my capabilities - only thing I can do is to brainstorm.

What if there was a designation that simply completely inhibited testing for a specific direction. As in instead of choosing from 26 possible directions it would choose 25 or less.

While I don't think it would affect the pathfinding in itself it would allow us to regulate traffic flows somewhat. While creatures trying to go into prohibited area will suffer from increased pathfinding the resulting decrease in traffic collisions might make it more responsive. No?

[Necromunger]

I dont like this idea. Takes to much away from the dwarfs.

[andrewas]

But for it to actually be A*, it has to use an "admissible heuristic" meaning that it cannot overestimate the distance to the goal^[1]. If distance is the number of steps to get to the square and the weighting is directly used as the heuristic, doesn't this mean that all values other than 1 break this guarantee? (and thus inspect far more of the map than they need to)

Weights less than one would break the heuristic. The current default setup has an admissable but over-optimistic heuristic, which can be fixed by changing the default weight in the init.

Now that I think about it, changing the heuristic to assume a weight of 2 and still allowing the player to set a cost of 1 may be worth looking at. This does give us an inadmissable heuristic, but you are still guaranteed a valid if suboptimal path. Which, if I'm figuring this right, will generally equate to an optimal path in the players eyes since it will take advantage of high-traffic designations it encounters, the suboptimality comes from failure to spot optimal paths that take advantage of a high traffic designation behind the starting point. (Also, define 'suboptimal' in a system where travel costs bear little relation to pathing weights.)

As for the original suggestion, I don't see that the use of A* makes that difficult. Tie the one-way function to a door or floor hatch rather than being able to designate an empty tile as one way, and stop the pathfinder from pathing into the door/hatch from the wrong sides. The pathfinder has to treat doors as a special case anyway so this should be doable without much performance hit.

[King Mir]

But for it to actually be A*, it has to use an "admissible heuristic" meaning that it cannot overestimate the distance to the goal^[1]. If distance is the number of steps to get to the square and the weighting is directly used as the heuristic, doesn't this mean that all values other than 1 break this guarantee? (and thus inspect far more of the map than they need to)

Weights less than one would break the heuristic. The current default setup has an admissable but over-optimistic heuristic, which can be fixed by changing the default weight in the init.

No, weights less than 0 would be unworkable.

Now that I think about it, changing the heuristic to assume a weight of 2 and still allowing the player to set a cost of 1 may be worth looking at. This does give us an inadmissable heuristic, but you are still guaranteed a valid if suboptimal path. Which, if I'm figuring this right, will generally equate to an optimal path in the players eyes since it will take advantage of high-traffic designations it encounters, the suboptimality comes from failure to spot optimal paths that take advantage of a high traffic designation behind the starting point. (Also, define 'suboptimal' in a system where travel costs bear little relation to pathing weights.)

This is exactly how the game works now.

Also, though varied traffic designations can potentially lead to sub optimal paths, they can be placed in such a way that they don't. For example, NW_Kohaku mentioned making dead ends into low traffic areas. This would never generate sub optimal paths. It would, however, lead to slower pathing when the goal is in the dead end. (the dwarves would spend time trying to route around the low traffic area, not realizing that they can't until they finally find the path)