Path

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

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

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

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

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

Применение:

В примерах ниже: А - существо, В - его цель.

Применение механизма поиска пути в целях безопасности

Для мастерских используется ближайший доступный материал, необходимый для работы. Простейший способ использовать это - окружить мастерскую складами, разрешив хранение только тех материалов, которые нужны. В предыдущих версиях это было единственным способом гарантировать создание предметов из конкретного материала или, например, только из магмостойчивых материалов. В текущей версии гораздо удобнее привязывать склады к мастерским. Однако это остается полезным для понимания того, почему ваш инкрустатор решил украсить пару крестьянских гробов из соседней мастерской канещика, вместо того, чтобы украшать кровати со склада фурнитуры.

Понимание алгоритма поиска пути поможет вам должным образом спроектировать крепость. Для крепости важно быть отрытой настолько, насколько возможно, т.к. увеличение числа проходов делает пути короче, снижая затраты на их поиск, и помогает избежать побочного эффекта метода Манхеттена, когда Урист решает взять предмет из смежной комнаты, несмотря на то, что для этого ему придется обойти полкрепости, вместо того, чтобы взять такой же на другом конце комнаты (потому что без учета препятствий предмет в соседней комнате ближе).

С планированием безопасности несколько иначе: враждебные существа и дфарфы, бегающие по делам, видят карту целиком, и с помощью алгоритма А* всегда найдут самый короткий маршрут. Поэтому путь каравана торговцев, направляющегося к торговой площади, отличается от гоблинской осады, ищущей кратчайший путь в крепость. На скриншоте справа продемонстрирован хитрый эксплоит, основанный на таком поведении: караваны всегда выберут петляющий верхний коридор, потому что в нем находится торговая площадь, тогда как вражеский отряд предпочтет более короткий нижний коридор, усеянный ловушками.

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

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.