Простой и быстрый алгоритм генерации ландшафта

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

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

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

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

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

image

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

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

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»
Share post
AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 38

    +11

    Почему же не классическим для этой задачи шумом Перлина?

      +1
      Шум Перлина для новичка будет сложнее в написании, даже по сравнению с «diamond-square», и даёт результат, схожий с последним. Алгоритм из статьи хорошо подходит для генерации ландшафта, например, в стратегиях.
        0
        Но зачем его писать, если пример его реализации уже есть практически во всех современных языках программирования?
          0
          Алгоритм из статьи хорошо подходит для генерации ландшафта, например, в стратегиях.
          Хотелось бы посмотреть на то, сколько ресурсов съест поиск маршрута на такой карте и какие выдаст результаты…
            0

            Понимаете, новичку на самом деле всё равно, что копипастить: ваш код или реализацию шума Перлина. Или вы думаете, что он, прочитав статью, будет реализовывать ваш алгоритм самостоятельно?

              0

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

                0
                Тогда уж лучше сразу книгу рекомендовать
                Грег Снук
                3D-ландшафты в реальном времени на C++ и DirectX 9
                +1

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

              +1
              На скиншоте видно несколько участков, которые вообще не были затронуты обработкой.
                0
                Дело не в том, что они не затронуты. Если присмотреться — можно увидеть, что они немного приподняты. Причиной тому служит то, что коэффициент «поднятия» был слишком мал.
              • UFO just landed and posted this here
                  +3
                  rand() % XY
                  Это ответ на вопрос.
                  • UFO just landed and posted this here
                      +3
                      rand — не очень хороший алгоритм генерации псевдослучайных чисел в диапазоне 0-32768.
                      XY — разные иксы и игреки, которые использовались в формуле. В общем, это положительное целое число, не превышающее 32768 (превышать нет смысла)
                      % — оператор получения остатка от деления одного целого числа на другое

                      Т.е. берётся остаток от деления не очень хорошего случайного числа и 128. Если вы знакомы с программированием вообще (не С++), то в данном случае берутся младшие 7бит целого числа (при размере сетки 128 клеток). А младшие биты в псевдослучайных числах итак не сильно случайны, а тут и само число очень плохо случайно… Вот и получаем не очень хороший результат в итоге.
                      Другое дело, что даже с настоящим генератором случайных чисел визуально разницы могло и не быть, потому что это же всё случайно.)
                      • UFO just landed and posted this here
                          +2
                          Так ведь rand() % 3 действительно выдаст число из диапазона от 0 до 2 (оба конца — включительно).
                          Остатки от деления на 3 могут быть: 0, 1, 2.
                      0

                      Прикреплю-ка видео по теме <random>, может кто ещё не видел.


                      What C++ Programmers Need to Know about Header <random>

                      Уже практически 6 лет стандарту C++11, а повсюду всё тот же rand()… Вот недавно на Coursera встретился, на новом курсе по алгоритмам.

                    +3
                    Результат работы — бессмысленный и беспощадный. Даже не соображу, какой естественный процесс мог бы породить такую местность. Наверно, можно использовать для «зашумления» рельефа, сгенеренного каким-то другим алгоритмом.
                      +6

                      Статья о том, как заполнить матрицу псевдослучайными числами… в следующей статье автор будет описывать сортировку пузырьком… "подписывайтесь, ставьте лайки".
                      Я прекрасно понимаю, что нужны материалы разного уровня. Но это уже совсем уг.

                        0
                        Возможно глупый вопрос, но в чем визуализация делалась? OpenGL?
                          0
                          GLFW + OpenGl
                            0
                            Спасибо!
                          0

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

                            0
                            Если лень возиться с шумом Перлина, старый добрый Value Noise самое то, по сути просто добавить интерполяцию для сглаживания. А-то получился просто шум по сути.
                              0
                              Есть небольшая разница. Комментаторы выше заметили, что на ландшафте присутствуют плоские участки. Как по мне это скорее плюс, нежели минус, Value Noise не оставит такие «плоскости». Рассматривайте это как альтернативу, а не замену.
                                0
                                Почему же не оставит, будут плоскости, шанс такой же случайный, но можно сглаживать определённые промежутки значений, если нужно, или ограничить сам диапазон изначально. А здесь, небольшие плоские промежутки, среди абсолютного шума, как это можно реально применит? Больше похоже на карту вулканического мира с очень большой высоты.
                                  0
                                  Оставит, только по углам они будут скруглены в пользу окружающих плоскость точек. В том и разница между алгоритмами — если делать обычный шум в один проход будет явно видно, что, например, если экстремумы задавались с шагом в 8 элементов в радиусе этих 8 элементов будет высматриваться одна и та же функция.
                                  Как я уже говорил ранее — в моём случае это стратегия, правда ещё не дописанная. Кто-то в комментариях предлагал генерацию планет, я же этот алгоритм планирую прикрутить на генерацию астероидов. Также вполне сойдёт для клона 3х-мерной песочницы по типу minecraft.
                                    0
                                    Вот главный момент, который мне непонятен, как это использовать в стратегии? Если для генерации «пассивных» элементов окружения, тогда ладно, а если реальный игровой ландшафт, то как? Без, как минимум, разглаживающего прохода под потенциальные базы, или игровой механики, подобной Периметру, как на таком играть?
                                      0
                                      Если есть необходимость сделать построение — выравниваем кусок ландшафта, предположим, 4х4 игровых полигона и на нём делаем наше построение.
                              0
                              Видел похожий алгоритм для
                              планет
                              по смыслу то же самое, только делается произвольными разрезами.

                              А вообще всем интересующимся вот ресурс. Тема знатная и богатейшая, хотя и не простая.
                                0
                                Мне кажется, что при малых количествах шагов алгоритма, карта будет уж очень квадратной, что, собственно, и описано в минусах. А при больших количествах шагов — первое: тогда пропадает надобность в использовании алгоритма, если основной аргумент — скорость; второе — как я понимаю, высота будет скапливаться в нижнем правом углу карты (максимальные значения x и y). Т.е. клетки карты расположенные в этом углу будут обрабатываться чаще остальных.
                                  0
                                  Совершенно верно. Если, например, целью является terrain на 4000х4000 полигонов — алгоритм затянется, ни о какой генерации в реальном времени для всего участка уже можно и не говорить. Однако алгоритм хорошо подходит для сеток размерами от 32х32 до 512х512.
                                  Что касательно второй проблемы — на практике данной проблемы при размерах более 32х32 не возникнет. Если же есть необходимость оставить края карты пологими можно ограничить площадь, на которой генерируются квадраты.
                                  0
                                  я может не прав, но вся идея генерации ландшафта не в том, чтобы получить что-то случайное, а в том, чтобы получить рельеф, удовлетворяющий заранее установленным требованиям. Аля «тут — непроходимые горы, а тут — почти плоская поляна»
                                  • UFO just landed and posted this here
                                      0
                                      я немного не про то. В общем случае, например, нас мало интересуют поляны, полностью окруженные горами
                                    +1
                                    О автор открыл для себя рандом. Поздравляю =)
                                    Вторым шагом можно попробовать blur. Идея в следующем, значение высоты равно (v[x+1,y] + v[x-1,y] + v[x,y+1] + v[x,y-1] + v[x,y] * 4) / 8. Если пробларить раза четыре получатся неплохие холмы =)
                                      0
                                      Неплохо. А можно узнать подробнее про вашу трехмерную стратегию?
                                        0
                                        Безусловно)
                                        В данный момент стратегия находится в начальной стадии разработки, т.к. к сроку сдачи я не успел. А началась разработка с того, что преподаватель в универе предложил написать стратегию используя OpenGl.

                                      Only users with full accounts can post comments. Log in, please.