Editing v0.31:Path

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.31"). 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.

Summary:

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)

Templates used on this page:

Template:!(( (view source) (protected)
Template:!)) (view source) (protected)
Template:(( (view source) (protected)
Template:)) (view source) (protected)
Template:ArticleVersion (view source) (protected)
Template:Av (edit)
Template:Border radius (view source) (protected)
Template:Category (view source) (protected)
Template:Current/version (view source) (protected)
Template:Dot (view source) (protected)
Template:Icolor (view source) (protected)
Template:Interface-color/orange/background (view source) (protected)
Template:Interface-color/orange/border (view source) (protected)
Template:Interface-color/orange/highlight (view source) (protected)
Template:Interface-color/orange/text (view source) (protected)
Template:Ns-name (view source) (protected)
Template:Ns-rel-id (view source) (protected)
Template:Quality (view source) (protected)
Template:Version links (view source) (protected)
Template:Version links/0 (view source) (protected)
Template:Version links/eval (view source) (protected)
Template:Version links/link (view source) (protected)
Module:MakeParserFunctions (view source)
Module:Versions (view source)
Module:Versions/parserFunctions (view source)

@@ Line 1: / Line 1: @@
-{{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.
-==How It Works==
-'''Most of this is conjecture and is meant more to offer a functional explanation than an accurate description.'''
-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===
-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.
-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 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.
-===Doing the Calculation===
-If DF is using the A* method(from the forum post):
-# 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.
-# 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.
-# Stop when we found the target an check which way lead us there.
-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:
-*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.
-==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.
-===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]].

Editing v0.31:Path

Navigation menu

Search