¡Hola a todos! Recientemente decidí escribir mi propio algoritmo de generación de terreno para mis juegos en el motor de juegos Unity 3D. De hecho, mi algoritmo es bastante adecuado para cualquier otro motor y no solo para motores, ya que usa solo C # puro. Hacer esto con la ayuda del ruido me pareció poco interesante y decidí implementar todo usando la interpolación. Por supuesto, todos dirán por qué reinventar la rueda, pero también es una buena práctica, y todo será útil en la vida. Si no le gusta mi implementación a través de la interpolación, escribiré un algoritmo para generar con Perlin Noise al final. Entonces empecemos.
1. Curvas de Bézier.
Decidí hacer la primera forma de implementación a través de la fórmula de curvas de Bezier. Fórmula para el n-ésimo número de puntos en el espacio:
, donde B - funciones básicas de la curva de Bezier, en otras palabras - polinomios de Bernstein. Su fórmula es
... [uno]
Es fácil codificar esto, así que comencemos.
1) Creemos una estructura de puntos, que tendrá dos parámetros: las coordenadas xey y redefiniremos algunos operadores (+, -, *, /) para ello.
[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) Escribamos ahora el método en sí para obtener el punto mediante el parámetro t. También necesitaremos crear una función para calcular el factorial.
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