Path

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

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

В игре используется модифицированный алгоритм поиска A* (красивая визуализация) (подтверждение), который быстро вычисляет правильный путь между точками. Метод A * берет точку A и пытается быстро вычислить подходящий путь для достижения точки B. Этот путь не всегда является самым быстрым — в игре с такой сложной и постоянно меняющейся средой, как Dwarf Fortress, алгоритм редко выбирает самый быстрый путь. Цель и полезность алгоритма состоит в том, чтобы найти полезный путь, балансируя между скоростью и количеством вычислений.

При поиске материалов в первую очередь путь ищется к тем материалам, Манхеттенское расстояние до которых будет наименьшим. Это гораздо менее затратно, чем вычислять полноценные пути ко всем материалам. Таким образом, при конструировании вещей список допустимых материалов будет упорядочен от ближайшего к самому дальнему; то есть первым делом проверяется расстояние от текущего положения дварфа до материала по горизонтали и вертикали, игнорируя диагональные перемещения и любые препятствия, которые могут оказаться на пути. Важная часть планирования крепости — строить как можно более открытые пространства; большее количество прямых путей приведет к более быстрым вычислениям (и, следовательно, к лучшей производительности), а также позволит избежать сложностей, когда по метрике объекты находятся рядом, а путь приходится искать через всю карту. Мастерские автоматически находят ближайшее доступное сырьё; а при строительстве вам доступен выбор, какой материал брать.

Применение

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

Применение механизма поиска пути. Обратите внимание: если зелёный мост поднят, существа пройдут по пути для каравана.

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

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

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

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

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

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

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

В дополнение, незначительные вариации:

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

Советы по оптимизации

Чтобы улучшить скорость поиска пути и производительность:

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

Односторонние пути

Невозможно создать области, по которым можно ходить только в одну сторону (хотя было возможно в 0.28 через эксплойт бага). Однако можно создать сильное предпочтение для разных путей в разных направлениях. Алгоритм A* сам по себе асимметричен, что говорит о том, что смещение в его приоритетах по крайней мере иногда может использоваться для разделения трафика по направлениям. Рассмотрим схему:

░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░ ░RR++++++++HH░ ░ →→→→→→→→→→ ░ ++░░░░░░░░░░++ ↔┤░░░░░░░░░░├↔ ░HH++++++++RR░ ░ ←←←←←←←←←← ░ ░░░░░░░░░░░░░░ ░░░░░░░░░░░░░░ ░ : стена + : floor - нормальный трафик H : floor - высокий трафик R : floor - ограниченный трафик

If this fragment is set up between a closed cave and outside, dwarves will always choose to pass through it via the left corridor, even if that corridor is farther both from the dwarf's original location and destination. Since A* is "best-first", i.e. strongly prioritizes lower path cost in the immediate vicinity, we may guess that DF calculates path from the destination to the creature. (This seems more efficient if creatures more often need to path from open space into a dead-end or maze than vice versa, or the destination is cut off from open space more often than the creature) This isn't foolproof (e.g. pets ignore traffic designations and dorfs don't path through it from end to end when picking up something within it), or even too useful in itself (you need alternate paths to be very close - enough that the immediate traffic cost matters much more than difference in distance), but it does allow to e.g. make assumptions as to whether a dwarf arrives or leaves for pressure plate automation purpose, without forcing path retries (and attendant CPU load) inherent in "suddenly closed door"/"suddenly opened hatch" technique (even if you need a strict one-way, these methods can be combined, to make path retry an exception rather than rule). The longer the space between entrance and exit (left and right in the diagram) of the two one-way-floors, the more likely dwarves will stick to the desired side even obstacles like animals and dwarves are in their way. Of course, there will be fewer actual collisions than predicted if everyone moves in the same direction.

Warning: Using Restricted traffic on floors dwarves have to pass - like the entrance of a fortress - leads to high pathing costs (and thus potentially FPS drop) because of searching for alternative routes!^{Требует проверки}

If you want to use this, keep those (path-through) restricted areas as small as possible. On the other side, the higher the restricted costs, the more likely dwarves stick to the correct site. The same is true for longer tunnels. And the longer the tunnel, the less additional pathing will be done. If the tunnel is at least as long as the costs of the restricted area, you don't have to bother additional costs. So, this should only be used for long tunnels. Never use it to control traffic inside your fort between rooms unless you restrict most of your fort's area!

Прочее

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

Если у вас есть длинный коридор шириной в 1 клетку, по которому уже движется дварф, другие дварфы, которым нужно перейти с одной стороны коридора на другую, попытаются избежать столкновения с этим дварфом, пройдя путь в другом месте. Если так получится, что коридор длинный и поблизости нет альтернативных маршрутов, это может привести к очень значительному увеличению нагрузки при поиске пути.

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

"Path" на других языках Дварфийский: nimar Эльфийский: alí Гоблинский: snust Язык людей: anur