Является ли хранение всех игровых объектов в одном списке приемлемым дизайном?

24

Для каждой игры, которую я сделал, я просто помещаю все свои игровые объекты (пули, машины, игроков) в один список массивов, который я перебираю, чтобы рисовать и обновлять. Код обновления для каждого объекта хранится в его классе.

Мне было интересно, это правильный путь, или это более быстрый и эффективный способ?

Дерек
источник
4
Я заметил, что вы сказали «список массивов», предполагая, что это .Net, вместо этого вам следует перейти на List <T>. Он почти идентичен, за исключением того, что List <T> является сильным типом, и поэтому вам не придется печатать cast каждый раз, когда вы получаете доступ к элементу. Вот документация: msdn.microsoft.com/en-us/library/6sh2ey19.aspx
Джон Макдональд

Ответы:

26

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

Конечно, вы могли бы сделать это по-другому, например, ведя однородный список для каждого типа объекта или обеспечив, чтобы все в вашем гетерогенном списке было сгруппировано так, чтобы вы улучшили когерентность для кода, который находится в кэше, или позволяли параллельное обновление. Видите ли вы заметное улучшение производительности, делая это, трудно сказать, не зная объема и масштабов ваших игр.

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

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

мистифицировать
источник
16

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

Нахожу ли я себя перебирать все объекты, но работаю только над их подмножеством?

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

Это сократит количество объектов, через которые вы проходите цикл, и пропустит ненужные проверки, поскольку вы уже знаете, что все объекты в списке должны быть обработаны.

Вы должны были бы профилировать его, чтобы увидеть, если вы получаете большую выгоду производительности.

Майкл
источник
Я согласен с этим, у меня обычно есть подмножества моего списка для объектов, которые необходимо обновлять каждый кадр, и я рассматривал возможность сделать то же самое для объектов, которые визуализируются. Однако, когда эти свойства могут меняться на лету, управление всеми списками может быть сложным. Когда и объект переходит от того, чтобы быть доступным для рендеринга, чтобы не быть доступным для обновления, или для обновления к не обновляемому, и теперь вы добавляете или удаляете их из нескольких списков одновременно.
Ник Фостер
8

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

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

Это одно из самых распространенных изменений, которые вы можете делать в зависимости от игрового дизайна. Я воспользуюсь возможностью и опишу несколько других (более сложных) примеров, но помните, что есть еще много других возможных причин и решений.

Для начала я укажу, что обновление ваших игровых объектов и их рендеринг могут иметь разные требования в некоторых играх, и поэтому должны обрабатываться отдельно. Некоторые возможные проблемы с обновлением и рендерингом игровых объектов:

Обновление игровых объектов

Вот отрывок из Game Engine Architecture, который я бы рекомендовал прочитать:

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

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

введите описание изображения здесь

Рендеринг игровых объектов

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

введите описание изображения здесь

Другими причинами могут быть, например, использование структуры данных с пространственным разделением для организации ваших объектов таким образом, чтобы повысить эффективность выполнения выбора усеченного вида.

Дэвид Гувея
источник
4

Ответ: «Да, это хорошо». Когда я работал над симуляциями большого железа, где производительность не подлежала обсуждению, я был удивлен, увидев все в одном большом глобальном массиве (BIG и FAT). Позже я работал над ОО-системой и сравнил их. Хотя это было ужасно, версия «один массив, чтобы управлять ими всеми» в однопоточном простом старом C, скомпилированном в отладке, была в несколько раз быстрее, чем «симпатичная» многопоточная OO-система, скомпилированная -O2 в C ++. Я думаю, что отчасти это связано с отличной локальностью кэша (как в пространстве, так и во времени) в версии с большим массивом.

Если вам нужна производительность, один большой толстый глобальный массив C будет верхним пределом (из опыта).

скоро
источник
2

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

Мне всегда был нужен один главный список, независимо от того, сколько других списков у меня было. Обычно я делаю это в виде карты, таблицы с ключами или словаря, чтобы иметь возможность произвольного доступа к отдельным элементам. Но простой список намного проще; если вы не получаете случайный доступ к игровым объектам, карта вам не нужна. И случайный последовательный поиск по нескольким тысячам записей, чтобы найти правильную, не займет много времени. Так что я бы сказал, что бы вы ни делали, планируйте придерживаться основного списка. Подумайте об использовании карты, если она становится большой. (Хотя, если вы можете использовать индексы вместо ключей, вы можете придерживаться массивов и получить что-то намного лучше, чем Map. Я всегда заканчивал большими промежутками между номерами индексов, поэтому мне пришлось отказаться от него.)

Несколько слов о массивах: они невероятно быстрые. Но когда они набирают около 100 000 элементов, они начинают подгонять сборщиков мусора. Если вы можете выделить место один раз и не трогать его потом, хорошо. Но если вы постоянно расширяете массив, вы постоянно выделяете и освобождаете большие куски памяти и склонны к тому, что ваша игра зависает на несколько секунд за раз, и даже выдает ошибку из-за ошибки памяти.

Так быстрее и эффективнее? Конечно. Карта для произвольного доступа. Для действительно больших списков связанный список превзойдет массив, если и когда вам не нужен произвольный доступ. Несколько карт / списков для организации объектов различными способами, по мере необходимости. Вы можете многопоточное обновление.

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

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

