Немного о графиках, сплайнах и генерации ландшафта

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

Прежде чем перейти к статье, хочу вам представить, экономическую онлайн игру Brave Knights, в которой вы можете играть и зарабатывать. Регистируйтесь, играйте и зарабатывайте!

Всем привет! Недавно я решил написать свой алгоритм генерации ландшафта для своих игр на игровом движке Unity 3D. На самом деле мой алгоритм вполне подойдет и для любых других движков и не только движков, так как использует только чистый C#. Делать это с помощью шума мне показалось неинтересным, и я решил реализовать все с помощью интерполяции. Конечно все скажут зачем изобретать велосипед, но это еще и хорошая практика, а в жизни пригодится все. Если вам не понравится моя реализация через интерполяцию, я в конце напишу алгоритм для генерации с помощью шума Перлина(Perlin Noise). Итак, приступим.

1.      Кривые Безье.

Первый способ реализации я решил сделать через формулу кривых Безье. Формула для n-го количества точек в пространстве:

, где B – базисные функции кривой Безье, по-другому – полиномы Бернштейна. Их формула -

.[1]

Реализовать это в коде совсем просто, так что приступим.

1)      Создадим структуру Point, которая будет иметь два параметра – координаты x и y и переопределим для него некоторые операторы(+,-,*,/).

[Serializable]

public struct Point

    {

        public float x, y;

        public Point(float x, float y)

        {

            this.x = x;

            this.y = y;

        }

        public static Point operator +(Point a, Point b) => new Point(a.x + b.x, a.y + b.x);

        public static Point operator -(Point a, float d) => new Point(a.x - d, a.y - d);

        public static Point operator -(Point a, Point b) => new Point(a.x - b.x, a.y - b.y);

        public static Point operator *(float d, Point a) => new Point(a.x * d, a.y * d);

        public static Point operator *(Point a, float d) => new Point(a.x * d, a.y * d);

        public static Point operator *(Point a, Point b) => new Point(a.x * b.x, a.x * b.y);

        public static Point operator /(Point a, float d) => new Point(a.x / d, a.y / d);

        public static Point operator /(Point a, Point b) => new Point(a.x / b.x, a.y / b.y);

        public static bool operator ==(Point lhs, Point rhs) => lhs.x == rhs.x && lhs.y == rhs.y;

        public static bool operator !=(Point lhs, Point rhs) => lhs.x != rhs.x || lhs.y != rhs.y;

    }

2)      Давайте теперь напишем сам метод для получения точки по параметру t. Еще нам нужно будет создать функцию для вычисления факториала.

int factorial(int n)

        {

            int f = 1;

            for (int i = 1; i < n; i++)

            {

                f *= i;

            }

            return f;

        }

 

        Point curveBezier(Point[] points, float t)

        {

            Point curve = new Point(0, 0);

            for (int i = 0; i < points.Length; i++)

                curve += points[i] * factorial(points.Length - 1) / (factorial(i) * factorial(points.Length - 1 - i)) * (float)Math.Pow(t, i) * (float)Math.Pow(1 - t, points.Length - 1 - i);

            return curve;

        }

Теперь возникает проблемка, если наши точки будут расположены не через одинаковый шаг, то значения будут получаться некорректно. Теперь нам нужно реализовать метод, который будет находить значение t для нашей функции, которое соответствует нужному x. Для этого я решил воспользоваться методом Ньютона, с помощью которого можно найти корни функции.[2] Для этого нам нужно найти производную для нашей функции Безье. Делается это очень просто, так как каждый член преобразуется из c_n * x ^ n в c_n * n * x ^ (n-1). Член с нулевой степенью пропадает.

3)      Теперь реализуем получение производной.

Point derivative(Point[] points, float t)

        {

            Point curve = new Point(0, 0);

            for (int i = 0; i < points.Length; i++)

            {

                Point c = points[i] * factorial(points.Length - 1) / (factorial(i) * factorial(points.Length - 1 - i));

                if (i > 1)

                {

                    curve += c * i * (float)Math.Pow(t, i - 1) * (float)Math.Pow(1 - t, points.Length - 1 - i);

                }

                if (points.Length - 1 - i > 1)

                {

                    curve -= c * (float)Math.Pow(t, i) * (points.Length - 1 - i) * (float)Math.Pow(1 - t, points.Length - 2 - i);

                }

            }

            return curve;

        }

4)      А так же получение параметра t по методу Ньютона.

float timeBezier(Point[] points, float x, float e = 0.0001f)

        {

            float t = 0.5f;

            float h = (curveBezier(points, t).x - x) / (derivative(points, t).x - 1);

            while (Math.Abs(h) >= e)

            {

                h = (curveBezier(points, t).x - x) / (derivative(points, t).x - 1);

                t -= h;

            }

            return t;

        }

В итоге у нас готовы все функции для построения кривой Безье с равномерным шагом. Для генерации лучше использовать шаг по оси x, а y мы будем получать. Давайте напишем код который будет генерировать ландшафт, пока что только по одной из осей. Этот код полностью подойдет только для движка Unity, в остальных нужно немного его изменить.

