Доброго времени суток. Как со мной бывает, как только я разобрался в каком-то сложном для себя вопросе, я сразу хочу рассказать всем решение. Поэтому решил написать серию из двух статей по такой интересной теме, как процедурная генерация. А конкретнее, я буду рассказывать про генерацию текстур планет. В этот раз я подготовился основательнее и постараюсь сделать материал качественнее, чем в моем предыдущем посте «Простая система событий в Unity» (кстати, спасибо всем за ответные посты). Прежде чем продолжить, хочу обратить ваше внимание на несколько моментов:
1)Этот генератор не претендует на реалистичность, и писал я его для того, чтобы сгенерировать уникальные текстуры для сотни маленьких шариков, которые занимают 10% экрана и к тому же прикрыты облаками.
2)Но это не значит, что я не буду рад критике. Напротив, одна из причин написания этого поста — получить советы по улучшению алгоритма, я с радостью улучшу его.
3)Чисто технический момент: я пишу на C# под Unity3d, так что думать о том, как выводить в изображение с приемлимой скоростью вам придется самим, для каждого языка и платформы свои способы.
Итак, план таков: в первой статье я рассказываю о процедурной генерации планет типа «терра», потом получаю шквал критики, ради которого все и делалось, улучшаю алгоритм, дорабатываю для других типов планет и пишу вторую часть.
Готовы? Поехали.
Пролог
*Эта часть не несет большой смысловой нагрузки*
Как я писал выше, мне позарез понадобились текстуры планет. В принципе хватило бы по 2 — 3 для каждого вида, но даже такое количество для меня, никогда не пользовавшегося ничем сложнее paint.net, является неподъемным. Да и даже если бы нарисовал, качество оставляло бы желать лучшего. Поэтому я решил, что лучше написать генератор. Разумеется, сразу кинулся писать велосипед. Я решил сделать «клеточную генерацию». Моя идея заключалась в том, что мы создаем двумерный массив, клетки которого могут принимать несколько целочисленных значений (или enum'ов, без разницы), отвечающие за то, какой «элемент» (трава, пустыня, море, коренная порода...) будет отрисован в этот пиксель на экране. Через день бесплодных попыток идея была бракована как «бесперспективняк». Может у такого подхода и есть право на жизнь, но у него куча недостатков:
1)Сложная логика, особенно если клеток несколько.
2)Из всех 16 млн цветов мы используем самое большее 10 — количество клеток.
В общем, я начал искать более оптимальные алгоритмы и на сцену выходит…
Diamond-Square
Давным давно один хороший человек, Gavin S. P. Miller, описал алгоритм генерации 2D шума. А 4 года назад другой хороший человек, deNULL, написал подробную статью про этот и некоторые другие методы генерации. Прежде чем идти дальше, настоятельно рекомендую прочитать, алгоритм описан очень хорошо. Но, когда я стал писать код, возникло несколько технических проблем. Какие были проблемы и как их удалось решить расскажу по ходу статьи. Начнем с общей схемы действий:
Сначала, с использованием нашего алгоритма, генерируем «карту высот» — примерно то же самое, что мы видим на второй картинке. Так как значение компоненты цвета в Unity представляется дробным числом от 0 до 1, то моя реализация алгоритма заполняет поле значениями в этом диапазоне, но переделать алгоритм под другой диапазон не составит труда. Затем это значение в определенных соотношениях заносим в значения r,g,b цвета соответствующего пикселя. Приступим к первому пункту.
Генерируем карту высот
На этом месте вы, надеюсь, уже представляете себе общий принцип действия самого diamond-square, если нет, все-таки прочитайте статью, которую я указал выше. Я только опишу свою реализацию. Для начала сформируем двумерный массив, измерения которого должны быть равны 2^n + 1, для других размеров работать не будет). Я взял 2049х1025 (соотношение 2:1 лучше всего подходит для сферических планет в вакууме). Напишем методы Square и Diamond. Первая принимает координаты левого нижнего и правого верхнего углов квадрата и записывает значение в его центр. Вторая — принимает значение точки, которую надо посчитать (т.е. середины сторон этого квадрата) и вычисляет ее на основе значений смежных углов квадрата, его центра и центра соседнего квадрата. Вот на этом месте будет интересная загвоздка, но сначала сами методы:
public static int ysize = 1025, xsize = ysize * 2 - 1;
public static float[,] heighmap = new float[xsize, ysize];
public static float roughness = 2f; //Определяет разницу высот, чем больше, тем более неравномерная карта высот
public static void Square(int lx, int ly, int rx, int ry)
{
int l = (rx - lx) / 2;
float a = heighmap[lx, ly]; // B--------C
float b = heighmap[lx, ry]; // | |
float c = heighmap[rx, ry]; // | ce |
float d = heighmap[rx, ly]; // | |
int cex = lx + l; // A--------D
int cey = ly + l;
heighmap[cex, cey] = (a + b + c + d) / 4 + Random.Range(-l * 2 * roughness / ysize, l * 2 * roughness / ysize);
}
Важное замечание: Random.Range(float min, float max) возвращает псевдослучайное число в указанном диапазоне. Он быстр, но есть только в Unity. Я пытался сделать на System.Random и он оказался НАМНОГО медленнее. Может, не стоило создавать его экземпляр в цикле, я им почти не пользовался. Я к тому, что возможно вам придется самим писать генератор псевдослучайных чисел.
Едем дальше:
bool lrflag = false;
public static void Diamond(int tgx, int tgy, int l)
{
float a, b, c, d;
if (tgy - l >= 0)
a = heighmap[tgx, tgy - l]; // C--------
else // | |
a = heighmap[tgx, ysize - l]; // B---t g----D |
// | |
// A--------
if (tgx - l >= 0)
b = heighmap[tgx - l, tgy];
else
if (lrflag)
b = heighmap[xsize - l, tgy];
else
b = heighmap[ysize - l, tgy];
if (tgy + l < ysize)
c = heighmap[tgx, tgy + l];
else
c = heighmap[tgx, l];
if (lrflag)
if (tgx + l < xsize)
d = heighmap[tgx + l, tgy];
else<source lang="cs">
d = heighmap[l, tgy];
else
if (tgx + l < ysize)
d = heighmap[tgx + l, tgy];
else
d = heighmap[l, tgy];
heighmap[tgx, tgy] = (a + b + c + d) / 4 + Random.Range(-l * 2 * roughness / ysize, l * 2 * roughness / ysize);
}
Вот здесь остановимся подробнее. Как видите, для каждой точки я провожу проверку: не выходит ли она за границы массива. Если выходит, то я присваиваю ей значение противоположной. Т.е. если, например, мы вычисляем ромб в левой части, то абсцисса его левой вершины меньше нуля, вместо нее используем значение точки ей симметричной, т.е. xsize — l (l — половина стороны квадрата). Таким образом при наложении на сферу мы получим текстуру без шва. Кроме того, для координаты, которая может выйти за правую границу, проводятся дополнительная проверка. Дело в том, что diamond-square действует только для квадратов. Я делаю прямоугольник со сторонами 2:1 и считаю его как два квадрата. Поэтому я ввел флаг, определяющий, в какой части мы действуем и в соответствии с ним считал правой границей либо 1025 либо 2049 (ysize или xsize). Не очень изящное решение, зато дешево, надежно и практично, мне все равно не требуются другие соотношения, так что я оставил как есть.
Перепроверьте все координаты! Я из-за одной ошибки в параметре diamond'a целый день ломал голову перед этой, безусловно интересной математически, но совсем не в тему картины:
Наши инструменты почти готовы, остался последний небольшой метод, объединяющий их для одного квадрата.
public static void DiamondSquare(int lx, int ly, int rx, int ry)
{
int l = (rx - lx) / 2;
Square(lx, ly, rx, ry);
Diamond(lx, ly + l, l);
Diamond(rx, ry - l, l);
Diamond(rx - l, ry, l);
Diamond(lx + l, ly, l);
}
Обратите внимание, мы НЕ вызываем этот метод рекурсивно, объясню почему. Посмотрите на эту картинку:
Я пошагово нарисовал, что будет если рекурсивно вызывать Diamond-Square для под-квадратов. Первый квадрат считается нормально, т.к. вершины diamond'a выходят за пределы массива и вместо них используется центр квадрата. Но вот квадрат внутри него считается уже неправильно, т.к. середины квадратов — соседей еще не посчитаны. В результате ничего хорошего не получится. Таким образом, как и написано в той статье, считать надо слоями и рекурсия в данном случае не нужна. Через некоторое время после осознания этого факта мне удалось придумать этот обсчет по слоям:
public static void Generate()
{
heighmap[0, 0] = Random.Range(0.3f, 0.6f);
heighmap[0, ysize - 1] = Random.Range(0.3f, 0.6f);
heighmap[xsize - 1, ysize - 1] = Random.Range(0.3f, 0.6f);
heighmap[xsize - 1, 0] = Random.Range(0.3f, 0.6f);
heighmap[ysize - 1, ysize - 1] = Random.Range(0.3f, 0.6f);
heighmap[ysize - 1, 0] = Random.Range(0.3f, 0.6f);
for (int l = (ysize - 1) / 2; l > 0; l /= 2)
for (int x = 0; x < xsize - 1; x += l)
{
if (x >= ysize - l)
lrflag = true;
else
lrflag = false;
for (int y = 0; y < ysize - 1; y += l)
DiamondSquare(x, y, x + l, y + l);
}
}
Мы перебираем все длины сторон квадратов (внимательные люди могли заметить, что перебор начинается сразу с уполовиненной длины; если честно, понятия не имею почему, но если брать сразу полную сторону, получаются материки — переростки на всю карту) и для каждой из них последовательно перебираем все левые нижние углы квадратов в этом «слое» длин. Таким образом все квадраты всегда «знают» центры соседей и получается правильная картинка. Кстати, как видно из кода, четыре угла картинки (в нашем прямоугольном случае 4 угла и середины больших сторон) должны быть заданы, это входные данные алгоритма.
Вуаля!
Ну а теперь самое интересное — цвет.
Disclaimer: Все, что написано далее — мой велосипед. И, честно сказать, не самый лучший. Он выдает далеко не самую реалистичную картинку, его код громоздок и я с удовольствием выслушаю идеи по улучшению. Все, вы предупреждены, готовьте свои клавиатуры к написанию сочинений по процессам образования планет, я в школе плохо слушал и ничего не запомнил =)
Я решил разделить всю планету на три пояса: снег, зеленая зона, пустынная зона. Помните в учебниках географии картинки с ними? Вот сейчас их и будем делать. Для этого я создал отдельный класс. Он небольшой, выкладываю сразу весь:
public static class TemperatureCurves_class
{
static int xsize = Heighmap_class.xsize;
public static int snowEdge = Heighmap_class.ysize / 10;
public static int greenEdge = Heighmap_class.ysize / 3;
public static int[] northGreen = new int[xsize];
public static int[] southGreen = new int[xsize];
public static int[] northSnow = new int[xsize];
public static int[] southSnow = new int[xsize];
static float snowRoughness = 0.03f;
static float greenRoughness = 0.15f;
static void MidPointDisplacement1D(ref int[] curve, int l, int r, float roughness)
{
if (r - l > 1)
{
curve[(l + r) / 2] = (curve[l] + curve[r]) / 2 + (int)Random.Range(-(r - l) * roughness, (r - l) * roughness);
MidPointDisplacement1D(ref curve, l, (l + r) / 2, roughness);
MidPointDisplacement1D(ref curve, (l + r) / 2, r, roughness);
}
}
public static void Generate()
{
northSnow[0] = northSnow[xsize - 1] = Heighmap_class.ysize - snowEdge;
southSnow[0] = southSnow[xsize - 1] = snowEdge;
northGreen[0] = northGreen[xsize - 1] = Heighmap_class.ysize - greenEdge;
southGreen[0] = southGreen[xsize - 1] = greenEdge
MidPointDisplacement1D(ref northGreen, 0, xsize - 1, greenRoughness);
MidPointDisplacement1D(ref southGreen, 0, xsize - 1, greenRoughness);
MidPointDisplacement1D(ref northSnow, 0, xsize - 1, snowRoughness);
MidPointDisplacement1D(ref southSnow, 0, xsize - 1, snowRoughness);
}
}
Итак, как следует из названия, в этом классе лежат границы климатических поясов. Они в виде массивов — две южные, две северные. А генерируем мы их с помощью предка diamond-square: midpoint displacement. В нашем случае мы его используем на прямой. Думаю, принцип его действия после diamond-square объяснять не надо, тем более deNULL давно уже за меня это сделал. Фактически, там лежит набор координат y, сопоставленных координате х, обозначающих границу раздела поясов. Чтобы пояс был замкнутым (мы ведь все это потом на сферу натягивать будем), его края мы делаем равными. А для реализма у снега и для зеленой полосы делаем разные значения roughness так, чтобы полярный круг был кругом (прямой на текстуре), а пояса могли извиваться по самым непредсказуемым траекториям (но важно не переборщить, пустыня на границе снега будет смотреться странно). Впрочем, пустыни все равно будут смотреться странно, т.к. они определяются не только близостью к экватору, но и горами, ветрами и прочими факторами.
Работаем с цветом
Самая громоздкая и велосипедная часть кода, приготовьтесь.
Во-первых, создадим массив цветов (в юнити есть метод, быстро считывающий такой массив и записывающий его элементы в пиксели текстуры, это намного быстрее, чем всякие SetPixel() и прочие):
public Texture2D tex; //Ссылка на текстуру, в которую записываем результат
public static Color[] colors = new Color[Heighmap_class.xsize * Heighmap_class.ysize];
float waterLevel = 0.2f;
Кстати говоря, как писал deNULL, полезно возвести значения карты высот в квадрат, это немного сгладит ее и сделает более похожей на реальную.
void SqrHeighmap()
{
for (int x = 0; x < Heighmap_class.xsize; x++)
for (int y = 0; y < Heighmap_class.ysize; y++)
Heighmap_class.heighmap[x, y] *= Heighmap_class.heighmap[x, y];
}
Кроме того, на готовую текстуру накладываю такой эффект:
void SmoothImg()
{
for (int i = 0; i < Heighmap_class.xsize * Heighmap_class.ysize - 2; i++)
{
Color clr1 = colors[i];
Color clr2 = colors[i + 1];
colors[i] = (2 * clr1 + clr2) / 3;
colors[i + 1] = (clr1 + 2 * clr2) / 3;
}
}
Эффект небольшой, но и на скорость вроде не особо влияет.
А теперь пишем методы для задания цветов разным типам местности:
void SetSnow(int counter, float heigh)
{
if (heigh < waterLevel + Random.Range(-0.04f, 0.04f))
colors[counter] = new Color(Random.Range(0.8f, 0.85f), Random.Range(0.8f, 0.85f), Random.Range(0.85f, 0.9f));
else
{
colors[counter].r = 0.005f / heigh + Random.Range(0.8f, 0.85f);
colors[counter].g = 0.005f / heigh + Random.Range(0.8f, 0.85f);
colors[counter].b = 0.01f / heigh + Random.Range(0.8f, 0.85f);
}
}
Зима близко. Если под раздачу попала вода, покрыть однородной коркой снега, иначе покрыть коркой снега со слабыми очертаниями материков с небольшими затемнениями в районе возвышенностей.
void SetOcean(int counter, float heigh)
{
colors[counter].r = heigh / 5;
colors[counter].g = heigh / 5;
colors[counter].b = 0.2f + heigh / 2 + Random.Range(-0.02f, 0.02f);
}
Ну тут все понятно, океан он и на других планетах океан.
void SetGreen(int counter, float heigh)
{
colors[counter].g = 0.1f / heigh + 0.05f + Random.Range(-0.04f, 0.04f);
if (heigh < waterLevel + 0.1f)
colors[counter].g -= (waterLevel + 0.1f - heigh);
if (colors[counter].g > 0.5f)
colors[counter].g = 0.5f / heigh + 0.05f + Random.Range(-0.04f, 0.04f);
colors[counter].r = 0;
colors[counter].b = 0;
}
Меняем цвет обратно пропорционально высоте — чем выше, тем темнее. Кроме того, чтобы края материков не были засвеченными, у кромки воды уменьшаем его немного.
void SetDesert(int counter, float heigh)
{
colors[counter].r = Random.Range(0.6f, 0.75f) + heigh / 2 - 0.35f;
colors[counter].g = Random.Range(0.6f, 0.75f) + heigh / 2 - 0.35f;
colors[counter].b = Random.Range(0.2f, 0.3f) + heigh / 2 - 0.35f;
}
Тут все понятно, и еще один тип местности:
void SetMountains(int counter, float heigh)
{
float rnd = Random.Range(-0.03f, 0.03f);
if (heigh > 1.1f)
heigh = 1.1f + Random.Range(-0.05f, 0.05f);
colors[counter].r = heigh * heigh / 2 + rnd - 0.1f;
colors[counter].g = heigh * heigh / 2 + rnd - 0.1f;
colors[counter].b = heigh * heigh / 2 + rnd - 0.05f;
}
Горы, при этом избегаем засвета (отдельный вопрос, почему вообще появляются значения больше 1.0f, но юнити вроде ничего против не имеет).
И служебный метод проверки значения между минимумом и максимум, будет использоваться для определения принадлежности точки поясу:
bool ChechInRange(int value, int min, int max, int rand)
{
return ((value > min + rand) && (value < max + rand));
}
А теперь самое мясо:
void Awake()
{
Heighmap_class.Generate();
TemperatureCurves_class.Generate();
tex.Resize(Heighmap_class.xsize, Heighmap_class.ysize);
tex.Apply();
SqrHeighmap();
int counter = 0;
for (int y = 0; y < Heighmap_class.ysize; y++)
for (int x = 0; x < Heighmap_class.xsize; x++)
{
float heigh = Heighmap_class.heighmap[x, y];
if (heigh < waterLevel)
SetOcean(counter, heigh);
else
{
if (ChechInRange(y, TemperatureCurves_class.southSnow[x], TemperatureCurves_class.northSnow[x], Random.Range(-10, 10)))
if (ChechInRange(y, TemperatureCurves_class.southGreen[x], TemperatureCurves_class.northGreen[x], Random.Range(-10, 10)))
{
SetDesert(counter, heigh);
if (heigh < waterLevel + 0.1f + Random.Range(-0.05f, 0.05f))
SetGreen(counter, heigh);
}
else
SetGreen(counter, heigh);
if (heigh > 0.82f + Random.Range(-0.05f, 0.05f))
SetMountains(counter, heigh);
}
if ((y < TemperatureCurves_class.southSnow[x] + Random.Range(-10, 10)) || (y > TemperatureCurves_class.northSnow[x] + Random.Range(-10, 10)))
SetSnow(counter, heigh);
counter++;
}
SmoothImg();
tex.SetPixels(colors);
tex.Apply();
}
Попробуем словами:
Генерируем карту высот, генерируем границы поясов, инициализируем текстуру, возводим в квадрат.
В цикле:
Если высота меньше уровня океана, заполнить пиксель океаном.
В противном случае, проверять на принадлежность зеленой полосе, внутри проверяем принадлежность пустыни, если да, то делаем пустыню, если нет — то зелень.
Поверх этого всего ставим горы, если вдруг высота стала высокой.
И еще выше, если попали за полярный круг, то зовем белых ходоков снег.
Ну и после цикла сглаживаем картинку и загружаем в текстуру.
Вот такой генератор получился у меня. А какой у вас?
Автор: ArXen42
