Комментарии 17
Шах и мат, велосипедоманы
Отличный материал. И переводчик молодец. Но вот зачем сайт с примером кода пытается читать личный сертификат — не очень понятно.
Надеюсь, оригинальный сайт не ляжет под Хабраэффектом...
Читал еще когда оригинал появился. Но как то показалось сложным. В общем обошелся шумом Перлина без каких либо сложных дополнений и распределений.
www.youtube.com/watch?v=_tKAjC7pAjU
www.youtube.com/watch?v=_tKAjC7pAjU
Да, шум Перлина тоже неплохо справляется с задачей изначальной генерации. Но представьте, что нужно динамическое изменение ландшафта на протяжении длительного периода времени — в результате тектонической активности, например. А тут есть литосферные плиты, воздушные потоки — можно пересчитывать биомы на лету, и это, скорее всего, придаст миру большее правдоподобие.
Мне кажется это как с генерацией эрозии — можно моделировать эффект текущей капли, по миллион каплей, на каждую миллион итераций. А можно получить тот же эффект с помощью воронова за конечных 9 итераций на высоту.
Алгоритмы с адекватной вычислительной сложностью — это круто.
Но тут автор тоже представил алгоритмы, в целом, приемлемой трудоемкости. И их отличие в том, что они оперируют исходными данными — кинетикой плит, воздушных масс и т.п.
Такая модель может быть актуальна для игр определенных жанров, где ландшафт является не статической, а динамической составляющей игры.
Простой пример — взрыв ядерной бомбы в игровом мире — применяя соответствующую модель можно правдоподобно рассчитать изменение климата, пути распространения радиоактивных осадков, зоны возникновения цунами. Это возможно потому, что в модели заложены параметры, исходя из которых и строится весь ландшафт.
Только вот вся проблема в том что там куча кода, который надо перелопатить и прочитать, чтобы найти интересующую деталь. В то время, как тем же вороновым, можно сделать два цикла и получу тот же результат что и у автора. А вот в самой статье ни строчки кода, только восхищения о том что его понадобилось на абзац текста очень мало.
Кстати вороновым можно сгенерить весь результат автора за кадр, а у него куча прогрессбаров прежде чем все построиться. Возможно на java это не так быстро, но вот повествование статьи слишком литературное, не научное. generateSubdividedIcosahedron — меня просто бросил в ужас. Все то что там есть можно представить следующим кодом, притом что Polygonize это корень вычисления где сразу можно понять логику и простоту расчетов.
И тут даже нет сложных контейнеров, только стандартные массивы.
Данная не равномерная сетка укладывается в массив 12x12, тут ровно 144 ячейки, которые изначально были банальной квадратной регулярной сеткой. Которые далее могут тайлиться с другими сегментами подобной сетки.
Кстати вороновым можно сгенерить весь результат автора за кадр, а у него куча прогрессбаров прежде чем все построиться. Возможно на java это не так быстро, но вот повествование статьи слишком литературное, не научное. generateSubdividedIcosahedron — меня просто бросил в ужас. Все то что там есть можно представить следующим кодом, притом что Polygonize это корень вычисления где сразу можно понять логику и простоту расчетов.
методы
public static Vector2 CellPoint(int x, int y, int seed, float range)
{
return new Vector2((LowPolyGenerator.rndf(x + y * 1000 + seed) - 0.5f) * range, (LowPolyGenerator.rndf(x * 1000 + y + 1 + seed) - 0.5f) * range);
}
public static Vector2[] CellsPoints(int fromx, int fromy, int divide, int seed, float range)
{
int qrc = divide > 1 ? divide : 1;
Vector2[] arr = new Vector2[(qrc + 2) * (qrc + 2) * 2];
int i = 0;
fromx *= qrc;
fromy *= qrc;
for (int y = - 1; y < qrc + 1; y++)
for (int x = -1; x < qrc + 1; x++)
{
Vector2 p = new Vector2(x, y);
arr[i] = p + CellPoint(x + fromx, y + fromy, seed, range);
arr[i + 1] = p + CellPoint(x + fromx, y + fromy, seed + 1, range) + Vector2.one * 0.5f;
i += 2;
}
return arr;
}
public void Polygonize(Vector2[] arr, int divide, out Vector2[] nvec, out int[][] polys)
{
List<int[]> polysrez = new List<int[]>();
List<Vector2> vecrez = new List<Vector2>();
Dictionary<Vector2, int> vechash = new Dictionary<Vector2, int>();
int qrc = divide > 1 ? divide : 1;
int str = (qrc + 2) * 2;
int i = str;
List<int> poly = new List<int>();
for (int y = 0; y < qrc; y++)
{
i += 2;
for (int x = 0; x < qrc; x++)
{
AddPolyVecs(poly, vechash, vecrez, ref arr[i], ref arr[i - str - 1], ref arr[i - str], ref arr[i - str + 1]);
AddPolyVecs(poly, vechash, vecrez, ref arr[i], ref arr[i - str + 1], ref arr[i + 2], ref arr[i + 1]);
AddPolyVecs(poly, vechash, vecrez, ref arr[i], ref arr[i + 1], ref arr[i + str], ref arr[i - 1]);
AddPolyVecs(poly, vechash, vecrez, ref arr[i], ref arr[i - 1], ref arr[i - 2], ref arr[i - str - 1]);
polysrez.Add(poly.ToArray());
poly.Clear();
i++;
AddEPolyVecs(poly, vechash, vecrez, ref arr[i], ref arr[i - 1], ref arr[i - str], ref arr[i + 1]);
AddEPolyVecs(poly, vechash, vecrez, ref arr[i], ref arr[i + 1], ref arr[i + 2], ref arr[i + str + 1]);
AddEPolyVecs(poly, vechash, vecrez, ref arr[i], ref arr[i + str + 1], ref arr[i + str], ref arr[i + str - 1]);
AddEPolyVecs(poly, vechash, vecrez, ref arr[i], ref arr[i + str - 1], ref arr[i - 2], ref arr[i - 1]);
polysrez.Add(poly.ToArray());
poly.Clear();
i++;
}
i += 2;
}
polys = polysrez.ToArray();
nvec = vecrez.ToArray();
}
static void CheckAndAddPolyVec(List<int> poly, Dictionary<Vector2, int> vechash, List<Vector2> vecrez, ref Vector2 a)
{
if (vechash.ContainsKey(a))
{
poly.Add(vechash[a]);
}
else
{
int id = vecrez.Count;
vechash.Add(a, id);
vecrez.Add(a);
poly.Add(id);
}
}
static void AddPolyVecs(List<int> poly, Dictionary<Vector2, int> vechash, List<Vector2> vecrez, ref Vector2 c1, ref Vector2 c2, ref Vector2 c3, ref Vector2 c4)
{
if (Vector2.SqrMagnitude(c1 - c3) < Vector2.SqrMagnitude(c2 - c4))
{
Vector2 a1 = (c1 + c2 + c3) * 0.333333f;
Vector2 a2 = (c1 + c4 + c3) * 0.333333f;
CheckAndAddPolyVec(poly, vechash, vecrez, ref a1);
CheckAndAddPolyVec(poly, vechash, vecrez, ref a2);
}
else
{
Vector2 a = (c1 + c2 + c4) * 0.333333f;
CheckAndAddPolyVec(poly, vechash, vecrez, ref a);
}
}
static void AddEPolyVecs(List<int> poly, Dictionary<Vector2, int> vechash, List<Vector2> vecrez, ref Vector2 c1, ref Vector2 c2, ref Vector2 c3, ref Vector2 c4)
{
if (Vector2.SqrMagnitude(c1 - c3) <= Vector2.SqrMagnitude(c2 - c4))
{
Vector2 a1 = (c1 + c2 + c3) * 0.333333f;
Vector2 a2 = (c1 + c4 + c3) * 0.333333f;
CheckAndAddPolyVec(poly, vechash, vecrez, ref a1);
CheckAndAddPolyVec(poly, vechash, vecrez, ref a2);
}
else
{
Vector2 a = (c1 + c2 + c4) * 0.333333f;
CheckAndAddPolyVec(poly, vechash, vecrez, ref a);
}
}Пример использования
Vector2[] arr = CellsPoints(Position.x, Position.y, Divide, Seed, Offset);
Gizmos.color = Color.gray;
Vector2[] nvec;
int[][] polys;
Polygonize(arr, Divide, out nvec, out polys);
for (int i = 0; i < polys.Length; i++)
for (int j = 0; j < polys[i].Length; j++)
{
int id1 = polys[i][j];
int id2 = (j == polys[i].Length - 1) ? polys[i][0] : polys[i][j + 1];
Gizmos.DrawLine(new Vector3(nvec[id1].x * scale, 0.0f, nvec[id1].y * scale), new Vector3(nvec[id2].x * scale, 0.0f, nvec[id2].y * scale));
}
И тут даже нет сложных контейнеров, только стандартные массивы.
изображение
Данная не равномерная сетка укладывается в массив 12x12, тут ровно 144 ячейки, которые изначально были банальной квадратной регулярной сеткой. Которые далее могут тайлиться с другими сегментами подобной сетки.
Автор пробовал применить генерацию сетки с помощью Воронового. Как уже описано в статье, то что подходит для евклидовой геометрии, не подходит для геометрии Римана.
Там все очень хорошо подходит. Весь воронов на случайных числах сводиться к добавлению случайной величины — смещения вершин, без разницы на какой поверхности. И последующая проверка ближайших точек, соответствующий поворот граней к ближайшим двум вершинам. Это весь алгоритм и он прекрасно ложиться на сферу, разница лишь в том что тут для каждой вершины икосаэдра 12 соседей, а на двухмерной их 8. Логику Воронова нужно переносить не на геометрию, а на сетку.
У каждой вершины 6 треугольников из которых берется центр и объединяется в полигон, каждый треугольник может разделиться на два или сложиться в один. Тут даже поворачивать саму грань нет необходимости можно сразу получить полигон для каждой вершины, только проверив условие разворота грани в рамках этих же 12 соседних вершин. Соседи индексируются очень просто — это один проход по всем треугольникам.
У каждой вершины 6 треугольников из которых берется центр и объединяется в полигон, каждый треугольник может разделиться на два или сложиться в один. Тут даже поворачивать саму грань нет необходимости можно сразу получить полигон для каждой вершины, только проверив условие разворота грани в рамках этих же 12 соседних вершин. Соседи индексируются очень просто — это один проход по всем треугольникам.
int[] count = new int[vertex_count];
int[][] index = new int[vertex_count][12];
for (i = 0; i<triangles_count; i++) {
int id0 = triangles[i].id0;
int id1 = triangles[i].id1;
int id2 = triangles[i].id2;
index[id0][count[id0]] = id1;
index[id0][count[id0] + 1] = id2;
count[id0]+=2;
index[id1][count[id1]] = id0;
index[id1][count[id1] + 1] = id2;
count[id1]+=2;
index[id2][count[id2]] = id1;
index[id2][count[id2] + 1] = id0;
count[id2]+=2;
}Я в примере взял среднее между вершинами треугольника, а для плавильной диаграммы воронова нужно брать центр описанной окружности. Я даже больше скажу, если в пример автора добавить расчет центра от описанной окружности (сферы), то также получиться диаграмма воронова, построенная относительно вершин сетки икосаэдра.
Это просто охранённым материал, спасибо
День третий: сотворение суши и земли, морей и растений ...
На самом деле очень круто, сам после статьей о Перлине думал, а нет ли алгоритмов поближе к симуляции, сам придумал плиты, но не придумал погоду. И замыкание на сферу очень приятно выглядит.
Вот такой же подход теперь развернуть на условно бесконечную плоскую карту с ленивой генерацией…
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Процедурная генерация планет