- 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 "DF2014 Talk:Path"
(→Direction of the Search: new section) |
|||
| Line 12: | Line 12: | ||
[[User:Kami|Kami]] ([[User talk:Kami|talk]]) | [[User:Kami|Kami]] ([[User talk:Kami|talk]]) | ||
| + | |||
| + | == Direction of the Search == | ||
| + | |||
| + | A simple search is done from the target to the start, and not from the start to the target. Otherwise, following the numbers will likely bring you to a dead end. | ||
| + | |||
| + | Of course it is possible to search from the start, and then invert the path, but this will require a nondeterministic amount of memory for all path nodes, and if the number gets too large, it may not fit into an array, or cause a lot of alloc(),free() overhead. | ||
| + | |||
| + | Another advantage of a search from the target is, that you don't have to follow the hole path. A dwarf has likely a storage for some path nodes, but may not be able to store the whole path, so you just have to follow the path, until the dwarf's storage is filled, and save time with nodes that are too far. Of course, you can store the whole path with dynamic memory allocation, but this is inefficient. | ||
| + | --[[Special:Contributions/79.200.87.130|79.200.87.130]] 22:35, 14 August 2015 (UTC) | ||
Latest revision as of 22:35, 14 August 2015
The following diagram shows witch fields the algorithm will have to calculate to connect between two sides through a split tunnel:
The following diagram shows witch fields the algorithm will have to calculate when you add a restricted area on both ends of either split to make units prefer one direction for each way:
The reason is, that as soon as the restricted point at the end of the tunnel is reached - in this case it is on the upper tunnel at the blue circle - the algorithm adds 25 to the manhattan distance to the end. This will make it look at every field outside the tunnel with lower costs (manhattan distance + field value). This way, it will check many additional fields, depending on the position of the target and the structure of the map there.
Direction of the Search[edit]
A simple search is done from the target to the start, and not from the start to the target. Otherwise, following the numbers will likely bring you to a dead end.
Of course it is possible to search from the start, and then invert the path, but this will require a nondeterministic amount of memory for all path nodes, and if the number gets too large, it may not fit into an array, or cause a lot of alloc(),free() overhead.
Another advantage of a search from the target is, that you don't have to follow the hole path. A dwarf has likely a storage for some path nodes, but may not be able to store the whole path, so you just have to follow the path, until the dwarf's storage is filled, and save time with nodes that are too far. Of course, you can store the whole path with dynamic memory allocation, but this is inefficient. --79.200.87.130 22:35, 14 August 2015 (UTC)