- 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.
Difference between revisions of "v0.34:Path"
(Importing content from v0.31 (391/614)) |
|||
| (10 intermediate revisions by 5 users not shown) | |||
| Line 1: | Line 1: | ||
| − | {{ | + | {{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]]. | |
| − | ''' | ||
| − | 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 | + | == Implications == |
| + | 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. | |
| − | |||
| − | |||
| − | + | == Applications == | |
| + | In the following examples, A is a creature and B is its goal. | ||
| − | For jobs | + | 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]]. |
| + | |||
| + | 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: | |
| − | # | + | # First, we check all the tiles next to the dwarf and mark their values. |
| − | # Now | + | # From there, repeatedly check all accessible tiles from the dwarf until we reach B. |
| − | + | # Now take the tiles with the lowest values that connect to that location, and you have a path. | |
| + | #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: | 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. |
| − | |||
*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: | |
*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. | |
| − | |||
Latest revision as of 13:52, 6 September 2017
| This article is about an older version of DF. |
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 fortress design and security design.
Implications[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 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 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.
Applications[edit]
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' coffins in the next-door mason's shop.
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.
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 dwarf and mark their values.
- From there, repeatedly check all accessible tiles from the dwarf until we reach B.
- Now take the tiles with the lowest values that connect to that location, and you have a path.
- 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.
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.
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.