Разработка игр для Android: какую структуру данных использовать?

Question

Я делаю игру для Android.Я стараюсь держать игру в секрете, поэтому не могу рассказать о ней слишком много, так что терпите меня.По сути, он работает в режиме реального времени (поэтому я буду реализовывать поток для обновления координат объектов), а его стиль похож на Duck Hunt;Вы должны ударить объекты, которые движутся по экрану. Однако игра время от времени немного отстает (работает на Samsung Galaxy S, который является одним из более совершенных устройств), поэтому я считаю, что мне нужно использоватьлучшая структура данных.

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

1. Поиск, если объект пересекается с заданной координатой (касаясь экрана), занимает O (n) время (в худшем случае), потому что мне приходится перемещаться с головы до хвостаи проверьте хитбокс каждого объекта.
2. Проверка столкновений между двумя объектами занимает O (n ^ 2) времени (опять же, в худшем случае), потому что для каждого объекта мне нужно проверить, пересекается ли его хитбокс с таковым для всехдругие объекты в связанном списке.

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

Я рассмотрелиспользуя многомерный массив.Этот метод предполагает разделение экрана на «ячейки», в которых может лежать объект.Например, на экране 480x800, если высота и ширина объекта равны 80 пикселям, я бы разделил экраны на сетку 6x10, или в контексте кода Java я бы сделал GameObject [6] [10].Я мог бы просто разделить координаты (на экране) объекта на 80, чтобы получить его индекс (на сетке), что также могло бы обеспечить вставку O (1).Это также может сделать поиск по координате O (1), как я мог бы сделать то же самое с координатами касания, чтобы проверить соответствующий индекс.

Проверка столкновения может все еще занять время O (n ^ 2), потому что у меня все еще естьпройти через каждую ячейку в сетке (хотя в этом случае мне нужно только сравнить не более 8 ячеек, которые примыкают к ячейке, которую я сейчас проверяю).

Однако идея сетки создает свои собственные проблемы:

1. Что если экран имеет разрешение, отличное от 480x800?Кроме того, что, если сетка не может быть равномерно разделена на 6x10?Это может сделать программу более подверженной ошибкам.
2. Дорого ли использование сетки игровых объектов с точки зрения памяти?Учитывая то, что я занимаюсь разработкой для мобильного устройства, мне нужно принять это во внимание.

Итак, главный вопрос: использовать ли список связанных данных, многомерный массив или что-то еще, что у меня нет?не рассматривается?

Ниже приводится идея о том, как я реализую коллизию:

private void checkForAllCollisions() {
 GameObject obj1 = mHead;

 while (obj1 != null) {
        GameObject obj2 = obj1.getNext();
            while (obj2 != null) {
                //getHitBox() returns a Rect object that encompasses the object
                Rect.intersects(obj1.getHitBox(), obj2.getHitBox());
                //Some collision logic
            }
            obj1 = obj1.getNext();
        }
}

Answer 1

Общие структуры данных для лучшей производительности по обнаружению столкновений: квадраты (в 2 измерениях) и октреи (3 измерения).

Если вы хотите придерживатьсясписок - есть ли причина, по которой вы используете LinkedList, а не ArrayList?Я надеюсь вы в настоящее время используете встроенную реализацию связанного списка ...

---

Samsung Galaxy S имеет 512 МБ ОЗУ - не беспокойтесь о том, чтобы занимать слишком многопамять с единой структурой данных (пока).Вам нужно иметь относительно большое количество относительно тяжелых объектов, прежде чем эта структура данных начнет всасывать значительные объемы ОЗУ.Даже если у вас есть 1000 GameObject экземпляров, и каждый экземпляр в структуре данных (включая связанный вес хранения экземпляра в упомянутой структуре данных) составлял 10 000 байт (что довольно много), это все равно всего 9,5 мегабайт памяти.

Answer 2

Так что я определенно думаю, что нам нужно сначала кое-что рассмотреть.

1.) LL vs. Array

Вы сказали, что использовали LL вместо массива из-за динамического свойства, которое дает вам LL. Тем не менее, я хотел бы сказать, что вы можете сделать использование массива достаточно динамичным, удвоив его размер после заполнения, что даст вам O (1) время выполнения вставки амортизируется (учитывая, что массив не сохраняется / не сортируется). Тем не менее, будет сценарий, в котором время от времени вставка может занять O (n), поскольку вы должны соответствующим образом копировать данные. Так что для живых игр, подобных этой, я считаю, что LL был хорошим выбором.

2.) Ваше рассмотрение памяти с точки зрения игровых объектов.

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

3.) Если разрешение отличается от 480x800, не беспокойтесь. Если вы используете сетку 6x10 для всего, рассмотрите возможность использования множителя плотности следующим образом:

float scale = getContext().getResources().getDisplayMetrics().density;

, а затем getWidth () и getHeight () должны быть умножены на этот масштаб, чтобы получить точную ширину и высоту устройства, которое использует ваше приложение. Затем вы можете разделить эти числа на 6 и 10. Однако обратите внимание, что некоторые сетки могут выглядеть некрасиво на некоторых устройствах, даже если они правильно масштабируются таким образом.

4.) Обработка столкновений

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

a.) Линейный зонд б.) Отдельная цепочка в.) Двойное хеширование

, все из которых, по общему признанию, являются хэш-стратегиями обработки столкновений, но могут быть реализованы с учетом вашей игры (о которой, опять же, вы узнали бы больше, поскольку сохранили некоторую информацию). Тем не менее, я скажу, что если вы используете сетку, вы можете захотеть сделать что-то по линии линейного зондирования или создать 2 хэш-таблицы вместе (если это уместно, но, похоже, это убирает макет сетки, который вы пытаетесь использовать) добиться, так что, опять же, на ваше усмотрение). Также обратите внимание, что вы можете использовать какое-то дерево (например, quadtree) для более быстрого обнаружения столкновений. Если вы не знаете о quadtree, проверьте их здесь . Хороший способ думать об этом - разделить квадратное изображение на отдельные пиксели на листьях и сохранить средние цвета в родительских узлах для сокращения . Просто способ помочь вам осмысленно думать о квадри.

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