Print

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

[Anticipation]

I wasn't really sure where to put this so I decided her by default.

Also I'm not entirly sure how to ask the question I mean so I'll just try my best. How does the DF pathfinding work? As in, what kind of search algorithem, does it look at all the spaces next to each creature, then all the spaces next to those, and next to those or some other kind or magic?

[Starver]

I wasn't really sure where to put this so I decided her by default.

Also I'm not entirly sure how to ask the question I mean so I'll just try my best. How does the DF pathfinding work?

Some would say "imperfectly", but perhaps it's best to say "suboptimally" with a generous helping of "it could be a lot worse".

As in, what kind of search algorithem, does it look at all the spaces next to each creature, then all the spaces next to those, and next to those or some other kind or magic?

As I understand it (from my largely passive/suggestions-only involvement in a certain Pathfinding Project of this parish) the current system uses the A* algorithm for specific from/to routes, which I think you could arguably describe as a weighted hybrid between depth- and width-first searches.

However, when looking for "nearest <generic item>" (e.g. a new piece of stone to work at a workshop) when it starts off by taking coordinate differences (with apparent bias towards X-Y closeness, even with a multiple Z-difference, and never mind how long the actual path will be) and then calculating (by A*) the route to get there (or its impossibility, forcing it to moving onto the next possibility).  That's rather than taking the route of a breadth-first search (or weighted equivalent) to find the actual nearest item.

And when searching for a position to work on a mining job (for example), it has a preference (I think: North, then South, West then East, then diagonals with in the same precedences) for where to stand to complete the job, regardless of whether the job could have been completed even by staying on the same square (and attacking from the SE) rather than finding a route all the way round the mountain to the tile (frexample) directly West of the to-be-mined tile to complete the tunnel.  So that complicates matters.

As does the fact that a closed route is only reacted to once the agent finds itself at the blockage on the previously open route.   Despite having omniscience in the original route-planning (even into bits of fortress they've never been in before, or across landscape so far unexplored by any other dwarf), they only re-route once their pre-planned route comes up against an apparently insurmountable obstacle, not dynamically when the closure first occurs.  Or even (for transient routes, opening and closing via liquid flow or dynamic architectural features) waiting around for the route to open up again.

BICBW, YMMV.  HTH, HAND.

(You see, I didn't know whether you were actually asking about how it comes up with the route (which is fairly optimal once calculated, but perhaps a little resource intensive in its derivation), or how it comes up with the end-point to any given route where multiple destinations are possible (definitely suboptimal, but once you know the tricks of the trade, can be accounted for and even exploited).  So I think I've given you everything you might want to know, and eagerly await someone telling me that I'm plain wrong about something.

[Sizik]

So I think I've given you everything you might want to know, and eagerly await someone telling me that I'm plain wrong about something.

(with apparent bias towards X-Y closeness, even with a multiple Z-difference, and never mind how long the actual path will be)

The bias is actually in the player, not the game; a stone 5 z-levels down seems farther away to the player than one 10 tiles away on the same level, but it's actually closer, since 5 < 10.

The function that calculates straight-line distance for job items ignores z-levels.  Here are a couple reports that include simple ways to reproduce the problem: one, two, three.  It should be a quintessential one-minute fix, but I know how that goes.

I've never been able to reproduce this.  I just dug a tunnel out below a depot and the stone all reported at the correct distances including the z levels, and the code in 40d is the same.  It didn't say zero for the stone directly below the depot.  The workshop job code all uses 3D staight line distances, which are bad compared to the path distance, but it doesn't return zero for Z coordinates.

[Starver]

The bias is actually in the player, not the game; a stone 5 z-levels down seems farther away to the player than one 10 tiles away on the same level, but it's actually closer, since 5 < 10.

Okay doke.  But it seems it still primarily seeks out stone five levels directly below reachable only by wandering 50 tiles to one side, navigating a minor labyrinth and braving who knows what subterranean horrors, then back again, rather than casually strolling over to the nearby well-stocked stockpile on the same level.  Unless that's changed since I started to engineer things so that my primary supply stockpiles were nominally on vertically adjacent levels reachable by horizontally adjacent stairwells, or similar. )

[Exponent]

The bias is actually in the player, not the game; a stone 5 z-levels down seems farther away to the player than one 10 tiles away on the same level, but it's actually closer, since 5 < 10.

Okay doke.  But it seems it still primarily seeks out stone five levels directly below reachable only by wandering 50 tiles to one side, navigating a minor labyrinth and braving who knows what subterranean horrors, then back again, rather than casually strolling over to the nearby well-stocked stockpile on the same level.  Unless that's changed since I started to engineer things so that my primary supply stockpiles were nominally on vertically adjacent levels reachable by horizontally adjacent stairwells, or similar. )

It occurs more often with vertically arranged fortresses, but it would happen just as obnoxiously if you had a stone stockpile next to a workshop on the same level, only separated by a wall with no door, and the path from the workshop to the stockpile required walking through crowded halls, out of the front gate, through the forest, through the canyon made by the brook, into the dam access passageway, along the power network, up the pump stack, past the obsidian factory, and into the obsidian stone stockpile.

[Starver]

No argument.  I was originally saying how it would choose destination based on absolute vector closeness, then look for a path.

(Z-displacement is the usual complaint, due to Z-connectivity being less likely between two spots than any other dimension, for most people, so I dwelt on that situation a bit too much, I think.)

[PencilinHand]

Part of the problem with all of this discussion is we aren't distinguishing between different functions of AI decisions, pathfinding being one of them, while resource selection is another.

The natural assumption we make is that a dwarf should get the closest material for a given job, for example.  However, this isn't necessarily the case, regardless the selection of and path too a given objective are two different but often related decisions or series of decisions for a path.

The there is room for both to improve in current implementation.  A simple search of "pathfinding" will result in many, many, discussions on both topics.