Algorithms
Mathematics
Game development
Comments 28
+1
Спасибо за статью. Именно ёё мне не хватало года 4 назад, когда хотел написать свой клон Космических Рейнджеров.
0
Прилично. Мне понравилось. Спасибо большое.
Ещё из похожей геометрии мне очень нравилсь триангуляция Делоне. Очень красиво получается, когда при добавлении точки перестраивается почти вся сеть.
+2
Так Делоне обычно с помощью Форчуна и делают (если речь о произвольных точках).
Если нужна просто сетка — то там есть и другие способы.
0
Дело было больше чем 25 лет назад. Не помню какой был алгоритм. Думаю, что придумывал что-то своё. Помню только — на С++, и что это был итерационный процесс. Ещё помню — очень нравилась визуализация процесса — как сеть перестраивается шаг за шагом… А потом стал искать — как добавить точку так, чтобы максимизировать количество перестановок рёбер… В общем — как-то так. Ничего уже не помню, кроме того, что выглядел этот процесс красиво (с моей точки зрения).
0
А не знает ли кто-нибудь адекватного способо построения сетки на торе? В смысле — циклически замкнутой?
А то ничего умнее построения сети с дублированием точек с противоположного края и последующим их пересоединением так и не придумал. В принципе метод работает, но напрягает непредсказуемое количество доп. точек. И их количество. Когда сама сеть имеет многие десятки тыс. точек то дополнение даёт ещё похожий порядок.
0
Взглянув на картинку (прочитав только условие), подумал, что графически это можно решать так: Строим воображаемую линию от места до места, находим середину, рисуем перпендикуляр. Ячейки будут образовываться пересечением этих перпендикуляров. (потом подумал что это же медианы треугольников с вершинами в местах)

Алгоритм же использует совсем другой подход. Очень интересно. Спасибо.
0
upd. Конечно же это не медианы, а серединные перпендикуляры.
Пересечение которых даёт — центр описанной окружности — а значит равное расстояние до вершин.
(Вспоминать школу — тоже, оказывается, интересно)
0

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

0

В boost есть хорошая реализация диаграмы Вороного. Причем не только для точек, но и для отрезков.

0
На счёт точно равной ничего не скажу, но примерно равную можно получить прогнав несколько (2..3 минимум) проходов релаксации. Собственно обычно так и делают.
0

К сожалению, это работает только на бескрайней плоскости. У автора статьи возникли трудности с краями прямоугольника, а мне так вообще надо разделить фигуру неправильной формы на несколько равных частей (или эквивалентно разделить набор точек на плоскости на несколько групп).

0
Про края ничего не скажу, однако метод вполне рабочий и для конечной. Достаточно зафискировать точки, которые на границе.
Про неправильную речи не было — таким образом разбить её на выпуклые (тут ячейки всегда выпуклые) в общем случае вообще невозможно. Если невыпуклые — можно изгалиться например разбив Вороным а потом выбрав рандомные точки и присоединяя к ним постепенно соседние ячейки, благо связность сетки позволяет это делать довольно легко. При дисбалансе соседних ячеек можно перераспределять, пока не дойдёт примерно до баланса.
0
Спасибо за ответ.

Постараюсь внятно сформулировать проблему, с которой борюсь. Есть двумерный массив («карта») из элементов двух типов: единички («суша») и нолики («море, реки, озёра»). У каждой единички есть минимум один сосед-единичка, т.е. «суша» — сплошная. Что-то типа:

0011101000
0111111100
0010001110
0011001100
0111011110
0011111100
0000111000


Эту «сушу» надо разделить на заданное число групп («стран») так, чтобы (1) каждая группа была сплошной, без анклавов и (2) все полученные группы были [примерно] одного размера.

Применение диаграмм Вороного «в лоб» приводит к группам разного размера (в некоторых группах большая часть элементов приходится на «воду») и к группам из двух несвязных частей (на разных берегах «реки»).
0
Собственно приведённый выше вариант должен решить проблему (для произвольной геометрии).
1. Диаграмму строить мелкую, по всему полю. Добавить точки строго по границе суши. Если использовать релаксацию, то эти точки не трогать. Тогда получим более-менее точную триангуляцию отдельно суши, а отдельно воды.
2. Отмечаем как-то треугольники, которые попали на воду им забываем про них.
3. Вычисляем площадь одной группы (т.е. по сути делим кол-во треугольников суши на кол-во групп)
3. Выбираем точку где-нибудь на границе и начинаем прицеплять к ней соседние полигоны (из диаграммы они известны) пока не получим нужное кол-во. Повторяем, пока площадь не кончится. Будет примерно равное разбиение. Если нужно прямо совсем точное — границы потом можно передвинуть в нужную сторону.

