Ландшафтная генерация, часть 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 зависает при генерации ландшафта
ДОБАВЛЕНО: ЧУТОЧКУ ВНИМАНИЯ! Ввиду случаев, сразу предупреждаю: это не предложение на добавление в minecraft-galaxy даной фичи (если бы было так, создал бы в соответствующем разделе)! Это просто тема вроде «посмотрите, что я нашел, круто, правда?»
› Все данные вычисляются и сохраняются на граф карте технологией CUDA
All data computed and stored on GPU via CUDA
› Прорисовка в реальном времени с помощью openGL и шейдеров
Real-time rendering with openGL + Shaders
› Весь трехмерный ландшафт описан системой уравнений
Whole terrain in 3D space described by set of equations
› Главным образом использовался трехмерный шум разной амплитуды и частоты
Mainly used 3D noise function of different amplitudes and frequencies
› Возможность взаимодействия с трехмерным материалом (Что делает его редактируемым)
Able to link with volumetric data (Makes terrain editable)
› Импорт трехмерного материала
Import volumetric data
› Бесконечные возможности генерирующих уравнений
Infinite possibilities of generating equations
› Нескончаемые системы пещер
Infinite cave system
› Нужны сюрреалистические или внеземные ландшафты?
Want it surreal/alien?
Редактировалось 8 раз(а), последний 2014-04-26 22:28:15
0 
| -2 |
| 0 |
| Редактировалось 1 раз(а), последний 2018-02-23 23:51:35 | 0 |
| TGC, кстати, а вот как генерируют ландшафт разработчики с NVIDIA: — Добавлено в 2014-04-25 11:48:37 Я, наверное, не совсем правильно задал название темы. Конечно же присутствует, но в майне генерация двухмерная. Я предлагаю просто сравнить и посмотреть, как эту же функцию сделали другие люди; возможно это кого-то вдохновит на что-то. Редактировалось 4 раз(а), последний 2014-04-25 11:49:27 | 1 |
| Вообще мне не понравилось! Редактировалось 1 раз(а), последний 2014-04-26 18:15:09 | -2 |
| Super-Ingener | (сообщение скрыто ввиду неодобрения читателями) показать | -3 |
| Вот только как я понял, эта технология исключительно на CUDA сделана? Редактировалось 1 раз(а), последний 2014-04-25 17:09:42 | 0 |
| 0 |
| 0 |
| #11: Этот пост был удален |
| 0 |
| 0 |
| 0 |
| Типа того, но можно ведь и не на CUDA сделать; например использовать OpenCL и запускать без привязок к архитектуре: на CUDA/AMD если поддерживается, или на проце, если GPU старенькая. Я как-то игрался с OpenCL, слишком замудренная штука, но програзм после написания еще тот. — Добавлено в 2014-04-25 19:00:31 Так вот и в чем фишка, что здесь мир редактируемый! И это круто, прямо же на видео можно видеть как происходит удаление и добавление материала. Редактировалось 4 раз(а), последний 2014-04-27 10:06:19 | 0 |
| 0 |
| Это взаимодействие заключается во внесении явно заданных правок в исходную функцию плотности (надеюсь, вы читали статью по вашей ссылке и понимаете, о чём я). То есть если это впилить в майнкрафт, то весь мир будет состоять из двух частей: изначально сгенерированный ландшафт в тех местах, где его никто не трогал, и такие же кубы, как сейчас, в тех местах, где кто-то покопался или что-то строил. Может, будет и красивее, чем сейчас, но невозможно будет руками повторить природный ландшафт, а это уже непохоже на майнкрафт. Это всё я пишу как программист с 20-летним стажем, работающий в области 3D-моделирования. Редактировалось 1 раз(а), последний 2014-04-25 19:56:27 | 0 |
| 0 |
| -1 |
| А в чём тогда будет отличие от того, что есть сейчас? Просто другой алгоритм генерации? Так он, скорее всего, меньше подходит для майнкрафта, чем существующий. Редактировалось 1 раз(а), последний 2014-04-25 20:02:22 | 0 |
| 0 |
| Изменяемый мир — на видео, в статье об этом ничего не говорится. Видео — это какой-то чел сделал магистерскую работу в универ — просто реализовал похожее, что было описано в статье. Мне понравилась сама идея изменяемого не-кубического мира, и я не совсем уверен, что этот мир на видео был сделан добавлением корректирующих параметров в формулу. Мне интересна сама идея изменяемого не-кубического мира. — Добавлено в 2014-04-25 20:37:03 В майнкрафте генерируется двухмерная «карта высот» с помощью алгоритма Diamond-Square или что-то типа того, возможно там уже немного изменили и использовали диаграмы Вороного (см. ССЫЛЬ и крутое ДЕМО), а затем сгенерировали пещеры и упадины с помощью алгоритма червья (как бы двигаясь и выедая все по пути). По ссылке много картинок, они немного отличаются от минекруфтовских, вроде этого. — Добавлено в 2014-04-25 20:45:29 Почему мелькнула мысль сюда написать. Здесь же вроди минекруфт гелаксе. И вдруг вспомнилась игрушка Corneroids, летаешь себе, ресурсы собираешь, корабли строишь, и на кораблях можно летать и стрелять. Автор ее забросил, а идея не вылазит с моей головы; мне кажется, в той игре отношения к галактике куда больше, чем в минекруфте и в любом его моде, т.к. летаем от планеты к планете же. Вот и подумал, если взять генерирование материала из первого поста, да воткнуть в Corneroids, и добавить возможности как в минекруфте, то цены такой игре небыло б)) А летать и исследовать вот такие вот планетки и астероиды с бешенными ландшафтами — это вам не в какой-то Nether мир мк сходить, там может быть реальная жесть, если для каждой планеты подбирать случайные параметры. Редактировалось 6 раз(а), последний 2014-04-25 20:47:11 | 1 |
| В общем, если говорить об идее не-кубического изменяемого мира, то я обеими руками за! Редактировалось 2 раз(а), последний 2014-04-25 20:47:27 | 0 |
| 0 |
|
Такое ведь только на картах Nvidia возможно? Редактировалось 3 раз(а), последний 2014-04-25 20:51:39 Источник статьи: http://forum.minecraft-galaxy.ru/topic/83814 |