v0.31:Path

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

v50.14 · v0.47 · v0.34 · v0.31.25 · v0.28 · v0.23 This article is about an older version of DF. More Info · V

Pathing in videogames refers to how the AI goes from A to B. There are many ways to do pathfinding, but this thread makes a strong argument that ToadyOne uses a modified A* method.

How It Works

Most of this is conjecture and is meant more to offer a functional explanation than an accurate description.

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

A is the thing (usually a dwarf) that needs to find a path to B (an item, a place, or an enemy). 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 accessible or 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

If DF is using the A* method(from the forum post):

1. Check all accessible tiles next to the dwarf and mark down for them how many steps it took to get there, how far away they are from the target (again calculating with the manhattan method) and the sums of both previous values. Also mark from which tile we found them.
2. Now find the tiles with the lowest sum - these are tiles which brought us closer to the target and are the fewest steps away from our starting point # and check their neighbors. Ignore other tiles for now unless their sum is low.
3. Stop when we found the target an check which way lead us there.

Things that are wandering(Animals, wandering invaders) may use a combination of the above method with some random movement. 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. This seems most likely in the case of stockpiles.
• Combat and other jobs that require catching a moving target either use these calculations very often or use a different calculation.
• 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.

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.

Traffic Zoning

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.