Рубрика «процедурная генерация карт»

Использование алгоритма Прима для генерации соединённых друг с другом пещер - 1 Использование алгоритма Прима для генерации соединённых друг с другом пещер - 2 Использование алгоритма Прима для генерации соединённых друг с другом пещер - 3

Я решил объяснить один из алгоритмов генерации карты, используемых в моей игре In the House of Silence. Главное преимущество этого способа заключается в том, что в отличие от других алгоритмов, он никаким образом не может сгенерировать карту с разделёнными частями.

Генерация идеального лабиринта

Использование алгоритма Прима для генерации соединённых друг с другом пещер - 4

Как понятно из названия, я использую хорошо задокументированный рандомизированный алгоритм Прима. Описание этого алгоритма можно найти на Википедии, однако вы можете применить любой другой алгоритм генерации лабиринтов.

Для понятности я привёл псевдокод, описывающий алгоритм Прима. Будет довольно просто приспособить его под любой язык программирования.
Читать полностью »

Что такое процедурная генерация?

Процедурная генерация включает в себя множество генеративных алгоритмов, принцип работы которых заключается в создании данных не вручную, а алгоритмически: вместо ручного изготовления того, что мы хотим создать (карты, музыки, рельефа…), пишется алгоритм, который успешно может создавать различные примеры без многократного выполнения того же процесса. Особенно полезен такой подход в видеоиграх, где случайным образом может генерироваться целая карта или уровень (например, карты в Minecraft, Terraria или Factorio, или схемы уровней в большинстве roguelike).

Алгоритм коллапса волновой функции и его области применения

В статье мы исследуем алгоритм коллапса волновой функции (WaveFunctionCollapse, WFC), предложенный Максимом Гуминым (в его Twitter есть коллекция потрясающего контента, созданного при помощи этого алгоритма другими разработчиками!) для процедурной генерации изображений или рельефа при помощи создания изображений, локально схожих с входящим изображением в условиях сетки заданного размера.

В основе алгоритма лежит идея пошагового создания готового изображения с отслеживанием того, какие тайлы «соответствуют» уже частично построенному изображению. Для изучения подробного описания алгоритма рекомендуем обратиться к исходному репозиторию WFC на Github и четвёртому разделу статьи "WaveFunctionCollapse is Constraint Solving in the Wild".

Адаптивная процедурная генерация при помощи алгоритма WaveFunctionCollapse и априорного распределения вероятностей - 1

Примеры процедурно сгенерированных из seed изображений
Читать полностью »

image

Для моей постапокалиптической игры Frameshift мне нужно было заполнить очень большой открытый мир разнообразными городами. В нашей команде всего 3 человека, поэтому я, разумеется, воспользовался процедурной мощью Houdini!

Раньше, когда не знал о Houdini, я писал на C# собственные инструменты процедурной генерации мешей для Unity. Добавление новых функций было очень долгим процессом, и когда я однажды услышал, что Houdini предназначен для подобных задач, то сразу перешёл на него. Я поэкспериментировал с разными способами генерации городов и улиц, и в этой статье я вкратце расскажу о методике, которая в конечном итоге была использовала для игры.

Сначала я создал инструмент для генерации сети улиц, которые можно было бы использовать в городе. Моё решение основано на изложенных здесь концепциях, а также на использованной по ссылке статье. Там много говорится о тензорных полях и собственных векторах, и всё написано очень технически, но вкратце это можно объяснить так: для моего случая (генерации дорожной сети на рельефе) мне нужно было сгенерировать контурные линии рельефа, а также линии, перпендикулярные им.
Читать полностью »

Создаём свою Minecraft: генерация 3D-уровней из кубов - 1

Частично из-за популярности Minecraft, в последнее время наблюдается рост интереса к идее игры, действие которой происходит в состоящем из кубов мире, построенном из 3D-рельефа и заполненного такими элементами, как пещеры, обрывы и так далее. Такой мир — идеальное применение для шума, сгенерированного в стиле моей библиотеки ANL. Данная статья возникла из обсуждений моих предыдущих попыток реализации этой техники. С тех пор в структуре библиотеки появились незначительные изменения.

В предыдущих постах я рассказывал об использовании функций 3D-шума для реализации рельефа в стиле Minecraft. После этого библиотека немного эволюционировала, поэтому я решил вернуться к этой теме. Так как мне пришлось отвечать на множество вопросов по этой системе, я попытаюсь более подробно рассказать о задействованных концепциях. Чтобы базовые концепции были понятнее, я начну с идеи генерации 2D-рельефа, используемого в таких играх, как Terraria и King Arthur's Gold, а затем расширю систему до 3D-примеров наподобие Minecraft. Это позволит мне эффективнее демонстрировать концепции на примере изображений.

Эта система разрабатывалась с учётом следующей абстрактной цели: мы должны иметь возможность передать системе координату определённой точки или ячейки, и определить, какой тип блока должен находиться в этой локации. Мы хотим, чтобы система представляла собой «чёрный ящик»: передаём ей точку, возвращаем тип блока. Разумеется, это относится только к изначальной генерации мира. Блоки в подобных играх могут изменяться действиями игрока, и будет неудобно пытаться описать такие изменения при помощи такой же системы. Подобные изменения должны отслеживаться каким-то иным образом. Эта система генерирует изначальный мир, первозданный и нетронутый руками игрока и других персонажей.
Читать полностью »

