Difference between revisions of "Path"

Latest revision as of 21:33, 29 March 2024

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

v50.14 · v0.47.05

This article is about the current version of DF.
Note that some content may still need to be updated.

Pathing is a videogame concept that refers to the path the AI selected to route from point A to B. It has important implications for fortress design, security design and framerate management.

Basic movement[edit]

Creatures can move in the four cardinal directions (north, south, east, and west), and four diagonal directions (northeast, southeast, southwest, northwest), as long as the target space is not blocked. This means creatures can path through diagonal gaps on the same Z-level. For example, this rat (r) can reach the cheese (%):

r	░
░	%

Creatures can move directly up or down, as long as the target space is not blocked and the movement is possible (via flying, climbing, swimming, stairs, etc.). Creatures can move diagonally across Z-levels only when both lateral and vertical movement are simultaneously possible (e.g., when using a ramp), with one exception[1] (see below). For example, this giant sparrow (S) can not attack the cat (c):

S

░

T

h

i

s

d

i

a

g

r

a

m

h

a

s

m

u

l

t

i

p

l

e

z

-

l

e

v

e

l

s

!

P

r

e

s

<

t

o

g

o

u

p

o

n

e

z

-

l

e

v

e

l

.

░

c

░

T

h

i

s

d

i

a

g

r

a

m

h

a

s

m

u

l

t

i

p

l

e

z

-

l

e

v

e

l

s

!

P

r

e

s

>

t

o

g

o

d

o

w

n

o

n

e

z

-

l

e

v

e

l

.

░

T

h

i

s

d

i

a

g

r

a

m

h

a

s

m

u

l

t

i

p

l

e

z

-

l

e

v

e

l

s

!

P

r

e

s

>

t

o

g

o

d

o

w

n

o

n

e

z

-

l

e

v

e

l

.

Exception for diagonal movement between Z levels[edit]

Diagonal movement between Z-levels is possible when the floor is missing from the space above the wall, which would otherwise block movement. Flying and swimming creatures can pass through the gap caused by the missing floor. Common causes for a missing floor include building an up-down or down stair (without the matching up staircase below it), or constructing a wall underneath tree branches.[2] For example, this giant sparrow can attack the cat, because the down stairs (>) on level 2 has removed the floor, creating a hidden gap:

S

░

T

h

i

s

d

i

a

g

r

a

m

h

a

s

m

u

l

t

i

p

l

e

z

-

l

e

v

e

l

s

!

P

r

e

s

<

t

o

g

o

u

p

o

n

e

z

-

l

e

v

e

l

.

░

>

c

░

T

h

i

s

d

i

a

g

r

a

m

h

a

s

m

u

l

t

i

p

l

e

z

-

l

e

v

e

l

s

!

P

r

e

s

>

t

o

g

o

d

o

w

n

o

n

e

z

-

l

e

v

e

l

.

░

T

h

i

s

d

i

a

g

r

a

m

h

a

s

m

u

l

t

i

p

l

e

z

-

l

e

v

e

l

s

!

P

r

e

s

>

t

o

g

o

d

o

w

n

o

n

e

z

-

l

e

v

e

l

.

Path finding method[edit]

Dwarf Fortress uses a modified A* search algorithm (a nice demo) (confirmation), which quickly calculates a decent path between points. 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 an environment as Dwarf Fortress, pathing probably rarely chooses the quickest path. The purpose and utility of the algorithm is to find a useful path without using a lot of processing space, balancing speed and computability.

Choosing the nearest raw materials uses the shortcut of checking the Manhattan distance from the dwarf's current position, rather than an actual search. Thus, when constructing things, the valid materials list will be ordered from nearest to farthest; this, however, ignores any walls or obstacles in the way. An important part of fortress design is to be as open as possible, as more doorways will result in quicker paths (and thus better performance) as well as avoiding the hurdles of cross-map walks to find something the metric says is a short distance away. Workshops automatically path to the nearest valid raw materials; building things allows you to choose what to grab.

Applications[edit]

For workshop jobs, the closest available valid material is used for the job. The simplest way to use pathing to your advantage is to surround a workshop with a stockpile accepting only specific raw materials that you want it to be using. While this is usually better handled by using linked stockpiles, it remains useful when trying to understand why, instead of decorating some beds in your furniture stockpile, your gem setter decides to fancify some commoners' coffins in the next-door mason's workshop.

