Path - Revision history

91.49.240.46: /* Path finding method */

2026-02-07T11:59:12Z

Path finding method

Silverwing235: /* Optimizations */

2025-05-09T11:05:06Z

Optimizations

Silverwing235 at 11:03, 9 May 2025

2025-05-09T11:03:04Z

Quietust: better yet, just remove this first bit

2025-05-09T03:47:33Z

better yet, just remove this first bit

Quietust: /* Path finding method */ fix this spot too

2025-05-09T03:42:41Z

Path finding method: fix this spot too

Putnam3145 at 01:50, 9 May 2025

2025-05-09T01:50:11Z

Quietust: /* Path finding method */ use interwiki links, which also preserves HTTPS

2024-03-29T21:33:14Z

Path finding method: use interwiki links, which also preserves HTTPS

ForgottenBeet: /* Implications */ Rename section and simplify wording slightly to improve accuracy

2024-03-29T18:43:01Z

Implications: Rename section and simplify wording slightly to improve accuracy

ForgottenBeet: Introduce basic movement with a focus on when diagonal moves are allowed

2024-03-29T18:27:17Z

Introduce basic movement with a focus on when diagonal moves are allowed

Quietust: /* Applications */ Rule T

2024-03-29T13:08:32Z

Applications: Rule T

← Older revision		Revision as of 11:59, 7 February 2026
Line 82:		Line 82:

	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. Workshops automatically path to the nearest valid raw materials; building things allows you to choose what to grab.		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. Workshops automatically path to the nearest valid raw materials; building things allows you to choose what to grab.
		+
		+	Note: The Manhatten distance does not really seem to be used in the current version to find the nearest (valid) material. That would mean that materials with x-distance n (and y-distance and z-distance both being zero) would be gathered before materials with x-distance (n-k), where 0<k<n, and (the sum of y-distance plus z-distance + k being greater than n), but this is not the case. Rather the materials with x-distance (n-k) are gathered before materials with x-distance n. So the actual algorithm for choosing the next material for a job seems to be using first the maximum norm in the three coordinate directions (ie. a cube of size 0 to k) until at least one valid material is found in a cube with radius i (0<=i<=k) - the cube radius is increased until at least one valid material is found in the cube. After such a cube is found the manhatten distance is used to decide which of the valid materials in the cube with radius i should be gathered. Of course walls and any obstacles are ignored.

	== Applications ==		== Applications ==

@@ Line 107: / Line 107: @@
 ===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).
+*Keep small stockpiles immediately next to workshops. This means Urist McCrafter doesn't have to do very much pathing to find their 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.

@@ Line 2: / Line 2: @@
 {{av}}
-[[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.
+[[File:pathing_preview.png|right]]'''Pathing''' is a videogame concept that refers to the path an AI selected to route from point A to B. It has important implications for [[workshop design|fortress design]], [[security design]] and [[framerate]] management.
 == Basic movement ==
@@ Line 79: / Line 79: @@
 == Path finding method ==
-''Dwarf Fortress'' uses the [[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 the ideal path between points. Despite what this wiki has previously said, the heuristic used in Dwarf Fortress is admissible, and thus the ideal path is always found; whether your dwarf actually picks the right point B to go to is a different question.
+''Dwarf Fortress'' uses the [[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 the ideal path between points. Despite what this wiki has previously said, the heuristic used in ''Dwarf Fortress'' is admissible, and thus the ideal path is always found; whether your dwarf actually picks the right point B to go to is a different question.
 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. Workshops automatically path to the nearest valid raw materials; building things allows you to choose what to grab.

@@ Line 81: / Line 81: @@
 ''Dwarf Fortress'' uses the [[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 the ideal path between points. Despite what this wiki has previously said, the heuristic used in Dwarf Fortress is admissible, and thus the ideal path is always found; whether your dwarf actually picks the right point B to go to is a different question.
-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 closed as possible, as more doorways will result in more path choices (and thus worse performance), though at the same time making sure that nearby regions have direct paths between them (to avoid 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.
+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. Workshops automatically path to the nearest valid raw materials; building things allows you to choose what to grab.
 == Applications ==

@@ Line 81: / Line 81: @@
 ''Dwarf Fortress'' uses the [[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 the ideal path between points. Despite what this wiki has previously said, the heuristic used in Dwarf Fortress is admissible, and thus the ideal path is always found; whether your dwarf actually picks the right point B to go to is a different question.
-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.
+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 closed as possible, as more doorways will result in more path choices (and thus worse performance), though at the same time making sure that nearby regions have direct paths between them (to avoid 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 ==

@@ Line 5: / Line 5: @@
 == Basic movement ==
-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>):
+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. For example, this rat (<tt>r</tt>) can reach the cheese (<tt>%</tt>):
 <diagram>
@@ Line 79: / Line 79: @@
 == 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.
+''Dwarf Fortress'' uses the [[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 the ideal path between points. Despite what this wiki has previously said, the heuristic used in Dwarf Fortress is admissible, and thus the ideal path is always found; whether your dwarf actually picks the right point B to go to is a different question.
 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.
@@ Line 87: / Line 87: @@
 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 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.
+The way pathing is handled should influence the way you design your fortress. An important part of fortress design is to be as closed as possible (again, the exact opposite of what the wiki has previously said), to reduce the amount of tiles searched overall; A*, in edge cases, will search every single tile on the map, so making sure there are simply fewer tiles will speed up the game in those edge cases. Those edge cases are, generally, the only place where pathfinding actually has any major effect on performance.
 [[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.]]
@@ Line 114: / Line 114: @@
 ===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:
+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 allows asymmetry, 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|\
 ░░░░░░░░░░░░░░  ░░░░░░░░░░░░░░

@@ Line 78: / Line 78: @@
 </diagram>
-== Implications ==
+== Path finding method ==
 ''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 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.
-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.
+Choosing the nearest raw materials uses the shortcut of checking the [http://en.wikipedia.org/wiki/Manhattan_distance 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 ==

← Older revision		Revision as of 18:27, 29 March 2024
Line 3:		Line 3:

	[[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.		[[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.
		+
		+	== Basic movement ==
		+	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>):
		+
		+	<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>></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>

	== Implications ==		== Implications ==