18 июня 2014 в 16:15

Генерация ландшафтов в Unity3d

• Разработка игр ,
• Unity

• Tutorial

Думаю все заметили, что сейчас стало появляться множество всяких бродилок с выживанием в стиле Minecraft . Сделать такую решился и я. Начало было лёгким - Unity3d имеет огромный функционал для сознания простеньких игр (и не только). Персонаж, игровые объекты, в общем основу сделать быстро. Но какой minecraft без рандомно генерируемого мира? Это стало первой трудной задачей. И думаю не только для меня. Просмотрев весь гугл и потратив кучу времени на эту бесполезную вещь я решил написать эту статью дабы сократить страдания других.

План действия

Для начала хорошо бы было разобраться, что подразумевается под генерацией ландшафта:

Итак, поняв общий план действий, надо приступать к делу.

Частые ошибки

С самого начала я думал, что всё будет очень просто и для рандомной генерации ландшафта можно обойтись обычной функцией Random(). Но это самый неправильный способ. Его результат это вовсе не красивая карта, а расчёска в приближении.

Шум Перлина

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

Perlin noise (Шум Перлина, также иногда Классический шум Перлина) - математический алгоритм по генерированию процедурной текстуры псевдо-случайным методом. Используется в компьютерной графике для увеличения реализма или графической сложности поверхности геометрических объектов. Также может использоваться для генерации эффектов дыма, тумана и т.д.

Думаю многих испугала приставка псевдо, но от неё легко избавиться. Далее представлен способ реализации шума в Unity3d:

