Создание процедурных ландшафтов

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

Вступление

Вообще, если речь идет не о генерации ландшафтов, а просто о формировании линейного(коридорного) игрового уровня, то тут все просто: берется несколько «кусков» уровня, и расставляется в случайном порядке.Но в случае с ландшафтами все намного сложнее. Для их генерации не достаточно одной функции 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, без них действительно огромные ландшафты просто невозможны.

Автор: risenow

Источник ^[1]