Olá a todos! Recentemente, decidi escrever meu próprio algoritmo de geração de terreno para meus jogos no mecanismo de jogo Unity 3D. Na verdade, meu algoritmo é bastante adequado para quaisquer outros motores e não apenas motores, uma vez que usa apenas C # puro. Fazer isso com a ajuda do ruído me pareceu desinteressante, e decidi implementar tudo por interpolação. Claro, todos dirão por que reinventar a roda, mas também é uma boa prática e tudo será útil na vida. Se você não gosta da minha implementação por interpolação, vou escrever um algoritmo para gerar com Perlin Noise no final. Então vamos começar.
1. Curvas de Bézier.
Resolvi fazer a primeira forma de implementação através da fórmula das curvas de Bezier. Fórmula para o n-ésimo número de pontos no espaço:
, onde B - funções básicas da curva de Bezier, ou seja - polinômios de Bernstein. A fórmula deles é
... [1]
É fácil codificar isso, então vamos começar.
1) Vamos criar uma estrutura Point, que terá dois parâmetros - coordenadas xey e redefinir alguns operadores (+, -, *, /) para ela.
[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) Vamos agora escrever o próprio método para obter o ponto pelo parâmetro t. Também precisaremos criar uma função para calcular o fatorial.
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