DF2014 Talk:Path

From Dwarf Fortress Wiki
Jump to navigation Jump to search

The following diagram shows witch fields the algorithm will have to calculate to connect between two sides through a split tunnel:

Pathing through 2 tunnels normal.gif

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:

Pathing through 2 tunnels restricted.gif

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.

Pathing through 2 tunnels explanation.gif

Kami (talk)

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. -- 22:35, 14 August 2015 (UTC)