AskePit Feb 19 at 09:00

Вороной, Манхэттен, рандом

Easy

34 min

19K

C++*Game development*Algorithms*Mathematics*Godot*

Retrospective

+160

Comments 53

GRaAL Feb 19 at 09:24

Отличный опыт, и выглядит симпатично!

Мои коллеги тоже возятся с биомами в своей игре, думаю, у них схожие проблемы.

Отдельный респект за Godot, незаслуженно мало про него статей.

AskePit Feb 19 at 12:40

Оу, был бы рад почитать в комментариях что-то интересное или дополняющее по теме от ваших коллег! Наверняка у них есть свои лайфхаки, секретики и боль по генерации карты, которые можно оставить для потомков

jamiederinzi Feb 19 at 10:07

Я и сам ни разу не математик, но на пальцах попробую:

Пусть . Тогда $0 \le b \le a$

В положительных числах все степени и корни строго возрастающие, значит, знаки неравенств сохраняются.

$0 \le b^n \le a^n$ $a^n \le (a^n+b^n) \le 2*a^n$ $\sqrt[n]{a^n} \le \sqrt[n]{a^n+b^n} \le \sqrt[n]{2*a^n}$ $a \le \sqrt[n]{a^n+b^n} \le \sqrt[n]{2}*a$

Поскольку в пределе корень бесконечной степени из 2 = 1, получаем $a \le \sqrt[\infty]{a^\infty+b^\infty} \le a$

excoder Feb 19 at 23:29

При a > b: lim[(a^n + b^n)^(1/n)] = lim[(a^n * (1 + (b/a)^n))^(1/n)] = lim[(a^n)^(1/n)] * lim[exp{ln(1 + (b/a)^n)*1/n}] = lim[a^(n/n)] * exp{lim[ln(1+(b/a)^n)] * lim[1/n]} = a * exp{ln(1 + lim((b/a)^n)) * 0} = a * exp{0 * 0} = a. Здесь lim((b/a)^n) = 0, т.к. b/a < 1.

В обратную сторону при a < b по аналогии.

При a=b технически lim((b/a)^n)=1, и остаётся ln(2), но он всё равно множится на 0.

В общем, неопределённостей не возникает, и мы просто тащим пределы внутрь.

@AskePit тем самым, доминирование формально вылезает в lim[(b/a)^n] или lim[(a/b)^n]. И никакого "доказательство оставим в качестве несложного упражнения читателю" :)

wataru Feb 19 at 23:45

Хабр поддерживает формулы же.

excoder Feb 20 at 00:25

Да только сейчас понял, что формулы теперь на "плюсике" сидят. Приношу извинения, редактировать уже поздно ?‍♂️

mayorovp Feb 19 at 10:35

Правда, математик из меня такой себе, поэтому я не очень понимаю, как $lim_{p \to \infty}$ превращает эту формулу в . Если кто-то в комментариях сможет доступно на пальцах это объяснить мне, буду очень благодарен.

Если совсем на пальцах - то всё просто. Чем больше показатель степени, тем сильнее большее из слагаемых "доминирует" над меньшим. При бесконечном p меньшее слагаемое перестаёт влиять на результат.

AcckiyGerman Feb 19 at 10:47

А мне понравилось определение из wikipedia - ёмко и понятно: Расстоя́ние Чебышёва — метрика на векторном пространстве, задаваемая как максимум модуля разности компонент векторов.

AskePit Feb 19 at 12:34

Ваше объяснение мне понравилось больше всего - я сразу все понял, спасибо!

Question_man Feb 21 at 19:31

А там разве обратная степень (1/p) не превращает все выражение в 1 (в пределе)?

wataru Feb 21 at 20:51

Там бесконечность же под корнем получается, так что нет.

mayorovp Feb 21 at 21:00

Там p и 1/p сокращаются

Sadler Feb 19 at 11:56

Насчёт построения дорог по точкам интереса -- это хорошо, но потом захочется сделать road connector'ы, через которые будут сцепляться POI строго в определённых точках и направлениях, затем обнаружите, что очень сложно сделать сеть линейных дорог только между POI, и придётся либо подбирать такие POI, чтобы их connector'ы сошлись, либо обращаться к pathfinding и выводить-таки криволинейную дорогу до других POI.

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

AskePit Feb 19 at 12:51

Поинт про коннекторы действительно хороший. У нас были заготовки для road connector'ов и их было строго ограниченное количество:

под углом 90 градусов
под углом 45 градусов
под углом 180 градусов (крч просто прямая)

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

И тут то, о чем вы говорите, действительно расцвело бы пышным цветом - POI по идее могли бы быть расставлены только ограниченными конфигурациями в пространстве, и мы бы наверное померли придумывать, как их генерировать.

