Оптимальная сортировка объектов для вывода на экран

← →
cyborg (2003-05-14 12:09) [0]

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

← →
neuro (2003-05-14 17:51) [1]

http://graphics.cs.msu.su/

← →
cyborg (2003-05-14 18:20) [2]

Куда там нажимать?

← →
neuro (2003-05-14 18:32) [3]

Везде =)
Этот центр издал замечательную книгу "Компьютерная графика: полигональные модели". Там по твоему вопросу страниц 100-150. Она там должна быть.

← →
cyborg (2003-05-14 18:37) [4]

Я просмотрел, ничего похожего на сортировку объектов для вывода не нашёл.

← →
cyborg (2003-05-14 18:39) [5]

И ещё, модели не полигональные, а спрайтовые ;)

← →
neuro (2003-05-14 19:01) [6]

Да понятно, что спрайтовые =) Но можно адаптировать некоторые =)

А у тебя спрайты в какой СК? В смысле абстрактно в игре?

← →
cyborg (2003-05-14 19:43) [7]

что такое СК? :) и как это абстрактно в игре?

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

← →
neuro (2003-05-14 19:54) [8]

СК -- система координат
Абстрактно в игре -- =) -- это типа до рендеринга, внутренне представление, во! =)

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

Есть еще некая "непрерывная невидимость", но боюсь, что это нерационально в твоем случае. Да я и не помню, как она реализуется -- помню, что красивый алгоритм =))).

← →
cyborg (2003-05-14 20:10) [9]

Система координат сверху спереди ~45 градусов, это я "Чебуратора" делаю :), хотелось бы не просто квадратные ячейки сделать, а большие деревья или другие объекты, которые могут вылезать за пределы своего квадрата на карте и рисуясь соответственно перед объектами находящимися дальше него, например монстр за деревом проходит.

← →
A_n_t (2003-05-15 04:18) [10]

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

Поэтому создается массив 700x255 (700 - высота экрана (то есть для разрешения экрана 800x600 - высота 600 + 100 снизу = 700); 250 - максимальное количество спрайтов на одну линию за раз).
И при просчете каждого спрайта вносится его поз.номер в соответствующую высоту массива, в свободную ячейку.
А при выводе графики пробегается весь массив, и выводятся соответствующие спрайты.

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

← →
cyborg (2003-05-15 10:58) [11]

Ерунду предложил 700*255=178500*4=714000, 700кило писать, а потом читать из памяти каждый кадр получается задница. Объектов у меня в игре несколько тысячь, они появляются и исчезают.

← →
NailMan (2003-05-15 12:38) [12]

Используй QuickSort по высоте спрайта.

Проводи сортировку каждый игровой тик, ну например через каждые 1/25 сек.

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

← →
A_n_t (2003-05-15 17:28) [13]

To cyborg:
Странный ты какой-то: ну зачем тебе каждый раз забивать все 255, если у тебя на экране в данной линии, например, 5 спрайтов.

P.S. Забивать весь массив придется, если на экране одновременно будет 178500 спрайтов :)

P.S.2 Ага ты еще Extended возьми, для прикола, тогда вообще 2 метра получится :)

Оптимальная сортировка объектов для вывода на экран Найти похожие ветки