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

Автор Сообщение
news_bot ®

Стаж: 6 лет 9 месяцев
Сообщений: 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
Профиль  ЛС 
Показать сообщения:     

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

Текущее время: 22-Ноя 14:51
Часовой пояс: UTC + 5