Так что, пожалуй, вы правы - лучше начать с дороги, а не наоборот.

Sadler Feb 19 at 12:56

Я просто уже обжёгся на этом. Это вам повезло, что у вас столько ограничений, мне вот пришлось в 3D всё это разруливать :D Не прямо идеально как я хочу, но более или менее работает. К сожалению, у нас бывают POI, которые обязаны быть повёрнуты строго по сторонам света, с ними больше всего проблем.

feelamee Feb 19 at 12:45

Очень интересная статья. Спасибо

Кстати, как насчёт какого-нибудь static_cast<int> в дефолт ветке switch в функции расстояния?

AskePit Feb 19 at 12:54

Спасибо!

А что кастовать будем? Я вот предпочел просто скатиться "дефолтную" Евклидову метрику, если в функцию скормлена какая-то белиберда.

feelamee Feb 19 at 14:06

метрику. Что-то вроде этого

template<SpaceMetric METRIC = SpaceMetric::Euqlid>
double distance_t(Point a, Point b)
{
	if constexpr (METRIC == SpaceMetric::Manhattan)
	{
		return abs(b.x - a.x) + abs(b.y - a.y);
	}
	else if constexpr (METRIC == SpaceMetric::Chebyshev)
	{
		return std::max(abs(b.x - a.x), abs(b.y - a.y));
	}
	else if constexpr (METRIC == SpaceMetric::Euqlid)
	{
		return sqrt(pow(b.x - a.x, 2) + pow(b.y - a.y, 2));
	}
    else
    {
        const int p = static_cast<int>(METRIC);
        return pow(pow(abs(b.x - a.x), p) + pow(abs(b.y - a.y), p), 1./p);
    }
}

AskePit Feb 19 at 17:58

А, я понял. У подхода есть одна серьезная проблема: не будут поддерживаться дробные числа - C++ не позволит енуму иметь float-значение. А это значит, что, например, два примера из моей статьи - p=1.5 и p=0.5 было бы невозможно построить с помощью такой функции. К тому же консистентность рушится еще и по причине метрики Чебышева, которая вообще $p=\infty$ и надо закреплять за ним какое-то спец-значение.

У меня витала в голове идея подобного рода - ведь я как-то сгенерировал для примеров карты с p=1.5 и p=0.5 ? Я эту реализацию писал на GDScript, но если транслировать мой код в C++, то используются две функции, которые можно заоверлоадить. Пример требует С++20 и выше из-за double в качестве non-type template parameter:

#include <iostream>

enum class SpaceMetric
{
	Euqlid,
	Manhattan,
	Chebyshev
};

struct Point
{
	double x;
	double y;
};

template <double ORDER>
double distance(Point a, Point b)
{
	return pow(pow(abs(b.x - a.x), ORDER) + pow(abs(b.y - a.y), ORDER), 1 / ORDER);
}

template <SpaceMetric METRIC>
double distance(Point a, Point b)
{
	if constexpr (METRIC == SpaceMetric::Manhattan)
	{
		return abs(b.x - a.x) + abs(b.y - a.y);
	}
	else if constexpr (METRIC == SpaceMetric::Chebyshev)
	{
		return std::max(abs(b.x - a.x), abs(b.y - a.y));
	}
	else
	{
		return sqrt(pow(b.x - a.x, 2) + pow(b.y - a.y, 2));
	}
}

int main()
{
	Point a{ 0, 0 };
	Point b{ 3, 4 };

	const double euclid    = distance<SpaceMetric::Euqlid>(a, b);
	const double manhattan = distance<SpaceMetric::Manhattan>(a, b);
	const double chebyshev = distance<SpaceMetric::Chebyshev>(a, b);
	const double order1_5  = distance<1.5>(a, b);
	const double order0_5  = distance<0.5>(a, b);

	for (const auto& val : { euclid, manhattan, chebyshev, order1_5, order0_5 }) {
		std::cout << val << std::endl;
		/*
		prints
			5
			7
			4
			5.58425
			13.9282
		*/
	}
}

Таким образом мы сели ровно на оба стульчика:

Там где можем использовать именные версии, там используем enum. Тут же покрыт неудобный Чебышев;
Для нонейм метрик используем в шаблоне double

mayorovp Feb 19 at 20:25

А на кой вам вообще отдельно функция и отдельно перечисление? Сравните:

	const double euclid    = distance<SpaceMetric::Euqlid>(a, b);
	const double manhattan = distance<SpaceMetric::Manhattan>(a, b);
	const double chebyshev = distance<SpaceMetric::Chebyshev>(a, b);

	const double euclid    = space_metric::euqlid(a, b);
	const double manhattan = space_metric::manhattan(a, b);
	const double chebyshev = space_metric::chebyshev(a, b);

