0,0
рейтинг
24 февраля 2013 в 16:50

Разработка → Создание процедурных ландшафтов из песочницы tutorial

Думаю, многим было интересно создать игру в которой бы игровая карта генерировалась случайным образом, что бы при каждом запуске игры мир менялся и был уникальным. Ведь это принесет дополнительный интерес играть в Вашу игру. Всегда интереснее «побродить» по процедурной карте, чем по уже известной, десятки раз проеденной.
В этой статье, я рассмотрю алгоритм построения карт высот с помощью шумов Перлина, а также про методы оптимизации и придания ландшафту реалистичности.

Вступление


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

Карты высот (Height Map)


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

Пример кода:

float heightmap[width][lenght];

for (int i = 0; j < width; j++)
{
for (int j = 0; j < length; j++)
{
heightmap[i] [j]=CurHeight;
}
}


Итак, у нас есть построенная карта высот. Что это нам дает? Да все. Далее нужно просто разбить все это дело на треугольники.

vector Vertexes[width*length*2*3];
for (int i = 0; j < width; j++)
{
for (int j = 0; j < length; j++)
{
//first triangle
Vertexes[c].x=i;
Vertexes[c].y=heightmap[i] [j];
Vertexes[c].z=j;

Vertexes[c+1].x=i+1;
Vertexes[c+1].y=heightmap[i+1] [j+1];
Vertexes[c+1].z=j+1;

Vertexes[c+2].x=i+1;
Vertexes[c+2].y=heightmap[i+1] [j];
Vertexes[c+2].z=j;

//second tr
Vertexes[c+3].x=i;
Vertexes[c+4].y=heightmap[i] [j];
Vertexes[c+5].z=j;

Vertexes[c+6].x=i+1;
Vertexes[c+7].y=heightmap[i+1] [j+1];
Vertexes[c+8].z=j+1;

Vertexes[c+9].x=i;
Vertexes[c+10].y=heightmap[i] [j+1];
Vertexes[c+11].z=j+1;

}
}


Где width будет шириной ландшафта (по оси х), length — длинной (по оси z), CurHeight значение высоты для данного узла.
Карта высот:



Карта высот, разбитая на треугольники:



Построение карты высот на основе алгоритма шумов Перлина


Очень часто, люди которые поняли смысл и логику логику карты высот, бегут реализовывать ее и заполнять полностью случайными значениями(random(100)).И получают в результате вот что:



Для ландшафта простого рандома недостаточно. Ведь ландшафт должен иметь последовательность, плавность и некую зависимость между узлами в карте высот. И с такой задачей идеально справляются шумы Перлина. Шум Перлина — математический алгоритм по генерированию процедурной n-мерной текстуры псевдо-случайным методом.Внимательный читатель наверняка удивился двум словам в определении: «текстуры» и " псевдо-случайным". Поясню. Текстура, созданная с помощью этого алгоритма имеет 2 цвета — белый и черный. Соответственно, цвет можно использовать, как значение высоты. А псевдо-случайность развеивается коэффициентом сдвига, рассчитываемым всего один раз перед построением самой «текстуры». Этот коэффициент должен быть полностью случайным. Так как сам алгоритм хорошо расписан на хабре, да и вообще в интернете, я не буду приводить самой его реализации, скажу лишь об устранении этой самой псевдо-случайности и о возможных оптимизациях. Только в отличие от генерации текстур, нужно считать интерполированный (можно использовать разную: линейную, косинусную, кубическую и другие) шум.
Текстура, сгенерированная по алгоритму Перлина:



Устраняем псевдо-случайность


Делается это довольно просто. Код:

fac=Random(1000);
for (i=0 ,i<width,i++)   //x
{
for (j=0 , i<length,i++)   //z
{
heights[i][j]=PerlinNoisef(i,j,fac);
}
}


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

То есть сама функция должна выглядить примерно вот так:

for (int i=0 , i<= 12, i++) do
begin
total :=total+ CompleteNoise(x*freq, y*freq) * ampl;
ampl := ampl*pres;
freq:=freq*2;
end;
total:=(total)*2;
Result:=total;


Итак, о возможных оптимизациях. Первое, что приходит на ум — уменьшение числа октав. Это намного ускоряет алгоритм благодаря снижения числа итераций. Так же можно использовать линейную интерполяцию. Правда, от этого сильно пострадает качество.

Оптимизация отображения ландшафта


