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.
Difference between revisions of "v0.34:Path"
Jump to navigation
Jump to search
(Importing content from v0.31 (391/614)) |
(Greatly cleaned up.) |
||
| Line 1: | Line 1: | ||
{{quality|Fine|23:59, 8 October 2010 (UTC)}}{{av}} | {{quality|Fine|23:59, 8 October 2010 (UTC)}}{{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. | 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=== | ===Choosing an A and a B=== | ||
| − | A is | + | 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. | Presumably, there are a few ways that the game finds its A and B. | ||
For constructions and buildings, the player designates the B from a list ordered by closest. | 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 | + | 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=== | ||
| − | + | 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. | 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. | ||
| + | |||
| + | ==Things That Reduce Pathing Speed== | ||
| + | *Resources that are geographically close to a workshop but inaccessible or hard to reach. | ||
==Tips For Improving Pathing Speeds== | ==Tips For Improving Pathing Speeds== | ||
| Line 32: | Line 37: | ||
*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]]. | |
| − | |||
| − | 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]]. | ||
Revision as of 19:52, 20 May 2012
| This article is about an older version of DF. |
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, this thread argues that ToadyOne use a version of 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 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
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.
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 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.