Как Карликовая крепость отслеживает так много объектов, не теряя производительности?

В Крепости Гномов в любой момент вы можете иметь сотни гномов, животных, гоблинов и т. д., каждый со своими сложными ИИ и программами поиска путей. Мой вопрос в том, как это не приводит к заметному замедлению? Каждый гном работает в своем потоке?

72 голоса | спросил RSH1 23 J000000Monday12 2012, 17:00:01

5 ответов


104

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

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

  • Не обрабатывать каждый объект в каждом кадре.
  • Разделить обработку на вещи, которые часто нужно делать, и вещи, которые не нужно делать часто.
  • Распространение длительных алгоритмов на нескольких кадрах, чтобы они не блокировали обработку в других системах.
  • Убедитесь, что используются эффективные алгоритмы и структуры данных.
  • Загрузите результаты дорогостоящих вычислений, если они скорее всего будут использоваться снова.
ответил Kylotan 23 J000000Monday12 2012, 17:31:30
62

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

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

Движение

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

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

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

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

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

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

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


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

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

ответил DampeS8N 23 J000000Monday12 2012, 17:34:53
44

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

  

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

     

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

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

Иерархическое отслеживание пути

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

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

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

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

ответил BlueRaja - Danny Pflughoeft 23 J000000Monday12 2012, 20:53:38
18

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

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

ответил Matt Kemp 23 J000000Monday12 2012, 17:31:15
10

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

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

int curUnit;
Массив & Lt; & блок GT; единицы;
[...]
while ([...]) //Game Loop
{
  [... логика игры ...]
  //обрабатываем 10 AI за кадр
  для (int i = 0; i ++; i <10)
  {
    curUnit ++
    if (curUnit == units.length ()) curUnit = 0;
    if (curUnit <units.length ())
      единицы [curUnit] .processAI ();
  }

  //Обновляем позицию всех блоков, это должно быть максимально оптимизировано
  foreach (Unit & единица измерения в единицах) {unit.move (); };

  [...графика...]
}

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

ответил API-Beast 24 J000000Tuesday12 2012, 17:33:58

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132