Ландшафтная генерация, часть 1
Запись от 09.03.2011
Я обещал написать о технических механизмах Minecraft’a, но так и не нашел время для этого. И сейчас я лечу на самолете откуда невозможно сбежать, начнем!
Одной из самых сложных и главный оставляющих мира Minecraft является генерация местности. Когда я изменил игру, от одной только зоны до бесконечной карты, генерировать местность стало намного сложнее, так как местность генерируется на лету, как игрок исследует мир, и оно не должно зависеть от того куда пойдет игрок.
1) Понятие бесконечность что это такое?
Прежде всего, позвольте мне прояснить кое-что о «бесконечной» карте: во-первых, карта не бесконечна, но в ней нет жесткого ограничения. Получается так: чем дальше вы находитесь тем больше у вас лагает. Ландшафт сгенерирован, сохранен и загружен, и (отчасти) представлен в блоках 16*16*128 блоков. Эти блоки имеют значение смещения, что является 32-битное целое число примерно в диапазоне от -2х млрд. до +2х млрд. Если вы выйдете за пределы этого диапазона (это около 25% пути до солнца, с того места где вы сейчас находитесь), то загружаясь и сохраняясь новые блоки начнут перезаписывать старые. На 1/16 этого расстояния, блоки или любые предметы, использующие позиции с целыми координатами, начнут вести себя странно и странно действовать.
Есть два жёстких ограничения.
Большинство других вещей, таких как семена, карты используют 64-битные числа и они делают намного более тонкие вещи. Например, при экстремально далекой дистанции, игрок может двигаться медленнее, чем у центра мира, из-за ошибок округления (у позиции есть огромная мантисса, у дельты перемещения есть крошечное, таким образом, это округляется быстрее). В сгенерируемой местности могут получаться такие странные постройки, огромные блоки одного вида, но я не вижу причины по которой это происходит. Одна из основных проблем, что при путешествии игрока на большие расстояния физика начинается глючить, таким образом игрок может случайно попасть под землю или застрять во время прогулки в стене.
Многие из этих проблем могут быть решены, изменяя математику локальных моделей вокруг игрока, центрирую числа так что числа могут иметь одинаковые значения. Minecraft уже использует локальные координаты в пределах блока и смещение положение блоков по отношению к игроку, чтобы дать впечатление движения игроку. Это происходит главным образом из-за OpengGL, 32-битных чисел с плавающей точкой для координат, но также и потому что погрешности округления чрезвычайно видимы в игре.
Мы, вероятно, не собираемся исправлять эти ошибки, пока это не распространено для игроков чтобы испытать их при игре законно. Мое шестое чувство подсказывает, что никто никогда до сих пор не имеет таких проблем, и никто не будет. Обход этого далеко займет очень долгое время. Кроме того, ошибки добавляют тайну и обаяние к Далеким Землям.
2) Вас не устраивает ландшафт?
В самой ранней версии Minecraft, я использовал 2D шума Перлина, чтобы придать миру форму. Или, скорее, я использовал их довольно много. Один для общей высоты, по одному на шероховатости (неровности) местности, и один для мелких деталей мира. Для каждой башни из блоков, высота вычислялась формулой (высота + (шероховатость (неровность) *мелкие детали)) *64 +64. Вертикальные поверхности и неровности были гладкими, с добавление крупномасштабных шумов, и детали становились более сложными. Этот метод был большим преимуществом в скорости, в нем только 16 * 16 * (количество шумов) образцов для генерации в блоке, но недостаток быть довольно скучен. В частности, нет никакого способа для этого метода что бы создать склоны и арки.
Так я перешел в систему аналогичные системе, основанной на 3D шумах Перлина. Вместо выборки «земля высоте», я рассматривал шумовые значение как «плотность», где все ниже нуля будет воздух, а все больше или равно нулю будет землей. Чтобы убедиться, что нижний слой твердый и верхней нет, я просто решил добавить высоты (за счет уровня воды).
К сожалению, я сразу же увидел проблемы в игровой механики. Проблемы в производительности, из-за огромного количества выборки сэмплов производительность падала, проблемы игровой механики были связанны с отсутствием равнин и пологих холмов. Решение обеих задач оказалось прост, переключение сэмплов на более низкое разрешение (8x по горизонтали, 4x по вертикали) и использование линейной интерполяции. Внезапно в игре появились равнины, пологие холмы, а также пропали проблемы с облаками.
Точная формула которую я использую немного сложней (и она секретна!), но она развивается медленно с течением времени, как я работал над игрой. Он по-прежнему я использую 2D высоты и карты шумов.
В будущем я вам расскажу о:
Биомах!
Пещеры и больших странностях
Деревья, озерах и малых особенностях
И о пустотах!
Теперь я буду готовиться к посадке, чтобы я смог сделать пересадку!
Источник статьи: http://stopgame.ru/blogs/topic/10632
Как генерируется мир в Minecraft
Minecraft люди воспринимают по-разному. Для сообщества это детский сад, для игровой индустрии — феномен, простой и гениальный. Господин Нотч необычайно умен и сотворил технически шедевральную игру, о внутренностях которой я хочу поведать.
В начале я расскажу о некоторых интересностях генерации игрового мира, чем вызваны и как связаны, а потом опишу непосредственно принцип генерации.
Этот псевдо-рандом используется в огромном количестве игр и эту статью можно считать отправной точкой в мир неслучайных случайностей.
Интересности
Начнем пожалуй с того, что количество вариаций игрового мира не бесконечно, всего 281 триллион вариантов, 281 триллион возможных » seed ов», которые можно указать при генерации карты.
Майнкрафт даже спидранят, для этого раннер просто тренирует и отрабатывает стратегию в определенном мире, а на начало рана вводит его «зерно» — буквенное или численное значение.
Ограниченность связана с количеством переменных, что задаются при генерации непосредственно мира, но об этом ниже.
Сам мир тоже не бесконечен, технически. Если вы потратите 2 года реального времени и добежите до координат более 15 миллионов блоков от центра (но все предпочитают телепортироваться), то наткнетесь на так называемые «Далекие земли» :
Связано это с тем, что значение переменной, отвечающей за «границы» игрового мира для генератора, становится больше положенного и старые элементы накладываются поверх новых.
Непосредственно генерация
Начать стоит с того, что мир генерируется не по блоку, существуют так называемые чанки площадью 16 на 16 блоков площади и 256 блоков в высоту, вот как они выглядят :
Прорисовываются и генерируются они на достаточно большой площади от игрока, всё зависит от настройки дальности. Прошу заметить, что блоков в чанке 65 536, такое количество элементов способно содержать в себе 16-битная переменная, отвечающая за свой чанк. Верно полагать каждому блоку полагается координата и его айди, для движка воздух тоже имеет айди, наверно равен он нулю.
Сама геометрия генерируется с помощью шума Перлина . Крайне занятная вещь, которую в майнкрафте применили почти везде. Шум Перлина представляет из себя процедурно-генерируемую псевдо-рандомную черно-белую текстуру :
Похоже на дым, а в шутерах используется для генерации эффектов дыма, но мы сейчас о майнкрафте. Вообще стандартная восьмибитная палитра содержит в себе 255 градиентов, что между белым и черным, однако из шума Перлина обычно берут 100 значений — от 0 до 1.
Можно использовать получившуюся текстуру для генерации высот карты, здесь можно уловить связь — самый черный цвет имеет значение 255 в палитре, напомнить высоту игрового мира? 256! Однако алгоритм оптимизирован и не позволит сгенерированной горе вырасти так высоко.
Из текстуры точечно берутся значения цвета пикселей и соотносятся к блоку на карте, в случае с картой высот — видом сверху. Это пример двухмерного использования шума, но есть трехмерный и даже четырехмерный!
Программисты любят баловаться с шумом Перлина, я говорил о карте высот, взгляньте :
Изначально шум получается уж очень резким и карта может выглядеть вот так :
Однако методами линейной интерполяции, один столб образует вокруг себя гору, а глубочайший блок — озеро, так как значения высоты усредняются в зависимости от соседних блоков.
Можно всё же не усреднять, а объединять. Спавним деревенщину шумом Перлина — многовато в одном месте? Стянуть всех сюда и воткнуть город.
Это будет не сглаживание, а наоборот, группировка или уплотнение.
Так же можно нарастить лес.
Возможности использования шума Перлина и математики в целом воистину безграничны, в дальнейшем я расскажу о алгоритмах
псевдо-рандома и где еще пригодился Перлин и его шум.
Источник статьи: http://zen.yandex.ru/media/strongholdofgamedev/kak-generiruetsia-mir-v-minecraft-5cc22697ad71e300b4a8d48e
[Гайд] Расширенная генерация мира в Minecraft 1.8
Итак, в Minecraft 1.8 (Снапшоты) был добавлен расширенный генератор мира. Включить его можно, выбрав в качестве типа мира «Customized«. Настройки генератора разделены на 3 блока. Для перехода между блоками используйте кнопки «Previous Page» (Назад) и «Next Page» (Вперёд)
Основные настройки (Basic Settings)
Sea Level — Уровень моря (По умолчанию: 63)
Strongholds — Крепости (По умолчанию: Включено)
Mineshafts — Заброшенные шахты (По умолчанию: Включено)
Ravines — Овраги (По умолчанию: Включено)
Dungeon Count — Количество подземелий (По умолчанию: 7)
Water Lake Rarity — Редкость озёр (По умолчанию: 4)
Water Lake Rarity — Редкость лавовых озёр (По умолчанию: 80)
Biome — Биом, который будет во всём мире (По умолчанию: Все)
River Size — Размер рек (По умолчанию: 4)
Caves — Пещеры (По умолчанию: Включено)
Villages — Деревни (По умолчанию: Включено)
Temples — Храмы (По умолчанию: Включено)
Dungeons — Подземелья (По умолчанию: Включено)
Water Lakes — Озёра (По умолчанию: Включено)
Lava Lakes — Лавовые озёра (По умолчанию: Включено)
Lava Oceans — Лавовые океаны (По умолчанию: Выключено)
Biome Size — Размер биомов (По умолчанию: 4)
Настройки руд (Ore Settings)
Spawn Size — Количество руды в одной жиле (По умолчанию: 33)
Min. Height — Минимальная высота (С какого блока распространяется?) (По умолчанию: 0)
Spawn Tries — Количество руды (Как часто будет встречаться руда?) (По умолчанию: 10)
Max. Height — Максимальная высота (До какого блока распространяется?) (По умолчанию: 256)
Расширенные настройки (Advanced Settings)
Советую не настраивать данные параметры. Неверная их настройка может повлечь за собой ужасные последствия для Вашего мира.
Источник статьи: http://ru-minecraft.ru/instrukcii-gajdy-minecraft/32567-gayd-rasshirennaya-generaciya-mira-v-minecraft-18.html
Генерация ландшафта как в MineCraft
Всем доброго времени суток.
Я хотел бы поделиться личным опытом по поводу генерации ландшафтов. Всё началось с того что я поиграл в Minecraft и больше всего меня поразил ландшафт, это был случайно генерируемый и при этом красивый ландшафт. Вообще признаюсь честно давно я не получал такого эстетического удовольствия глядя на уходящие в даль кубообразные холмы.
Конечно мне стало интересно, а как же такое вообще работает, на каких именно алгоритмах и все в этом духе. Долго ковыряясь с самой игрой, а так же облазив многие сайт с модами я узнал не так много, как хотелось бы, но позже нашел статью в блоге разработчиков о там как они раньше создавали свой ландшафт. Естественно я тоже решил попробовать создать свою версию ландшафта. Скажу честно, даже после прочтения той статьи пришлось долго искать на предмет других алгоритмов генерации ландшафтов, эрозии, биомов и сглаживания.
И так собственно о том, как я делал. Сначала я попробовал делать на основе шума Перлина (строил карту высот и по ней уже создавал 3д ландшафт), получилось достаточно интересно, но как видно не очень-то и похоже на Minecraft.
В 2д варианте это выглядело вот так.
Упрощенный пример кода для шума Кена Перлина.
for x:=-20 to 20 do
for y:=-20 to 20 do begin
n := x + y * 57;
n := (n shl 13) xor n;
ObjectCount:=ObjectCount+1;
Engine.AddProxy(PerlinCube,RootCube,’Cube’+IntToStr(ObjectCount),FileListBox1.FileName,x,2*(1 — ((n * (n * n * 15731 + 789221) + 1376312589) and $7fffffff) / 1073741824),y,0,1,0,1,1,1);
Map2[x,y]:=’Cube’+IntToStr(ObjectCount);
end;
В 3д смотрится лучше, да и то из за добавленного уровня воды. 
После прочтения статьи модифицировал, так как примерно было раньше в самой игре. Для каждого столба блоков высота равнялась (общ_высота + (шероховатость*детали))*64+64. От себя я добавил простое сглаживание. Получилось гораздо лучше.
Вот упрощенная часть кода для небольшого куска:
for x:=-20 to 20 do
for y:=-20 to 20 do begin
nerov:=Random(3);
melk:=Random(2);
Map1[x,y]:=((pod+(nerov+melk))*5+5)-25;
end;
Engine.AddUCube(RootCube,’PerlinCube’,FileListBox1.FileName,x,(1 — ((n * (n * n * 15731 + 789221) + 1376312589) and $7fffffff) / 1073741824),y,0,1,0,1,1,1);
for x:=-20 to 20 do
for y:=-20 to 20 do begin
ObjectCount:=ObjectCount+1;
Engine.AddProxy(PerlinCube,RootCube,’Cube’+IntToStr(ObjectCount),FileListBox1.FileName,x,map1[x,y],y,0,1,0,1,1,1);
Map2[x,y]:=’Cube’+IntToStr(ObjectCount);
end;
Я заснял поэтапно.
1. Построен кусочек карты. 
2. Добавлен шум Перлина. 
3. Первый цикл сглаживания. 
4. Второй цикл сглаживания. 
5. В конце немного деревьев что было не так уныло. 
Результатом я доволен, правда для полноценной игры вроде Minecraft он не дотягивает, но для 2д аркады в самый раз. Именно туда я прикрутил генерацию разреза ландшафта и отбрасывал кубы которые выше или ниже границы что бы было более удобно с точки зрения геймплея аркады. 
Ссылки.
Кому интересно вот ссылка на перевод статьи о ландшафте Minecarft.
Очень понравилась статья о шуме Перлина ссылка.
Так же напомнили про очень интересную статью по генерации ландшафтов ссылка.
Источник статьи: http://habr.com/ru/post/128368/
