Комментарии 17

Сей генератор формально тоже велосипед, но выделяется некоторым изяществом.

Отличный материал. И переводчик молодец. Но вот зачем сайт с примером кода пытается читать личный сертификат — не очень понятно.

Благодарю! Как видите, и сама статья, и сайт достаточно древние — почти 5 лет для веба — не шутки. Возможно какие-то нюансы настройки.

Надеюсь, оригинальный сайт не ляжет под Хабраэффектом...

Читал еще когда оригинал появился. Но как то показалось сложным. В общем обошелся шумом Перлина без каких либо сложных дополнений и распределений.
www.youtube.com/watch?v=_tKAjC7pAjU

Да, шум Перлина тоже неплохо справляется с задачей изначальной генерации. Но представьте, что нужно динамическое изменение ландшафта на протяжении длительного периода времени — в результате тектонической активности, например. А тут есть литосферные плиты, воздушные потоки — можно пересчитывать биомы на лету, и это, скорее всего, придаст миру большее правдоподобие.

Алгоритмы с адекватной вычислительной сложностью — это круто.
Но тут автор тоже представил алгоритмы, в целом, приемлемой трудоемкости. И их отличие в том, что они оперируют исходными данными — кинетикой плит, воздушных масс и т.п.
Такая модель может быть актуальна для игр определенных жанров, где ландшафт является не статической, а динамической составляющей игры.
Простой пример — взрыв ядерной бомбы в игровом мире — применяя соответствующую модель можно правдоподобно рассчитать изменение климата, пути распространения радиоактивных осадков, зоны возникновения цунами. Это возможно потому, что в модели заложены параметры, исходя из которых и строится весь ландшафт.

Только вот вся проблема в том что там куча кода, который надо перелопатить и прочитать, чтобы найти интересующую деталь. В то время, как тем же вороновым, можно сделать два цикла и получу тот же результат что и у автора. А вот в самой статье ни строчки кода, только восхищения о том что его понадобилось на абзац текста очень мало.

Кстати вороновым можно сгенерить весь результат автора за кадр, а у него куча прогрессбаров прежде чем все построиться. Возможно на 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));
    }



И тут даже нет сложных контейнеров, только стандартные массивы.
изображение
image

Данная не равномерная сетка укладывается в массив 12x12, тут ровно 144 ячейки, которые изначально были банальной квадратной регулярной сеткой. Которые далее могут тайлиться с другими сегментами подобной сетки.

Автор пробовал применить генерацию сетки с помощью Воронового. Как уже описано в статье, то что подходит для евклидовой геометрии, не подходит для геометрии Римана.

Там все очень хорошо подходит. Весь воронов на случайных числах сводиться к добавлению случайной величины — смещения вершин, без разницы на какой поверхности. И последующая проверка ближайших точек, соответствующий поворот граней к ближайшим двум вершинам. Это весь алгоритм и он прекрасно ложиться на сферу, разница лишь в том что тут для каждой вершины икосаэдра 12 соседей, а на двухмерной их 8. Логику Воронова нужно переносить не на геометрию, а на сетку.

У каждой вершины 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;
}
Я в примере взял среднее между вершинами треугольника, а для плавильной диаграммы воронова нужно брать центр описанной окружности. Я даже больше скажу, если в пример автора добавить расчет центра от описанной окружности (сферы), то также получиться диаграмма воронова, построенная относительно вершин сетки икосаэдра.

Мне тоже очень понравилась статья, поэтому и решил вкатиться переводчиком.

День третий: сотворение суши и земли, морей и растений ...

На самом деле очень круто, сам после статьей о Перлине думал, а нет ли алгоритмов поближе к симуляции, сам придумал плиты, но не придумал погоду. И замыкание на сферу очень приятно выглядит.


Вот такой же подход теперь развернуть на условно бесконечную плоскую карту с ленивой генерацией…

Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.