Способ хранения потенциально бесконечных данных 2D-карты?

29

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

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

Blam
источник
2
Некоторые структуры данных, которые вы могли бы изучить для большего вдохновения, - это разреженные матрицы и (многоуровневые) таблицы страниц .
Эндрю Рассел
Низкий приоритет: не могли бы вы уточнить, является ли «длинный» тип данных 32- или 64-битным?
Рэндольф Ричардсон
2
@Randolf, учитывая, что это C #, вероятно, он имеет в виду C #, longкоторый является 64-битным (то есть maxlong Int64.MaxValue).
Эндрю Рассел
У Нотча есть кое-что интересное, что можно сказать о бесконечных картах в Minecraft в его блоге здесь: notch.tumblr.com/post/3746989361/terrain-generation-part-1
dlras2

Ответы:

17

Создайте собственный формат карты для своей игры. Это проще, чем вы думаете. Просто используйте класс BinaryWriter. Сначала напишите заголовок в несколько целых или кратких. Информация для включения в шапку:

  • Волшебная строка / магическое число вашего формата файла.
  • Начало / конец / размер фрагментов, описанных в этом файле

а также (и здесь идет критическая часть производительности

  • целые, которые описывают начальную позицию внутри файла. Таким образом, вам не нужно искать конкретные куски.

С помощью вышеуказанного метода вы можете (и должны) создать индекс содержимого ваших файлов, содержащий какое-то описание (пользовательское имя для региона / фрагмента или просто координаты) и в качестве второго значения позицию в файле.

Затем, когда вы хотите загрузить определенный фрагмент, вам просто нужно искать внутри индекса. Когда вы получили позицию, просто установите fileStream.Position = PositionOfChunkFromIndex, и вы можете загрузить ее.

Все дело в дизайне файлового формата с заголовком, наиболее эффективно описывающим содержимое файла.

Просто сохраните файлы с пользовательским расширением, которое вы создали, и все готово.

БОНУС: Добавьте сжатие BZip2 к определенным областям файла / всему содержимому (не к заголовку !!), чтобы вы могли распаковать определенные куски из файла, чтобы сэкономить очень мало места.

Riki
источник
12
Стоит отметить, что если вы собираетесь изменять этот файл на лету, вам понадобится либо фиксированный размер, либо внешний заголовок / индекс, чтобы вы могли добавлять куски в файл без необходимости переписывать весь файл (из-за изменения смещений).
Эндрю Рассел
В этот момент, разве вы не просто внедряете плоскую базу данных?
Апе-инаго
13

Я столкнулся с подобной проблемой и решил создать свою собственную структуру для обработки данных. Он свободно основан на квадродереве, но обладает бесконечной (по крайней мере, такой же большой, как Int) расширяемостью во всех направлениях. Он был разработан для обработки данных, основанных на сетке, которые расширялись из центральной точки, так же, как сейчас делает Minecraft. Это экономит место в памяти и очень быстро.

Вы можете указать минимальную величину для каждого узла (величина 7 будет 128x128), и как только у любого узла будет определенный процент заполненных его подузлов, он автоматически сведется в двумерный массив. Это означает, что очень густонаселенная часть (например, полностью изученный континент) будет иметь производительность массива (очень быстро), но малонаселенная часть (например, береговая линия, когда кто-то бродил вверх и вниз, но не исследовал внутреннюю территорию) будет иметь хорошую производительность и низкое использование памяти.

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

Я еще не использовал его для хранения данных в файле, но это интересная проблема, и я могу заняться этим дальше.

dlras2
источник
Так что это в основном расширяемое дерево, верно? Чего мне не хватает?
КаоД
2
Самым большим улучшением по сравнению с расширяемым деревом является то, что оно «сглаживает» определенные узлы дерева, которые сильно заселены (по умолчанию 70%), в двумерные массивы, а не сохраняет их структурированными, как деревья. Это дает вам скорость поиска в массиве без (бесконечного) размера бесконечного массива.
dlras2
Как лист, так и внутренние узлы, верно? Интересная идея, может дать хорошие результаты, я попробую, если мне когда-нибудь понадобится это. Кстати, +1 за выдачу кода и быстрый ответ! Да, и модульное тестирование тоже сделано, я (к сожалению) никогда не делаю этого в своих личных проектах :)
kaoD
Мы не проводим модульное тестирование на моей работе, так что, к сожалению, это мой способ восстания ... Я сделал для него демо-приложение, которое показывает, как оно заполняется и выравнивается, так что, если я смогу это исправить в следующие несколько дней, так что это презентабельно, я также выложу здесь. Это имеет больше смысла, когда вы видите это.
dlras2
1
Я потерял из виду это, извини! Я все еще хотел бы привести его в порядок, но я медленно переделываю часть кода между классом и домашней работой, так что это не будет какое-то время. На данный момент старая, не очень красивая демо здесь: j.mp/qIwKYt Под un-pretty я частично имею в виду, что это требует много объяснений, так что не забудьте прочитать README и не стесняйтесь задавать вопросы здесь или по электронной почте.
dlras2
3