Генерация подземелий и пещер для моей игры - 1

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

Разбиение пространства

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

Способов разбиения пространства тоже очень много: разделение на сетки, двоичное разбиение пространства, разбиение пространства деревом квадрантов, диаграммы Вороного и т.д. Я решил использовать двоичное разбиение пространства, потому что оно хорошо подходит для генерации прямоугольных комнат. Этот метод получил популярность благодаря статье на RogueBasin.

Единственная сложность этого алгоритма — выбор позиции разделения. Если мы не наложим ограничение на позицию разделения, то будем получать странные разбиения пространства:

Генерация подземелий и пещер для моей игры - 2

Такого поведения можно избежать несколькими способами. Один из них — ограничить позицию разделения двумя соотношениями длин сторон, например, в интервале от 30% до 70% или от 40% до 60%. Другой способ — использовать вместо равномерного распределения нормальное или биномиальное, благодаря этому повысится вероятность разделения по центру стороны, а не по краям. Эти способы устраняют проблему, но сложно понять, как конкретно параметры влияют на окончательный результат.
Читать полностью »

image

Diablo 1 — это классический roguelike 1996 года в жанре hack and slash. Это была одна из первых успешных попыток познакомить широкие массы с roguelike, которые до этого имели нишевую графику в виде ASCII-арта. Игра породила несколько сиквелов и множество имитаций. Она известна своей тёмной, мрачной атмосферой, сгущающейся по мере спуска игрока в подземелья, располагающиеся под городом Тристрам. Это была одна из первых для меня игр с процедурной генерацией карт, и возможность генерации столь правдоподобных уровней просто потрясла меня.

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

Благодарю Дэвида Бревика и команду Blizard North за создание такой потрясающей игры, а также galaxyhaxz и команду Devilution за их удивительную работу по восстановлению читаемого исходного кода проекта.
Читать полностью »

image

Скотт Тёрнер продолжает работу над своей процедурно генерируемой игрой и теперь решил заняться проблемой оформления границ карт. Для этого ему предстоит решить несколько непростых задач и даже создать собственный язык описания границ.

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

В настоящее время в моей игре Dragons Abound есть пара простых способов отрисовки границ. Она может отрисовывать одинарную или двойную линию по периметру карты и добавлять простые элементы в углах, как на этих рисунках:

Создаём границы процедурно генерируемой карты - 2

Создаём границы процедурно генерируемой карты - 3

Также игра может добавлять поле в нижней части границы для названия карты. В Dragons Abound есть несколько вариаций этого поля, в том числе такие сложные элементы, как фальшивые головки винтов:

Создаём границы процедурно генерируемой карты - 4

В этих полях названий присутствует вариативность, но все они созданы вручную.

Один из интересных аспектов границ фэнтезийных карт заключается в том, что они одновременно и креативны, и шаблонны. Часто они состоят из небольшого количества простых элементов, сочетающихся разными способами для создания уникального результата. Как всегда, первым шагом при работе с новой темой для меня является изучение коллекции примеров карт, создание каталога типов элементов границ и изучение их внешнего вида.
Читать полностью »

Как написано в недавних постах блога, я боролся за то, чтобы получить в своей игре Dragons Abound нужную детализацию береговых линий. Моё разочарование возникло во время реализации барьерных островов. Чтобы создать как можно более узкий остров, я делал их шириной в одну локацию — на рисунке ниже каждая локация является треугольником Делоне:

Снова о диаграммах Вороного - 1

Это было довольно неприятно — и из-за того, что остров оказался очень изломанным, и потому, что размер деталей был слишком большим. Казалось, что при сильном увеличении количества треугольников Делоне (то есть при сильном уменьшении их размеров) эта проблема решится — но нужная мне плотность треугольников приводила к сбою браузера.
Читать полностью »

В декабрьских новостях об урагане Флоренс часто упоминались Внешние отмели — ряд барьерных островов на побережье Северной Каролины:

Генерация барьерных островов - 1

Барьерные острова — это плоские или глыбистые участки песка, формируемые волнами и прибоем параллельно побережью материка. Они часто имеют вид длинных цепочек, которые могут тянуться на многие десятки миль. Барьерные острова обычно разделены небольшими приливными протоками, и могут формировать лагуны между островами и материком.

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

Чтобы понять, почему это так, давайте взглянем на «ванильную» карту острова:
Читать полностью »

image

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

Введение

Алгоритм был написан как часть работы на получение степени бакалавра и основан на статье Ma et al (2014). Целью работы было ускорение алгоритма и дополнение его новыми функциями. Я вполне доволен результатом, потому что мы сделали алгоритм достаточно быстрым, чтобы использовать его во время выполнения игры. После завершения бакалаврской работы мы решили превратить её в статью и отправить на конференцию Game-ON 2018.

Алгоритм

Для создания уровня игры алгоритм получает в качестве входных данных набор полигональных строительных блоков и граф связности уровня (топологию уровня). Узлы графа обозначают комнаты, а рёбра определяют связи между ними. Цель алгоритма — назначить каждому узлу графа форму и расположение комнаты таким образом, чтобы никакие две формы комнат не пересекались, и каждая пара соседних комнат могла соединяться дверьми.
Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js