Как по мне, второй вариант куда проще...

feelamee Feb 19 at 20:33

Да, можно так. Либо же можно использовать constexpr double ... вместо enum. Минус в том, что нет автодополнения, но это можно исправить, если засунуть это в отдельный namespace.

Насчёт бесконечности - можно ведь numeric_limits. Но лучше все же оптимизированную версию

wataru Feb 19 at 13:52

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

wataru Feb 19 at 14:16

Подумалось, есть же простой алгоритм построения диаграм вороного за O(n^3) (тут n - количество регионов, а не пикселей на картинке!). Все эти хитрые алгоритмы работают за O(n log n), но для ваших нескольких точек вы разницу не намеряете, да и за счет меньшей константы наивный алгоритм может даже работать быстрее, если у вас всего 10 точек.

Идея проста: границы областей проходят по линиям, равноудаленным от двух каких-то точек. Так что вам надо построить все такие линии и все их попересекать. Это, правда, работает только для тех метрик, где эти линии легко построить. Но все стандартные метрики p=1,2,infinity этим свойством обладают. У вас будет или прямая, или ломанная.

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

Тут также элементарно обрезать все области прямоугольной границей карты. просто добавьте 4 прямые-границы карты ко всем экви-дистантным лучам в самом начале.

Надо немного геометрии: научитесь переекать прямые/лучи/отрезки. Ну еще, надо будет уместь в точке по набору отрезков из нее выбрать ближайший по углу слева. Тут вам помонут или atan2() или векторное и скалярное произведения.

В манхеттонской метрике вообще можно все в целых числах рассчитать: эти ломанные будут проходить в худшем случае по точкам с половинными координатами. А все пересечения будут максимум по точкам с 1/4 координатами. Так что если изначальные координаты целые и их умножить на 4, то все точки в расчетах будут с целыми координатами.

AskePit Feb 19 at 16:45

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

ris58h Feb 25 at 07:26

Сработает только для полигонов, а для кривых уже нет.

Делал подобное для power distance:

Начинаем с N полигонов совпадающих с областью зарисовки. Очевидно, все генераторы (точки для которых строим Вороного) лежат внутри своих полигонов.
Отсекаем у полигонов лишнее для всех пар генераторов.

Да, сложность выше, чем для хитрых построений через переход в 3д и обратно, но для нескольких десятков генераторов это незаметно. Зато алгоритм прост и понятен.

wataru Feb 25 at 11:41

Да, я прямо так и написал же:

Это, правда, работает только для тех метрик, где эти линии легко построить. Но все стандартные метрики p=1,2,infinity этим свойством обладают. У вас будет или прямая, или ломанная.

Вместо отсечения от изначального прямоугольника проще и быстрее все ломаные попересекать и выделить внутреннюю область.

domix32 Feb 19 at 14:31

Ещё бы понять какая метрика какая на примере. Зиг-заг знаю что из манхэттена получается, а какой из путей чебышев, каков евклид?

wataru Feb 19 at 15:23

Где косые линии под разными наклонами - это точно эвклид. В чебышеве, как и манхеттене, бывают только линии под углами в 45 градусов. Но вообще вроде все картинки в статье ясно подписаны.

domix32 Feb 19 at 19:58

См первые две картинки в "Расстояния". Найдёте, подписи к ним - зовите.

mayorovp Feb 19 at 20:28

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

Под второй картинкой (та что с шахматной доской) ниже есть целый абзац с пояснениями.

AskePit Feb 19 at 16:34

А на каком примере из кучи в статье? :)

Если вы про цветастые примеры для одних и тех же десяти точек, то каждая картинка внизу подписана. Разве нет? У меня и в мобильной версии и на ПК видно.

А если конкретно про примеры нашей игры, то я всю статью читателям уши жужжу про Манхэттенскую метрику ( p=1 )

domix32 Feb 19 at 19:57

На той на которой три пути из пункта желтая точка в пункт желтая точка нарисованы. Красная, синяя и жёлтая. Я сначала подумал, что это примеры разных метрик на плоскости, но похоже что они нарисованы просто от балды и не соотвествуют метрикам из статьи.

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

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

mayorovp Feb 19 at 20:30

На той на которой три пути из пункта желтая точка в пункт желтая точка нарисованы. Красная, синяя и жёлтая. Я сначала подумал, что это примеры разных метрик на плоскости, но похоже что они нарисованы просто от балды и не соотвествуют метрикам из статьи.

