Что такое хороший формат плоского файла для хранения 2D-карты тайлов, которая может бесконечно расти в любом направлении?

9

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

Каков хороший способ хранения картографических данных, привязанных к исходной точке 0,0, чтобы можно было быстро и эффективно загрузить прямоугольное подмножество картографических данных из любой точки на карте?

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

Натан Ридли
источник

Ответы:

7

Я бы не советовал использовать один плоский файл для теоретически бесконечных объемов данных.

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

Если вы распределяете свои чанки по нескольким файлам, получить чанк в (-110, 5000) - это просто сказать «% APPDATA% / game / map / -110 / 5000.dat» (или другое имя файла, если вы хотите начать сжимать их). Базы данных просто нужно запросить. Если в чанке нет данных, вы можете просто ничего не хранить. Один плоский файл не предлагает скорость и удобство произвольного доступа сразу.

В одном файле произвольного размера для быстрого произвольного доступа у вас должна быть гарантия местоположения любого куска данных, что означает использование индекса (поскольку необработанный двоичный поиск по вашим блокам данных снижает производительность, а создание сетки в вашем файл с "пустыми" пятнами дает вам проблему с Byte56 ). Как только вы разработаете систему индексирования, дадите ей эффективность и напишите себе API, вы воссоздали что-то вроде файловой системы или базы данных. Если вы на самом деле не получаете что-то от этого, это, вероятно, не стоит инвестиций. Например, Steam получает огромную выгоду от своих форматов файлов GCF / NCF.

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

doppelgreener
источник
4

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

Если вам нужно придерживаться одного файла, то вы можете найти вдохновение для своей реализации из ext2 fs. http://en.wikipedia.org/wiki/Ext2 Я знаю, что это помогло мне принять некоторые правильные решения, когда мне пришлось реализовать простую ФС для игры.

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

Ричард Фабиан
источник
4

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

Я также попробовал две файловые системы. Один файл содержит карту пар «позиция чанка» и «смещение файла чанка». Второй содержит все куски. Когда генерируется новый чанк, он просто идет в конец файла чанка, а его смещение сохраняется в файле position-> offset. Эта проблема была проблемой, когда у вас было МНОГО чанков, и поиск смещения в файле position-> offset занимал немного времени. Если вы найдете это возможным, вы можете загрузить данные положения -> смещения в хеш-карту при загрузке, чтобы иметь быстрый доступ.

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

MichaelHouse
источник
Я бы предложил посмотреть в sqlite sqlite.org . Он очень автономен, индексируется, обрабатывает BLOB-объекты и т. Д. Это поможет повысить производительность и устранить «дыры» в вашем файле.
Даниэль Блезек