Using UnityEngine; using System.Collections; public class PerlinNoisePlane: MonoBehaviour { public float power = 3.0f; public float scale = 1.0f; private Vector2 startPoint = new Vector2(0f, 0f); void Start () { MakeNoise (); } void MakeNoise() { MeshFilter mf = GetComponent(); // Ищем mesh Vector3 vertices = mf.mesh.vertices; // Получаем его вершины for (int i = 0; i < vertices.Length; i++) { float x = startPoint.x + vertices[i].x * scale; // X координата вершины float z = startPoint.y + vertices[i].z * scale; // Z координата вершины vertices[i].y = (Mathf.PerlinNoise (x, z) - 0.5f) * power; // Задаём высоту для точки с вышеуказанными координатами } mf.mesh.vertices = vertices; // Присваиваем вершины mf.mesh.RecalculateBounds(); // Обновляем вершины mf.mesh.RecalculateNormals(); // Обновляем нормали } }
Я бы не сказал, что данный способ даёт ошеломляюще реалистичные результаты, но он довольно неплох для создания пустынь или равнин.

Алгоритм diamond-square

После долгих часов скитаний по интернету наткнулся на этот алгоритм, и он оправдал все мои ожидания. Он даёт прекрасные результаты. Для расчитывания вершин есть очень простая формула.
Представим себе плоскость, её 4 вершины и точку по центру. Её высота будет равна сумме высот 4 вершин, делённая на их кол-во и некого случайного числа с коэффициентом. Вот код для unity3d (халява копи-пастерам):

Using UnityEngine; using System.Collections; public class TerrainGenerator: MonoBehaviour { public float R; // Коэффициент скалистости public int GRAIN=8; // Коэффициент зернистости public bool FLAT = false; // Делать ли равнины public Material material; private int width=2048; private int height=2048; private float WH; private Color32 cols; private Texture2D texture; void Start () { int resolution = width; WH = (float)width+height; // Задаём карту высот Terrain terrain = FindObjectOfType (); float[,] heights = new float; // Создаём карту высот texture = new Texture2D(width, height); cols = new Color32; drawPlasma(width, height); texture.SetPixels32(cols); texture.Apply(); // Используем шейдер (смотри пункт 3 во 2 части) material.SetTexture ("_HeightTex", texture); // Задаём высоту вершинам по карте высот for (int i=0; i 1.0f) { middle = 1.0f; } } divide(x, y, newWidth, newHeight, c1, edge1, middle, edge4); divide(x + newWidth, y, newWidth, newHeight, edge1, c2, edge2, middle); divide(x + newWidth, y + newHeight, newWidth, newHeight, middle, edge2, c3, edge3); divide(x, y + newHeight, newWidth, newHeight, edge4, middle, edge3, c4); } } }

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

В какой ситуации удобен алгоритм

Недавно столкнулся с задачей: написать простую стратегию с трёхмерным ландшафтом. Так как я в данный момент обладаю маленьким опытом программирования на языке С++, мои попытки написать «diamond-square» закончились ошибками на ровном месте (ссылка на статью по «diamond-square» также будет в конце). Требовался простой в написании алгоритм, не дающий реалистичный ландшафт, так что данный метод поможет в первую очередь новичкам.

Алгоритм и результат

Прежде чем описывать сам алгоритм поделюсь его результатами:

Алгоритм заключается в том, что программа в случайных координатах заполняет карту прямоугольниками случайного размера. Карта имеет вид двухмерного массива, представляющего карту высот нашего ландшафта.

Для простоты создадим структуру прямоугольника:

Struct tRect { int x1, y1, x2, y2; }
Переменные x1 и y1 - левая нижняя координата прямоугольника, x2 и y2 - правая верхняя.

Наша карта представлена в виде массива HM;
- mapsizey и mapsizex - переменные, определяющие размер вашей карты;
- genStep - переменная, отвечающая за количество наших прямоугольников;
- zscale - некий коэффициент растяжения карты в высоту. Можно заменить числом.
- recSizex и recSizey - пределы размеров прямоугольника.

Теперь необходимо заполнить нашу карту прямоугольниками:

For (int i=0; i mapsizey) genRect.y2 = mapsizey; if (genRect.x2 > mapsizex) genRect.x2 = mapsizex; for (int i2 = genRect.x1; i2 Рельеф со скриншота был получен значениями:

genStep = 1024
zscale = 512
mapsizex и mapsizey = 128
recSize = 10

Далее вы выводите карту на экран любым доступным вам способом. В моём случае - openGl+glfw.

Преимущества и недостатки алгоритма

Преимущества:

• Простота и скорость в написании самого алгоритма
• Скорость исполнения алгоритма

Недостатки:

• Примитивность
• При маленьком шаге заполнения карты ландшафт становится «квадратным»
• Отсутствует возможность разбивать ландшафт на биомы по ходу генерации карты высот

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

Надеюсь, данная статья была Вам полезной.

Данная статья зародилась в моей голове, после того, как нам выдали курсач по мультимедийным технологиям в универе. «Универ… пф-ф-ф...» - так подумает мой читатель. Да только иногда здесь бывают дельные вещи. Вот, почему.

В курсаче предполагается создание виртуального ландшафта в старенькой программе VistaPro. В силу того, что раньше я ни с чем подобным не работал, я не могу сказать, насколько она функциональная. Но её большой плюс заключается в том, что она крайне проста в использовании (а другие террагены подчас довольно нетривиальны, что может вызвать некоторые трудности. Час же работы может не гарантировать успеха, в отличие от моего антиквариата), а освоить её от и до: разобрать весь функционал можно меньше чем за день не зная до этого ровным счётом ничего о ней. Небольшим, но всё-таки плюсом является совсем малый вес (~3 МБ). Разумеется, сейчас есть много подобных террагенов, которые обгоняют по функциональности VistaPro.

Здесь можно найти остальные части:

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

Я максимально подробно пишу всё, будто я это делаю для школьника 4-5 лет, ибо сам часто сталкиваюсь с тем, что написано очень заумно, в результате приходится тратить много времени на то, чтобы разобрать: а что же всё-таки написано?.. Конечно, мой читатель может сказать, что слишком большое количество деталей читать бывает слишком скучно и утомительно. Но, пока я остановлюсь именно на таком стиле изложения.

Итак, здесь можно будет найти описание функционала VistaPro, а также иллюстрацию работы большинства опций.

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

Кроме того, я поэтапно создам мирок или два для демонстрации возможностей программулины.

Посмотреть то, что может VistaPro можно, например, тут, на видосике:

Что же, начнём.

Скачать сей объект можно здеся:

Creation. Генерация карт

Для начала, стартанём экзешник. Откроется окно в стиле Windows 98. Это немного пугает изначально. Но потом привыкаешь.

Для того, чтобы не засорять пока что голову всякой чешуёй вроде работы с камерой и т.п. Погенерим, прежде всего, ландшафт, чтобы перед глазами постоянно мелькали картиночки. Может быть это слегка заинтересует моего читателя, после чего он захочет потыркать кнопочки программки и сам её поисследовать.

Итак, выполняем следующие действия.

Теперь, дорогой читатель, ты умеешь делать небольшой финт ушами для перехода от пирамиды к пирамидам(зачеркнуто), хотя слегка и хаотичным.

Итак, мы научились генерить карту. Для чистоты эксперимента, я открою новый файлик, в котором ничего нет, только чистое поле с пирамидкой. Отседова мы начнём попытки получить что-то ещё.

Все названия кнопочек я буду выделять жирным шрифтом.

Seed value

Под Seed value (Seed value будем везде брать равным 0, либо, в редких случаях другому числу. Чаще всего 1) находится магическая чиселка, которая задаёт некоторое начальное число генерации. Оно появляется случайно при нажатии на Randomize seed . Очевидно, что генерируя ландшафт с одинаковым Seed value , получим одинаковые карты, с разными - разные.

При генерации новой карты, можно действовать двумя методами. Либо нажать Randomize seed , либо активировать поле Seed value и нажать клавишу Enter . В первом случае будет сгенерено новое число Seed value , во втором случае значение не поменяется. Так удобно действовать, когда нужно экспериментировать с ландшафтом для получения одинаковых карт.

Feature Size

Идём далее. Feature size . Данная фитча позволяет сказать, насколько ландшафт будет разреженным. Или по-другому: этим свойством можно задать масштаб. Я возьму разные значения Seed value Например, при Feature size = 1 будет выглядеть так (две следующие картинки созданы для Feature size = 1):

При Feature size = 8 так (две следующие картинки созданы для Feature size = 8):

Разница очевидна. В принципе, некоторыми махинациями можно преобразовать ландшафт из структуры FeatureSize = 1 в структуру FeatureSize = 8. Но об этом позже. Это осуществляется во вкладке Manipulation :

Сравните (FeatureSize = 1 и FeatureSize = 8):

И ещё(FeatureSize = 1 и FeatureSize = 8):

Отрендеренные для тех же значений соответственно:

Set landscape

Рассмотрим Set landscape size . Эта опция задаёт размер мира. Automatic! - это то же самое, что и Small . Не отличается ничем.

Размер мира влиет на максимальное и минимальное значение координат X и Y.

Mega (С пяток секунд сидели, тупили. Здесь, при рендеренге, комп слегка подвис, поэтому рендерить я буду только на Small , за редким исключением):

Кроме того, размер влияет на чёткость структур (чем больше, тем чётче, т.е. масштаб больше), время генерации. Сравните (Feature size = 8) Mega и Small :

На данном этапе мы формируем поверхность. Фактически происходит работа тектонических процессов.

Fractal roughness

Как задавать высоту гор? Для этого рассмотрим параметр Fractal roughness . Для Fractal Roughness == 100 мы уже видели (смотрите выше). Возьмём теперь 0. Ответ напрашивается. Высота гор равна нулю, значит их просто нет. Плоскость:

А при Fractal roughness = 1000 наступает ад. Встречайте Гималаи.

Enlarge section

Enlarge section - выделение определённого участка и интерполяция (Interpolate ) его на всю карту, либо растяжение (Duplicate ) его по всей карте. Выбрать интерполяцию или дублирование можно сразу после того, как будет выбрана область.

Интерполяция подразумевает сглаживание грубых участков карты, а дублирование (или растяжение) это действие не выполняет. Для того, чтобы было понятно, в чём отличие, я поставлю Landscape size == Small . На больших картах, а точнее на карте ландшафта, этого эффекта практически не заметно. Сравните (я взял верхний левый угол):

Тот же участок, только для большой карты:

Smooth

На примере Enlarge section верхнего левого угла с опцией Duplicate , будет отлично видно, как работает сглаживание (Smooth ). После многократного нажатия вот что получим:

Erode

Теперь продемонстрируем ещё одну опцию - эрозия или старение (Erode ). Данный процесс выравнивает ландшафт, делает его однородным. Что это собой представляет? Мы запускаем процесс, после чего на карте чёрным цветом маркируются области с одинаковой высотой. Это происходит итеративно. В зависимости от изначальной ситуации это может происходить быстро (гладкий, изреженный острыми горами ландшафт, т.е. старые горы), либо медленно (ландшафт изрежен острыми горами, т.е. молодые горы). Скорость со временем нарастает: чем старше горы, тем сильнее будут заметны эрозийные процессы. Ландшафт получен после сглаживания (Smooth ) из предыдущего. Кстати, на больших картах эрозия работает тоже крайне долго. Устаёшь ждать.

Если сглаживания не проводить (не жамкаем много раз на кнопочку Smooth ), то получим нечто такое:

Получаются огромные плато в горах.

Сглаживание в отличие от эрозии делает гладкими горы, но не делает никаких плато.

Roughen

Но, постойте… А что если некий Вовочка подошёл и испортил наши офигитительские горы, которые мы получили, подбирая, например, Seed value . Скажем он их очень сильно сгладил. В таком случае можно откатиться (право, не до начального состояния), но всё-таки. Это делается с помощью Roughen . Я ещё раз срендерю ландшафт. После чего его сглажу. Здесь получится практически идентичный вышеприведённой карте ландшафт:

Сглаженный (без Roughen ):

После Roughen :

Но данная опция не проявляет себя, если на неё жамкать многократно, как например, на Smooth .

Stretch

Теперь жамкнем Stretch . Эффект получается как от Fractal roughness при генерации:

Ну, и на последок, картинка с Size landscape = Mega :

А теперь немного про вкладку Camera, окошко с ландшафтом и окошко камеры. Но основной упор я сделаю на это в следующий раз.

Экран VistaPro

В программе практически везде и всегда доступны 4 области: ландшафт, камера, параметры, вкладки.

Ландшафт

На карте с ландшафтом есть несколько объектов. Жёлтый квадратик - то место, где находится камера, жёлтый крестик - место, куда она направлена (далее, в разделе создания анимации, я скажу об этом моменте отдельно. Это очень важно для удаления эффекта тряски), две красные линии , ограничивающие угол обзора. Есть два слайдера : по оси Х, и по оси Y (выделены красным), которые позволяют осуществлять навигацию по карте - смещение центра карты вверх и вниз. Также есть маркеры "+" , "-" и "=" , осуществляющие увеличение, уменьшение масштаба и возвращение в исходное, центрированное состояние соответственно. Помимо этого есть ещё две опции: «C» - центрирование относительно положения камеры (относительно жёлтого квадратика) (следует попробовать сдвинуть камеру в строну, а после этого заюзать данную функцию), «T» - центрирвоание относительно фокуса (взгляда) (относительно жёлтого крестика). Для этого стоит сместить фокус, зажав Place target в разделе Camera , пощёлкать по карте ландшафта, после чего нажать «T»

На карте с ландшафтом можно найти координаты точки. Для этого подводим мышку в нужное место (на скрине мышку не заметно, но поверьте мне, что она есть на карте). Над окном ландшафта появятся координаты X=* Y=* Z=*.

Камера - это окошко в левом углу. Здесь можно увидеть в первом приближении, что будет срендерено. Это очень удобно, так как рендер занимает некоторое время, а здесь можно примерно представить, что будет видно на картинке.

Крестик в центре окна совпадает с крестиком, который тыркнут на ландшафте - это направление камеры. Для понимания того, что происходит, лучше попробовать что-нибудь поделать на карте и с камерой (Для этого будет идеальным сгенерить рандомную карту).

Рендеринг карты можно локализовать, выделив определённую область. Простите Вашего покорного слугу, но я не удержался и взял заготовленный ландшафт. Он чуть интереснее Пирамиды Хеопса. Сравните:

Для того, чтобы отследить этот эффект, следует нажать клавишу «BB» , после чего выделить область на ландшафте:

После рендеринга получим:

Чтобы убрать данный эффект, нажмите BB ещё разочек:

Кнопочки "+" и "-" около камеры меняют угол обзора, что непосредственно будет отражаться на изображении перед камерой: выпуклое, сжимающиеся в точку изображение или вогнутое соответственно. На ландшафте также происходят изменения (две красные прямые съезжаются и разъезжаются соответственно).

Смотрим в точку:

А тут смотрим с широким углом обзора:

Есть небольшой баг (возьму заготовленный ландшафт): место, куда указывает жёлтый плюсик на ландшафте не соответствует изображению перед камерой при бесконечно малых углах. Особенно хорошо это видно на границе водораздела: выставляем указатель камеры на ландшафте на землю (крутить камеру можно в разделе Camera -> Place target ), максимально близко к воде, после чего делаем фокусное расстояние очень большим (1000+ - долго-долго жмём на "+" ), после чего замечаем что камера смотрит на воду, а на ландшафте она сфокусирована на земле. Но это, разумеется, мелочи:

Каждый элемент интерфейса обладает подсказкой. Достаточно подвести к нему курсор, после чего высветится информация в левом нижнем углу, на label:

Внизу, под параметрами есть две кнопочки, которые доступны из любой вкладки: Render и Display . С одной из мы уже знакомы: Render . С помощью неё мы можем сгенерить ландшафт. Есть также Display . С помощью этой кнопочки можно загрузить последний срендереный ландшафт.

Вкладки

Вкладки представляют собой определённый разделы для моделирования мира. Рассмотрим каждый из них в целом, а затем разберём отдельно:

• Camera
  Данный раздел едва ли нужно пояснять. Здесь всё о положении камеры. Практически всё, что можно сделать с наблюдателем, можно сделать именно отседова.
• Light
  Свет - аналогичная ситуация. Солнце, солнечные затмения, освещённость и другие приятности можно найти тут.
• Sky
  Здесь можно завалить или подправить горизонт, включить облака, сделать тучи, добавить луну, а также поразвлекаться с атмосферой так, как хочется.
• Terrain
  Снег в горах, деревья, палитра текстур гор и многое другое.
• Water
  Здесь можно утопить свой мир цунами (плохо, право, топится).
• Tree
  Кэп.
• Texture
  Добавить свои или подправить родные.
• Manipulation
  Игры демиургов - здесь находятся кнопочки, позволяющие править мир целиком (видимо, по-другому и нельязя, только всё и сразу).
• Creation
  Генерим карту.
• Placement
  Построй свой город.
• Image
  Шумы, размеры картинки, а также другие параметры.
• VR Control
  Виртуальная реальность.
• Path
  Путь передвижения камеры (данная фишка нужна для анимации).
• Animation
  Создаём своё видео.

Трехмерными ландшафтами сегодня в компьютерных играх уже давно никого не удивишь. Вспомнить хотя бы такие игры как WarHammer: Dark Omen, Аллоды 3, или какую-нибудь современную стратегию в 3D. А задумывались ли вы, как эти ландшафты представляются в компьютере, строятся в памяти или отрисовываются на экране монитора? В данной статье я постараюсь рассмотреть тему построения трехмерных ландшафтов, некоторые концепции и идеи.

Первым пунктом мы коснемся способов представления данных о структуре ландшафта на компьютере. Потом проанализируем различные алгоритмы построения (генерации) ландшафтов. И, напоследок, речь пойдет об алгоритмах и приемах визуализации уже построенных ландшафтов. Ну что, поскакали?

Представление данных о ландшафте

Существует несколько основных принципов представления данных для хранения информации о ландшафтах:

• Первый - использование регулярной сетки высот (или еще другое название Карта Высот - HeightMap).
• Второе - использование иррегулярной сетки вершин и связей, их соединяющих (т.е. хранение простой триангулизированной карты).
• Третий - хранение карты ландшафта, но в данном случае хранятся не конкретные высоты, а информация об использованном блоке. В этом случае создается некоторое количество заранее построенных сегментов, а на карте указываются только индексы этих сегментов.

Рассмотрим первый вариант - использование карты высот

Данные представлены в виде двухмерного массива. Уже заданы две координаты (x, y - по высоте и ширине массива), и третья координата задается значением в конкретной ячейке, это высота.

Обычно карту высот хранят в файлах картинок. Это позволяет легко вносить изменения и более-менее наглядно просматривать данные. Тогда двумя координатами будет положение конкретного пикселя на картинке, а третья координата будет представлена цветом (чем выше значение, прямая зависимость от яркости пикселя - тем больше значение высоты для этой точки). Обычно такие картинки содержатся в монохромном варианте, но можно использовать и все цвета радуги. Второй вариант дает нам больше градаций высоты, чем предполагаемые 256 градаций в случае монохромного представления.

Например, вот карта высот и получившийся ландшафт (построено при помощи программы ReLife3D 2 - найти можно на моем сайте):

С помощью этого способа можно представить достаточно обширные пространства. Но у него есть один существенный недостаток - слишком много описаний для точек, а также, в некоторых случаях, наблюдается избыточность данных (например, когда у вас задается простая плоскость, то, в этом случае, для построения простой плоскости будет использоваться множество точек, хотя можно бы было обойтись тремя - надеюсь, геометрию все помнят:-)). Хотя и эта самая избыточность может пойти нам на пользу, например, при вертексном освещении.

У этого метода существует и несколько плюсов:

• наглядность, в любой программе просмотра графических файлов можно сразу увидеть всю информацию;
• простота изменения этих самых данных, так каксуществует множество программ для работы с растровой графикой;
• и еще одно, в таких картах можно хранить не только данные о высоте. Например, предположим, что для хранения высоты мы используем 16 бит, т.е. две цветовые компоненты, это получается 256x256=65536 градаций высоты. Остальные 8 бит мы можем использовать для хранения информации о каких-либо особенностях ландшафта, например, расположение зданий, строений, мостов, растительности и так далее.
• Еще одна идея использования карт высот. Будем хранить, также числовые, значения, но теперь не высот, а блоков (назовем их ландшафтными). Можно заранее создать некоторое количество карт высот небольшого размера (скажем 8x8 или 16x16 пикселей), а в нашей карте блоков высот хранить идентификатор существующего блока. Это дает нам значительно больший размер карты и, следовательно, ландшафта. Правда тут нужно будет обратить особое внимание на места соединения блоков. То есть, получается, что у нас первый способ представления данных для построения ландшафта плавно перекочевал в третий!
• Из некоторых других плюсов можно упомянуть легкость нахождения координат (и высоты!) на карте.
• И еще один плюс - так как вершинные точки расположены регулярно и достаточно близко, можно более правильно и достаточно аккуратно производить динамическое освещение (зачастую, освещенность вершины напрямую зависит от расстояния от этой вершины до источника освещения). Это и есть та самая польза от избыточности данных.

Теперь второй способ - иррегулярная сетка

Еще один способ представления данных для ландшафтов - иррегулярная сетка вершин и связей их соединяющих. Зачастую такие решения применяются в специализированных пакетах для игр (например, редактор уровней для Серьезного дядюшки Сэма) или специальных пакетах для работы с трехмерной графикой (типа 3Dmax, Maya и иже с ними). И хранятся в виде трехмерных моделей. Это дает основной выигрыш по сравнению с картами высот:

• используется значительно меньше информации для построения ландшафта. Нам необходимо хранить только значения высот каждой вершины и связи эти вершины соединяющие. Это дает нам выигрыш в скорости при передаче огромных массивов информации по AGP, в процессе визуализации ландшафта.

Но кроме плюсов у этого способа имеется и множество недостатков:

• алгоритмы построения ландшафтов в основном предназначены для регулярных карт высот. Оптимизация таких алгоритмов под этот способ потребует значительных усилий;
• Сложности при динамическом освещении - вершины расположены достаточно далеко друг от друга и неравномерно;
• Хранение, просмотр, модификация такого ландшафта также представляет сложности. При использовании карт высот вы пользуетесь достаточно простыми и "стандартными" средствами пиксельной графики. Хотя бы тем же MS Paint"ом. Тут же вам потребуются более навороченные и "весомые" пакеты.

Да, а вот и картинка изображающая данный принцип:

Способ третий - посегментная карта высот

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

• Возможность представления огромнейших открытых пространств;
• Кроме самих ландшафтов в таких блоках можно хранить и информацию о зданиях, строениях, растениях, специфических ландшафтных решениях (например, пещеры или скалы, нависающие друг над другом);
• Возможность создания нескольких вариантов одного и того же сегмента, но при разной степени детализации. В зависимости от скорости или загруженности компьютера можно выбирать более или менее детализованные варианты (так называемые LOD ландшафты - LOD - Level Of Detail).

Минусов у такого способа тоже хватает:

• Первый минус - надеюсь, для вас очевидный - проблема стыковки разных сегментов.
• Второй - неочевидность данных. Взглянув на картинку, вы (если вы конечно не гений мысли и у вас отсутствует поларойд в голове) не сможете моментально представить, как это должно будет выглядеть в игре.
• Следовательно, встает и проблема модификации. Если при первом варианте вы используете Paint, во втором 3DMax, то тут вам, скорее всего, потребуются самому писать редактор (хотя, наверное, такие уже существуют. Правда, я пока ни одного не знаю).

Текстуры для ландшафтов

Текстуры для ландшафтов можно разделить на три части примерно стиалогичным образом.

Во-первых - можно использовать всего одну текстуру для всего ландшафта. Это позволяет нам работать всего с одним ресурсом, при этом процедура рендеринга ландшафта произвольного размера будет содержать в лучшем случае 2-е строки, в худшем - 5-6 строк.

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

При использовании для текстуризации одиночной текстуры, мы имеем два возможных варианта:

• Размер текстуры меньше, либо равен, размеру ландшафта (при этом лучше, чтобы эти размеры были равными, или на худой конец, кратными друг другу).
• Размер текстуры больше размеров ландшафта.

Это дает возможность выбора формата вершин для ландшафта. Во втором случае нам однозначно придется использовать текстурированные вершины. В первом же случае все намного интереснее: мы можем использовать не текстурированные вершины, а окрашенные. При этом текстуру мы используем как ресурс, хранилище информации о цветах конкретных вершин. Это может дать нам большой прирост скорости, а при использовании огромных (именно огромных, а не больших около 5000x5000 пикселей и более) ландшафтов и текстур позволит добиться большей детализации (хотя в таком случае скорость будет сильно зависеть от размера, ведь при размере в 5000 на 5000 единиц для хранения ландшафта потребуется 5000x5000=25000000 вершин умножить на объем памяти для одной вершины равный 36 байт, 12 на три координаты - тип float, + 24 на цвет, тип DWORD. Получаем, что для хранения информации о таком ландшафте нам потребуется 25000000x36=900000000 байт!!! Это примерно 900 мб! При этом ландшафт у нас представлен 49980002 полигонами! Поэтому, пока лучше такими огромными ландшафтами не пользоваться).

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

Сгенерируем ландшафт

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

Вот использованный мной алгоритм:

• Создаем двухмерный массив необходимого размера;
• Генерируем в этот массив (во все ячейки) случайные значения;
• Проходимся простым сглаживающим фильтром:
  • Берем точку (все по порядку);
  • Вокруг этой точки берем значения всех восьми точек + значение выбранной точки;
  • Суммируем все эти девять значений;
  • Делим полученное значение на 9 (количество точек - простое усреднение);
  • Полученный результат записываем в исходную точку;
  • Пробегам весь массив;
• Далее заполняем случайными значениями еще несколько точек в исходном массиве (примерное количество точек всего - tsize*tsize , нужно заполнить tsiza*10 точек), конкретная точка выбирается случайным образом;
• Заново проходимся сглаживающим фильтром.

На что здесь следует обратить внимание. На втором шаге мы заполняем массив случайными значениями - я выбирал их пределы примерно от -300 до +300. В предпоследнем шаге мы опять используем случайные значения - в данном случае я брал их в пределе от -500 до +500. Это позволяет добиться достаточно изрезанного ландшафта. Вот скриншот, показывающий применение этого алгоритма в моей будущей игре:

Это простейший алгоритм, и, я думаю, запрограммировать его проблем не будет.

Теперь рассмотрим еще несколько алгоритмов.

Генерация ландшафтов с использованием Холмового алгоритма (Hill Algoritm)

Это простой итерационный алгоритм, основанный на нескольких входных параметрах. Алгоритм изложен в следующих шагах:

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

Как сгенерировать один холм

Первый, второй и четвертый шаги тривиальны, пятый и шестой мы рассмотрим далее. Теперь же займемся третьим шагом. Что же означает "поднять" холм? Фактически холм - это в нашем случае половина шара, чем больше радиус - тем больше холм (и выше). Математически это похоже на перевернутую параболу. Что бы не быть голословным покажу как это выглядит:

здесь (x1, y1) - заданная точка, r - выбранный радиус, (x2, y2) - высота холма. Вот как выглядит одиночный холм:

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

Теперь у нас уже есть построенный ландшафт. Теперь пойдем далее - к нормализации полученого результата.

Нормализация Ландшафта

При генерации значений для ландшафта мы не учитывали выходы этих значений за некоторые пределы (например - если у нас потом ландшафт будет храниться в монохромной картинке, то нам необходимо, чтобы все значения находились в пределе от 0 до 256). Для этого нам необходимо произвести нормализацию значений. Математически нормализация - это процесс получения значений из одного предела, и перевод его в другие пределы. Вот как это выглядит графически:

Чтобы нам это сделать мы производим следующие действия:

• сперва проходим по всему массиву и запоминаем наибольшее и наименьшее значения;
• после того, как мы узнали эти значения, мы заново проходим по всему ландшафту и производим нормализацию конкретных значений в пределы от 0 до 1. В виде формулы это выглядит так:

После этого мы имеем готовый ландшафт, нормализованный и готовый к дальнейшему использованию. Теперь перейдем к вопросу о "долинизации" ландшафта.

"Долинизация" ландшафта

Вообще говоря, данный ландшафт уже можно использовать. Что же мне еще не нравится? Конечно, ландшафт уже готов, но если присмотреться, то в нем достаточно мало долин. Склоны холмов излишне крутые, хочется сделать их более пологими. В этом нам поможет наш предыдущий шаг - нормализация. Все значения у нас сейчас находятся в пределах от 0 до 1. Идея "долинизации" состоит в следующем - взять от каждого значения квадратный корень. Это в большей степени влияет на средние значения, практически не затрагивая минимумов и максимумов. Графически это выглядит так:

А вот, как это повлияло на наш ландшафт:

Теперь с эти алгоритмом можно закончить.

В основном, рассмотренные нами алгоритмы предназначены для создания простого холмистого или гористого ландшафта. Но существуют и другие типы ландшафтов. Например, острова (точнее группы островов), озерные ландшафты. Их можно реализовать достаточно просто:

• создаем простой, достаточно холмистый ландшафт;
• затем перемещаем уровень воды вверх или вниз. (при этом следует оговориться, что мы примем за уровень воды, я обычно имею в виду нулевой уровень, там где координаты у=0).

Практически мы просто проходим весь массив высот и смещаем их на какое-то значение.

Теперь рассмотрим еще один тип ландшафтов - одиночные острова или горные плато (как часто показывают в американских фильмах), в зависимости от того, где мы затем "разместим" воду.

Модификация холмового алгоритма для островов

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

В исходном алгоритме мы выбирали центральную точку случайным образом, и она могла располагаться в любой части ландшафта. Теперь же нам интересно, чтобы холмы были расположены ближе к центру. Чтобы сделать это, введем две переменных (которые потом будем случайным образом изменять), назовем их расстояние и угол . Расстояние будет означать, как далеко от центра находится центральная точка для одиночного холма. Оно может изменяться от ноля (прямо по центру карты высот) до половины величины карты высот минус радиус холма. Это позволит нам избежать ситуаций пересечения холмов с краем карты высот. Угол будет показывать, в каком направлении от центра нам нужно будет поставить холм. Изменяется в пределах от 0 до двух Пи. Используя эти два значения, мы можем получить значения (x, y) для центральной точки конкретного холма и использовать их как и в простом алгоритме. Вот как нам можно получить значения для x и y:

здесь size - размер карты высот, distance - расстояние, theta - угол. Помните - радиус должен быть меньше половины размера карты высот.

Поработав с этими величинами, мы можем получить довольно прилично выглядящий остров:

Вот и весь алгоритм. Все предельно просто, и остров действительно похож на остров. Хотя нет, чего-то не хватает. Ну конечно же - остров-то где расположен? В воде…

Вот мы и рассмотрели некоторые алгоритмы построения карт высот для ландшафтов. Рассмотрим еще некоторые сопутствующие операции:

• Сглаживание (или по-другому - размытие). Низкочастотный фильтр для уменьшения эффектов угловатости. При многократном применении позволяет добиться очень гладких очертаний ландшафта. (Есть аналог в программе Adode Photoshop - фильтр Blur). Как это делается я уже показывал в первом алгоритме;
• Превращение гористой местности в холмистую. Я их различаю по очертанию вертикальных разрезов у вторых более пологие края. Как это делается я уже показывал ("долинизация" ландшафта);
• Создание пляжей и отмелей в случае с островами и берегами. Для этого места соприкосновения с водой сглаживают. Хотя могут существовать и скалистые пляжи и просто скалы.

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

В заключение

Ну… Это лишь небольшая часть существующих алгоритмов генерации ландшафтов. Я постарался рассмотреть некоторые достаточно простые в плане реализации и эффективные в плане полученного результата. В будущем, я думаю, реализую программу, которая будет генерировать карты высот, хотя, если поискать в Интернет, то наверняка что-нибудь отыщется.

P.S. При подготовке материала использовался пакет для триангуляции и визуализации ландшафтов ReLife3D 2.

Надеюсь, вам помогают мои советы и примеры. Следите за последующими обновлениями.