Все три соответствуют манхэттенской метрике. О чём прямым текстом написано в следующем за картинкой абзаце.

domix32 Feb 19 at 21:33

метрика манхэттенская, а эвристика не обязательно.

AskePit Feb 19 at 23:43

Извиняюсь за недоразумение, подписал изображение во избежание путаницы.

Про "от балды" правда не понял - изображение ровно такое, какое должно быть, и абзацем ниже про него все расписано. И про то, что это Манхэттен; и про то, что пути разные, но расстояние по факту одно и то же - 12 клеток, можете сами посчитать, там 12. Где что чему не соответствует-то? Каким метрикам из статьи?

domix32 Feb 19 at 23:58

У вас в статье есть три эвристики, которые можно использовать в алгоритмах поиска - Дийкстре, A* и прочие. В зависимости от ограничений на плоском поле и выбранной эвристики - то есть алгоритму по которой отдаётся приоритет точке в алгоритме поиска пути - находимый путь может отличаться количеством поворотов между точками при одинаковой метрике в заданном пространстве - то есть способу измерять расстояния между точками в заданном векторном пространстве.

"От балды" означает, что этот путь вы нарисовали ручками, а не как результат работы какого-либо алгоритма, но с разными эвристиками, о чём я подумал изначально.

AskePit Feb 20 at 09:16

Я дико извиняюсь, но в моей статье ничего такого, о чем вы говорите, нет. В ней есть только то, что я написал. Ни про три эвристики, ни тем более про алгоритм поиска со звездочкой в ней нет ни слова.

Более того, в статье в Википедии, откуда мое изображение перерисовано, тоже речь идет не про три эвристики и алгоритм *, а только лишь про природу Манхэттенского расстояния, о чем и я вторю своими словами и своими руками (в случае периначенного изображения)

Dominux Feb 19 at 15:33

После этого никакую миграцию на другой движок вы не сделаете от слова совсем — просто выкидываете весь код и пишете все с нуля

Чем обусловлена необходимость миграции?

AskePit Feb 19 at 16:32

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

Так зачем же себя огрничивать в большей степени, чем в меньшей?

Dominux Feb 19 at 20:06

Миграция всё же - вопрос спорный. Для реальных проектов это скорее исключение

А в целом тот же дядя Боб говорил, что не стоит привязываться к зависимостям как раз по этим причинам

А то так можно и выбирать язык программирования не из-за его синтаксиса и семантики, а потому, что у он просто похож на какой-то другой

Antohin Feb 19 at 15:53

Статья доказывает азбучную истину геймдева - разработка игры должна начинаться с геймплея. Геймплей без графики возможен - тот же ВампирСурвайвор (не, с точки зрения быстродействия графики там тот еще хардкор похоже, я про саму графику). А вот наоборот - вряд ли. Я вот всё ломал себе голову - а что бы мне было интересно делать на этой симпатичной карте? Так и не придумал. Но я и не геймдизайнер ни разу.

ЗЫ: Это замечание ни в коем случае не укор автору - материал и интересный, и раскрывает множество тем, о которых если и слышал, то краем уха. Ну и плюс доказывает, что любое занятие даже если конечный ожидаемый результат не достигнут, все равно идет в пользу в плане новых знаний и опыта.

AskePit Feb 19 at 16:37

Спасибо! Вы очень даже правы. В нашей команде есть один существенный минус - геймдизайнеры из нас никакие, поэтому мы страдаем, чем можем :)

SadOcean Feb 19 at 20:03

Очень неплохо.

Результат крутой.

Я делал вороной брутфорсом, на самом деле для практичных применений это не сложно:
- Обычно мы не делаем полностью рандомные точки, они выглядят так себе, мы используем какой то вариант с нормальным распределением. Хороший вариант - взять квадратную или треугольную сетку точек и добавить случайное смещение. Результат получается с хорошим распределением, примерно одинаковым размером блоков и достаточно рандомным.
- После этого нужно взять широкую сетку и найти 4-5 ближайших точек к центру каждой ячейки (получается O(n)^2, но для очень крупнозернистой сетки)
- Потом можно брать сетку нужного разрешения (текстуру, к примеру) и на ней уже находить финальную диаграмму.

Конкретно задачу сгенерировать меши Я не решал, думаю можно сделать это с марширующими квадратами.
Я делал биомы/области для стратегической игры с гексиками.

excoder Feb 20 at 00:34

Спасибо за статью, отличная!

При :

