26.04.2021 13:26
M3r1al 4 2300 Источник

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