Path: различия между версиями

Материал из Dwarf Fortress Wiki
Перейти к навигацииПерейти к поиску
Нет описания правки
Нет описания правки
 
(не показано 27 промежуточных версий 5 участников)
Строка 1: Строка 1:
[[File:pathing_preview.png|right]]'''Поиском пути''' в видеоиграх называется то, как ИИ идёт из A в B. Эта механика оказывает большое влияние на [[framerate|частоту кадров]], [[security design|построение обороны]] и [[workshop design|дизайн крепости]] в целом.


==Как это работает==
В игре используется модифицированный [[wikipedia:ru:A*_search_algorithm|алгоритм поиска A*]] ([http://qiao.github.io/PathFinding.js/visual/ красивая визуализация]) ([http://www.gamasutra.com/view/feature/131954/interview_the_making_of_dwarf_.php?page=8 подтверждение]), который быстро вычисляет правильный путь между точками. Метод A* берет точку A и пытается быстро вычислить подходящий путь для достижения точки B. Этот путь не всегда является самым быстрым — в игре с такой сложной и постоянно меняющейся средой, как ''Dwarf Fortress'', алгоритм редко выбирает самый быстрый путь. Цель и полезность алгоритма состоит в том, чтобы найти полезный путь, балансируя между скоростью и количеством вычислений.


'''Поиск пути''' в видеоиграх относится к тому, как ИИ идёт из A в B. Существует несколько способов поиска пути, но в [http://www.bay12forums.com/smf/index.php?topic=56041.0 этой теме] приведены серьёзные аргументы, что [[ToadyOne]] использует модифицированный [http://ru.wikipedia.org/wiki/Алгоритм_поиска_A* метод A*].
При поиске материалов в первую очередь путь ищется к тем материалам, [[wikipedia:ru:Расстояние_городских_кварталов|Манхеттенское расстояние]]<ref>Манхеттенское расстояние — простая сумма разностей по координатам и для трехмерной системы вычисляется по формуле: <br />
{{заготовка}}
|X<sub>A</sub> - X<sub>B</sub>| + |Y<sub>A</sub> - Y<sub>B</sub>| + |Z<sub>A</sub> - Z<sub>B</sub>|</ref> до которых будет наименьшим. Это гораздо менее затратно, чем вычислять полноценные пути ко всем материалам. Таким образом, при конструировании вещей список допустимых материалов будет упорядочен от ближайшего к самому дальнему; то есть первым делом проверяется расстояние от текущего положения дварфа до материала по горизонтали и вертикали, игнорируя диагональные перемещения и любые препятствия, которые могут оказаться на пути. Важная часть планирования крепости — строить как можно более открытые пространства; большее количество прямых путей приведет к более быстрым вычислениям (и, следовательно, к лучшей производительности), а также позволит избежать сложностей, когда по метрике объекты находятся рядом, а путь приходится искать через всю карту. Мастерские автоматически находят ближайшее доступное сырьё; а при строительстве вам доступен выбор, какой материал брать.
==Как это работает==
'''Большая часть этого текста - догадки, и предполагает скорее функциональное объяснение, чем точное описание.'''


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


При поиске пути к материалу используется так называемый метод Манхеттена<ref>Манхеттенское расстояние - просто среднее разностей по координатам и для трехмерной системы вычисляется по формуле: <br />
[[File: Pathing.jpg|thumb|right|300px|Применение механизма поиска пути. Обратите внимание: если зелёный мост поднят, существа пройдут по пути для каравана.]]
|X<sub>A</sub> - X<sub>B</sub>| + |Y<sub>A</sub> - Y<sub>B</sub>| + |Z<sub>A</sub> - Z<sub>B</sub>|</ref> (расстояние городских кварталов), куда менее затратный, чем настоящий поиск пути: то есть проверяется расстояние от текущего положения дварфа до материала по горизонтали и вертикали, игнорируя диагональные перемещения и любые препятствия, которые могут оказаться на пути. Так строится список доступных при строительстве материалов.


===Применение:===
Для [[Workshop|мастерских]] используется ближайший доступный материал, необходимый для работы. Простейший способ использовать это окружить мастерскую [[Stockpile|складами]], разрешив хранение только тех материалов, которые нужны. В предыдущих версиях это было единственным способом гарантировать создание предметов из конкретного материала или, например, только из [[Magma-safe materials|магмостойчивых]] материалов. В текущей версии гораздо удобнее привязывать склады к мастерским. Однако это остается полезным для понимания того, почему ваш [[gem setter|инкрустатор]] решил украсить пару крестьянских [[coffin|гробов]] из соседней мастерской каменщика, вместо того, чтобы украшать кровати со склада фурнитуры.
В примерах ниже: А - существо, В - его цель.
[[File: Pathing.jpg|thumb|right|300px|Применение механизма поиска пути в целях безопасности]]
Для [[Workshop|мастерских]] используется ближайший доступный материал, необходимый для работы. Простейший способ использовать это - окружить мастерскую [[Stockpile|складами]], разрешив хранение только тех материалов, которые нужны. В предыдущих версиях это было единственным способом гарантировать создание предметов из конкретного материала или, например, только из [[Magma-safe materials|магмостойчивых]] материалов. В текущей версии гораздо удобнее привязывать склады к мастерским. Однако это остается полезным для понимания того, почему ваш [[gem setter|инкрустатор]] решил украсить пару крестьянских [[coffin|гробов]] из соседней мастерской канещика, вместо того, чтобы украшать кровати со склада фурнитуры.


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


С планированием [[Security design|безопасности]] несколько иначе: враждебные существа и дфарфы, бегающие по делам, видят карту целиком, и с помощью алгоритма А* всегда найдут самый короткий маршрут. Поэтому путь каравана торговцев, направляющегося к торговой площади, отличается от гоблинской осады, ищущей кратчайший путь в крепость. На скриншоте справа продемонстрирован хитрый эксплоит, основанный на таком поведении: караваны всегда выберут петляющий верхний коридор, потому что в нем находится торговая площадь, тогда как вражеский отряд предпочтет более короткий нижний коридор, усеянный ловушками.
С планированием [[Security design|безопасности]] несколько иначе: враждебные существа и дварфы, бегающие по делам, видят карту целиком, и с помощью алгоритма А* всегда найдут самый короткий маршрут. Поэтому путь [[Caravan|каравана]] торговцев, направляющегося к [[Trade depot|торговой площади]], отличается от [[Goblin|гоблинской]] [[Siege|осады]], ищущей кратчайший путь в крепость. На скриншоте справа продемонстрирован хитрый эксплоит, основанный на таком поведении: караваны всегда выберут петляющий верхний коридор, потому что в нем находится торговая площадь, тогда как вражеский отряд предпочтет более короткий нижний коридор, усеянный [[Trap|ловушками]].


===Выполняем вычисление===
===Выполняем вычисление===
If DF is using the A* method(from the forum post):
Если DF использует алгоритм A*, то для каждой [[Tile|клетки]] карты, обрабатываемой алгоритмом, рассчитывается стоимость пути через нее, получающуюся из информации о том, насколько эта клетка близка к конечной цели (используются эвристические функции, вроде метода Манхеттена) и ее значении [[traffic|траффика]].
# 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.
Процесс поиска пути должен выглядеть примерно так:
# 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.
# Сначала мы проверяем все соседние точке А клетки и рассчитываем их значения.
# Stop when we found the target an check which way lead us there.
# Затем последовательно проверяем все свободные клетки, пока не достигнем точки B.
# Выбираем те из клеток, соединяющих А и В, которые имеют наименьшую стоимость.
# Теперь А может следовать к точке В.
 
Бесцельно скитающиеся существа могут использовать этот метод в комбинации со случайными перемещениями.  Для работ, которые требуют преследования движущегося существа алгоритм будет повторяться снова и снова (или будет использован другой алгоритм).
 
В дополнение, незначительные вариации:
* Дварфы могут помнить путь, который работал раньше, и проверят его, прежде чем искать новый.
* Недоступные предметы могут быть невидимы для дварфов, будучи помеченными как [[forbidden]] через некоторое время после того, как дварфы узнают, что он недоступен. Таким образом, этот предмет не будет учитываться при поиске пути.
 
===Советы по оптимизации===
Чтобы улучшить скорость поиска пути и производительность:
*Ставьте маленькие склады вплотную к мастерским. Это значит, что Уристу МакКрафтеру не придется долго искать путь к своему камню (хотя это может привести и к тому, что он будет искать еще дольше).
*Держите носильщиков в местах, где часто нужно [[Hauler|таскать вещи]] (особенно рядом со складами, шахтами, [[Butcher's shop|скотобойней]] и другими мастерскими, которые производят на выходе большое количество предметов).
*Старайтесь, чтобы входы и выходы из зон мастерских было легко найти.
*Размещение лестниц в комнатах, а не в центре зон, значительно уменьшает время поиска пути.
*Грамотная разметка {{tt|зон передвижения|traffic areas}} значительно уменьшает время поиска пути. Назначьте углам комнат высокую цену, а центрам важных проходов и комнат со складами низкую. Подробнее в статье [[Traffic]].
 
===Односторонние пути===
 
Невозможно создать области, по которым можно ходить только в одну сторону (хотя было возможно [[One-way|в 0.28]] через эксплойт бага). Однако можно создать сильное предпочтение для разных путей в разных направлениях. Алгоритм A* сам по себе асимметричен, а значит смещение в его приоритетах по крайней мере иногда может использоваться для разделения трафика по направлениям. Рассмотрим схему:
 
░░░░░░░░░░░░░░  ░░░░░░░░░░░░░░
░RR++++++++HH░  ░ →→→→→→→→→→ ░
++░░░░░░░░░░++  ↔┤░░░░░░░░░░├↔
░HH++++++++RR░  ░ ←←←←←←←←←← ░
░░░░░░░░░░░░░░  ░░░░░░░░░░░░░░
+ : нормальный трафик
H : высокий трафик
R : ограниченный трафик
░ : стена
 
Если этот фрагмент расположен между закрытой пещерой и открытым пространством, дварфы всегда предпочтут пройти через него через левый коридор, даже если этот коридор находится дальше как от исходного местоположения, так и от места назначения дварфа. Поскольку A* является алгоритмом "[[wikipedia:ru:Поиск_по_первому_наилучшему_совпадению|лучший — первый]]", то есть отдает приоритет более низкой стоимости пути в непосредственной близости, мы можем предположить, что DF вычисляет путь ''от'' пункта назначения до существа. (Эффективнее, если существам нужно чаще переходить из открытого пространства в тупик или лабиринт, чем наоборот, или если цель бывает отрезана от открытого пространства чаще, чем само существо.)
 
Здесь нет "защиты от дурака" (например, домашние животные игнорируют разметку трафика, а дварфы не проходят через него из конца в конец, когда подбирают что-то внутри этого туннеля), и даже не слишком полезно само по себе (вам нужно, чтобы альтернативные пути проходили очень близко — достаточно, чтобы непосредственная стоимость трафика имела гораздо большее значение, чем разница в расстоянии), но это позволяет, например, делать предположения относительно того, прибывает ли дварф или уходит для автоматизации чего-либо посредством [[pressure plate|нажимных пластины]], без принудительных повторных прогонов поиска пути (и сопутствующей загрузки ЦП), присущих технике "внезапно закрытая дверь"/"внезапно открывшийся люк" (даже если вам нужен строго односторонний проход, эти методы можно комбинировать, чтобы повторные попытки поиска пути были исключением, а не правилом).


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.


==Советы для повышения скорости нахождения пути==
'''Важно:''' Использование ограниченного трафика на этажах, через который дварфы должны проходить — при входе в крепость, например — приводит к высоким затратам на поиск пути (и, следовательно, к потенциально падению FPS) из-за поиска альтернативных маршрутов!{{verify}}
*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]].


{{Translation
| dwarven = nimar
| elvish  = alí
| goblin  = snust
| human  = anur
}}
[[Категория:Механика игры]]
[[en:Path]]
[[en:Path]]
== Примечания ==
<references />

Текущая версия от 22:06, 28 января 2024

Pathing preview.png

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

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

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

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

Применение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Здесь нет "защиты от дурака" (например, домашние животные игнорируют разметку трафика, а дварфы не проходят через него из конца в конец, когда подбирают что-то внутри этого туннеля), и даже не слишком полезно само по себе (вам нужно, чтобы альтернативные пути проходили очень близко — достаточно, чтобы непосредственная стоимость трафика имела гораздо большее значение, чем разница в расстоянии), но это позволяет, например, делать предположения относительно того, прибывает ли дварф или уходит для автоматизации чего-либо посредством нажимных пластины, без принудительных повторных прогонов поиска пути (и сопутствующей загрузки ЦП), присущих технике "внезапно закрытая дверь"/"внезапно открывшийся люк" (даже если вам нужен строго односторонний проход, эти методы можно комбинировать, чтобы повторные попытки поиска пути были исключением, а не правилом).

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

Важно: Использование ограниченного трафика на этажах, через который дварфы должны проходить — при входе в крепость, например — приводит к высоким затратам на поиск пути (и, следовательно, к потенциально падению FPS) из-за поиска альтернативных маршрутов!Требует проверки

Если вы хотите использовать это, старайтесь делать ограниченные области как можно меньше. С другой стороны, чем выше цена прохода по клетке, тем больше вероятность, что дварфы будут придерживаться правильного пути. То же самое и с более длинными туннелями. И чем длиннее туннель, тем меньше потребуется дополнительных поисков пути. Если длина туннеля по крайней мере не меньше стоимости прохода по клеткам зоны, вам не придётся беспокоиться о дополнительной стоимости прохода. Таким образом, эту механику следует использовать только для длинных туннелей. Никогда не используйте его для зоны трафика внутри крепости для контроля перемещения между комнатами, если вы собираетесь не ограничивать большую часть территории крепости!

"Path" на других языках
Дварфийский: nimar
Эльфийский: alí
Гоблинский: snust
Язык людей: anur
  1. Манхеттенское расстояние — простая сумма разностей по координатам и для трехмерной системы вычисляется по формуле:
    |XA - XB| + |YA - YB| + |ZA - ZB|