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

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

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

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

  

Чанк a, b. Позиция x, y.

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

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

10 голосов | спросил The Communist Duck 29 12010vEurope/Moscow11bEurope/MoscowMon, 29 Nov 2010 23:38:57 +0300 2010, 23:38:57

2 ответа


9

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

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

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

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

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

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

ответил MrCranky 5 SunEurope/Moscow2010-12-05T15:46:43+03:00Europe/Moscow12bEurope/MoscowSun, 05 Dec 2010 15:46:43 +0300 2010, 15:46:43
6

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

ответил 30 22010vEurope/Moscow11bEurope/MoscowTue, 30 Nov 2010 00:11:12 +0300 2010, 00:11:12

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

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

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