Path

Поиск пути в видеоиграх относится к тому, как ИИ идёт из A в B. Существует несколько способов поиска пути, но в этой теме приведены серьёзные аргументы, что ToadyOne использует модифицированный метод A*.

Данная статья помечена как не оконченная. Вы можете прочитать эту статью на английском или помочь проекту её переводом.

Как это работает

Большая часть этого текста - догадки, и предполагает скорее функциональное объяснение, чем точное описание.

Метод A* берет точку A и пробует быстро вычислить кратчайший путь до точки B. Этот путь не всегда получается самым быстрым. Фактически, в игре с таким сложным и изменчивым окружением, как в DF, алгоритм нахождения пути редко найдет самый быстрый путь. Целью алгоритма является найти путь быстро, не слишком сильно отклоняясь от нужного направления.

Выбор 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.

Выполняем вычисление

If DF is using the A* method(from the forum post):

1. 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.
2. 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.
3. 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.

Советы для повышения скорости нахождения пути

• 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.