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

79

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

RSH1
источник
6
Интересный вопрос. Хотя мне не нравится, как это сформулировано, так как было бы просто предположить, что ответ на этот вопрос будет сформулирован. В любом случае, вы, возможно, видели эту статью, разговаривающую с Тарном Адамсом. Где они кратко охватывают поиск пути.
MichaelHouse
25
Он абсолютно производит заметное замедление, когда у вас сложная туннельная топология и более 100 гномов.
Рассел Борогове
3
Да, DF в моем опыте невероятно медленный в сценарии, который вы описываете.
argentage
4
Уничтожьте основной лестничный колодец и наблюдайте, как ваша частота кадров падает, как камень, на мгновение, в то время как каждый гном внезапно повторяет в одно и то же время.
Mooing Duck
2
Я собираюсь присоединиться и согласиться, что DF не лучший пример; на самом деле DF, как известно, страдает от проблем с производительностью.
Роберт С.

Ответы:

110

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

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

  • Не обрабатывайте каждую сущность в каждом кадре.
  • Разделите обработку на вещи, которые нужно делать часто, и вещи, которые не нужно делать часто.
  • Распределите долгосрочные алгоритмы по нескольким кадрам, чтобы они не блокировали обработку в других системах.
  • Убедитесь, что используются эффективные алгоритмы и структуры данных.
  • Кэшируйте результаты дорогих вычислений, если они могут быть использованы снова.
Kylotan
источник
2
+1 за это, за то, что я на самом деле объясняю, что происходит, а не за что-то про графику вроде меня. :)
Мэтт Кемп
4
Честно говоря, я тоже дал вам +1, потому что я забыл об этом аспекте, и это очень верно - убрать gfx из уравнения, и это похоже на мгновенное увеличение скорости работы компьютеров в 2 или 3 раза.
Kylotan
Я слышал, что DF теперь многопоточный, но, по крайней мере, до недавнего времени, все это было сделано в один поток. (Это все еще может быть, не уверен)
Mooing Duck
@MooingDuck Это все еще не так.
Тарвен
63

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

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

движение

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

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

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

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

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

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

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


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

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

DampeS8N
источник
1
1024X1024X32? Вертикаль 128 или 256 я считаю. Это намного больше, чем 32.
Лотон
@Lawton Я считаю, что я не правильно указал максимальный размер, но высота не так уж и неправильна. Я исправляю это. Я загрузил игру, и старт, на котором я нахожусь, составляет всего около 45 уровней. Еще можно «смоделировать», но у меня нет доступа к ним для копания или строительства.
DampeS8N
@ DampeS8N Я только что загрузил немодированную карту среднего размера и мог просматривать от +16 до -156, около 180 уровней. Карты 40 уровней являются исключением, а не правилом. Даже если вы сможете выкопать только 40 из них из-за того, что они заблокированы водоносным горизонтом или лавой, это не имеет значения, поскольку область под ними все еще заполнена симуляцией веселья.
Лотон
@Lawton, моя карта позволяет мне пролистывать только 45 уровней. Они абсолютно изменчивы, но я не мог легко найти цифры о том, сколько доступно каждой карте. Это также может зависеть от того, какую версию игры мы используем. В конце концов, это не так важно для моего ответа.
DampeS8N
Это старый пост, но глубина в карликовой крепости зависит от осадочных слоев. Как будто земная кора в некоторых местах толще. DF не совсем геологически корректен, но человек изучает это как профессионалы: D.
Madmenyo
50

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

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

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

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

Иерархический поиск пути

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

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

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

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

BlueRaja - Дэнни Пфлугхофт
источник
3
Я нашел это видео от разработчика RimWorld очень поучительным. Это похожая игра, пока только в 2D. Он объясняет основы поиска пути и преимущества разделения карты на регионы. youtube.com/watch?v=RMBQn_sg7DA
Отец
18

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

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

Мэтт Кемп
источник
8
Одним из доводов в пользу этого является переписывание OpenGL, которое, как я помню, значительно увеличило частоту кадров. Так что даже делая простую спрайт-графику, DF эффективно оказал влияние.
Миллимы
3
+1 Полосная графика = огромное количество свободного времени для геймплейных вычислений
Лоран Кувиду
2
Стоит отметить, что графика DF примерно такая же требовательная, как и любая современная инди 2D игра. Есть много текстур, даже если они маленькие и простые, и их можно распространять на мониторы недвижимости Full HD. Здесь нет каких-либо эффектных ярких частиц или чего-то еще, но необработанная работа «покрасить все эти пиксели» все еще присутствует, и из-за количества вызовов отрисовки, необходимых для крошечных размеров листов, на самом деле довольно большая задача сделать производительность.
DampeS8N
Поначалу это может показаться глупым ответом, но это правильно, представьте, что можно сделать с помощью графического процессора 4-12 ГБ и 4-12 Тфлопс, если вам не нужно рисовать сложные примитивы, разворачивать текстуры, преобразовывать трехмерные векторы в 2d массив пикселей, шейдеров и т. д.
Felype
10

Я не знаю, как кодируется 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...]
}

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

API-Beast
источник
Можно многое сказать о том, как проходить стеки задач, которые не являются точными на уровне кадра. Игры ААА часто явно распределяют время между отдельными отделами в процентах фреймов, чтобы один отдел не мог наступить на пальцы других отделов. Если метод анимации колебаний дерева, основанный на скорости и направлении ветра, является медленным, меньше деревьев будет обрабатываться, а не поглощать бюджет других команд.
DampeS8N