The way pathing is handled should influence the way you design your fortress. An important part of fortress design is to be as open as possible, as more doorways will result in quicker paths (and thus better performance) as well as avoiding the hurdles of cross-map walks to find something the metric says is a short distance away.

Applications of pathing (aka pathing abuse). Note that they do see every path, so if the green bottom bridge is raised, they will take the caravan entrance instead.

Implications in security design are a bit more thorough. Hostile creatures and dwarves running errands are able to consider the entire map when making pathing choices, and their A* pathfinding will mean that they will always take the shortest route, if there is a choice. This is a point separating trading caravans, which path to your trade depot, from goblin sieges, which look for the shortest path in instead. One clever exploit of this behavior is demonstrated at right; caravans will always take the winding, clean-top path, because that is where the trading post is, while incoming enemies will prefer the shorter, trapped bottom entrance.

Doing the Calculation[edit]

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:

First, we check all the tiles next to the target and mark their values.
From there, repeatedly check all accessible tiles from the target until we reach the dwarf.
From the dwarf, pick recursively the tiles with the lowest value, and you have a path.
Now the dwarf will follow this path to get to the target.

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 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.

Optimizations[edit]

To improve pathing speed and performance:

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.

Splitted One-way[edit]

It's not possible to create areas path-able in one way only (though it was in 0.28, by exploiting a bug). However, it's possible to create a strong preference for pathing differently in different directions. A* algorithm in itself is asymmetrical, which suggests that bias in its priorities at least sometimes can be exploited to split traffic by direction. Consider this floor diagram:

░

R

+

H

░

→

░

+

░

+

↔

┤

░

├

↔

░

H

+

R

░

←

░

:

w

a

l

+

:

f

l

o

r

-

n

o

r

m

a

l

t

r

a

f

i

c

H

:

f

l

o

r

-

H

i

g

h

t

r

a

f

i

c

R

:

f

l

o

r

-

R

e

s

t

r

i

c

t

e

d

t

r

a

f

i

c

If this fragment is set up between a closed cave and outside, dwarves will always choose to pass through it via the left corridor, even if that corridor is farther both from the dwarf's original location and destination. Since A* is "best-first", i.e. strongly prioritizes lower path cost in the immediate vicinity, we may guess that DF calculates path from the destination to the creature. (This seems more efficient if creatures more often need to path from open space into a dead-end or maze than vice versa, or the destination is cut off from open space more often than the creature.)

This isn't foolproof (e.g. pets ignore traffic designations and dorfs don't path through it from end to end when picking up something within it), or even too useful in itself (you need alternate paths to be very close - enough that the immediate traffic cost matters much more than difference in distance), but it does allow to e.g. make assumptions as to whether a dwarf arrives or leaves for pressure plate automation purpose, without forcing path retries (and attendant CPU load) inherent in "suddenly closed door"/"suddenly opened hatch" technique (even if you need a strict one-way, these methods can be combined, to make path retry an exception rather than rule).

The longer the space between entrance and exit (left and right in the diagram) of the two one-way-floors, the more likely dwarves will stick to the desired side even obstacles like animals and dwarves are in their way. Of course, there will be fewer actual collisions than predicted if everyone moves in the same direction.

Warning: Using Restricted traffic on floors dwarves have to pass — like the entrance of a fortress - leads to high pathing costs (and thus potentially FPS drop) because of searching for alternative routes!^[Verify]

If you want to use this, keep those (path-through) restricted areas as small as possible. On the other side, the higher the restricted costs, the more likely dwarves stick to the correct site. The same is true for longer tunnels. And the longer the tunnel, the less additional pathing will be done. If the tunnel is at least as long as the costs of the restricted area, you don't have to bother additional costs. So, this should only be used for long tunnels. Never use it to control traffic inside your fort between rooms unless you restrict most of your fort's area!

Other dwarves[edit]

It is possible for entities such as dwarves to walk over each other when necessary. However, moving over occupied tiles in this manner is much slower, and dwarves will try to path so that they can avoid it. This introduces an important consideration to fortress design.

