Привет! Меня зовут Артём, и я 3D‑моделлер, который много лет работает в 3ds Max. Недавно я решил углубиться в геймдев и прошёл курс по менеджменту игровых проектов в Высшей школе Бизнеса ВШЭ, что помогло мне структурировать свои знания и подойти к разработке игр более осознанно. В рамках обучения и экспериментов с Unreal Engine я создал игру Run Eternal Depths — roguelike с процедурной генерацией подземелий, которая уже доступна для добавления в вишлист в Steam. Релиз запланирован на 21 мартаЧитать полностью »
Рубрика «генерация лабиринтов»
Как я создал roguelike Run Eternal Depths: технические аспекты и простая генерация подземелий
2025-03-17 в 5:00, admin, рубрики: Gamedev, Алгоритмы, генерация лабиринтов, процедурная генерация, стимГенерация лабиринтов: алгоритм Эллера
2022-05-24 в 13:51, admin, рубрики: c++, Gamedev, алгоритм генерации, алгоритм эллера, Алгоритмы, генерация лабиринтов, Лабиринт, С++
Вступление
Как оказалось, что тема генерации лабиринтов не сильно раскрывается в русско- и англоязычном сообществе. На хабре существует одна статья Алгоритм Эллера для генерации лабиринтов. Статья, является переводом англоязычной статьиЧитать полностью »
Использование алгоритма Прима для генерации соединённых друг с другом пещер
2021-01-19 в 6:33, admin, рубрики: алгоритм Прима, Алгоритмы, генерация лабиринтов, клеточные автоматы, пещеры, процедурная генерация карт, разработка игр
Я решил объяснить один из алгоритмов генерации карты, используемых в моей игре In the House of Silence. Главное преимущество этого способа заключается в том, что в отличие от других алгоритмов, он никаким образом не может сгенерировать карту с разделёнными частями.
Генерация идеального лабиринта
Как понятно из названия, я использую хорошо задокументированный рандомизированный алгоритм Прима. Описание этого алгоритма можно найти на Википедии, однако вы можете применить любой другой алгоритм генерации лабиринтов.
Для понятности я привёл псевдокод, описывающий алгоритм Прима. Будет довольно просто приспособить его под любой язык программирования.
Читать полностью »
Генерация подземелий и пещер для моей игры
2019-07-24 в 14:27, admin, рубрики: Алгоритмы, генерация лабиринтов, двоичное разбиение пространства, Дизайн игр, клеточные автоматы, процедурная генерация карт, разработка игр
На этой неделе я начал работать над новой темой: генерацией подземелий и пещер. Я использовал разбиение пространства для генерации комнат, алгоритмы генерации лабиринтов для генерации коридоров и клеточные автоматы для придания пещерам более естествненного внешнего вида.
Разбиение пространства
Существует множество способов генерации комнат для подземелья (случайное размещение, генерация на основе агентов, с использованием separation steering behavior или физического движка, и т.д.). Но мой любимый метод — это разбиение пространства, потому что оно легко контролируется и расширяется.
Способов разбиения пространства тоже очень много: разделение на сетки, двоичное разбиение пространства, разбиение пространства деревом квадрантов, диаграммы Вороного и т.д. Я решил использовать двоичное разбиение пространства, потому что оно хорошо подходит для генерации прямоугольных комнат. Этот метод получил популярность благодаря статье на RogueBasin.
Единственная сложность этого алгоритма — выбор позиции разделения. Если мы не наложим ограничение на позицию разделения, то будем получать странные разбиения пространства:
Такого поведения можно избежать несколькими способами. Один из них — ограничить позицию разделения двумя соотношениями длин сторон, например, в интервале от 30% до 70% или от 40% до 60%. Другой способ — использовать вместо равномерного распределения нормальное или биномиальное, благодаря этому повысится вероятность разделения по центру стороны, а не по краям. Эти способы устраняют проблему, но сложно понять, как конкретно параметры влияют на окончательный результат.
Читать полностью »
Лабиринты: классификация, генерирование, поиск решений
2019-03-29 в 9:46, admin, рубрики: алгоритм эллера, Алгоритмы, Алгоритмы поиска пути, генерация лабиринтов, Дизайн игр, заливка, Лабиринты, разработка игр, решение лабиринтов
В этом классическом посте подробно рассказывается о самых популярных способах создания и прохождения лабиринтов. Статья разделена на четыре части: классификация, алгоритмы генерации, алгоритмы решения лабиринтов и другие операции с лабиринтами.
Классификация лабиринтов
Лабиринты в целом (а значит, и алгоритмы для их создания) можно разбить по семи различным классификациям: размерности, гиперразмерности, топологии, тесселяции, маршрутизации, текстуре и приоритету. Лабиринт может использовать по одному элементу из каждого класса в любом сочетании.Читать полностью »
Процедурная генерация уровней
2018-07-30 в 20:14, admin, рубрики: Алгоритмы, генерация лабиринтов, никто не читает теги, процедурная генерация, процедурная генерация уровней, разработка игр, случайные карты
Работы по программированию, графике и звукам в некой новой игрухе закончены — остались только уровни. Лёгкая и приятная работа, но почему-то идёт с большим трудом. Возможно, сказывается общая усталость.
Думая, как бы упростить себе жизнь, в голову пришла идея о процедурной генерации. Ясное дело, её тоже надо будет писать, но как говорилось в одном известном произведении, "лучше день потерять, потом за пять минут долететь".
Внимание! Под катом много текста и "жирных" гифок.
Генератор случайных двумерных пещер
2018-07-06 в 13:51, admin, рубрики: 2d, C#, texture2d, unity3d, Алгоритмы, генерация лабиринтов, горы, пещера, процедурная генерация, процедурная генерация уровней, разработка игрПредисловие
Если вы тоже ленитесь заботитесь о своём времени, делая уровень для своей игры, то вы попали куда надо.
Эта статья подробно расскажет вам как можно использовать один из множества других методов генерации на примере горной местности и пещер. Мы будем рассматривать алгоритм Олдоса-Бродера и то, как сделать сгенерированную пещеру красивее.
По завершении чтения статьи у вас должно получиться что-то такое:
Итог
Процедурная генерация лабиринтов в Unity
2018-04-10 в 6:01, admin, рубрики: unity, unity3d, генерация лабиринтов, процедурная генерация, процедурные меши, разработка игр
Примечание: этот туториал написан для Unity 2017.1.0 и предназначен для опытных пользователей. Подразумевается, что вы уже хорошо знакомы с программирование игр в Unity.
Вы, как Unity-разработчик, наверно, имеете достаточный опыт в создании уровней вручную. Но хотели ли вы когда-нибудь генерировать уровни на лету? Процедурная генерация мешей для полов и стен, в отличие от простого расположения заранее созданных моделей, обеспечивает гораздо большую гибкость и реиграбельность игры.
В этом туториале вы научитесь следующему:
- Процедурно генерировать уровни на примере создания игры про бег в лабиринте.
- Генерировать данные лабиринтов.
- Использовать данные лабиринтов для построения меша.
Приступаем к работе
В большинстве алгоритмов (таких, например, как этот и этот) создаются «идеальные» плотные лабиринты, то есть такие, у которых есть только один верный путь и нет петель. Они похожи на лабиринты, публикуемые в газетных разделах «Головоломки».
Однако в большинство игр приятнее играть, когда лабиринты неидеальны и в них есть петли. Они должны быть обширными и состоящими их открытых пространств, а не из узких извилистых коридоров. Это особенно справедливо для жанра rogue-like, в котором процедурные уровни являются не столько «лабиринтами», а скорее подземельями.
В этом туториале мы реализуем один из простейших алгоритмов лабиринтов, описанный здесь. Я выбрал его для того, чтобы реализовать лабиринты в игре с минимальным количеством усилий. Такой простой подход хорошо работает в классических играх, перечисленных по ссылке, поэтому мы можем использовать его для создания лабиринтов в игре под названием Speedy Treasure Thief.
Читать полностью »
Использование BSP-деревьев для создания игровых карт
2017-07-11 в 8:44, admin, рубрики: binary space partitioning, bsp, Алгоритмы, генерация лабиринтов, двоичное разбиение пространства, разработка игр, случайные карты
При заполнении области объектами (например, комнатами в подземелье) в случайном порядке вы рискуете тем, что всё будет слишком случайным. Результат может оказаться абсолютно бесполезным хаосом. В этом туториале я покажу, как использовать для решения этой проблемы двоичное разбиение пространства (Binary Space Partitioning, BSP).
Я подробно и по этапам расскажу об использовании BSP для создания простой двухмерной карты, к примеру, схемы подземелья. Я покажу, как создать простой объект Leaf, который мы используем для разделения области на маленькие сегменты. Затем мы займёмся генерированием в каждом Leaf случайной комнаты. И, наконец, узнаем, как соединить все комнаты коридорами.
Примечание: хоть код примеров и написан на AS3, концепцию можно использовать практически в любом другом языке.
Читать полностью »
Duplo Railroad Tycoon: Синтез железнодорожной сети с максимальным покрытием
2017-01-17 в 5:39, admin, рубрики: irony, lego, pythonic way, генерация лабиринтов, дилетантство, железная дорога, Занимательные задачки, ненормальное программирование, программирование микроконтроллеров, разработка игр, Разработка робототехники, синтез
Детям Дед Мороз принес железную дорогу Duplo. Сегменты рельс очень легко соединяются между собой, и можно построить какой-нибудь небольшой, скорее всего просто замкнутый путь, поставить станцию и смотреть, как паровозик бегает по кругу. Иногда он останавливается и детёнок должен паровоз «заправить» из колонки, после чего паровоз снова поедет.
Читать полностью »