RalphChapin
источник
Я действительно не думаю, что связанный список превзойдет массив любого размера, если только вы часто не добавляете и не удаляете вещи из середины.
Zan Lynx
@ZanLynx: И даже тогда. Я думаю, что новые оптимизации во время выполнения очень помогают массивам - не то, что им это нужно. Но если вы выделяете и освобождаете большие порции памяти многократно и быстро, как это может случиться с большими массивами, вы можете связать сборщик мусора в узлы. (Здесь также учитывается общий объем памяти. Проблема связана с размером блоков, частотой свободного и выделенного пространства и доступной памяти.) Сбой происходит внезапно, когда программа зависает или происходит сбой. Обычно там много свободной памяти; ГК просто не может его использовать. Связанные списки позволяют избежать этой проблемы.
RalphChapin
С другой стороны, связанные списки имеют значительно более высокую вероятность кеширования при итерации из-за того, что узлы не являются смежными в памяти. Это не так просто. Вы можете устранить проблемы перераспределения, не делая этого (если это возможно, выделять заранее, поскольку это часто происходит), и вы можете облегчить проблемы когерентности кэша в связанном списке, выделяя узлы из пула (хотя у вас все еще есть последующая стоимость ссылки это относительно тривиально).
Джош
Да, но даже в массиве, вы не просто храните указатели на объекты? (Если это не недолговечный массив для системы частиц или чего-то в этом роде.) Если это так, то все равно будет много пропусков кэша.
Тодд Леман
1

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

  1. У вас есть небольшое количество или известный максимум игровых объектов
  2. Вы предпочитаете простоту перед производительностью (то есть: более оптимизированные структуры данных, такие как деревья, не стоят проблем)

В любом случае я реализовал это решение как массив фиксированного размера, который содержит gameObject_ptrструктуру. Эта структура содержала указатель на сам игровой объект и логическое значение, представляющее, был ли объект «жив».

Целью логического выражения является ускорение операций создания и удаления. Вместо того, чтобы уничтожать игровые объекты при их удалении из симуляции, я бы просто установил флаг «в живую» false.

При выполнении вычислений на объектах код должен проходить по массиву, выполняя вычисления для объектов, помеченных как «живые», и отображаются только объекты, помеченные как «живые».

Еще одна простая оптимизация - организовать массив по типу объекта. Например, все маркеры могут находиться в последних n ячейках массива. Затем, сохраняя int со значением индекса или указателем на элемент массива, на конкретные типы можно ссылаться с меньшими затратами.

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

Это мой первый пост! Я надеюсь, что это отвечает на ваш вопрос!

БИК
источник
первый пост! ура!
Тили
0

Это приемлемо, хотя и необычно. Такие термины, как «быстрее» и «более эффективный», являются относительными; обычно вы бы организовали игровые объекты по отдельным категориям (один список для пуль, один список для врагов и т. д.), чтобы сделать программирование более организованным (и, следовательно, более эффективным), но компьютер не будет проходить по всем объектам быстрее ,

jhocking
источник
2
Достаточно верно для большинства игр XNA, но организация ваших объектов может на самом деле ускорить итерацию по ним: объекты одного типа с большей вероятностью попадут в кэш инструкций и данных вашего ЦП. Промахи кеша стоят дорого, особенно на консолях. Например, на Xbox 360 пропуск кэша L2 обойдется вам ~ 600 циклов. Это оставляет много производительности на столе. Это единственное место, где управляемый код имеет преимущество перед собственным кодом: объекты, расположенные близко друг к другу во времени, также будут близки в памяти, и ситуация улучшится с сборкой мусора (уплотнением).
Программист хронических игр
0

Вы говорите, один массив и объекты.

Так что (без вашего кода, чтобы посмотреть) Я предполагаю, что все они связаны с «uberGameObject».

Так что, может быть, две проблемы.

1) У вас может быть объект «бога» - он делает тонны вещей, на самом деле не сегментированный тем, что он делает или является

2) Вы перебираете этот список и приводите к типу? или распаковывать каждый. Это имеет большое снижение производительности.

рассмотрите возможность разбиения различных типов (маркеры, плохие парни и т. д.) на собственные строго типизированные списки.

List<BadGuyObj> BadGuys = new List<BadGuyObj>();
List<BulletsObj> Bullets = new List<BulletObj>();

 //Game 
OnUpdate(gameticks gt)
{  foreach (BulletObj thisbullet in Bullets) {thisbullet.Update();}  // much quicker.
DR9
источник
Нет необходимости выполнять приведение типов, если есть какой-то общий базовый класс или интерфейс, который имеет все методы, которые будут вызываться в цикле обновления (например, update()).
Bummzack
0

Я могу предложить некоторый компромисс между общим списком и отдельными списками для каждого типа объекта.

Сохранить ссылку на один объект в нескольких списках. Эти списки определяются базовым поведением. Например, MarineSoldierобъект будет ссылаться на PhysicalObjList, GraphicalObjList, UserControlObjList, HumanObjList. Таким образом, когда вы обрабатываете физику, вы проходите итерацию PhysicalObjList, когда процесс, повреждающий яд, - HumanObjListесли Солдат умирает - удаляет его, HumanObjListно сохраняет его PhysicalObjList. Чтобы этот механизм работал, вам нужно организовать автоматическую вставку / удаление объекта при его создании / удалении.

Преимущества подхода:

  • типизированная организация объектов (нет AllObjectsListс приведением при обновлении)
  • списки основаны на логике, а не на классах объектов
  • нет проблем с объектами с комбинированными возможностями ( MegaAirHumanUnderwaterObjectбудет вставлен в соответствующие списки вместо создания нового списка для его типа)

PS: Что касается самообновления, вы столкнетесь с проблемой, когда несколько объектов взаимодействуют, и каждый из них зависит от других. Чтобы решить эту проблему, нам нужно воздействовать на объект извне, а не на самообновление.

Бригадир
источник