v50 Steam/Premium information for editors
  • v50 information can now be added to pages in the main namespace. v0.47 information can still be found in the DF2014 namespace. See here for more details on the new versioning policy.
  • Use this page to report any issues related to the migration.
This notice may be cached—the current version can be found here.

Editing v0.34:Path

Jump to navigation Jump to search

Warning: You are not logged in.
Your IP address will be recorded in this page's edit history.

You are editing a page for an older version of Dwarf Fortress ("Main" is the current version, not "v0.34"). Please make sure you intend to do this. If you are here by mistake, see the current page instead.

The edit can be undone. Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.

Latest revision Your text
Line 1: Line 1:
{{Quality|Superior|20:04, 25 July 2013 (UTC)}}
+
{{quality|Fine|23:59, 8 October 2010 (UTC)}}{{av}}
{{av}}
+
Pathing in videogames refers to how the AI goes from A to B. There are many ways to do pathfinding, but [http://www.bay12forums.com/smf/index.php?topic=56041.0 this thread] makes a strong argument that ToadyOne uses a modified A* method.
  
'''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]].
+
==How It Works==
 +
'''Most of this is conjecture and is meant more to offer a functional explanation than an accurate description.'''
  
== Implications ==
+
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.
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 a complicated and ever changing environments like 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 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.
  
== Applications ==
+
For constructions and buildings, the player designates the B from a list ordered by closest.
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 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.
 
 
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.
 
 
 
[[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.
 
  
 
===Doing the Calculation===
 
===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:
+
If DF is using the A* method(from the forum post):
# First, we check all the tiles next to the dwarf and mark their values.
+
# 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.
# From there, repeatedly check all accessible tiles from the dwarf until we reach B.
+
# 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.
# Now take the tiles with the lowest values that connect to that location, and you have a path.
+
# Stop when we found the target an check which way lead us there.
#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.
 
  
 +
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:
 
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.
+
*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.
 
*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.
  
To improve pathing speed and performance:
+
==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 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).
 
*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.
 
*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.
 
*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]].
 
 
==Other dwarves==
 
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.
+
===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]].

Please note that all contributions to Dwarf Fortress Wiki are considered to be released under the GFDL & MIT (see Dwarf Fortress Wiki:Copyrights for details). If you do not want your writing to be edited mercilessly and redistributed at will, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource. Do not submit copyrighted work without permission!

To protect the wiki against automated edit spam, we kindly ask you to solve the following CAPTCHA:

Cancel Editing help (opens in new window)