Для клеточного варианта можно пропустить диаграмму и работать непосредственно с соседними клетками.

Можно добавить так-же вероятность НЕ включения ячейки, чтобы граница была не ровной. Чтобы не случилось цикла вероятность можность делать пропорциональной расстоянию от начальной точки, чтобы вблизи хватали всё, а дальше уже как получится. Или при получении цикла просто заполнять всю захваченную зону а потом отрезать от границы лишнее.

Стоит учесть, что если река делит сушу на неравные куски, либо на равные, но нечётное число групп — то равномерное распределение невозможно в принципе. Всегда будет где-то больше, где-то меньше. Тогда придётся цеплять остаток кому-то.

Можно это оформить и в виде клеточного автомата, чтобы оно само балансировалось. Правда придётся прогонять много итераций.
0
Ещё раз спасибо за познавательную информацию. Для дискретной (клеточной) версии «родил» такую идею: чтобы узнать, разделится ли после присоединения клетки оставшаяся область на несвязные части, достаточно посмотреть на её соседей (8 клеток). Если из этих соседей клетки оставшейся области образуют сплошной массив, то не разделится. Если они разделены клеткой третьей области, то обязательно разделится. Если разделены «водой», то неоднозначно (могут соединяться в другом месте).

Сорри за сумбурное изложение.
0
А зачем знать — разделится или нет, если у вас задача строго не делить. Сделайте клетки меньше, чем ширина водоёма раза в 2 и тогда гарантированно можно присоединять всех не-водных соседей.
0
Условный пример — карта 3х3 клетки, из которых 5 «суша»:

010
111
010


Эту сушу я хочу разделить на 2 группы. Первым делом я выбираю два «центра», скажем, на противоположных краях. После этого я по оцереди присоединяю к ним соседние клетки. Так вот, центральную клетку я присоединить не могу, т.к. оставшая область разделится. Поэтому во вновь созданной группе будет лишь одна клетка, а остальные 4 составят другую группу.
0
Да это понятно. Вопрос — надо ли так принципиально использовать большие клетки? Если уменьшить из размер в 2 раза — задача решаема, причём сразу 2мя способами. А если принципиально, то стоит тщательнее подбирать структуру поля под количество групп. В играх такое деление идёт либо на 4 группы, либо на 2 + ничейные земли под захват.

Ну и тут как раз вариант, который на 2 ровно не делится без весьма большой погрешности.

Кстати именно с такой структурой и мелкими клетками и мой вариант может не справиться без дополнительных эвристик. Если перекрыть проходы в центре, то второму достанутся 3 изолированных лепестка. Правда если добавить механизм захвата (для клеточного автомата) то он через некоторое время может сбалансироваться и на таком поле.
0
Недавно увидел на дороге очень выразительную трещину на асфальте.
image
Задумался о ней, как о динамической системе: все эти напряжения в материале, разрывы, их направления и изгибы, где-то ближе, где-то дальше. А результат даже композиционно эстетичен. Стало интересно — смогу ли я смоделировать правдоподобно выглядящую трещину. В итоге пришёл к выводу что оптимально для этого подойдёт именно диаграма Вороного. Но посмотрев на алгоритмы её построения, отложил это развлечение в долгий ящик.
0
На самом деле похожая сетка получается элементарно:
1. Строим диаграмму на рандомных точках.
2. Каждую прямую разбиваем на №дцать отрезков.
3. Все вершины смещаем как
x+= perlin_noise(x,y) * scale;
y+= perlin_noise(x+const1,y+const2) * scale;

