Как эффективно сортировать объекты по порядку рисования при рендеринге 2D-игры?

Мне нужно отобразить «плитку» с объектами, которые перекрываются, потому что они выше, чем плитка, на которой они стоят, например, игры на этих снимках экрана:

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

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

<p> <img src =

5 голосов | спросил DatVM 4 FebruaryEurope/MoscowbMon, 04 Feb 2013 17:16:13 +0400000000pmMon, 04 Feb 2013 17:16:13 +040013 2013, 17:16:13

5 ответов


8

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

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

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

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

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

В большинстве игр в большинстве случаев порядок объектов будет одинаковым или почти одинаковым между двумя кадрами. В этом случае я рекомендую вам использовать Сортировка вставки . Обычно он считается подпараметрическим алгоритмом, но в особым случаем данных, который уже почти отсортированный , он значительно превосходит все алгоритмы сортировки общего назначения, такие как quick-sort или merge-sort. Я использую этот метод в игре, которую я сейчас разрабатываю. Заменив стандартную сортировку Javascript на собственную реализацию сортировки вставки, я смог сократить время выполнения, затрачиваемое на сортировку объектов, с 3% до 0,2%, хотя сортировка по умолчанию имеет то преимущество, что она реализована изначально (измеряется в Firefox с использованием профайлер расширения Firebug).

ответил Philipp 4 FebruaryEurope/MoscowbMon, 04 Feb 2013 18:58:09 +0400000000pmMon, 04 Feb 2013 18:58:09 +040013 2013, 18:58:09
3

Я хотел бы добавить, что стабильность алгоритма сортировки также важен.

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

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

Я думаю, что в то время я пошел с сортировкой Merge, но Филипп подробно остановился на сортировке вставки и в лучшем случае, поэтому я бы посмотрел на это.

ответил David Gouveia 5 FebruaryEurope/MoscowbTue, 05 Feb 2013 01:52:30 +0400000000amTue, 05 Feb 2013 01:52:30 +040013 2013, 01:52:30
1

Просто отсортируйте их. Используйте quicksort. (Обычно это сортировка по умолчанию на любом языке, который вы используете.)

Просто, чтобы дать вам представление о незначительности мысли о других способах этого: быстрая сортировка 100 000 предметов, как правило, будут работать около 1 миллисекунды на современном оборудовании.

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

ответил CaptainCodeman 5 FebruaryEurope/MoscowbTue, 05 Feb 2013 01:28:00 +0400000000amTue, 05 Feb 2013 01:28:00 +040013 2013, 01:28:00
0

Думаю, вам, наверное, все равно.

Если у вас есть <100 (движущихся) объектов, тогда их сортировка, вероятно, будет настолько быстрой, что это не важно.

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

Объекты, которые постоянно прикреплены к наземным плиткам, не нужно сортировать (более одного раза), так как они не будут перемещаться, не так ли?

ответил MarkR 4 FebruaryEurope/MoscowbMon, 04 Feb 2013 19:11:41 +0400000000pmMon, 04 Feb 2013 19:11:41 +040013 2013, 19:11:41
0

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

ответил Yannick 5 FebruaryEurope/MoscowbTue, 05 Feb 2013 00:59:07 +0400000000amTue, 05 Feb 2013 00:59:07 +040013 2013, 00:59:07

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

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

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