v0.34:Path

xTATTEREDx  · +FINE+  · *SUPERIOR*  · ≡EXCEPTIONAL≡  · ☼MASTERWORK☼

v50.13 · v0.47 · v0.34.11 · v0.31 · v0.28 · v0.23 This article is about an older version of DF. More Info · V

In the context of videogames and AI, pathing refers to finding a route from point A to point B. ToadyOne use a version of A*, a fact confirmed in an interview with Gamasutra, here.

The A* method takes point A and tries to quickly calculate a decent path to reach point B. This path is not always the quickest path. In fact, in a game with as complicated and ever changing environments as DF, the pathing probably rarely chooses the quickest path. The point is to find a path quickly without going too far out of the way.

Choosing an A and a B

In our example, A is a creature and B is its goal.

Presumably, there are a few ways that the game finds its A and B.

For constructions and buildings, the player designates the B from a list ordered by closest.

For jobs at workshops, it seems that the closest item(s) to the workshop that are usable are chosen as the B. This is likely done by the manhattan method, which basically chooses the closest item that meets the criteria, ignoring whether it is actually easy for a dwarf to reach. This can have the unfortunate side-effect of Urist McHauler deciding to get something that is in an adjacent room, even if he has to walk through your entire fortress to actually get there, rather than something on the other side of the room Urist is in.

Doing the Calculation

Each tile will have a value, this value is in some way based on how close it brings us to the item and that tile's traffic value. Thus the procedure is something like this:

1. First, we check all the tiles next to the dwarf and mark their values.
2. From there, repeatedly check all accessible tiles from the dwarf until we reach B.
3. Now take the tiles with the lowest values that connect to that location, and you have a path.
4. Now A will follow this path to get to B.

Things that are wandering(Animals, wandering invaders) may use a combination of the above method with some random movement.

For jobs that require chasing a moving thing, this is procedure may be done over and over, or a different algorithm may be used.

Additionally, the following variations have been suggested, but nothing is certain:

• Dwarves may remember paths that have worked before and try them before anything else.
• Inaccessible items may be invisibly considered forbidden for a certain amount of time after a dwarf discovers it is inaccessible and therefore not considered in pathing.

Things That Reduce Pathing Speed

• Resources that are geographically close to a workshop but inaccessible or hard to reach.

Tips For Improving Pathing Speeds

• Keep small stockpiles immediately next to workshops. This means Urist McCrafter doesn't have to do very much pathing to find his rocks (though it may cause Urist McHauler to do even more pathing).
• Keep Haulers near places where things will need to be moved from (excess stockpiles, mines, butcher's shops or other shops that have a high item yield).
• Make it easy to get in and out of the areas where workshops are.
• Staircases in rooms instead of in central areas should greatly improve pathing speeds.
• Applying traffic costs properly will greatly increase the speed of finding paths. Make corners of rooms higher cost and the center of major hallways and rooms with stockpiles and workshops lower cost. More on traffic.