Вместо этого вы можете использовать базу данных - PostgreSQL имеет некоторые специальные возможности индексирования, оптимизированные для данных этого типа, которые расположены по координатам X и Y. Вы также можете указать, что возвращаемые данные находятся в пределах определенного радиуса, а не в квадратной или продолговатой области.

  PostgreSQL (бесплатный и открытый исходный код)
  http://www.postgresql.org/

Существуют и другие базы данных, и для клиентской стороны вы можете найти определенные типы, которые лучше подходят для этого, поскольку они могут работать автономно (инициируется вашим игровым клиентским приложением) или могут быть включены как часть библиотеки кода. что вы можете «просто использовать». Преимущество состоит в том, что вам не нужно разрабатывать схему индексации, потому что большинство механизмов баз данных SQL уже делают это достаточно хорошо.

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

Я заметил, что некоторые игры хранят «кэш» картографических данных на локальном жестком диске после его получения в первый раз (это, несомненно, уменьшает сетевой ввод / вывод), например, Ashen Empires:

  Ashen Empires (бесплатная игра, красивая 2D реализация)
  http://www.ashenempires.com/

Отслеживание «последних обновленных» временных меток с каждым чанком / плиткой также будет полезно, поскольку для локально хранимых данных SQL-запрос может включать дополнительное предложение «WHERE timestamp_column> $ local_timestamp», чтобы получать только обновленные чанки / плитки загруженный (два преимущества экономии пропускной способности, как это: более низкая стоимость подключения и меньшая задержка для ваших игроков, что станет более очевидным, когда ваша игра станет популярной).

Снимок экрана из Ashen Empires (несколько персонажей находятся в местном банке, и, судя по тем костям на полу, похоже, что несколько скелетных монстров, должно быть, забрели внутрь и, вероятно, были убиты охранниками местного города):

введите описание изображения здесь

Рэндольф Ричардсон
источник
2

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

Теоретически вы можете сделать буквально бесконечную карту, которая будет таким образом сохранять в очень маленький файл.

код sh
источник
@ Джош Петри, спасибо за значительные и отличные языковые / стилистические исправления в моем посте. Жаль, что я не могу проголосовать за редактирование :-D
код
1

Есть ли способ разделить куски (некие «субконтиненты / страны» в вашем мире)? Так что, возможно, у вас могут быть какие-то индексные файлы, которые позволят вам быстро найти, какой подфайл / часть большего файла вам нужно загрузить, чтобы иметь чанк в памяти ...

phtrivier
источник
всегда есть способ разделить куски. ВСЕГДА. независимо от того, являются ли они видимыми для игрока / релевантными для остальной системы или нет, всегда есть способ разделить мировые данные на куски, обычно несколькими различными способами.
код
0

Вы можете взять идею из Minecraft. Первоначально у них был файл на кусок. Теперь они используют формат MCRegion, который группирует фрагменты в области 32x32 и сохраняет одну из них на файл.

Коммунистическая утка
источник