Генератор ландшафта в Minecraft. Часть 1

В последнем посте в своем блоге Notch рассказал краткую историю создания и основные принципы работы генератора ландшафта в Minecraft. Предлагаю вам перевод данного материала (Осторожно, много терминологии!).

1) Насколько бесконечен мир?

Во-первых, позвольте разъяснить некоторые подробности насчет "бесконечности" миров. Миры не бесконечны, но и не имеют никаких жестких границ. Просто в игре появляется больше багов, когда вы заходите очень далеко. Ландшафт генерируется, хранится и загружается с диска и отрисовывается кусками по 16*16*128 блоков. У каждого куска имеется значение смещения, которое хранится в виде 32-битного целого числа и может находиться в диапазоне примерно от минус двух миллиардов до плюс двух миллиардов. Если вы зайдете за пределы этого диапазона (а это примерно четверть расстояния от Земли до Солнца), то новые куски начнут перекрывать собой старые. А после того, как вы преодолеете шестнадцатую часть этого расстояния, функции, использующие целые числа для работы с позициями блоков, такие как использование инструментов и поиск путей, начнут странно себя вести.

Это два действительно жестких ограничения.

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

Большинство этих проблем может быть решено сменой системы координат для математических расчетов на локальную, центром которой будет игрок. Тогда все рабочие значения не будут сильно отличаться друг от друга. Нечто подобное уже реализовано для прорисовки - Minecraft использует локальные координаты игрока в пределах блока и смещает блоки относительно игрока, чтобы создать видимость движения. Такой принцип применяется в основном из-за того, что OpenGL использует 32-битные дробные числа для позиций, но, кроме этого, еще и потому, что ошибки округления очень заметны при выводе на экран.

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

2) Ну разве эти ландшафты не восхитительны?

В очень ранней версии Minecraft для придания миру формы была использована карта высот на основе двумерного шума Перлина. Или, если быть точнее, несколько карт высот. Одна для общей высоты, одна для шероховатости ландшафта и одна для мелких деталей. Для каждого столба блоков высота равнялась (общ_высота + (шероховатость*детали))*64+64. Карты общей высоты и шероховатости были гладкими, сильно масштабированными шумами, а детали были более мелкими. У этого метода было замечательное преимущество в скорости, так как нужно было провести всего 16*16*(количество_шумов) расчетов на кусок карты, но его недостатком был скучный ландшафт. В частности из-за невозможности генерировать нависающие над землей выступы.

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

К сожалению, мгновенно появились проблемы производительности и играбельности. Первые - из-за большого количества требуемых расчетов, вторые - из-за отсутствия плоских местностей и гладких холмов. Решение обеих проблем заключалось в понижении разрешения при расчетах (8x масштабирование по горизонталям и 4x по вертикали) и достраивании ландшафта с помощью линейной интерполяции. В игре появились плоскости и холмы, а заодно исчезло большинство парящих в воздухе блоков.

Окончательная формула, которая используется сейчас, немного улучшена (и секретна!). Она медленно развивалась в течение разработки игры, и, кстати, до сих пор использует двумерные карты высот и шумности.

---

 

В СЛЕДУЮЩИХ ЧАСТЯХ:

• Биомы!
• Пещеры и крупные детали рельефа!
• Деревья, озера и мелкие детали рельефа!
• Мир Nether!

Перевод - Terzalo. Ссылка на оригинал