public Point[] points;

public GameObject prefab;

public int length;

private void Start()

    {

        for(int i = 0; i < length; i++)

        {

            GameObject block = Instantiate(prefab) as GameObject;

            float t = timeBezier(points, points[0] + (points[points.Length-1].x – points[0].x) * i / length);

            block.name = i.ToString();

            block.transform.parent = transform;

            block.transform.position = transform.position + new Vector3(curveBezier(points, t).x, curveBezier(points, t).y, 0);

        }

    }

Осталось сделать такую же генерацию по оси z и потом вычислять не для x, а для обоих осей.

public Point[] px, pz;

public GameObject prefab;

public int length;

private void Start()

{

               for(int i = 0; i < length; i++)

       {

   for(int j = 0; j < length; j++)

   {

             GameObject block = Instantiate(prefab) as GameObject; 

             float tx = timeBezier(points, px[0] + (px[px.Length-1].x – px[0].x) * i / length); 

             float tz = timeBezier(points, pz[0] + (pz[pz.Length-1].x – pz[0].x) * i / length);

             block.name = i.ToString() + “ “ + j.ToString();

             block.transform.parent = transform;

             block.transform.position = transform.position + new Vector3(curveBezier(px, tx).x, (curveBezier(px, tx).y + curveBezier(pz, tz).y), curveBezier(pz, tz).x);

                  }

       }

}

Итак, теперь у нас готов простой генератор, который создает ровный ландшафт по заданным точкам. Еще можно написать функцию для генерирования рандомных точек, а генерировать их в зависимости от сида, для этого легко использовать класс Random() из пространства имен System. Главное при создании этого класса не забыть в скобках написать сид, иначе будет рандомные значения, а не определенные. Самое лучшее – пользоваться методом NextDouble(), просто преобразуя его в float, тогда у вас все значения будут в диапазоне от 0 до 1 включительно.

2.      Сплайн Лагранжа
Давайте теперь попробуем реализовать генерацию ландшафта с помощью сплайна Лагранжа[3]. Его формулу еще легче реализовать, так как там в качестве параметра выступает x, а не t.

1) Напишем функцию которая будет получать позицию по x и y по одному x.

Point curveLagrange(Point points, float x) {    Vector2 curve = new Vector2(x, 0);

         for(int i = 0; i < points.Length; i++)

         {

            float dx = points[i].y;

            for (int k = 0; k < points.Length; k++)

               if (k != i)

                  dx *= (x - points[k].x) / (points[i].x - points[k].x);

            curve.y += dx;

         }

         return curve;       }

      2) Осталось в методе Start() заменить код на немного другой.

for(int i = 0; i < length; i++)

         {

            GameObject block = Instantiate(prefab) as GameObject;

            block.name = i.ToString();

            block.transform.parent = transform;

            block.transform.position = transform.position + new Vector3(curveLagrange(points, points[0].x + (points[points.Length - 1].x - points[0].x) * (float)i / (float)(length - 1)).x, curveLagrange(points, points[0].x + (points[points.Length - 1].x - points[0].x) * (float)i / (float)(length - 1)).y);

         }

      Для генерации по двум осям нужно проделать все то же самое, что и с кривыми Безье.

Теперь я покажу как генерировать ландшафт с помощью шума Перлина(только для Unity).

for(int i = 0; i < size_x; i++)

{

   for(int j = 0; j < size_z; j++)

   {

      GameObject block = Instantiate(prefab) as GameObject;

      block.transform.parent = transform;

      block.transform.position = transform.position + new Vector3(i, Mathf.PerlinNoise(i, j), j);

   }

}

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

Ссылки:

[1] – https://en.wikipedia.org/wiki/B%C3%A9zier_curve

[2] – https://en.wikipedia.org/wiki/Newton%27s_method

[3] – https://en.wikipedia.org/wiki/Lagrange_polynomial

Источник: https://habr.com/ru/post/554484/


Интересные статьи

Интересные статьи

Цель данной статьи - объяснить логику работы радиуса в примерах, избавить от боязни и иллюзии сложности использования. Читать далее
Привет, меня зовут Александр, я тимлид команды разработки трекинговых решений компании Admitad. Почти всегда на собеседованиях мне задают вопросы, чем занимается команда, какие у нас про...
О популярной библиотеке SQLAlchemy для работы с разными СУБД из Python было написано довольно много статей. Предлагаю вашему вниманию обзор и сравнение запросов с использованием ORM и SQL...
Каждый лишний элемент на сайте — это кнопка «Не купить», каждая непонятность или трудность, с которой сталкивается клиент — это крестик, закрывающий в браузере вкладку с вашим интернет-магазином.
Эта статья посвящена одному из способов сделать в 1с-Битрикс форму в всплывающем окне. Достоинства метода: - можно использовать любые формы 1с-Битрикс, которые выводятся компонентом. Например, добавле...