В какой ситуации удобен алгоритм
Недавно столкнулся с задачей: написать простую стратегию с трёхмерным ландшафтом. Так как я в данный момент обладаю маленьким опытом программирования на языке С++, мои попытки написать «diamond-square» закончились ошибками на ровном месте (ссылка на статью по «diamond-square» также будет в конце). Требовался простой в написании алгоритм, не дающий реалистичный ландшафт, так что данный метод поможет в первую очередь новичкам.
Алгоритм и результат
Прежде чем описывать сам алгоритм поделюсь его результатами:
Алгоритм заключается в том, что программа в случайных координатах заполняет карту прямоугольниками случайного размера. Карта имеет вид двухмерного массива, представляющего карту высот нашего ландшафта.
Для простоты создадим структуру прямоугольника:
struct tRect
{
int x1, y1, x2, y2;
}
Переменные x1 и y1 — левая нижняя координата прямоугольника, x2 и y2 — правая верхняя.
Пусть:
— Наша карта представлена в виде массива HM[mapsizex][mapsizey];
— mapsizey и mapsizex — переменные, определяющие размер вашей карты;
— genStep — переменная, отвечающая за количество наших прямоугольников;
— zscale — некий коэффициент растяжения карты в высоту. Можно заменить числом.
— recSizex и recSizey — пределы размеров прямоугольника.
Теперь необходимо заполнить нашу карту прямоугольниками:
for (int i=0; i<genStep; i++)
{
genRect.x1 = rand()%mapsizex;
genRect.y1 = rand()%mapsizey;
genRect.x2 = genRect.x1 + recSizex / 4 + rand()%recSizex;
genRect.y2 = genRect.y1 + recSizey / 4 + rand()%recSizey;
if (genRect.y2 > mapsizey) genRect.y2 = mapsizey;
if (genRect.x2 > mapsizex) genRect.x2 = mapsizex;
for (int i2 = genRect.x1; i2<genRect.x2; i2++)
for (int j2 = genRect.y1; j2<genRect.y2; j2++)
Map.HM[i2][j2]+= float(zscale) / float(genStep) + rand()%50 / 50.0;
}
Рельеф со скриншота был получен значениями:
genStep = 1024
zscale = 512
mapsizex и mapsizey = 128
recSize = 10
Далее вы выводите карту на экран любым доступным вам способом. В моём случае — openGl+glfw.
Преимущества и недостатки алгоритма
Преимущества:
- Простота и скорость в написании самого алгоритма
- Скорость исполнения алгоритма
Недостатки:
- Примитивность
- При маленьком шаге заполнения карты ландшафт становится «квадратным»
- Отсутствует возможность разбивать ландшафт на биомы по ходу генерации карты высот
Данный способ, как уже было сказано выше, подходит в первую очередь для новичков и людей, сильно ограниченных временем.
Надеюсь, данная статья была Вам полезной.
> Статья про генерацию игровых уровней
> Статья про «diamond-square»
Комментарии (38)
impwx
10.01.2017 15:13+1На скиншоте видно несколько участков, которые вообще не были затронуты обработкой.
Deathberry
11.01.2017 00:09Дело не в том, что они не затронуты. Если присмотреться — можно увидеть, что они немного приподняты. Причиной тому служит то, что коэффициент «поднятия» был слишком мал.
suharik
10.01.2017 15:15Можно увидеть еще один результат выполнения алгоритма? У вас на примере два «плоских» участка довольно большой площади, как сие получилось?
maaGames
10.01.2017 15:47+3rand() % XY
Это ответ на вопрос.suharik
10.01.2017 16:34+1Спасибо, ответ такой же загадочный, как и сам «алгоритм». Алгоритм в виде куска кода. Манускрипт Войнича для человека, который не знаком с С++. Вы что тут сделали, перемножили X и Y или это X с индексом Y?
maaGames
10.01.2017 16:40+3rand — не очень хороший алгоритм генерации псевдослучайных чисел в диапазоне 0-32768.
XY — разные иксы и игреки, которые использовались в формуле. В общем, это положительное целое число, не превышающее 32768 (превышать нет смысла)
% — оператор получения остатка от деления одного целого числа на другое
Т.е. берётся остаток от деления не очень хорошего случайного числа и 128. Если вы знакомы с программированием вообще (не С++), то в данном случае берутся младшие 7бит целого числа (при размере сетки 128 клеток). А младшие биты в псевдослучайных числах итак не сильно случайны, а тут и само число очень плохо случайно… Вот и получаем не очень хороший результат в итоге.
Другое дело, что даже с настоящим генератором случайных чисел визуально разницы могло и не быть, потому что это же всё случайно.)suharik
10.01.2017 17:01Теперь понял, спасибо. Наткнулся на одну не очень хорошую статью на cppstudio, там и запутался:
запись rand() % 3 в итоге выдаст число из диапазона от 0 до 2
. В итоге весь кусок кода прочел не так, как он работает.
marsermd
10.01.2017 17:24+2Так ведь rand() % 3 действительно выдаст число из диапазона от 0 до 2 (оба конца — включительно).
Остатки от деления на 3 могут быть: 0, 1, 2.
JIghtuse
10.01.2017 17:58Прикреплю-ка видео по теме <random>, может кто ещё не видел.
What C++ Programmers Need to Know about HeaderZenitchik
10.01.2017 17:10+3Результат работы — бессмысленный и беспощадный. Даже не соображу, какой естественный процесс мог бы породить такую местность. Наверно, можно использовать для «зашумления» рельефа, сгенеренного каким-то другим алгоритмом.
greabock
10.01.2017 20:30+6Статья о том, как заполнить матрицу псевдослучайными числами… в следующей статье автор будет описывать сортировку пузырьком… "подписывайтесь, ставьте лайки".
Я прекрасно понимаю, что нужны материалы разного уровня. Но это уже совсем уг.
evgenius123
11.01.2017 00:17Видел программу-скринсейвер для DOS, рисующую по точно такому же алгоритму разноцветную "плазму". Алгоритм, состоящий в заполнении поля случайными прямоугольниками, был заметен при замедлении работы программы, например, средствами DOSBox. Просто вместо высоты алгоритм генерировал порядковый номер оттенка из градиентной палитры.
TearOfTheStar
11.01.2017 00:21Если лень возиться с шумом Перлина, старый добрый Value Noise самое то, по сути просто добавить интерполяцию для сглаживания. А-то получился просто шум по сути.
Deathberry
11.01.2017 00:25Есть небольшая разница. Комментаторы выше заметили, что на ландшафте присутствуют плоские участки. Как по мне это скорее плюс, нежели минус, Value Noise не оставит такие «плоскости». Рассматривайте это как альтернативу, а не замену.
TearOfTheStar
11.01.2017 00:50Почему же не оставит, будут плоскости, шанс такой же случайный, но можно сглаживать определённые промежутки значений, если нужно, или ограничить сам диапазон изначально. А здесь, небольшие плоские промежутки, среди абсолютного шума, как это можно реально применит? Больше похоже на карту вулканического мира с очень большой высоты.
Deathberry
11.01.2017 02:29Оставит, только по углам они будут скруглены в пользу окружающих плоскость точек. В том и разница между алгоритмами — если делать обычный шум в один проход будет явно видно, что, например, если экстремумы задавались с шагом в 8 элементов в радиусе этих 8 элементов будет высматриваться одна и та же функция.
Как я уже говорил ранее — в моём случае это стратегия, правда ещё не дописанная. Кто-то в комментариях предлагал генерацию планет, я же этот алгоритм планирую прикрутить на генерацию астероидов. Также вполне сойдёт для клона 3х-мерной песочницы по типу minecraft.TearOfTheStar
11.01.2017 02:48Вот главный момент, который мне непонятен, как это использовать в стратегии? Если для генерации «пассивных» элементов окружения, тогда ладно, а если реальный игровой ландшафт, то как? Без, как минимум, разглаживающего прохода под потенциальные базы, или игровой механики, подобной Периметру, как на таком играть?
Deathberry
14.01.2017 22:41Если есть необходимость сделать построение — выравниваем кусок ландшафта, предположим, 4х4 игровых полигона и на нём делаем наше построение.
SadOcean
11.01.2017 00:26Видел похожий алгоритм для
планет
по смыслу то же самое, только делается произвольными разрезами.
А вообще всем интересующимся вот ресурс. Тема знатная и богатейшая, хотя и не простая.
A1essandro
11.01.2017 00:26Мне кажется, что при малых количествах шагов алгоритма, карта будет уж очень квадратной, что, собственно, и описано в минусах. А при больших количествах шагов — первое: тогда пропадает надобность в использовании алгоритма, если основной аргумент — скорость; второе — как я понимаю, высота будет скапливаться в нижнем правом углу карты (максимальные значения x и y). Т.е. клетки карты расположенные в этом углу будут обрабатываться чаще остальных.
Deathberry
11.01.2017 00:37Совершенно верно. Если, например, целью является terrain на 4000х4000 полигонов — алгоритм затянется, ни о какой генерации в реальном времени для всего участка уже можно и не говорить. Однако алгоритм хорошо подходит для сеток размерами от 32х32 до 512х512.
Что касательно второй проблемы — на практике данной проблемы при размерах более 32х32 не возникнет. Если же есть необходимость оставить края карты пологими можно ограничить площадь, на которой генерируются квадраты.
Antervis
11.01.2017 05:55я может не прав, но вся идея генерации ландшафта не в том, чтобы получить что-то случайное, а в том, чтобы получить рельеф, удовлетворяющий заранее установленным требованиям. Аля «тут — непроходимые горы, а тут — почти плоская поляна»
suharik
12.01.2017 14:50Это все должно в алгоритме описываться, так ведь? Есть у нас на участке две горы, значит хватит. А глубина озера не более 25 единиц. И чтоб поля были, три штуки — малое, среднее и очень среднее. А вот расположение уже рандомное, иначе у вас просто отрисовка заведомо определенного ландшафта. Генерация неслучайных величин вообще бывает?
Antervis
13.01.2017 04:45я немного не про то. В общем случае, например, нас мало интересуют поляны, полностью окруженные горами
MrGobus
12.01.2017 15:17+1О автор открыл для себя рандом. Поздравляю =)
Вторым шагом можно попробовать blur. Идея в следующем, значение высоты равно (v[x+1,y] + v[x-1,y] + v[x,y+1] + v[x,y-1] + v[x,y] * 4) / 8. Если пробларить раза четыре получатся неплохие холмы =)
ex_Prizrak
14.01.2017 22:38Неплохо. А можно узнать подробнее про вашу трехмерную стратегию?
Deathberry
14.01.2017 22:39Безусловно)
В данный момент стратегия находится в начальной стадии разработки, т.к. к сроку сдачи я не успел. А началась разработка с того, что преподаватель в универе предложил написать стратегию используя OpenGl.
staticlab
Почему же не классическим для этой задачи шумом Перлина?
Deathberry
Шум Перлина для новичка будет сложнее в написании, даже по сравнению с «diamond-square», и даёт результат, схожий с последним. Алгоритм из статьи хорошо подходит для генерации ландшафта, например, в стратегиях.
agasper
Но зачем его писать, если пример его реализации уже есть практически во всех современных языках программирования?
Tujh
staticlab
Понимаете, новичку на самом деле всё равно, что копипастить: ваш код или реализацию шума Перлина. Или вы думаете, что он, прочитав статью, будет реализовывать ваш алгоритм самостоятельно?
Ogi
Ещё можно наложить друг на друга несколько разночастотных шумов, как описано в статье, в которой этот метод по ошибке назван шумом Перлина. Тоже даёт схожий результат, но пишется совсем просто.
Tujh
Тогда уж лучше сразу книгу рекомендовать
aikixd
Шумы очень простая штука. Пару недель назад, за день написал демку. Там всего две функции.