$\begin{align*} \lim_{n \to \infty} \left(a^n + b^n\right)^{\frac{1}{n}} &= \lim_{n \to \infty} \left(a^n \left(1 + \left(\frac{b}{a}\right)^n\right)\right)^{\frac{1}{n}} \\ &= \lim_{n \to \infty} \left(a^n\right)^{\frac{1}{n}} \cdot \lim_{n \to \infty} \exp\left\{\ln\left(1 + \left(\frac{b}{a}\right)^n\right)\cdot\frac{1}{n}\right\} \\ &= \lim_{n \to \infty} a^{\frac{n}{n}} \cdot \exp\left\{\lim_{n \to \infty} \ln\left(1+\left(\frac{b}{a}\right)^n\right) \cdot \lim_{n \to \infty} \frac{1}{n}\right\} \\ &= a \cdot \exp\left\{\ln\left(1 + \lim_{n \to \infty} \left(\frac{b}{a}\right)^n\right) \cdot 0\right\} \\ &= a \cdot \exp\{0 \cdot 0\} \\ &= a \end{align*}$

Здесь $\lim_{n \to \infty} \left(\frac{b}{a}\right)^n = 0$ , т.к. .

В обратную сторону при по аналогии.

При технически $\lim_{n \to \infty} \left(\frac{b}{a}\right)^n = 1$ , и остаётся , но он всё равно множится на .

В общем, неопределённостей не возникает, и мы просто тащим пределы внутрь.

Тем самым, доминирование формально вылезает в $\lim_{n \to \infty} \left(\frac{b}{a}\right)^n$ и в $\lim_{n \to \infty} \left(\frac{a}{b}\right)^n$

И никакого "доказательство оставим в качестве несложного упражнения читателю" :)

Suvitruf Feb 20 at 12:10

Ого, вот это статья так статья. Спасибо!

VadimChes Feb 20 at 13:03

В ChatGPT иногда есть польза )

CGCFSS Feb 20 at 23:45

Каеф, вы сделали мою игру :D
Я аналогичные алгоритмы использовал для генерации карт и тоже вдохновлялся Don't Starve.

AskePit Feb 20 at 23:52

Здорово) Добавил в вишлист! Приятно видеть, что кто-то довел до конца безумие с рандомной генерацией. А на каком движке разрабатываете?

CGCFSS Feb 21 at 11:58

Спасибо
Godot)

eugenk Feb 21 at 09:30

Спасибо, статья отличная ! Сам сейчас осваиваю Godot (хочу из эмбеддерства перебраться в игрострой), и сам буквально пару дней назад игрался с формулой, очень похожей на метрику Минковского (чуть более общей). Правда немного с другой целью. Рисовал 3D-фишки для сочиняемой сейчас игры.

Единственно чего не понял, почему столь большие трудности вызвала диаграмма Вороного ??? Алгоритм Форчуна идеологически очень прост https://web.archive.org/web/20120305230844/http://www.ams.org/samplings/feature-column/fcarc-voronoi. И основан на определении прямой как кратчайшей кривой между двумя точками(геодезической), и параболы, как геометрического места точек, с равным расстоянием между заданными прямой и точкой. Для произвольной метрики, нам остается только понять как выглядят её прямая и парабола, отображенные в нашу привычную эвклидову плоскость. Что по-моему сделать достаточно легко(хотя не знаю, возможно мне просто это кажется. Но задача интересная, возможно сделаю). А дальше всё довольно прозрачно.

wataru Feb 21 at 20:58

Алгоритм Форчуна идеологически очень прост

Идеологически-то он прост, да. Но там очень много деталей и подводных камней.

Например, в эвклидовой метрике 2 параболы могут пересечься по двум точкам. В манхеттонской - аж по лучам, ведь параболы вырождаются в 2 отрезка под углом 45 градусов и 2 вертикальных луча.

И вообще в алгоритме форчуна надо поддерживать сбалансированное дерево этих самых растущих кусков парабол, как-то упорядоченных. И там вообще не очевидно, как манхеттонские ломанные сравнивать и что порядок там со временем меняться не будет.

ris58h Feb 25 at 08:01

Несколько лет назад нужно было нарисовать Вороного, но используя power distance (в ru источниках информации нет, потому пишу так). Прошёл через все эти же стадии поиска и терзаний. В итоге написал сам в лоб, т.к. переписывать чужой непонятный код (алгоритм: 3д - туда и обратно) не хотелось.

dangometr Mar 15 at 08:34

Любопытно, как вам удалось модифицировать классический алгоритм Форчуна для использования Манхэттенской метрики. Сам недавно пытался разобраться с построением карты Вороного. Мне было бы интересно узнать, какие конкретно изменения вы внесли и что было самым сложным в процессе этой работы. Спасибо за хорошую статью