Ландшафтная генерация, часть 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 высоты и карты шумов.

В будущем я вам расскажу о:

Биомах!
Пещеры и больших странностях
Деревья, озерах и малых особенностях
И о пустотах!

Теперь я буду готовиться к посадке, чтобы я смог сделать пересадку!

*facepalm* Надо же было так много написать +) Взято с notch.tumblr.com и переведено в AkelPad +)