«Зонирование» областей на большой карте тайлов, а также подземелий

В моей игре карта, похожая на Minecraft, в псевдоинфинитном и случайном порядке. И большой. Скажем, пользователь исследовал зону 1000x1000 (здесь 2D), так что это 1 000 000 плиток.

Очевидно, я не смогу хранить все это в памяти. И при этом я просто не хочу игнорировать все из 10 плиток или любого другого радиуса - оба ничего не обновят (все NPC, возможно, реактивные плитки), и мне придется работать с неловкими позициями, такими как 1382,12918.

Поэтому, если бы я разбил его на куски или зоны или что-то вроде плиток 64x64, мне пришлось бы хранить каждую плитку и позицию объекта следующим образом:

Кусок а, б. Положение х, у.

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

И есть сторона памяти; сколько я мог бы потенциально хранить в памяти в то же время разумно? Я мог бы делать плитки по идентификатору довольно легко, и там был обычный 2D-массив. Или, опять же, есть ли более эффективное решение, чем наличие файла данных типов листов ? Так что для 64x64 ... это будет только 20K или что-то еще. Я бы хотел, чтобы как можно больше загружалось окружение для наиболее реалистичного обновления. Но я не знаю, на какие ограничения я могу выйти, не затрачивая память.

Хотя я согласен с мнением: «не беспокойтесь об этом, если это не доказанная проблема», я думаю, что стоит задуматься на раннем этапе: переоснащение решения гораздо более болезненно. И да, только обновление «соседних» тайлов - это их путь. Но эффективное хранение и адресация предметов в вашем игровом мире очень важны по соображениям производительности.

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

Стандартное решение проблемы разреженных наборов данных состоит в том, чтобы отделить индекс / адресуемость от фактического хранилища данных. Поэтому, если объект мозаики дорогой, сохраните его в компактной форме (например, в виде плоского массива). Но позвольте ему индексироваться через более дешевый объект. В простейшем виде это может быть двумерная (или трехмерная) матрица, которую можно легко индексировать по координатам, но каждый элемент в матрице является просто индексом. Затем вы используете этот индекс для поиска фактического содержимого тайла в отдельном компактном массиве. Если содержимое тайла еще не существует, добавьте его в конец массива и сохраните индекс в трехмерной матрице.

Решение становится более сложным, если вы хотите поддерживать удаление содержимого (так как оно приводит к фрагментации массива содержимого), и если содержимое вашего фрагмента дешевое, тогда дополнительный вес индекса (32-битные или 64-битные индексы) вероятно, сокрушит экономию от не хранения каждой потенциальной плитки. Это также дополнительный поиск, который снизит производительность вашего кеша.

Вы можете получить еще большую эффективность хранения, введя дополнительные уровни косвенности. Допустим, вы организовываете свои фрагменты в чанки, а чанки имеют гранулярность 64x64x64. Учитывая, что тайл 125, 1, 132, вы знаете, что он принадлежит чанку (1,0,2). Таким образом, у вас есть мир, который состоит из компактного массива чанков и матрицы индексов чанков (-1, если чанк не существует). Содержимое каждого блока (если имеется) представляет собой матрицу индексов листов размером 64x64x64 (-1, если лист еще не существует) и компактный массив используемых листов. Таким образом, вы не сжигаете огромное количество индексов плитки для кусков, которые никогда не используются. Следуя такому подходу и выбирая разумные числа для гранулярности фрагментов, вы можете масштабировать свою вселенную и контролировать использование памяти. На самом деле, если вы делаете свои куски 32x32x32,

Вы также можете делать хитрые трюки, например, использовать старший бит вашего индекса или фрагмента для обозначения чего-то особенного. Таким образом, если запись в матрице мозаики имеет верхний установленный бит, то младшие 31 бит не означают индекс мозаики, они означают «индекс деформации» или что-то подобное, и вы можете посмотреть это в отдельном поддерживаемом списке. чтобы узнать координаты, к которым он ведет.

Почему вы не можете хранить один миллион плиток в памяти? Даже мой телефон имеет 256 МБ ОЗУ; миллион пустых плиток будет 4-32MB?