If you have a long, 1-tile wide corridor which already has a dwarf moving through it, other dwarves who need to get from one side of the corridor to the other will try to avoid colliding with that dwarf, by pathing elsewhere. If it so happens that the corridor is long, and there are no nearby alternative routes, this may cause a very significant increase in pathfinding burden.

For this reason, it's best to make high-traffic routes at least 2 tiles wide, and avoid single doors and single stairs. This ensures that when a dwarf tries to find a detour around another dwarf in his way, he will be able to do so easily and without modifying his current path much.

"Path" in other Languages

Dwarven:	nimar
Elven:	alí
Goblin:	snust
Human:	anur

@@ Line 1: / Line 1: @@
-{{Migrated_article}}
+{{Quality|Exceptional}}
-{{Quality|Superior|20:04, 25 July 2013 (UTC)}}
 {{av}}
-'''Pathing''' is a video game concept that refers to the path that the AI selected to route from point A to point B. It has important implications for [[workshop design|fortress design]] and [[security design]].
+[[File:pathing_preview.png|right]]'''Pathing''' is a videogame concept that refers to the path the AI selected to route from point A to B. It has important implications for [[workshop design|fortress design]], [[security design]] and [[framerate]] management.
-== Implications ==
+== Basic movement ==
-Dwarf Fortress uses a modified [http://en.wikipedia.org/wiki/A*_search_algorithm A* search algorithm] ([http://qiao.github.io/PathFinding.js/visual/ a nice demo]) ([http://www.gamasutra.com/view/feature/131954/interview_the_making_of_dwarf_.php?page=8 confirmation]), which quickly calculates a decent path between points. 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 Dwarf Fortress, pathing probably rarely chooses the quickest path. The purpose and utility of the algorithm is to find a useful path without using a lot of processing space, balancing speed and computability.
+Creatures can move in the four cardinal directions (north, south, east, and west), and four diagonal directions (northeast, southeast, southwest, northwest), as long as the target space is not blocked. This means creatures can path through diagonal gaps on the same Z-level. For example, this rat (<tt>r</tt>) can reach the cheese (<tt>%</tt>):
-Pathing to raw materials uses the so-called [http://en.wikipedia.org/wiki/Manhattan_metric Manhattan metric]: meaning, the material is checked by distance from the dwarf's current position, rather than by an actual search. Thus, when constructing things, the valid materials list will be ordered from nearest to farthest; this, however, ignores any walls or obstacles in the way. An important part of fortress design is to be as open as possible, as more doorways will result in quicker paths (and thus better performance) as well as avoiding the hurdles of cross-map walks to find something the metric says is a short distance away. Workshops automatically path to the nearest valid raw materials; building things allows you to choose what to grab.
+<diagram>
+r░
+░%
+</diagram>
+Creatures can move directly up or down, as long as the target space is not blocked and the movement is possible (via flying, climbing, swimming, stairs, etc.). Creatures can move diagonally across Z-levels only when both lateral and vertical movement are simultaneously possible (e.g., when using a ramp), with one exception[http://www.bay12forums.com/smf/index.php?topic=144364.msg5705256#msg5705256] (see below). For example, this giant sparrow (<tt>S</tt>) can not attack the cat (<tt>c</tt>):
+<diagram>
+<frame type=level level=0>
+S░░
+This diagram has multiple z-levels! Press
+< to go up one z-level.
+</frame>
+<frame type=level level=1>
+░░░░
+░ c░
+░░░░
+This diagram has multiple z-levels! Press
+> to go down one z-level.
+</frame>
+<frame type=level level=2>
+ ░░
+This diagram has multiple z-levels! Press
+> to go down one z-level.
+</frame>
+</diagram>
+=== Exception for diagonal movement between Z levels ===
+Diagonal movement between Z-levels is possible when the floor is missing from the space above the wall, which would otherwise block movement. Flying and swimming creatures can pass through the gap caused by the missing floor. Common causes for a missing floor include building an up-down or down stair (without the matching up staircase below it), or constructing a wall underneath tree branches.[http://www.bay12games.com/dwarves/mantisbt/view.php?id=7130#c26072] For example, this giant sparrow ''can'' attack the cat, because the down stairs (<tt>&gt;</tt>) on level 2 has removed the floor, creating a hidden gap:
+<diagram>
+<frame type=level level=0>
+S░░
+This diagram has multiple z-levels! Press
+< to go up one z-level.
+</frame>
+<frame type=level level=1>
+░░░░
+░>c░
+░░░░
+This diagram has multiple z-levels! Press
+> to go down one z-level.
+</frame>
+<frame type=level level=2>
+ ░░
+This diagram has multiple z-levels! Press
+> to go down one z-level.
+</frame>
+</diagram>
+== Path finding method ==
+''Dwarf Fortress'' uses a modified [[wikipedia:A* search algorithm|A* search algorithm]] ([http://qiao.github.io/PathFinding.js/visual/ a nice demo]) ([http://www.gamasutra.com/view/feature/131954/interview_the_making_of_dwarf_.php?page=8 confirmation]), which quickly calculates a decent path between points. 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 an environment as ''Dwarf Fortress'', pathing probably rarely chooses the quickest path. The purpose and utility of the algorithm is to find a useful path without using a lot of processing space, balancing speed and computability.
+Choosing the nearest raw materials uses the shortcut of checking the [[wikipedia:Manhattan distance|Manhattan distance]] from the [[dwarf]]'s current position, rather than an actual search. Thus, when constructing things, the valid materials list will be ordered from nearest to farthest; this, however, ignores any walls or obstacles in the way. An important part of fortress design is to be as open as possible, as more doorways will result in quicker paths (and thus better performance) as well as avoiding the hurdles of cross-map walks to find something the metric says is a short distance away. Workshops automatically path to the nearest valid raw materials; building things allows you to choose what to grab.
 == Applications ==
-In the following examples, A is a creature and B is its goal.
-For workshop jobs, the closest available valid material is used for the job. The simplest way to use pathing to your advantage is to surround a workshop with a stockpile accepting only specific raw materials that you want it to be using; in previous versions, this was the only way to ensure [[magma-safe]] materials would be used for application with [[magma]], and the only way to ensure certain jobs would be done in a certain way. Now, this process is better handled by linked stockpiles instead. Nonetheless, it remains useful when trying to understand why, instead of decorating some beds in your furniture stockpile, your [[gem setter]] decides to fancify some commoners' [[coffin]]s in the next-door [[mason's shop]].
+For workshop jobs, the closest available valid material is used for the job. The simplest way to use pathing to your advantage is to surround a workshop with a stockpile accepting only specific raw materials that you want it to be using. While this is usually better handled by using linked stockpiles, it remains useful when trying to understand why, instead of decorating some beds in your furniture stockpile, your [[gem setter]] decides to fancify some commoners' [[coffin]]s in the next-door [[mason's workshop]].
-The way pathing is handled should inform the way you design your fortress. An important part of fortress design is to be as open as possible, as more doorways will result in quicker paths (and thus better performance) as well as avoiding the hurdles of cross-map walks to find something the metric says is a short distance away.
+The way pathing is handled should influence the way you design your fortress. An important part of fortress design is to be as open as possible, as more doorways will result in quicker paths (and thus better performance) as well as avoiding the hurdles of cross-map walks to find something the metric says is a short distance away.
 [[File:Pathing.jpg|thumb|right|300px|Applications of pathing (aka pathing abuse). Note that they do see every path, so if the green bottom bridge is raised, they will take the caravan entrance instead.]]
-Implications in security design are a bit more thorough. Hostile creatures and dwarves running errands are able to consider the entire map when making pathing choices, and their A* pathfinding will mean that they will always take the shortest route, if there is a choice. This is a point separating trading [[caravan]]s, which path to your [[trade depot]], from [[goblin]] [[siege]]s, which look for the shortest path in instead. One clever exploit of this behavior is demonstrated at right; caravans will always take the winding, clean top path because that is where the trading post is, while incoming enemies will prefer the shorter, trapped bottom entrance.
+Implications in security design are a bit more thorough. Hostile creatures and dwarves running errands are able to consider the entire map when making pathing choices, and their A* pathfinding will mean that they will always take the shortest route, if there is a choice. This is a point separating trading [[caravan]]s, which path to your [[trade depot]], from [[goblin]] [[siege]]s, which look for the shortest path in instead. One clever exploit of this behavior is demonstrated at right; caravans will always take the winding, clean-top path, because that is where the trading post is, while incoming enemies will prefer the shorter, trapped bottom entrance.
 ===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 | traffic value]]. Thus the procedure is something like this:
