Path

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

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

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

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

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

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

Применение

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

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

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

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

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

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

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

1. Сначала мы проверяем все соседние точке А клетки и рассчитываем их значения.
2. Затем последовательно проверяем все свободные клетки, пока не достигнем точки B.
3. Выбираем те из клеток, соединяющих А и В, которые имеют наименьшую стоимость.
4. Теперь А может следовать к точке В.

Бесцельно скитающиеся существа могут использовать этот метод в комбинации со случайными перемещениями. Для работ, которые требуют преследования движущегося существа алгоритм будет повторяться снова и снова (или будет использован другой алгоритм). В дополнение, незначительные вариации:

• Дварфы могут помнить путь, который работал раньше, и проверят его, прежде чем искать новый.
• Недоступные предметы могут быть невидимы для дварфов, будучи помечеными как forbidden через некоторое время после того, как дварфы узнают, что он недоступен. Таким образом, этот предмет не будет учитываться при поиске пути.

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

• Ставьте маленькие склады вплотную к мастерским. Это значит, что Уристу МакКрафтеру не придется долго искать путь к своему камню (хотя это может привести и к тому, что он будет искать еще дольше).
• Держите носильщиков в местах, где часто нужно таскать вещи (особенно рядом со складами, шахтами, скотобойней и другими мастерскими, которые производят на выходе большое количество предметов).
• Страрайтесь, чтобы входы и выходы из зон мастерских было легко найти.
• Размещение лестниц в комнатах, а не в центре зон, значительно уменьшает время поиска пути.
• Грамотная разметка зон передвижения значительно уменьшает время поиска пути. Назначьте углам комнат высокую цену, а центрам важных проходов и комнат со складами - низкую.

Регулирование движения

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.