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|Fine|23:59, 8 October 2010 (UTC)}}{{av}} |
− | {{av}} | ||
− | + | In the context of videogames and AI, pathing refers to find a route from point A to point B. While no one is certain about how [[ToadyOne]] does pathing, [http://www.bay12forums.com/smf/index.php?topic=56041.0 this thread] argues that ToadyOne use a version of [http://en.wikipedia.org/wiki/A*_search_algorithm A*]. | |
− | + | 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=== | |
+ | In our example, A is a creature and B is its goal. | ||
− | + | Presumably, there are a few ways that the game finds its A and B. | |
− | |||
− | For | + | 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 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=== | ===Doing the Calculation=== | ||
Line 26: | Line 21: | ||
#Now A will follow this path to get to B. | #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. | + | 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. | For jobs that require chasing a moving thing, this is procedure may be done over and over, or a different algorithm may be used. | ||
Line 34: | Line 29: | ||
*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. | ||
− | + | ==Things That Reduce Pathing Speed== | |
+ | *Resources that are geographically close to a workshop but inaccessible or hard to reach. | ||
+ | |||
+ | ==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). | ||
Line 40: | Line 38: | ||
*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]]. | *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]]. | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− |