(495) 925-0049, ITShop интернет-магазин 229-0436, Учебный Центр 925-0049
  Главная страница Карта сайта Контакты
Поиск
Вход
Регистрация
Рассылки сайта
 
 
 
 
 

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

Источник: habrahabr
risenow

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

Вступление

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

Ссылки по теме


 Распечатать »
 Правила публикации »
  Написать редактору 
 Рекомендовать » Дата публикации: 26.02.2013 
 

Магазин программного обеспечения   WWW.ITSHOP.RU
EMS Data Comparer for Oracle (Business) + 1 Year Maintenance
VMware Horizon 7 Standard : 10 Pack (CCU)
Allround Automation PL/SQL Developer Single user license
IBM Domino Enterprise Server Processor Value Unit (PVU) Annual SW Subscription & Support Renewal
AutoCAD LT 2019 Commercial New Single-user ELD Annual Subscription PROMO
 
Другие предложения...
 
Курсы обучения   WWW.ITSHOP.RU
 
Другие предложения...
 
Магазин сертификационных экзаменов   WWW.ITSHOP.RU
 
Другие предложения...
 
3D Принтеры | 3D Печать   WWW.ITSHOP.RU
 
Другие предложения...
 
Новости по теме
 
Рассылки Subscribe.ru
Информационные технологии: CASE, RAD, ERP, OLAP
Новости ITShop.ru - ПО, книги, документация, курсы обучения
Программирование на Microsoft Access
Программирование в AutoCAD
Компьютерный дизайн - Все графические редакторы
OS Linux для начинающих. Новости + статьи + обзоры + ссылки
Реестр Windows. Секреты работы на компьютере
 
Статьи по теме
 
Новинки каталога Download
 
Исходники
 
Документация
 
Обсуждения в форумах
Ремонт ноутбука (1)
здравствуйте. Мой сын поломал ноутбук и мы решили поискать хороших специалистов по ремонту...
 
Сервисный центр (1)
Здравствуйте. Я решил купить себе смарт часы и смартфон фирмы Apple, но два года часы...
 
Где отремонтировать Макбук (1)
Всем привет! У сына сломался макбук и я решил поискать специалистов по ремонту фирменной...
 
Смарт часы (1)
Добрый день. У меня поломались почти новые смарт часы и я не знал, где их ремонтируют. Решил...
 
"Косметический салон" Corel PaintShop Pro (4)
А мы вот реальный косметологический салон хотим открыть, и нужно туда заказать не мало разного...
 
 
 



    
rambler's top100 Rambler's Top100