Эффективно получить Z упорядоченных объектов в окне просмотра в 2D-игре

Question

Представьте себе 2D-игру с большой игровой площадкой, скажем, 10000x10000 пикселей. Теперь представьте, что в этой области есть тысячи объектов. Все объекты находятся в списке заказов Z, поэтому каждый объект имеет четко определенную позицию относительно любого другого объекта, даже если он находится далеко.

Предположим, что в этом игровом поле есть область просмотра, показывающая площадь области 500x500 этой зоны игры. Очевидно, что если алгоритм «для каждого объекта в списке заказов Z, если внутри видового экрана, визуализируйте его», то вы тратите много времени на итерирование всех тысяч объектов, находящихся далеко за пределами области просмотра. Лучшим способом было бы поддерживать Z-упорядоченный список объектов вблизи или внутри области просмотра.

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

Answer 1

Типичным решением такого рода проблем является группировка объектов в соответствии с их приблизительным местоположением XY. Например, вы можете перемещать их в области 500x500, то есть объекты, пересекающие [0,500] x [0,500], объекты, пересекающие [500,1000] x [0,500] и т. Д. Очень большие объекты могут быть перечислены в нескольких ведрах, но предположительно есть не слишком много очень больших объектов.

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

Answer 2

Вам не нужно сохранять структуру памяти, строго упорядоченную Z. Вместо этого вам нужно хранить свои объекты в структуре пространственного разбиения, ориентированной вдоль поверхности просмотра.
Типичная структура разбиения, представляет собой квадрат , в 2D. Вы можете использовать двоичное дерево , вы можете использовать сетку , или вы можете использовать пространственную схему хеширования . Вы можете даже смешивать эти методы и объединять их друг с другом.
Нет «лучшего», но вы можете добавить в баланс легкость написания и поддержания кода. И память у вас есть.
Давайте рассмотрим сетку, она будет самой простой в реализации, быстрее всего доступной и простой для прохождения. (перемещение - это факт перехода к ячейкам окрестности)

Представьте, что вы позволяете себе использовать 20 МБ ОЗУ для скелета сетки, учитывая, что содержимое ячейки - это всего лишь небольшой объект (например, std :: vector или aC# List), скажем, 50 байт. для 10k пикселей квадратуры вы затем:

sqrt(20*1024*1024/50) = 647 

Вы получаете 647 клеток для одного измерения, поэтому 10k/647 = 15 пикселей в ширину ячеек.
Все еще очень маленький, поэтому я полагаю, что это абсолютно приемлемо. Вы можете настроить номера, чтобы получить ячейки размером 512 пикселей. Он должен хорошо подходить, когда несколько ячеек подходят к окну просмотра.

Тогда тривиально легко определить, какие ячейки активированы в окне просмотра, деля верхний левый угол на размер ячейки и полы, которые приводят к результату, это дает вам индекс непосредственно в ячейке. (при условии, что пространство вашего пространства просмотра и пространство сетки начинаются с 0,0 и то же.в противном случае вам необходимо смещать)
Наконец, возьмите нижний правый угол, определите координату сетки для ячейки; и вы можете сделать двойной цикл (x и y) между min и max для итерации по активированным ячейкам.
При обработке ячейки вы можете нарисовать объекты, которые она содержит, пройдя список объектов, которые вы ранее уложили.

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

Эта же логика применяется для более гибкого парирования, такого как бинарные деревья.

У меня есть реализация для обоих имеющихся в моем двигателе, проверьте код, оно может помочь вам получить через детали: http://sourceforge.net/projects/carnage-engine/

Заключительные слова о вашей Z Заказ, если у вас несколько хранения памяти для каждого Z, то вы уже сделали пространственное разбиение, просто не вдоль хорошей оси.
Это можно назвать расслоением.
Что вы можете сделать, как оптимизация, это вместо того, чтобы хранить списки объектов в ваших клетках, вы можете хранить (заказать) map сек объектов и их ключи их Z, поэтому итерация будет упорядочен по Z.