Ландшафты 1 000 х 1 000 и больше, будут состоять из 2 000 000 + треугольников, что представляет собой довольно большую нагрузку на растеризатор. Поэтому минимум, что нужно использовать — это VBO, то есть хранить информацию о вершинах на видеокарте. Но это не спасет от лагов, например при ландшафте 10 000 х 10 000. Так что, кроме этого требуется делать Frustum Culling (по Oct Tree) и Occlusion Culling. Так же есть такая вещь, как GeoMipMap, но это отдельная тема.Скажу лишь, что для больших ландшафтов она обязательна, и открывает большие просторы для оптимизации (например LOD'ы).

Дополнительные фичи


Для придания реалистичности ландшафту, следует использовать per-pixel lighting (для ландшафта хватит и простой апромиксации Фонга), parallax mapping и сплатинг. Если первые две вещи у человека, знакомого с 3D графикой, обычно не вызывают вопросов, то что такое сплатинг ландшафта многие изначально не знают. Так вот, сплатинг ландшафта служит для того, что бы имитировать такой природный процесс, как эрозия. Вы замечали, что на резких склонах гор поверхность покрыта не травой, как на равнине, а песком / землей. Для реализации всего этого дела нужны две текстуры. Одна — для равнинной поверхности ландшафта, другая — для поверхности склонов. Теперь, если мы примем равнинную текстуру за T1, а текстуру склона за T2, то формула будет выглядеть примерно так:

C = mix(T1,T2,dot(normal,vec3(0,1,0))

Где С — итоговый цвет, normal — нормаль к треугольнику, mix — функция линейной интерполяции.
dot(normal,vec3(0,1,0) — возвращает нам косинус угла отклонения от оси Y.Это можно упростить примерно так:

dot(norma,vec3(0,10) )= normal.x*0+normal.y*1+normal.z*0 = normal.y

А значит итоговая формула цвета будет такой:

C = mix(T1,T2,normal.y)

Все это хорошо реализовывается с помощью шейдеров. Приведу пример на GLSL.
Вершинный шейдер:

varying vec3 normal;
varying vec2 tc0;
varying vec3 pos;

void main(void)
{
 pos = vec3(gl_ModelViewMatrix* gl_Vertex);
 normal  =normalize(gl_Normal);
 gl_Position = ftransform();
 tc0  = gl_MultiTexCoord0.xy;
}



Фрагментальный шейдер:

uniform sampler2D diffuseMap;
uniform sampler2D splatMap;
uniform float splatCoef;
 
varying vec3 normal;
varying vec2 tc0;
varying vec3 pos;

void main(void)
{
vec3 n =( normal );
vec3 newDiff = mix(texture2D(diffuseMap,tc0),texture2D(splatMap,tc0),n2.y*splatCoef);
gl_FragColor  =diffuse;//vec4(newDiff,1); //ambient + diffuse;// + specular;
}


Заключение


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

Graphics Programmer
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (29)

  • +7
    А можете рассказать как заполнять такой ландшафт объектами? На примере майнкрафта это деревья (которые бывают частично на одном чанке (корень), частично на другом (листва)), деревеньки, реки, которые тянутся через множество чанков, биомы…
    • 0
      Также запрашиваю информацию о генерации ландшафтов с «overhangs», то есть объемных ландов с навесами, пещерами и т.п. Как я себе это представляю, нужно уже брать трехмерный Перлинов шум и что-то с ним хитрое вытворять.
      • 0
        Ничего хитрого 8) Сначала нужно сгенерировать карту высот основываясь на обычном 2ух мерном шуме Перлина. Затем пройтись по этой карте трехмерным шумом Перлина. Правда, придется поменять формат хранения карты высот.
        vector2 heightmap[i][j];
        

        Где heightmap[i,j].x и heightmap[i,j].y(на сомом деле z) — настоящие координаты узла, вычисленные уже с помощью трехмерного шума Перлина.
        • 0
          Я долго пытался понять, но не понял. Сначала мы сгенерировали карту высот, для любой точки на карте у нас есть координата z ландшафта. Далее каждую точку (x,y,z) ланда скармливаем трехмерному шуму, который даст еще одно значение. Итого на каждую точку ландшафта есть два значения, одно из них высота, другое непонятное. Как это поможет сгенерировать нависающую гору?
          • 0
            Я там ошибся немного. Должно быть vector3 heightmap[i][j];. Нужна еще y для хранения высоты. Ну, вы должны понимать что невозможность сделать нависающую гору создает именно то, что в стандартном виде карта высот не позволяет задать X и Y лежащие не в заданном интервале интервале. А если задавать карту высот так (vector3 heightmap[i][j];), то проблема устраняется, благодоря возможности заполнять X и Z любыми значениями.
            • 0
              Вот теперь я понял, спасибо. Мы каждую вершину карты высот итого сможем двигать по X,Y координатам относительно узла сетки. Правда, могут появиться артефакты при наложении таких плавающих вершин.
              • 0
                Эти артефакты можно будет аналитически выявить и устранять. Не думаю что алгоритм устранения артефактов будет очень сложным.
            • 0
              Честно говоря я не понял как устраняется эта проблема? Допустим мы скормили точку 0,0 в двумерный шум, и получили координаты вершины. Получили высоту ландшафта (скажем H). Теперь под этой точкой мы хотим пещеру. Пещера — это минимум еще 2 вершины под уже определенной (0, 0, H). Каким образом вообще трехмерный Перлинов шум даст нам нам координаты этих двух точек — я не понимаю. И уж тем более не понимаю, как перлинов шум поможет построить индексы, даже если мы знаем координаты всех точек пещеры. Объясните пожалуйста.
              • 0
                Скормили точку 0, 0 в двумерный шум, получили значение высоты H. Передаем в 3 мерный шум 0,H,0 и получаем R. Делаем сдвиг данного узла (0,0), находим его смещение. Итоговая координата узла будет (0+R*XC),H,(0+R*ZC), где XC,ZC =(Random(100)/100)*interval .То есть обобщенная формула координат узла будет такая (X+R*XC),(H),(Z+R*ZC).
                • 0
                  Прошу прощенья, там нужно XC,ZC =(Random(-100,100)/100)*interval.
                • 0
                  Рандом конечно это классно, но в этом случае мы получим пещеру как на этом изображении:

                  Причем опять же не ясно где где границы пещеры. Она будет по всей карте?
                • –1
                  И почему мы двигаем вдоль горизонтальной плоскости (x, z) вершину? И что такое interval? Пока количество вопросов только увеличивается…
                  • +2
                    Только по x,z.Я уже говорил, почему.
                    вы должны понимать, что невозможность сделать нависающую гору создает именно то, что в стандартном виде карта высот не позволяет задать X и Z лежащие не в заданном интервале. А если задавать карту высот так (vector3 heightmap[i][j];), то проблема устраняется, благодаря возможности заполнять X и Z любыми значениями.

                    Интервал — интервал между узлами в карте высот. Рандом всего от -1 до 1(если интервал 1), то есть такого не будет.Можно даже постоянные XC и ZC брать, главное, что бы они отличались, и были не больше interval, и не меньше (-interval).
                    • 0
                      Все, я понял что к чему, спасибо. Да, нависающую гору сделать можно, а вот с более менее глубокими пещерами будет очень много артефактов. Надо будет как-то повышать плотность вершин в области, которую вытягиваем. Еще раз спасибо за объяснения.
    • +1
      Попробуйте поискать здесь
    • НЛО прилетело и опубликовало эту надпись здесь
      • 0
        Это немного не то. Меня интересует как создавать и размещать обьекты вне масштаба чанков — примеры привел выше
    • 0
      Там, в принципе ничего сложного нет. В майнкрафте это сложнее из-за разделения всей карты на воксели. А в обычном ландшафте нужно просто узнать на каких треугольниках будет располагаться предмет, затем составить для него матрицу поворота(3х3), взяв за значение 2ой компоненты матрицы средний вектор нормалей треугольников на которых расположен объект, а за Х векстор в матрице взять средний нормализированный вектор между двумя точками в треугольниках. Вектор Z в матрице будет равен векторному произведению, уже найденных векторов X и Y.
      • 0
        Боюсь, я не совсем корректно выразился — с помощью шума Перлина мы можем создать кусок ландшафта, чанк. Но как сделать так чтобы через этот чанк проходила, скажем, река? Как сгенерировать сплайн этой реки так, чтобы он естественно переходил с чанка на чанк, и продолжался по мере генерации новых?
        • +1
          Хм, ну тут уже зависит от того, как у вас прдеставленна эта самая река. Если река представлена в виде заранее нарисованной 3D модели, то алгоритм будет выглядить примерно так:
          1) Смещаем реку на нужную позицию по x и z на нужную позицию, а по y смещаем так что-бы все вершины реки находились выше вершин ландшафта.
          2)Через середину каждого треугольника реки трасируем луч с вектором 0,-1,0 (вниз). Ищем пересечение с каждым треугольником ландшафта. По треугольнику с которым произошло пересечение строим матрицу поворота для данного треугольника реки. Так делаем для каждого треугольника реки.
          3)Применяем матрицу поворота к вершинам реки и смещаем по y на нужную нам позицию.
        • 0
          Насколько я знаю, в Minecraft реки не генерируются как сплайны (непрерывную карту было бы сложно так генерировать), скорее они образуются аналогично генерации обычной карты высот — посредством некоторой функции от пары координат (x, y) (точнее выделяются некие области на плоскости, окрестности границ между которыми и становятся реками — поэтому они могут запросто течь от одного океана к другому или вовсе превращаться в кольца).

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

          Как-то так:
  • +6
    Я просто оставлю это здесь.
  • +1
    а вот и ещё статейка по теме
    www.decarpentier.nl/scape-render
  • +1
    Вы не опоздали со статьей лет эдак на 15? Под этим заголовком стоило бы рассказать о десятке технологий генерации карт высот, хотябы с помощью World Machine. Я уже не говорю об обзоре разных подходов текстурирования, включая megatexture, normal-based mapping и пр.
    Как раз «использование perlin noise для самых маленьких» можно почитать и в печатной литературе прошлого века. Например,
    Texturing & Modeling: A Procedural Approach, David S. Ebert, et al. AP Professional, July 1998 ISBN 0-12-228730-4

    Ну и конечно же, ни одно описание работы с террейном не должно проходить без ссылки на vterrain.org/
    • +1
      Это моя вступительная статья. Ни более, ни менее.
      >разных подходов текстурирования
      >normal-based mapping
      Normal map, если, что это не метод текстурирования, а метод нанесения микрорельефа.
      World Machine — это уже готовая тулза, а в этой статье я рассказывал о создание своей.
      • +1
        Normal map, если, что это не метод текстурирования, а метод нанесения микрорельефа.

        побойтесь бога, я говорил не о normal mapping, а о использовании физического смысла вектора нормали для нанесения текстур (скалярное произведение между вектором нормали и зенита [0,0,1] показывает, наклонная эта часть ландшафта, либо плоская).

        World Machine — это уже готовая тулза, а в этой статье я рассказывал о создание своей.

        Вы собираетесь в следующих статьях рассказать, как реализовать эррозию, терассирование? генерировать дороги и места под строения? Если нет, то полученную вашей утилитой карту высот надо будет все-равно доводить до ума в каком-то редакторе. И там уже окажется, что 10-октавный Perlin Noise с заданными параметрами, а заодно и авто-раскраской делается в один клик, чтобы высвободить время под более важные задачи.

        Пока что, статья очень напоминает курсовые работы в современных вузах — вроде и работа сделана, и умные дядьки ставят плюсы, кивают головой, но на деле это все уже страшно устарело, не имеет никакой ценности и 200 раз уже печаталось ранее. Отсюда один шаг до интересных задач и сложных технологий, но пока этот шаг не сделан. Мне кажется, в 2013м году статью про террейн без подобной картинки вообще стыдно публиковать:
        • +1
          О господи, вы вообще статью читали, нет?
          побойтесь бога, я говорил не о normal mapping, а о использовании физического смысла вектора нормали для нанесения текстур (скалярное произведение между вектором нормали и зенита [0,0,1] показывает, наклонная эта часть ландшафта, либо плоская).

          Это называется сплатинг ландшафта. И о нем я подробно рассказал в статье.
          Это статья с пометкой «из песочинцы» и «туториал». Слишком большие у вас требования к статье. Про дороги и размещение других объектов на ландшафте я написал в комментариях.
          • 0
            О господи, вы вообще статью читали, нет?

            Это называется сплатинг ландшафта. И о нем я подробно рассказал в статье.


            Каюсь, просмотрел этот абзац. Правда, это и не сплаттинг в современном понимании, но в целом сойдет. Ок, выправил оценку с 3- до 3 :)

            Upd:
            Перечитайте еще раз свой абзац, замените буквы «О» на нули, проставьте недостающие знаки (скобки, запятые, буквы), поменяйте местами T1 и T2.
  • –2
    Ещё бы мой Генератор абстракций прикрутить в качестве текстур, был бы вообще космос! Кто не видел, может ознакомиться: vk.com/absgn

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.