Hello everyone! Recently I decided to write my own terrain generation algorithm for my games on the Unity 3D game engine. In fact, my algorithm is quite suitable for any other engines and not only engines, since it uses only pure C #. To do this with the help of noise seemed to me uninteresting, and I decided to implement everything using interpolation. Of course, everyone will say why to reinvent the wheel, but it's also a good practice, and everything will come in handy in life. If you don't like my implementation through interpolation, I will write an algorithm for generating with Perlin Noise at the end. So let's get started.
1. Bezier curves.
I decided to do the first way of implementation through the formula of Bezier curves. Formula for the n-th number of points in space:
, where B - basic functions of the Bezier curve, in other words - Bernstein polynomials. Their formula is
... [one]
It's easy to code this, so let's get started.
1) Let's create a Point structure that will have two parameters - coordinates x and y and redefine some operators (+, -, *, /) for it.
[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) Let's now write the method itself for getting the point by the parameter t. We will also need to create a function to calculate the 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