Предисловие
Если вы тоже
Эта статья подробно расскажет вам как можно использовать один из множества других методов генерации на примере горной местности и пещер. Мы будем рассматривать алгоритм Олдоса-Бродера и то, как сделать сгенерированную пещеру красивее.
По завершении чтения статьи у вас должно получиться что-то такое:
Итог
Теория
Гора
Если честно, то пещеру можно сгенерировать и на пустом месте, но ведь это будет как-то некрасиво? В роли «площадки» для размещения шахт я выбрал горный массив.
Эта гора генерируется достаточно просто: пускай у нас будет двумерный массив и переменная высоты, изначально равная половине длины массива по второму измерению; мы просто пройдемся по его столбикам и будем заполнять чем-то все строчки в столбике до значения переменной высоты, изменяя ее со случайным шансом в большую или меньшую сторону.
Пещера
Для генерации самих подземелий я выбрал — как мне показалось — отличный алгоритм. Простым языком его можно объяснить так: пускай у нас будут две (можно даже десять) переменные X и Y, и двумерный массив 50 на 50, мы задаем этим переменным случайные значения в пределах нашего массива, например, X = 26, а Y = 28. После чего мы некоторое количество раз делаем однообразные действия: получаем случайное число от нуля до , в нашем случае до четырех; а потом в зависимости от выпавшего числа меняем
наши переменные:
switch (Random.Range(0, 4))
{
case 0: X += 1; break;
case 1: X -= 1; break;
case 2: Y += 1; break;
case 3: Y -= 1; break;
}
Потом мы, разумеется, проверяем не выпала-ли какая-нибудь переменная за границы нашего поля:
X = X < 0 ? 0 :
(X >= 50 ? 49 : X);
Y = Y < 0 ? 0 :
(Y >= 50 ? 49 : Y);
После всех этих проверок, мы в новых значениях X и Y для нашего массива что-нибудь выполняем (например: прибавляем к элементу единицу).
array[X, Y] += 1;Подготовка
Давайте для простоты реализации и наглядности наших методов мы будем рисовать получившиеся объекты? Я так рад, что вы не против! Мы будем делать это с помощью Texture2D.
Для работы нам потребуется всего два скрипта:
ground_libray — это то, вокруг чего будет крутиться статья. Тут мы и генерируем, и чистим, и рисуем
ground_generator — это то, что будет пользоваться нашим ground_librayПускай первый будет статичным и ни от чего не будет наследоваться:
public static class ground_librayА второй обычный, только метод Update нам не понадобится.
Так же давайте создадим на сцене игровой объект, с компонентом SpriteRenderer
Практическая часть
Из чего всё состоит?
Для работы с данными мы будем использовать двумерный массив. Можно взять массив разных типов, от byte или int, до Color, но я считаю, что сделать так будет лучше всего:
Новый тип
Эту штуку мы пишем в ground_libray.
[System.Serializable]
public class block
{
public float[] color = new float[3];
public block(Color col)
{
color = new float[3]
{
col.r,
col.g,
col.b
};
}
}
Объясню это тем, что это позволит нам как сохранять наш массив, так и модифицировать его, если будет нужно.
Горный массив
Давайте, прежде чем начнем генерировать гору, обозначим место, где мы будем ее хранить.
В скрипте ground_generator я написал так:
public int ground_size = 128;
ground_libray.block[,] ground;
Texture2D myT;
ground_size — размер нашего поля (то есть массив будет состоять из 16384-х элементов).
ground_libray.block[,] ground — это и есть наше поле для генерации.
Texture2D myT — это то, на чем мы будем рисовать.
Как это будет работать?
Принцип работы у нас будет такой — мы будем вызывать какие-нибудь методы ground_libray из ground_generator, отдавая первому наше поле ground.
Давайте создадим первый метод в скрипте ground_libray:
Создание горы
И сразу же попытаемся понять, что тут происходит: как я уже сказал, мы просто пробегаемся по столбикам нашего массива b, параллельно изменяя переменную высоты h_now, которая изначально была равна половине 128 (64). Но есть тут еще кое-что новое — mount_noise. Это переменная отвечает за шанс смены h_now, ибо если менять высоту очень часто, то гора будет смотреться как расческа.
public static float mount_noise = 0.02f;
public static void generate_mount(ref block[,] b)
{
int h_now = b.GetLength(1) / 2;
for (int x = 0; x < b.GetLength(0); x++)
for (int y = 0; y < h_now; y++)
{
b[x, y] = new block(new Color(0.7f, 0.4f, 0));
h_now +=
Random.value > (1.0f - mount_noise) ?
(Random.value > 0.5 ? 1 : -1) : 0;
}
}
И сразу же попытаемся понять, что тут происходит: как я уже сказал, мы просто пробегаемся по столбикам нашего массива b, параллельно изменяя переменную высоты h_now, которая изначально была равна половине 128 (64). Но есть тут еще кое-что новое — mount_noise. Это переменная отвечает за шанс смены h_now, ибо если менять высоту очень часто, то гора будет смотреться как расческа.
Цвет
Я сразу задал слегка коричневатый цвет, пускай хотя бы какой-нибудь будет — в дальнейшем он нам не понадобится.
Теперь давайте перейдем в ground_generator и в методе Start напишем вот это:
ground = new ground_libray.block
[ground_size, ground_size];
ground_libray.generate_mount(ref ground);
Мы инициализируем переменную ground
После без объяснений отправляем ее ground_libray-ю.
Так мы сгенерировали гору.
Почему я не вижу свою гору?
Давайте теперь нарисуем то, что у нас получилось!
Для рисования мы напишем в нашем ground_libray такой метод:
Рисование
Тут мы уже не будем отдавать кому-то свое поле, дадим только его копию (правда, из-за слова class, мы дали чуточку больше, чем просто копию). А так же подарим этому методу нашу Texture2D.
Первые две строки: мы создаем нашу текстуру размером с поле и убираем фильтрацию.
После чего мы проходимся по всему нашему поле-массиву и там, где мы ничего не создали (class нужно инициализировать) — мы рисуем пустой квадратик, в ином случае, если там не пусто — мы рисуем то, что сохранили в элемент.
public static void paint(block[,] b, ref Texture2D t)
{
t = new Texture2D(b.GetLength(0), b.GetLength(1));
t.filterMode = FilterMode.Point;
for (int x = 0; x < b.GetLength(0); x++)
for (int y = 0; y < b.GetLength(1); y++)
{
if (b[x, y] == null)
{
t.SetPixel(x, y, new Color(0, 0, 0, 0));
continue;
}
t.SetPixel(x, y,
new Color(
b[x, y].color[0],
b[x, y].color[1],
b[x, y].color[2]
)
);
}
t.Apply();
}
Тут мы уже не будем отдавать кому-то свое поле, дадим только его копию (правда, из-за слова class, мы дали чуточку больше, чем просто копию). А так же подарим этому методу нашу Texture2D.
Первые две строки: мы создаем нашу текстуру размером с поле и убираем фильтрацию.
После чего мы проходимся по всему нашему поле-массиву и там, где мы ничего не создали (class нужно инициализировать) — мы рисуем пустой квадратик, в ином случае, если там не пусто — мы рисуем то, что сохранили в элемент.
И, конечно, по завершении мы идем в ground_generator и дописываем это:
ground = new ground_libray.block
[ground_size, ground_size];
ground_libray.generate_mount(ref ground);
//вот тут дописываем
ground_libray.paint(ground, ref myT);
GetComponent<SpriteRenderer>().sprite =
Sprite.Create(myT,
new Rect(0, 0, ground_size, ground_size),
Vector3.zero
);
Но сколько бы мы не рисовали на нашей текстуре, в игре мы это сможем увидеть, только наложив этот холст на что-нибудь:
SpriteRenderer нигде не принимает Texture2D, но нам ничего не мешает создать из этой текстуры спрайт — Sprite.Create(текстура, прямоугольник с координатами нижнего левого угла и верхнего правого, координата оси).
Эти строчки будут вызываться самыми последними, все остальное мы будем дописывать выше метода paint!
Шахты
Теперь нужно заполнить наше поля случайными
ref block[,] b - это мы отдаем наше поле.
int thick - толщина краев пещеры
int size - в некотором роде это можно назвать размером пещеры
Color outLine - цвет краевПещера
Для начала мы объявили наши переменные X и Y, вот только назвал я их xNow и yNow соответственно.
Первая, а именно xNow — получает случайное значение от нуля до размера поля по первому измерению.
А вторая — yNow — так же получает случайное значение: от нуля, до середины поля по второму измерению. Почему? Мы генерируем нашу гору с середины, шанс того, что она будет дорастать до «потолка» — не большой. Исходя из этого я не считаю релевантным генерировать пещеры в воздухе.
После сразу идет цикл, количество тиков которого зависит от параметра size. Каждый тик мы обновляем поле в позиции xNow и yNow, а уже потом обновляем их самих (обновления поля можно поставить в конец — разницы вы не ощутите)
Так же тут есть метод make_thick, в параметры которого мы передаем наше поле, ширину обводки пещеры, текущую позицию обновления пещеры и цвет обводки:
public static void make_cave(ref block[,] b,
int thick, int size, Color outLine)
{
int xNow = Random.Range(0, b.GetLength(0));
int yNow = Random.Range(0, b.GetLength(1) / 2);
for (int i = 0; i < size; i++)
{
b[xNow, yNow] = null;
make_thick(ref b, thick, new int[2] { xNow, yNow }, outLine);
switch (Random.Range(0, 4))
{
case 0: xNow += 1; break;
case 1: xNow -= 1; break;
case 2: yNow += 1; break;
case 3: yNow -= 1; break;
}
xNow = xNow < 0 ? 0 :
(xNow >= b.GetLength(0) ? b.GetLength(0) - 1 : xNow);
yNow = yNow < 0 ? 0 :
(yNow >= b.GetLength(1) ? b.GetLength(1) - 1 : yNow);
}
}Для начала мы объявили наши переменные X и Y, вот только назвал я их xNow и yNow соответственно.
Первая, а именно xNow — получает случайное значение от нуля до размера поля по первому измерению.
А вторая — yNow — так же получает случайное значение: от нуля, до середины поля по второму измерению. Почему? Мы генерируем нашу гору с середины, шанс того, что она будет дорастать до «потолка» — не большой. Исходя из этого я не считаю релевантным генерировать пещеры в воздухе.
После сразу идет цикл, количество тиков которого зависит от параметра size. Каждый тик мы обновляем поле в позиции xNow и yNow, а уже потом обновляем их самих (обновления поля можно поставить в конец — разницы вы не ощутите)
Так же тут есть метод make_thick, в параметры которого мы передаем наше поле, ширину обводки пещеры, текущую позицию обновления пещеры и цвет обводки:
Обводка
Метод берет переданную ему координату start, и вокруг нее на расстоянии t перекрашивает все блоки в цвет o — все очень просто!
static void make_thick (ref block[,] b, int t, int[] start, Color o)
{
for (int x = (start[0] - t); x < (start[0] + t); x++)
{
if (x < 0 || x >= b.GetLength(0))
continue;
for (int y = (start[1] - t); y < (start[1] + t); y++)
{
if (y < 0 || y >= b.GetLength(1))
continue;
if (b[x, y] == null)
continue;
b[x, y] = new block(o);
}
}
}
Метод берет переданную ему координату start, и вокруг нее на расстоянии t перекрашивает все блоки в цвет o — все очень просто!
Теперь давайте допишем в наш ground_generator эту строчку:
ground_libray.make_cave(ref ground, 2, 10000,
new Color(0.3f, 0.3f, 0.3f));
Вы можете установить скрипт ground_generator как компонент на наш объект и проверить как это работает!
Еще о пещерах...
- Чтобы сделать больше пещер, вы можете вызвать метод make_cave несколько раз (использовать цикл)
- Изменение параметра size не всегда увеличивает размер пещеры, но зачастую она становится больше
- Изменяя параметр thick — вы значительно увеличиваете количество операций:
если параметр равен 3, то количество квадратиков в радиусе 3 будет 36, значит при параметре size = 40000 — количество операций будет 36* 40000 = 1440000
Коррекция пещер
Вы не замечали, что в этом виде пещера выглядит не лучшим образом? Слишком много лишних деталей (возможно, вы считаете иначе).
Чтобы избавиться от вкраплений какого-то #4d4d4d мы напишем в ground_libray вот этот метод:
Чистильщик
Но будет сложно понять, что тут происходит, если вы не будете знать, что делает функция solo:
В параметрах у этой функции обязано находиться наше поле, радиус проверки точки, «порог уничтожения» и координаты проверяемой точки.
Вот подробное объяснение того, что делает эта функция:
Краткое описание алгоритма: мы проходимся по всему полю и проверяем все точки на то, нужны они ли нет.
public static void clear_caves(ref block[,] b)
{
for (int x = 0; x < b.GetLength(0); x++)
for (int y = 0; y < b.GetLength(1); y++)
{
if (b[x, y] == null)
continue;
if (solo(b, 2, 13, new int[2] { x, y }))
b[x, y] = null;
}
}
Но будет сложно понять, что тут происходит, если вы не будете знать, что делает функция solo:
static bool solo (block[,] b, int rad, int min, int[] start)
{
int cnt = 0;
for (int x = (start[0] - rad); x <= (start[0] + rad); x++)
{
if (x < 0 || x >= b.GetLength(0))
continue;
for (int y = (start[1] - rad); y <= (start[1] + rad); y++)
{
if (y < 0 || y >= b.GetLength(1))
continue;
if (b[x, y] == null)
cnt += 1;
else
continue;
if (cnt >= min)
return true;
}
}
return false;
}
В параметрах у этой функции обязано находиться наше поле, радиус проверки точки, «порог уничтожения» и координаты проверяемой точки.
Вот подробное объяснение того, что делает эта функция:
int cnt — то счетчик текущего «порога»
Далее идут два цикла, которые проверяют все точки вокруг той, координаты которой переданы в start. Если находится пустая точка, то мы прибавляем к cnt единицу, по достижении «порога уничтожения» мы возвращаем истину — точка является лишней. Иначе мы ее не трогаем.
Порог уничтожения я установил в 13 пустых точек, а радиус проверки 2 (то есть проверит он 24 точки, не включая центральную)
Пример
Вот эта останется невредимой, так как всего 9 пустых точек.
А вот этой не повезло — вокруг целых 14 пустых точек
А вот этой не повезло — вокруг целых 14 пустых точек
Краткое описание алгоритма: мы проходимся по всему полю и проверяем все точки на то, нужны они ли нет.
Далее мы просто добавляем в наш ground_generator такую строчку:
ground_libray.clear_caves(ref ground);Итог
Как мы видим — большая часть ненужных частичек просто ушло.
Добавим немного красок
Наша гора выглядит очень монотонно, я считаю это скучным.
Давайте добавим немного красок. Добавим метод level_paint в ground_libray:
Закрашивание горы
Я выбрал всего 3 цвета: Зеленый, темно-красный и темно-серый.
Вы, разумеется, можете изменить как количество цветов, так и значения каждого. У меня получилось так:
Но все же это выглядит слишком строго, чтобы добавить немного хаотичности цветам, мы напишем в ground_libray вот такое свойство:
В итоге у вас должно все выглядеть примерно так:
public static void level_paint(ref block[,] b, Color[] all_c)
{
for (int x = 0; x < b.GetLength(0); x++)
{
int lvl_div = -1;
int counter = 0;
int lvl_now = 0;
for (int y = b.GetLength(1) - 1; y > 0; y--)
{
if (b[x, y] != null && lvl_div == -1)
lvl_div = y / all_c.Length;
else if (b[x, y] == null)
continue;
b[x, y] = new block(all_c[lvl_now]);
lvl_now += counter >= lvl_div ? 1 : 0;
lvl_now = (lvl_now >= all_c.Length) ?
(all_c.Length - 1) : lvl_now;
counter = counter >= lvl_div ? 0 : (counter += 1);
}
}
}
</
<cut />source>
В параметры к методу мы передаем нашу гору и массив красок. Цвета будут использовать так, чтобы нулевой элемент массива красок был сверху, а последний снизу.
Мы проходимся по всем столбикам нашего поля, а обход по строчкам начинаем сверху. Найдя первую строчку с существующим элементом мы делим значение <b>Y </b>на количество цветов, чтобы поровну разделить цвета на столбик.
</spoiler>
После мы дописываем в <b>ground_generator </b>вот это:
<source lang="cs">
ground_libray.level_paint(ref ground,
new Color[3]
{
new Color(0.2f, 0.8f, 0),
new Color(0.6f, 0.2f, 0.05f),
new Color(0.2f, 0.2f, 0.2f),
});
Я выбрал всего 3 цвета: Зеленый, темно-красный и темно-серый.
Вы, разумеется, можете изменить как количество цветов, так и значения каждого. У меня получилось так:
Итог
Но все же это выглядит слишком строго, чтобы добавить немного хаотичности цветам, мы напишем в ground_libray вот такое свойство:
Случайные цвета
И теперь в методах level_paint и make_thick, в строчках, где мы присваиваем цвета, например в make_thick:
Мы напишем так:
А в level_paint
public static float color_randomize = 0.1f;
static float crnd
{
get
{
return Random.Range(1.0f - color_randomize,
1.0f + color_randomize);
}
}
И теперь в методах level_paint и make_thick, в строчках, где мы присваиваем цвета, например в make_thick:
b[x, y] = new block(o);Мы напишем так:
b[x, y] = new block(o * crnd);А в level_paint
b[x, y] = new block(all_c[lvl_now] * crnd);В итоге у вас должно все выглядеть примерно так:
Итог
Недостатки
Предположим, что у нас поле 1024 на 1024, нужно сгенерировать 24 пещеры, толщина края которых будет 4, а размер 80000.
1024 * 1024 + 24 * 64 * 80000 = 5 368 832 000 000 операций.
Этот способ подходит только для генерации небольших модулей для игрового мира, сгенерировать что-то очень большое за раз — нельзя.
Комментарии (14)
zigrus
09.07.2018 10:19сейчас работаю над батником который генерирует лабиринты
проблема с островками тоже есть
пока не придумал как с ними бороться
ваш вариант мне понравился, буду думать как это перевести в cmd
huckim
Пробовал у себя в игре подобное генерацию, но не алгоритмом Олдоса-Бродера, а клеточными автоматами. Пришлось отказаться от всей этой затеи, так как из-за такой случайной генерации персонаж не на все мог запрыгнуть. Сейчас генерирую пещеры очень простым, не совсем натурально выглядящим, но надежным способом. Кстати, нашлось ли какое-то элегантное решение избавления от всего «висящего в воздухе»?
wHDorld Автор
Да, я подробно описал это в разделе «Коррекция пещер». Можно установить порог не 13, а 12 или вызывать метод несколько раз — мелких висячих кусочков точно не будет. А если Вы об «островах», то можно через алгоритм поиска путей из любой точки острова попытаться дойти до, например, нижнего левого края карты (если не дойдем — это остров), так как он точно не висит в воздухе)
huckim
Спасибо! Кстати, ещё генерацию высот гор можно делать шумом Перлина — Mathf.PerlinNoise в Unity.
Igor_Sib
У Sebastian Lague описан способ сглаживания, по моему в этом видео, если нет — посмотри в других по этой же теме.
www.youtube.com/watch?v=v7yyZZjF1z4&frags=pl%2Cwn
huckim
Отличный канал с алгоритмами! Спасибо.