Print

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

[Slogo]

Actually, dwarves path in straight lines in sufficiently open areas. It's only when you have tight labyrinths and twisty halls that they need to go tile by tile to find the way through.

Are you sure that the algorithm actually jumps in straight lines through open areas, and that it doesn't just result in a straight path? I know there are algorithms that are smart enough to leap along straight paths when there are no obstacles, without going all A* and flooding the room, but I was not under the impression that DF had implemented such a thing.

It's highly unlikely that Toady is using jump point search algorithms since uh well one since pathfinding seems to slow things down and two just timing wise jump point search is still a relatively recent thing (at least in terms of publicly available info on it).

[omega_dwarf]

Actually, dwarves path in straight lines in sufficiently open areas. It's only when you have tight labyrinths and twisty halls that they need to go tile by tile to find the way through.

Are you sure that the algorithm actually jumps in straight lines through open areas, and that it doesn't just result in a straight path? I know there are algorithms that are smart enough to leap along straight paths when there are no obstacles, without going all A* and flooding the room, but I was not under the impression that DF had implemented such a thing.

It's highly unlikely that Toady is using jump point search algorithms since uh well one since pathfinding seems to slow things down and two just timing wise jump point search is still a relatively recent thing (at least in terms of publicly available info on it).

Yeah, that was definitely my impression.

It's cool stuff though, you've gotta admit.

Edit: it seems like DF's pathfinding would REALLY benefit from dead end elimination and/or swamp optimization. Like, all fortresses are basically hallways with rooms on the sides - really wide hallways as far as plain A* is concerned, except with sufficiently small entryways.

[Sadrice]

Conventional wisdom (I think Toady confirmed it) is that dwarf fortress uses modified A*. I don't know how modified it is but it seems to suffer from vast open areas, dead end passages, and excessively wide hallways.  Sealing mined out veins or other unused areas helps.  Traffic designations can help a lot.  Placing high traffic routes on the main stairwell can make them actually take it all the way up to the destination floor without checking at each level if there is an alternate route.  High traffic zones on main lateral corridors may help, but it may encourage the pathing algorithm to check down each of your lovingly designated main thoroughfares before going the rest of the way up the stairwell.  Using traffic designations to prioritize vertical movement is usually the most helpful.  You can also reduce the strain caused by large open spaces by connecting the doors with high traffic zones, so that dwarves will preferentially path from door to door rather than checking the rest of the room.

Be careful with using high weightings in traffic options.  "Forbidden" is already pretty high, at 25 (normal is 2, high is 1).  Before pathing across a tile of a forbidden zone, the dwarf must investigate all routes that cost less than 25.  If you have wide forbidden zones, but dwarves keep taking jobs on the other side (traffic designations do not prevent this, they just muck with pathing), or you increased the traffic cost of forbidden zones in the init options to prevent them from doing this (it won't work), they might have to try to path across every other available tile in the map before confirming that there isn't a way to path around the forbidden zone.

[Nikow]

In one interview Toady was speaking about modified A* used in DF for pathing, but it was modified in many, many ways, because there is soo much small things.

For pathing, i always build doors in every room, just because it looks fine and because i do not need for whole time most of those rooms. When i mine out a big area (for my future farming use) i usualy build two door there which are tight closed most of time. Just because FPS. When i open all doors my FPS drops to 5... from 30.