[Taugeshtu]

Warning! Алгоритмическая база топикстартера очень маленькая, так что просьба приводить ссылки на описание предлагаемых/обсуждаемых алгоритмов. Да, я до сих пор не выучил Octree. Заранее спасибо.

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

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

Какая идея пришла в голову мне во время бесед с Данилом и PAX'ом:
во-первых, хранить не байт информации для одного кубика, а бит. Просто флаг существования в данной точке пространства материи.
во-вторых, модифицировать формат кранча. не просто развернутый в последовательность бит массив, а развернутый по-плоскостно (т.е. вертикальная координата меняется после того, как записали все клетки в этой горизонтальной плоскости) массив, содержащий запись вида:
12 9 4
где 12 - число следующих за предыдущей отметкой других знаков. Началом всегда считается 0, т.е. запись выше равна:
000000000000 111111111 0000
(но в файле использовать 15-ричную систему, 16-й символ (код "1111") - конец числа, указывающего длинну последовательности)

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

Идем дальше. А как узнать, какого типа этот конкретный кубик?
Тут я предлагаю использовать хитрую штуку по имени "геологические карты": текстуры 1024х1024. В R-канале - толщина слоя от конца предыдущего слоя до начала следующего (или от дна мира, если предыдущего слоя нет; или до поверхности, если следующего слоя нет), в G-канале - по 4 бита на тип породы и тип примеси, в B- и A-каналы можно засунуть дополнительную информацию. Почему именно текстуры? Просто проще редактировать. На 1 тексель приходится площадь либо 1 (0.5?) кранча, либо 10х10 кубиков - тут надо посмотреть, как удобнее будет. Детализировать (определять, какой конкретно кубик какого конкретно материала) предлагаю процедурными алгоритмами (каким-нибудь 100%-повторяемым нойзом)
В итоге 10-20 текстурами мы опишем ландшафт 10х10 километров, созданный дизайнером а не машиной.

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

Спавнеры и прочие особенности я думаю имеет смысл записывать в форме отдельного блока данных с указанием координат и типа элемента.

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

Последнее. Как это всё собрать в единую картинку мира:
(геологические данные + интерполяция нойзом) * битовую запись существования материи + запись уникальных объектов (спавнеров) + запись скрафченного игроком.

Разумеется, всё это - в рамках зоны видимости.

Ну а теперь мне интересно, что вы думаете об алгоритмах майнкрафта (не только записи карты мира) ?