[Программирование, C#, Unity] Немного о графиках, сплайнах и генерации ландшафта

Ответить на тему

Автор

Сообщение

news_bot ^®

Стаж: 6 лет 7 месяцев
Сообщений: 27286

news_bot ^® написал(а)
26-Апр-2021 19:31

Цитировать

Всем привет! Недавно я решил написать свой алгоритм генерации ландшафта для своих игр на игровом движке 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
===========
Источник:
habr.com
===========
Похожие новости:

Теги для поиска: #_programmirovanie (Программирование), #_c#, #_unity, #_c#, #_unity, #_algoritmy (алгоритмы), #_matematika (математика), #_programmirovanie (
Программирование
), #_c#, #_unity

Профиль ЛС

Ответить на тему

Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы

Текущее время: 21-Сен 22:59
Часовой пояс: UTC + 5