Как Dwarf Fortress отслеживает так много сущностей без потери производительности?

В Dwarf Fortress вы можете одновременно иметь в игре сотни гномов, животных, гоблинов и т. Д., Каждый со своим сложным ИИ и процедурами поиска пути. Мой вопрос: как это не вызывает заметного замедления? Каждый гном работает в своем собственном потоке?

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

Простой ответ заключается в эффективности обработки каждой сущности в игре.

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

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

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

движение

Говоря о нахождении пути, это часто может быть очень трудной проблемой для больших пространств, таких как карта DF (например, 768x768x64 IIRC), однако проблему можно упростить и ускорить следующими способами:

• Предварительно запеченная сеть узлов: когда карта создана, мир можно разбить на куски, и каждому куску можно сопоставить свои выходы и входы. При обновлении чанка, например при возведении стены, требуется обновление только сети этого чанка.
• Поэтапное нахождение пути: Выполнение пути по всей карте, ячейка за ячейкой, заняло бы много времени, вместо этого вам нужно было бы найти путь по большой сети чанков, которая отображает все соединения между чанками, и затем запускать только внутренний чанк, когда переходя от куска к куску. Это делает 2 вещи для вас. Он ускоряет поиск пути, разбивая его на множество более мелких фрагментов, а также позволяет устройству менять направление на части пути вдоль пути при обновлении фрагмента. Он будет перенаправлен через большую сеть, если какой-либо из узлов будет нуждаться в перекрестном обновлении.
• Случайное рулевое управление: когда объект не движется к цели, ему нужно только ходить бесцельно. Многие мошенники просто перемещают юнит в случайном направлении, что кажется неестественным. Можно использовать различные техники рулевого управления, простые из которых предпочитают двигаться по прямой линии и имеют все меньше и меньше шансов двигаться в направлениях, идущих назад, что может составлять всего около 1%. Таким образом, устройство иногда полностью изменяет направление, но редко.

Я не буду раскрывать основы поиска пути. Большинство roguelikes используют A *, но есть и другие способы снятия кожи с кошки. Мммм кошачьей кожи ..

Личные Задачи

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

Некоторые задачи имеют требования. Изготовление кожаной юбки требует, чтобы dorf находился в таком-то магазине, где есть X предметов. Так что все они проверяются и добавляются в качестве задач в свой список. Просто как тот.

Поскольку большую часть времени единица будет в пути, проверки того, что делают юниты, могут быть очень быстрыми, только несколько юнитов будут делать выбор в любой данный момент, и поэтому в целом нет замедления даже для сотен или тысячи единиц. И помните, в DF все от пчел до троглодитов и деревьев - это единицы.

Проведя некоторые дополнительные исследования, становится ясно, что DF весело работает с поиском пути в целом. Она не разбивает карту на куски, она разбивает карту на сегменты или области, которые связаны между собой (что лучше, чем ничего наверняка), так что моя оценка выше является еще менее примером того, как работает DF, чем я думал. :) Что не означает, что DF - это не что иное, как удивительный по миллиону других причин.

Это говорит о том, что в игре важен игровой процесс. Не графика, не отличное программирование, не отличное написание, не отличная музыка, даже не интерфейс; ничто иное не важнее, чем сама игра.

С этой страницы :

Ну, [поиск пути] выглядит потрясающе с моей стороны, так как есть метрическая тонна персонажей, делающих это одновременно.

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

Я не знаю, определенно ли так он предотвращает «затопление карты» , но обычный способ сделать это в играх - использовать изменение A *, называемое Hierarchical Path-Finding A * или HPA *. Идея состоит в том, чтобы разбить сетку на множество меньших, но больших кусков, а затем использовать A *, чтобы найти лучший путь от каждого куска к соседним. Вы можете использовать это, чтобы построить намного меньший график, по которому нужно запускать A * для каждого подразделения.

Вы также можете сгруппировать эти фрагменты в еще более крупные фрагменты, откуда и происходит «иерархическое».

Этот алгоритм находит только почти оптимальные пути, но для таких игр, как Dwarf-Fortress, это нормально. Все еще гарантированно найти путь, если он существует; и когда нет пути, он только заполнит меньший график, сэкономив огромное количество времени.

Существует также абстракция HPA *, которая имеет дело с юнитами, которые могут пересекать некоторую местность, но не с другими (такими как скалы, по которым воздушные юниты могут пересекать, но наземные юниты не могут) . Это называется НАА * , и есть очень доступная статья объясняя это здесь .

Вы можете прочитать больше о различных алгоритмах поиска пути здесь .

Во всяком случае, все наоборот - все работает в одном потоке, и теперь оно достигает точки, где это становится фактором блокировки (в прошлый раз, когда я проверял!)

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

Я не знаю, как кодируется DF, но количество ИИ меня не впечатляет, потому что люди часто следят за тем, чтобы ИИ не нуждался в точности . Совершенно жизнеспособно делать большинство вещей только каждые несколько секунд. Также целесообразно использовать неточные расчеты. Несовершенство значительно экономит производительность . Вы можете запускать процедуру принятия решения из 100 блоков каждые 100 мс, или вы можете запускать ее из расчета 1000 блоков каждую секунду, это займет столько же процессорного времени, но хорошо ... у вас в 10 раз больше единиц.

Вот простой пример того, как можно обрабатывать много единиц:

int curUnit;
Array<Unit> units;
[...]
while([...]) // Game Loop
{
  [...game logic...]
  // process 10 AIs per Frame
  for(int i=0; i++; i<10)
  {
    curUnit++
    if(curUnit == units.length()) curUnit=0;
    if(curUnit < units.length())
      units[curUnit].processAI();
  }

  // Update the position of all units, this should be as optimized as possible
  foreach(Unit& unit in units){ unit.move(); };

  [...graphics...]
}

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