+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|traffic value]]. Thus the procedure is something like this:
-# First, we check all the tiles next to the dwarf and mark their values.
+# First, we check all the tiles next to the target and mark their values.
-# From there, repeatedly check all accessible tiles from the dwarf until we reach B.
+# From there, repeatedly check all accessible tiles from the target until we reach the dwarf.
-# Now take the tiles with the lowest values that connect to that location, and you have a path.
+# From the dwarf, pick recursively the tiles with the lowest value, and you have a path.
-#Now A will follow this path to get to B.
+#Now the dwarf will follow this path to get to the target.
-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.
+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 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.
+*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.
+===Optimizations===
 To improve pathing speed and performance:
 *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).
@@ Line 41: / Line 112: @@
 *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]].
+===Splitted One-way===
+It's not possible to create areas path-able in one way only (though it was [[40d:One-way|in 0.28]], by exploiting a bug). However, it's possible to create a strong preference for pathing differently in different directions. A* algorithm in itself is asymmetrical, which suggests that bias in its priorities at least sometimes can be exploited to split traffic by direction. Consider this floor diagram:
+{{diagram|spaces=yes|\
+░░░░░░░░░░░░░░  ░░░░░░░░░░░░░░
+░RR++++++++HH░  ░ →→→→→→→→→→ ░
+++░░░░░░░░░░++  ↔┤░░░░░░░░░░├↔
+░HH++++++++RR░  ░ ←←←←←←←←←← ░
+░░░░░░░░░░░░░░  ░░░░░░░░░░░░░░
+░ : wall
++ : floor - normal traffic
+H : floor - High traffic
+R : floor - Restricted traffic
+}}
+If this fragment is set up between a closed cave and outside, dwarves will always choose to pass through it via the left corridor, even if that corridor is farther both from the dwarf's original location and destination. Since A* is "best-first", i.e. strongly prioritizes lower path cost in the immediate vicinity, we may guess that DF calculates path ''from'' the destination to the creature. (This seems more efficient if creatures more often need to path from open space ''into'' a dead-end or maze than vice versa, or the destination is cut off from open space more often than the creature.)
+This isn't foolproof (e.g. pets ignore traffic designations and dorfs don't path ''through'' it from end to end when picking up something ''within'' it), or even too useful in itself (you need alternate paths to be very close - enough that the immediate traffic cost matters much more than difference in distance), but it does allow to e.g. make assumptions as to whether a dwarf arrives or leaves for [[pressure plate]] automation purpose, without forcing path retries (and attendant CPU load) inherent in "suddenly closed door"/"suddenly opened hatch" technique (even if you need a strict one-way, these methods can be combined, to make path retry an exception rather than rule).
+The longer the space between entrance and exit (left and right in the diagram) of the two one-way-floors, the more likely dwarves will stick to the desired side even obstacles like animals and dwarves are in their way. Of course, there will be fewer actual collisions than predicted if everyone moves in the same direction.
+'''Warning:''' Using Restricted traffic on floors dwarves have to pass — like the entrance of a fortress - leads to high pathing costs (and thus potentially FPS drop) because of searching for alternative routes!{{verify}}
+If you want to use this, keep those (path-through) restricted areas as small as possible. On the other side, the higher the restricted costs, the more likely dwarves stick to the correct site. The same is true for longer tunnels. And the longer the tunnel, the less additional pathing will be done. If the tunnel is at least as long as the costs of the restricted area, you don't have to bother additional costs. So, this should only be used for long tunnels. Never use it to control traffic inside your fort between rooms unless you restrict most of your fort's area!
 ==Other dwarves==
@@ Line 48: / Line 143: @@
 For this reason, it's best to make high-traffic routes at least 2 tiles wide, and avoid single doors and single stairs. This ensures that when a dwarf tries to find a detour around another dwarf in his way, he will be able to do so easily and without modifying his current path much.
+{{Translation
+| dwarven = nimar
+| elvish  = alí
+| goblin  = snust
+| human   = anur
+}}
+{{Category|Game mechanics}}
+[[ru:Path]]