[Программирование, C#, Unity] Немного о графиках, сплайнах и генерации ландшафта
Автор
Сообщение
news_bot ®
Стаж: 6 лет 9 месяцев
Сообщений: 27286
Всем привет! Недавно я решил написать свой алгоритм генерации ландшафта для своих игр на игровом движке 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
===========
Источник:
habr.com
===========
Похожие новости:
- [Программирование, Проектирование и рефакторинг] Чистая архитектура. Часть II — Парадигмы программирования
- [Программирование, Алгоритмы, Математика] Вебинар от Яндекс.Практикума «Конечные автоматы в реальной жизни»: теория, кодинг и Q&A за один вечер
- [Занимательные задачки, Программирование, Алгоритмы, Node.JS, VueJS] Создаем кэшируемую пагинацию, которая не боится неожиданного добавления данных в БД
- [PHP, Программирование, Тестирование веб-сервисов] Работа с частичными моками в PHPUnit 10
- [Программирование микроконтроллеров, Умный дом, Интернет вещей, DIY или Сделай сам, Электроника для начинающих] Рожденные в карантине: беспроводной датчик и все-все-все. Битва роботов в конце
- [Программирование, C++, Промышленное программирование] Современный C++ нас не спасет (перевод)
- [Ненормальное программирование, Программирование, Go, Дизайн] Go Rant
- [Программирование, Java] Избавляемся от мусора в Java (перевод)
- [Тестирование IT-систем, PHP, Программирование] Практики при работе с PHPUnit
- [.NET, ASP, C#] 6 вещей, которые не стоит делать в ASP.NET контроллерах
Теги для поиска: #_programmirovanie (Программирование), #_c#, #_unity, #_c#, #_unity, #_algoritmy (алгоритмы), #_matematika (математика), #_programmirovanie (
Программирование
), #_c#, #_unity
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 22-Ноя 14:51
Часовой пояс: UTC + 5
Автор | Сообщение |
---|---|
news_bot ®
Стаж: 6 лет 9 месяцев |
|
Всем привет! Недавно я решил написать свой алгоритм генерации ландшафта для своих игр на игровом движке 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; } 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; } 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; } 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; } 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); } } 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); } } } Давайте теперь попробуем реализовать генерацию ландшафта с помощью сплайна Лагранжа[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; } 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); } 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); } } =========== Источник: habr.com =========== Похожие новости:
Программирование ), #_c#, #_unity |
|
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 22-Ноя 14:51
Часовой пояс: UTC + 5