Как стать автором
Обновить

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

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

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

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

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

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

Пусть a=max(|x2-x1|, |y2-y1|), b=min(|x2-x1|, |y2-y1|). Тогда 0 \le b \le a

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

0 \le b^n \le a^na^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

При 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]. И никакого "доказательство оставим в качестве несложного упражнения читателю" :)

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

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

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

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

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

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

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

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

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

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

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

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

  • под углом 90 градусов

  • под углом 45 градусов

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

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

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

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

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

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

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

Спасибо!

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

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

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);
    }
}

А, я понял. У подхода есть одна серьезная проблема: не будут поддерживаться дробные числа - 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

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

	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);

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • Отсекаем у полигонов лишнее для всех пар генераторов.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

При a > b:

\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, т.к. b/a < 1.

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

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

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

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

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

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

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

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

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

Спасибо
Godot)

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

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

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

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

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

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

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

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

Зарегистрируйтесь на Хабре, чтобы оставить комментарий

Публикации

Изменить настройки темы

Истории