При написании игры, мы, нередко, сталкиваемся с двумя наборами данных: карта и игровые объекты (с поправкой на тип игры). Давайте рассмотрим наиболее очевидные способы хранения этих данных и подыщем тот, который сделает хранение наиболее удобным, а применение данных - оптимальным. Учитывая тот факт, что каждая отрисовка изображения вынуждена перебирать всю (или часть) такой структуры - будет совсем не лишним подыскать оптимальный способ.
Два типа данных
Изначально, карта и игровые объекты - это две разных структуры данных, которые обрабатываются, местами, по-разному. Игровые объекты могут перемещаться, объекты карты - статичны; объекты карты могут взаимодействовать друг с другом, объекты карты - просто входные условия.
Если упростить, данные карты можно рассматривать как массив чисел, где каждое значение отвечает за какой-то блок карты (стена, пол, пропасть итд), однако есть некоторая структура, которая описывает поведения этого блока один раз.
А вот данные игровых объектов - это тоже массив - однако массив структур, внутри которой описываются, как минимум, координаты (которые можно сопоставить с определённой ячейкой карты) и какие-то дополнительные свойства, которые нам сейчас не особо интересны. Для простоты задачи, будем считать, что каждый игровой объект уже сопоставлен с некоторой ячейкой карты и имеет дополнительное смещение (в точках) относительно его левого-верхнего угла - двойные координаты.
Почему не оставить всё так, как есть?
Вообще - можно. Однако мы сталкиваемся с двумя проблемами: производительность и наложение отрисовки. Давайте разберёмся.
Две структуры - один цикл
У нас, изначально, есть две структуры (а их может быть и больше, если усложнить задачу) и, соответственно, каждую структуру надо отрисовать отдельно: сперва карту, потом - игровые объекты. То есть, после отрисовки каждой клеточки карты, надо посмотреть, а нет ли какого-то игрового объекта, который должен рисоваться поверх и если есть - отрисовать. То есть после отрисовки каждой клеточки карты, нам придётся перебирать весь список игровых объектов и смотреть, что надо нарисовать поверх. Падение производительности - катастрофическое (для большого количества игровых объектов и приличного размера карты). Не говоря уже о том, что если игровой объект рисуется со смещением относительно левого-верхнего угла, то следующая нарисованная клетка карты частично закроет его. Но это уже следующая проблема.
Перекрытие спрайтов
Тут, как написано выше, есть проблема перекрытия нарисованного спрайта клетками карты, так и правильность порядка отрисовки игровых объектов и ячеек карты: какие-то объекты должны всегда рисоваться поверх (например, плита, открывающая дверь всегда должна рисоваться под героем), а какие-то, несмотря ни на что - должны быть перекрыты (при изометрической проекции стена может перекрывать игровой объект - скажем - персонажа).
Итого
Задача сделать так, чтобы цикл выполнялся один раз (желательно только для видимой части экрана, но эту оптимизацию можно пока пропустить), а все элементы отрисовывались верно. Кроме того, игровые объекты должны иметь некоторый приоритет отрисовки и, в случае "перекрытия", порядок отрисовки должен быть предопределён (герой всегда рисуется поверх плиты-кнопки).
Входные данные
Карта всегда рисуется сверху вниз, слева направо. Она может быть какой угодно формы (просто в условном квадрате, описывающем структуру лабиринта, часть ячеек - пустые и никак не обрабатываются), может быть как угодно развёрнута, но, в целом, рисуется всегда по единому принципу (алгоритмически, перебирать одномерный массив можно как угодно). Но давайте не будем усложнять, а решим задачу в общем вид, итак:
- Требуется "прогонять" все отрисовки в одном цикле и делать это быстро;
- Сперва рисуется карта, поверх - игровые объекты в правильном порядке;
- Общий приоритет такой, что объекты, находящиеся левее и/или выше рисуются под объектами, которые находятся правее и/или ниже.
Последний пункт примечателен тем, что если игровые объекты не совпадают по размеру с клеткой, то оно всё равно будет отрисовываться правильно и не перекрываться объектом, который должен быть отрисован под ним. Как на рисунке ниже.
Объединяем всё в один цикл
Давайте создадим промежуточное решение.
У каждого рисуемого объекта есть свой размер - 1 клетка. Может быть и больше, но это не сильно влияет на алгоритм, так что не будем углубляться в детали.
Отображаемый объект может визуально перекрывать от одной до четырёх клеток (по количеству углов), но, поскольку мы привыкли ориентироваться на левый верхний угол - он всегда будет привязан к ячейке, на которую приходится этот угол, прочие ячейки можно вычислить.
Так как всё рисуется слева-направо сверху-вниз, то рисовать игровой объект надо тогда, когда ячейка карты, соответствующая правому нижнему углу.
Вопрос приоритетов решается предельно просто: то что ниже всегда рисуется поверх того, что выше; при одинаковом вертикальном смещении - то что правее - выше того, что левее. Таким образом, перед каждым циклом надо отсортировать игровые объекты по этому признаку.
Давайте немного оптимизируем код и посмотрим, что получилось.
Две точки уязвимости
В предложенном выше примере есть две основных точки уязвимости: сортировка перед отрисовкой каждого кадра и перебор всех объектов для каждой ячейки.
Но их можно решить одним махом: для этого нам нужен просто какой-то механизм, который возвращал бы отсортированный массив объектов, правый нижний угол которой соответствует текущей ячейке.
Эту задачу можно решить на уровне передвижений объектов, который происходит до отрисовки. На всякий случай, напомню: ИИ игры двигает персонажи, игрок, также, двигает своего персонажа. Всё это происходит в одном цикле, который перебирает все игровые объекты. Затем цикл прогоняется ещё раз и проверяются пересечения всех объектов друг с другом и, если что, происходит добавление временных объектов (например, летящий снаряд).
Вот на втором этапе и надо формировать (каждый раз новую) хэш-карту, которая по ключу - x/y ячейки, на которую пришёлся левый нижний угол игрового объекта - создаёт запись: массив, который заново сортируется после каждого добавления объекта по тому же признаку.
Таким образом, решение - регулярно пересоздаваемая хэш-карта, которая по ключу, создаваемому из координат ячейки возвращает отсортированный массив элементов, правый нижний угол которых рисуется на этой ячейке.
Для очень слабого железа эта задача может, также, показаться "тяжёлой"; в этом случае делается оптимизация: учитываются только те объекты, которые сейчас доступны для взаимодействия (что за границей экрана - того и не существует).
Вот код, который формирует хэш-карту; контекст не учитывается.
Исследуем прирост производительности
Для начала я замерил среднее значение отрисовки при изначальном подходе. Получилось 0.394 миллисекунды на кадр.
На мой взгляд, показатель неплохой, но использованный подход не предполагает сортировку изображений и управления порядком.
Посмотрим, удастся ли его улучшить? Не удалось - получилось 0.453 миллисекунды. А интересно, что будет с картой побольше?
1.621 миллисекунд на кадр для первого варианта. Что же, время вычислений выросло примерно пропорционально росту размера карты. А как поведёт себя новый метод? 1.718 - разница стала меньше. Вероятно, дальнейшее увеличение размера карты и рост количества объектов позволит обогнать изначальный подход, но это не точно.
Выводы
В абсолютном виде прироста производительности мы не получили, однако те издержки, которые мы понесли - приемлемы, т.к. позволяют сделать отрисовку более правильной и соответствующей порядку. И хотя данные теперь хранятся и обрабатываются более эффективно, прироста производительности, увы, не случилось. Остаётся только надеяться, что он проявится тогда, когда размер карты и количество объектов - прибавится.