В этом плане гораздо интереснее старые наклейки. Они ссыхаясь рвутся иерархически — т.е. сначала на крупные ячейки, потом крупные на более мелкие.
0
Элементарно? Но ведь сложность генерации шума Перлина для двумерного пространства квадратична, а для алгоритма Форчуна строящего диаграмму Вороного n * log n
+1
Элементарно с точки зрения реализации, а не вычислительной сложности. Но и последнюю вы оценили не совсем корректно.

1. У вас на картинке примерно 60..80 точек для диаграммы, что совсем ни о чём. Я много играюсь с этим, и могу сказать, что нормальная либа строит диаграмму в сотни тысяч точек за какое-то незначительное время (не засекал, но на глаз — какие-то доли секунды.)

2. Для смещения сетки не требуется полное заполенние всей площади шумом. Достаточно (количество_рёбер*количество_отрезков), что очень сильно отличается от полного заполнения.

3. Если вдруг душа требует полного заполнения — на ГПУ (даже на древнем встроенном интеле) шум Перлина без проблем генерится в реальном времени с пристойным фпс. Собственно когда замучался ждать, пока сгенерится несколько больших слоёв 2D или 3D (последнее на ЦПУ просто невероятно долго) — переделал на ГПУ и забыл про эту проблему.

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

image

Кстати теоретически подобную картинку можно получить и один фрагментным шейдером (Вороной тоже вполне на ГПУ строится). Правда при этом информацию о границах не получить (адекватным способом. всякие детекторы границ не в счёт)
0
Действительно очень похоже, хотя это разбиение и выглядит более равномерным. Интересно было бы дать строгое обоснование почему то или иное разбиение больше или меньше похоже на настоящие трещины, но для этого, наверное, надо одолеть нетривиальную (для меня) физику явления.
Кстати, по вашему алгоритму есть какие-то статьи/мануалы? «Строим диаграмму на рандомных точках», — какую именно всё-таки диаграмму и как строим? А для какой задачи, кстати, Вам потребовалось строить на сотнях тысяч точек, если не секрет?
P.S. Мне не для дела — праздный интерес.
0
Равномерность зависит от изначального разброса точек. У меня они просто рандомные. Если использовать для точек не чисто случаную выборку, а клеточно-случаную (как в шейдерах, там всё поле делится на клетки и в каждой выбирается случайная точка с тем или иным разбросом относительно центра) может получаться как раз похожая картина групп крупных и редких пятен.

Единого обоснования быть не может, поскольку причин появления трещин много, и, как следствие, разные процессы могут описываться разными закономерностями. Например асфальт часто трескается не сам по себе (ему это вообще не свойственно), а из-за локального изгиба, за который может отвечать неравномерная подложка или наоборот, локальная перегрузка сверху. Например тяжелые грузовики очень хорошо проламывают асфальт со слабой подложкой. В тех случаях, когда материал трескается сам — там уже зависит от конкретного процесса. Например ссыхающаяся краска и упомянутые мной наклейки трескаются по разному.

Алгоритм стандартный, тот же Форчун. Если интересно — вот эти исходники. Чистый С, очень быстрый.
Пардон, диаграмму Вороного, естественно.

Задачи, на самом деле, очень разные. Я много эксперементирую со всякими (иногда странными) идеями. Да и Вороной вообще очень много где используется. Везде, где требуется неравномерное разбиение пространства, поскольку это самый эффективный способ получить случайную связную сеть.

У меня самые большие сетки были для симуляции эррозии на больших пространствах. Реально такого количества не требовалось, но ради эксперемента проверял, потянет ли большой масштаб. Да и 100К — на самом деле не так много. Достаточно мелкая сетка на поле 1024*1024 легко потянет в разы больше.
0
Аа, так всё-таки в основе диаграмма Вороного! Я вначале подумал, что тупо случайный граф по ближайшим соседям, но по картинке заподозрил неладное. Теперь стало гораздо понятнее.
А для чего нужно было симулировать эррозию? Интересно конечное практическое применение: был ли это GameDev, или собственно развлекательное программирование или что-то научно-промышленно?
0
Не, для промышленного обычно используется симуляция на регулярной сетке. А так эррозия (или её подобие) нужна везде, где нужен более-менее реалистичный ландшафт. В частности я балуюсь всяческой процедурной генерацией (больше из любопытства, чем по делу).
Вот хороший пример использования Вороного для прокладки рек.
Only those users with full accounts are able to leave comments. , please.