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