Как сделать бесконечный уровень в unity

Unity: бесконечный процедурно генерируемый город, получаемый при помощи алгоритма WFC (коллапс волновой функции)

Как законодатели мод по теме Unity на российском рынке предлагаем вам почитать интересное исследование о практическом использовании алгоритма WFC (Wave Function Collapse), построенного по образу и подобию известного принципа квантовой механики и очень удобного при процедурной генерации уровней в играх. Ранее на Хабре уже публиковался подробный рассказ об этом алгоритме. Автор сегодняшней статьи Мариан Кляйнеберг рассматривает алгоритм в контексте трехмерной графики и генерации бесконечного города. Приятного чтения!

Мы поговорим об игре, где вы идете по бесконечному городу, который процедурно генерируется по мере вашего движения. Город строится из набора блоков при помощи алгоритма WFC (коллапс волновой функции).

Играбельная сборка доступна для скачивания на сайте itch.io. Также можете взять исходный код на github. Наконец, я предлагаю видео, в котором иду по сгенерированому таким образом городу.

Алгоритм

Я буду называть словом “ячейка” такой элемент 3D-воксельной сетки, который может содержать блок или пустовать. Словом «модуль» я буду называть блок, который может занимать такую ячейку.

Алгоритм решает, какие модули подбирать в каждую ячейку игрового мира. Массив ячеек считается волновой функцией в ненаблюдаемом виде. Таким образом, каждой ячейке соответствует множество модулей, которые могут в ней оказаться. В терминах квантовой механики можно было бы сказать, «ячейка находится в суперпозиции всех модулей». Существование мира начинается в полностью ненаблюдаемом виде, где в каждой ячейке может находиться любой модуль. Далее все ячейки схлопываются, одна за другой. Это означает, что для каждой ячейки случайным образом выбирается по одному модулю из всех возможных.

Далее следует этап распространения ограничений (constraint propagation). Для каждого модуля подбирается такое подмножество модулей, которым разрешено быть смежными с ним. Всякий раз при схлопывании модуля обновляются подмножества других модулей, которые по-прежнему допускаются в качестве смежных ему. Этап распространения ограничений – самая ресурсозатратная часть алгоритма с точки зрения вычислительной мощности.

Важный аспект алгоритма заключается в определении того, какую ячейку схлопнуть. Алгоритм всегда схлопывает ячейку с наименьшей энтропией. Это ячейка, допускающая минимальное количество вариантов выбора (то есть, ячейка с наименьшей хаотичностью). Если у всех модулей вероятность схлопывания одинакова, то наименьшая энтропия будет у той ячейки, которой соответствует минимальное количество возможных модулей. Как правило, вероятности попасть под выбор для разных наличествующих модулей отличаются. Ячейка с двумя возможными модулями, имеющими одинаковую вероятность, предусматривает более широкий выбор (большую энтропию), чем та, в которой два модуля, и для одного из них вероятность попасть под выбор очень велика, а для другого – очень мала.

(Гифка помещена ExUtumno на Github)

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

Вот видео, демонстрирующее этот алгоритм в действии.

О блоках, прототипах и модулях

Мир генерируется из набора, в котором около 100 блоков. Я создал их при помощи Blender. Сначала блоков у меня было совсем немного, и я понемногу добавлял их, когда считал это нужным.

Алгоритму необходимо знать, какие модули могут располагаться рядом друг с другом. Для каждого модуля существует 6 списков возможных соседей, по одному в каждом из направлений. Однако, я хотел избежать необходимости создавать такой список вручную. Кроме того, я хотел автоматически генерировать повернутые варианты для каждого из моих блоков.

Обе эти задачи решаемы при помощи так называемых прототипов модулей. В сущности, это MonoBehaviour , с которым удобно работать в редакторе Unity. Модули вместе со списками допустимых соседних элементов и повернутыми вариантами автоматически создаются на основе таких прототипов.

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

У каждого блока по 6 контактов, по одному на каждую грань. У контакта есть номер. Кроме того, горизонтальные контакты могут быть перевернуты, неперевернуты или симметричны. Вертикальные контакты либо имеют индекс вращения в диапазоне от 0 до 3, либо помечаются как вращательно инвариантные.

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

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

Путь к бесконечности

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

Сначала я попробовал генерировать фрагменты конечного размера и пользоваться контактами смежных фрагментов как ограничениями. Если фрагмент сгенерирован, а смежный ему фрагмент также сгенерирован, то допускаются лишь такие модули, которые укладываются рядом с имеющимися модулями. С данным подходом возникает такая проблема: всякий раз при схлопывании ячейки распространение ограничений будет урезать возможности даже на расстоянии в несколько ячеек. На следующем изображении заметны последствия схлопывания единственной ячейки:

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

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

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

Граничные условия

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

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

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

Я решил эту проблему, создав карту размером 1×n×1, где n — высота. Данная карта использует закольцовывание мира (world wrapping) для распространения ограничений. Механизм работает как в игре Pacman: выходя за правый край карты, персонаж возвращается на нее из-за левого края. Теперь я могу применять на моей карте распространение любых ограничений. Всякий раз при создании новой ячейки на бесконечной карте, эта ячейка инициализируется с набором модулей, соответствующим конкретной позиции на карте.

Состояния ошибок и поиск с возвратом

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

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

На мой взгляд, из-за такого ограничения применение алгоритма WFC с бесконечными мирами не подходит для коммерческих игр.

Предыстория

Я взялся за проработку этой задачи после того, как посмотрел лекцию Оскара Стельберга, рассказывающего, как он использует алгоритм для генерации уровней в игре Bad North. В общих чертах мой алгоритм был реализован во время недели procjam.

У меня есть некоторые идеи о дальнейшей доработке этого алгоритма, но я не уверен, что когда-нибудь соберусь добавить к нему геймплей. А если и соберусь – наверняка это будет не такая эпичная стратегия, которую вы себе уже вообразили. Однако, если вы хотите проверить, как работает с этим алгоритмом ваша любимая игровая механика – просто попробуйте сами! В конце концов, исходный код выложен в открытом доступе и лицензирован MIT.

• Блог компании Издательский дом «Питер»
• Разработка игр
• Алгоритмы
• C#
• Unity

Генерация уровней – как автоматически создавать сцены и уровни в Unity?

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

С тех пор как разработка игр стала легко доступной для инди разработчиков, появилось не мало игр, где дизайну уделялось не такое большое внимание, а все силы уходили именно на геймплей. Позже разработчики пришли к тому, что стали доверять машинам и алгоритмам генерации. Самый яркий пример таких игр с генерируемыми мирами, это конечно же – Minecraft , где весь ландшафт состоит из блоков, хоть это и является иллюзией – ведь хранить даже обозримое кол-во блоков в оперативной памяти невероятно затратно, и все что мы видим в игре на самом деле это один большой “ супермеш ”.

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

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

Геймплей

Сначала разберем то, что будет из себя представлять будущая игра, точнее, нужно придумать примерно абстрактную модель генерируемого мира в игре. Пусть это будет простая 2D игра, где персонажу необходимо попасть из точки А в точку Б в случайно сгенерируемом уровне.

Сцена состоит из 2D блоков, которые будут случайным образом сгенерированы перед прохождением.

Процесс игры разобьем на три этапа:

• Генерация уровня. Сперва необходимо будет сгенерировать уровень, состоящий из блоков.
• Прохождение уровня. Помещаем персонажа на сцену и проходим уровень.
• Завершение игры. Уничтожаем старый уровень и переходим к созданию нового.

Генерация уровня

Уровень будет состоять из блоков, разного типа:

• Стартовый блок. Это именно то место, откуда игрок будет начинать свое путешествие.
• Конечный блок. При попадании игрока на последний блок уровня, игра считается пройденной.

• Промежуточный блок. Из этих блоков будет состоять большая часть уровня.

Именно кол-во промежуточных блоков будет влиять на дизайн и длину уровня.

Программная часть генерации блоков

Создадим скрипт Control , где укажем три переменных спрайтовых ( Sprite ) переменных для каждого типа блока.

1. publicclass Control : MonoBehaviour
2. public Sprite startBlock ;
3. public Sprite midBlock ;
4. public Sprite endBloc ;
5. >

В эти три переменные занесем каждый спрайт блока по отдельности: стартовый, промежуточный и конечный. Дополним скрипт Control стартовым методом Start .

1. publicclass Control : MonoBehaviour
2. public Sprite startBlock ;
3. public Sprite midBlock ;
4. public Sprite endBloc ;
5. publicvoid Start () <>
6. >

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

1. publicclass Control : MonoBehaviour
2. public Sprite startBlock ;
3. public Sprite midBlock ;
4. public Sprite endBloc ;
5. publicvoid Start () <>
6. private IEnumerator OnGeneratingRoutine () <>
7. >

В методе OnGeneratingRoutine , будем выполнять сам процесс генерации уровня. Так как уровни у нас могут быть как большими, так и маленькими и генерироваться разное количество времени, процесс генерации мы поместим в корутину, чтобы игра не “ зависала ” во время работы “ генератора ”. Далее добавим одну числовую переменную completeLevels, с помощью которой будем указывать количество пройденных уровней.

1. publicclass Control : MonoBehaviour
2. public Sprite startBlock ;
3. public Sprite midBlock ;
4. public Sprite endBloc ;
5. privateint completeLevels = 0 ;
6. publicvoid Start () <>
7. private IEnumerator OnGeneratingRoutine () <>
8. publicvoid CompleteLevel ()
9. this . completeLevels += 1 ;
10. >
11. >

Добавим метод CompleteLevel , который будет увеличивать переменную completeLevels на одну единицу каждый раз, когда игрок пройдет очередной уровень. Переменная completeLevels в будущем поможет нам генерировать все более сложные и длинные уровни в процессе прохождения игры.

Теперь можно переходить к методу OnGeneratingRoutine , где мы начнем описывать сам алгоритм генерации уровня.

1. publicclass Control : MonoBehaviour
2. public Sprite startBlock ;
3. public Sprite midBlock ;
4. public Sprite endBloc ;
5. privateint completeLevels = 0 ;
6. /*…остальной код…*/
7. private IEnumerator OnGeneratingRoutine ()
8. Vector2 size = new Vector2 ( 1 , 1 );
9. Vector2 position = new Vector2 ( 0 , 0 );
10. yieldreturn new WaitForEndOfFrame ();
11. >
12. >

Для начала в методе OnGeneratingRoutine объявим две векторные переменные: size , где укажем размер блоков по длине и высоте и position, где укажем точку, откуда будет начинать строится уровень. Теперь можно построить стартовый блок.

1. publicclass Control : MonoBehaviour
2. public Sprite startBlock ;
3. public Sprite midBlock ;
4. public Sprite endBloc ;
5. privateint completeLevels = 0 ;
6. /*…остальной код…*/
7. private IEnumerator OnGeneratingRoutine ()
8. Vector2 size = new Vector2 ( 1 , 1 );
9. Vector2 position = new Vector2 ( 0 , 0 );
10. GameObject newBlock = new GameObject ( “ Start block” );
11. yieldreturn new WaitForEndOfFrame ();
12. >
13. >

Создаем новый GameObject newBlock на сцене.

1. private IEnumerator OnGeneratingRoutine ()
2. Vector2 size = new Vector2 ( 1 , 1 );
3. Vector2 position = new Vector2 ( 0 , 0 );
4. GameObject newBlock = new GameObject ( “ Start block” );
5. newBlock . transform . position = position ;
6. newBlock . transform . localScale = size ;
7. SpriteRendere renderer = newBlock . AddComponent < SpriteRenderer >();
8. renderer . sprite = this . startBlock ;
9. yieldreturn new WaitForEndOfFrame ();
10. >

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

Теперь запустим корутину OnGeneratingRoutine в методе Start и проверим ее выполнение.

1. publicvoid Start ()
2. StartCoroutine ( OnGeneratingRoutine ());
3. >

Переходим к созданию промежуточных блоков. Для этого в корутине OnGeneratingRoutine добавим еще одну переменную count .

1. private IEnumerator OnGeneratingRoutine ()
2. Vector2 size = new Vector2 ( 1 , 1 );
3. Vector2 position = new Vector2 ( 0 , 0 );
4. GameObject newBlock = new GameObject ( “ Start block” );
5. newBlock . transform . position = position ;
6. newBlock . transform . localScale = size ;
7. SpriteRendere renderer = newBlock . AddComponent < SpriteRenderer >();
8. renderer . sprite = this . startBlock ;
9. int count = this . completeLevels + 5 ;
10. yieldreturn new WaitForEndOfFrame ();
11. >

Числовая переменная count будет указывать какое кол-во промежуточных блоков необходимо построить, это число будет зависеть от количества пройденных уровней и, чтобы их изначально не было слишком мало на первых уровнях, еще пяти (5) дополнительных блоков. Строить промежуточные блоки будем через цикл for .

1. private IEnumerator OnGeneratingRoutine ()
2. Vector2 size = new Vector2 ( 1 , 1 );
3. Vector2 position = new Vector2 ( 0 , 0 );
4. GameObject newBlock = new GameObject ( “ Start block” );
5. newBlock . transform . position = position ;
6. newBlock . transform . localScale = size ;
7. SpriteRendere renderer = newBlock . AddComponent < SpriteRenderer >();
8. renderer . sprite = this . startBlock ;
9. int count = this . completeLevels + 5 ;
10. for ( int i = 0 ; i < count ; i ++)
11. newBlock = new GameObject ( “ Middle block” );
12. renderer = newBlock . AddComponent < SpriteRenderer >();
13. renderer . sprite = this . midBlock ;
14. >
15. yieldreturn new WaitForEndOfFrame ();
16. >

Также как мы строили стартовый блок, также строим и промежуточные: создаем новый GameObject , добавляем ему компонент SpriteRenderer , указываем спрайт для отображения на сцене и задаем размер и позицию.

Так как промежуточные блоки строятся по горизонтали, значит и позицию необходимо с каждым новым блоком сдвигать немного вправо. Для того чтобы узнать на сколько ее необходимо сдвинуть, воспользуемся переменной size , где указаны размеры блоков.

1. private IEnumerator OnGeneratingRoutine ()
2. Vector2 size = new Vector2 ( 1 , 1 );
3. Vector2 position = new Vector2 ( 0 , 0 );
4. /*…остальной код…*/
5. int count = this . completeLevels + 5 ;
6. for ( int i = 0 ; i < count ; i ++)
7. newBlock = new GameObject ( “ Middle block” );
8. renderer = newBlock . AddComponent < SpriteRenderer >();
9. renderer . sprite = this . midBlock ;
10. newBlock . transform . localScale = size ;
11. position . x += size . x ;
12. newBlock . transform . position = position ;
13. >
14. yieldreturn new WaitForEndOfFrame ();
15. >

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

1. private IEnumerator OnGeneratingRoutine ()
2. Vector2 size = new Vector2 ( 1 , 1 );
3. Vector2 position = new Vector2 ( 0 , 0 );
4. /*…остальной код…*/
5. int count = this . completeLevels + 5 ;
6. for ( int i = 0 ; i < count ; i ++)
7. newBlock = new GameObject ( “ Middle block” );
8. renderer = newBlock . AddComponent < SpriteRenderer >();
9. renderer . sprite = this . midBlock ;
10. newBlock . transform . localScale = size ;
11. position . x += size . x ;
12. position . y += size . y * Random . Range (- 1 , 2 );
13. newBlock . transform . position = position ;
14. >
15. yieldreturn new WaitForEndOfFrame ();
16. >

Высота блока по Y в переменной position также смещается вверх, либо вниз, в зависимости от размера блока, умноженного на случайное число от -1 до 1. Метод Random.Range генерирует ЦЕЛЫЕ числа от минимального до максимально (ИСКЛЮЧИТЕЛЬНО), это значит, что максимальное указанное число никогда достигнуто не будет. Завершаем цикл постройки промежуточных блоков новым WaitForEndOfFrame .

1. private IEnumerator OnGeneratingRoutine ()
2. Vector2 size = new Vector2 ( 1 , 1 );
3. Vector2 position = new Vector2 ( 0 , 0 );
4. /*…остальной код…*/
5. int count = this . completeLevels + 5 ;
6. for ( int i = 0 ; i < count ; i ++)
7. newBlock = new GameObject ( “ Middle block” );
8. renderer = newBlock . AddComponent < SpriteRenderer >();
9. renderer . sprite = this . midBlock ;
10. newBlock . transform . localScale = size ;
11. position . x += size . x ;
12. position . y += size . y * Random . Range (- 1 , 2 );
13. newBlock . transform . position = position ;
14. yieldreturn new WaitForEndOfFrame ();
15. >
16. yieldreturn new WaitForEndOfFrame ();
17. >

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

1. private IEnumerator OnGeneratingRoutine ()
2. Vector2 size = new Vector2 ( 1 , 1 );
3. Vector2 position = new Vector2 ( 0 , 0 );
4. /*…остальной код…*/
5. newBlock = new GameObject ( “ End block” );
6. renderer = newBlock . AddComponent < SpriteRenderer >();
7. renderer . sprite = this . endBlock ;
8. position . x += size . x ;
9. position . y += size . y * Random . Range (- 1 , 2 );
10. newBlock . transform . position = position ;
11. newBlock . transform . localScale = size ;
12. yieldreturn new WaitForEndOfFrame ();
13. >

Готово, алгоритм генерации завершен, запускаем игру для последней проверки.

Заключение

Чтобы генерация уровня происходила каждый раз когда игрок завершает игру, в методе CompleteLevel достаточно просто запустить корутину OnGeneratingRoutine заново.

1. publicclass Control : MonoBehaviour
2. public Sprite startBlock ;
3. public Sprite midBlock ;
4. public Sprite endBloc ;
5. privateint completeLevels = 0 ;
6. publicvoid Start () <>
7. private IEnumerator OnGeneratingRoutine () <>
8. publicvoid CompleteLevel ()
9. this . completeLevels += 1 ;
10. StartCoroutine ( OnGeneratingRoutine ());
11. >
12. >

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

Контент-ориентированная генерация уровня в Unity в конкурсе «Храм Хаоса»

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

Описаный мною подход к генерации помимо очевидных плюсов имеет и ряд жестких минусов. Так что идеальным его, конечно, не назовешь. Но, идеальных методов и не существует. Этот подход я использовал в своей недоделанной игре, которая была создана на конкурс «Храм Хаоса».

Пролог

Сначала был массив…

Нет, сначала конечно же был вопрос самому себе — зачем мне это? С этим вопросом я обратился к интернету. И бездушная машина выдала мне ответ: процедурная генерация уровней — вопрос достаточно старый и обсосанный, чтобы давать конкретные ответы.

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

Классика жанра.

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

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

И есть одно общее, можно сказать, один мегаэлемент, объединяющий абсолютно все алгоритмы и методы генерации. Это МАССИВ. Чаще двумерный, в отдельных упоротых случаях — многомерный. Массив, задача которого хранить нагенерённые позиции зон. В классическом данжен-генераторе значения элементов в массиве это 0 и 1, стена или пол, а индексы — координаты зоны в пространстве. В лабиринтах зачастую чуток сложнее, но за рамки квадратного массива это не выходит.

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

Это обстоятельство поначалу никак не заботило меня. Моя задача была — запустить хоть какую-то генерацию. Я планировал сделать ряд вложенных генераторов, дабы усложнить уровень, но…

Первая попытка. Печальная.

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

Я взял за основу один из многочисленных алгоритмов данжен-генератора. Смысла его описывать здесь не вижу, их много, и я взял тот, который уже был написан на С#, и мне оставалось лишь незначительно переписать его под Юнити-варимый вариант.

Я планировал так. Первый проход алгоритма — глобальный генератор — создает макро-уровень, где каждый элемент массива — зона 100х100 юнитов (префаб). 1 — зона, заполненная «зданием», 0 — пустая зона улицы. Далее, каждая зона «здания» внутри себя запускает свой генератор, который расставляет зоны поменьше (допустим 20х20), но с другими префабами, которые представляли собой либо комнаты (1), либо проходы без стен (0). Помимо всего прочего, каждый префаб комнат и проходов тоже мог содержать в себе генератор пропсов, но уже без особых алгоритмов.

Как мы помним из моей первой демки — все было плохо. Генерилось все хорошо, но фрактализация была жуткая, occlusion culling всего этого работал плохо, отчего тормозило дико. В конце концов, я добавил поворот на рандомный угол каждой мегазоны, что поначалу показалось мне интересным, но превратило игру еще в большую кашу…

Я отчаялся. Отчаялся и начал думать…

Пытки разума

Думал я мучительно. Смотрел кучу видосиков, читал статейки. Но везде у меня приходило в голову одно и то же — «это все не то!». Я вспомнил главного рандом-монстра игровой истории — Дьяблу. Вспомнил как круто все там было, как здорово, мегарандомно, но и мега-слажено одновременно. И вдруг я стал понимать. В Дьябле все было круто потому что игра была — изометрия про данжены!

Но у меня — экшен! Да еще и из головы! И в памяти начал всплывать угарный угар, в который я долго рубался давным давно — многими противоречиво любимо-ненавидимый Хеллгейт. Точной информации о методах генерации уровней в Хеллгейте всемирный разум мне не дал (возможно, я плохо искал), но вспоминая уровни, я начал, похоже, догадываться, что мне нужно делать для экшена. Так начали проявляться первые наброски идеи под названием CBLG (Content-Based Level Generator).

Чё за кантент, ё?

Казалось бы, при чем тут контент? Ответ на этот вопрос будет немного ниже.

А начну я с другого. Что мы знаем об экшенах? Особенно о современных экшенах, старых консольных экшенах? В основном то, что мы бежим по коридорам и комнатам, стреляем врагов, ищем ключи… Мы знаем, что в экшенах нет сетчатых уровней, лабиринтов в классике, где коридоры имеют шаг, углы 90 градусов, а комнаты статичны и пропорциональны. В экшенах окружающий нас контент — многообразен. Однообразие Вольфенштейна закончилось вместе с ним. А значит, генерация блоками здесь уже неуместна. Нужно, чтобы коридоры были кривыми, разной длины, комнаты были любой геометрии. Были спуски, подъемы, ямы, непонятные формы пола и потолка.

Становится ясно, что реализация всего этого массивами становится затруднительной, где-то даже сомнительной затеей. Что же тогда? Как гененировать? Ведь тогда генерация каждого последующего элемента геометрии уровня должна зависеть от предыдущего? То есть генерация контента должна быть в прямой и абсолютной зависимости от самого контента!

Вот оно! Решение!

Основа

Любой коридор имеет вход и выход. Любая комната имеет вход и выход, даже несколько. Всё, во что мы можем войти, имеет место, откуда мы входим — начало. И если это не тупик — имеет выход — конец. Если мы выходим «откуда-то», то мы входим в новое «куда-то». То есть конец одного места совмещен с началом другого места.

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

Для упрощения задачи, примем за правило, что у зоны может быть один (и только один!) «вход» и сколь угодно выходов. Останется лишь правильно сорентировать следующую зону в пространстве относительно выхода предыдущей. И в этом деле Unity — очень большой молодец 🙂

Симуляция на пальцах

Префабы в Юнити — пожалуй, самая полезная из доступных штук. Они лучше всего подходят к нашей задаче. Максимально. Если бы их не было — их пришлось бы придумать 🙂

Итак, пусть у нас есть 2 префаба геометрии уровня: коридор и комната. У каждого префаба есть «вход» — для удобства работы вход — это точка внутри префаба, относительно которой строится вся геометрия. Обычно это уровень пола, центр дверного проема, а дальше вся геометрия строится вдоль оси Z в положительную сторону, при этом в высоту и ширину (Y и X) в любые стороны. Но Z — строго от нуля и вперед!

Это первый важный элемент нашей системы. Вход в зону — всегда !

Далее, мы создаем объект (префаб) под названием zoneExit, ставим в него пару примитивов, симулируя визуально стрелочку вдоль оси Z. Задача — конец стрелочки внутри префаба zoneExit должен находиться в точке , сама стрелочка тянется вдоль оси Z от минуса к нулю. По X и по Y — строго по нулям! Это нужно нам для визуальной ориентации выхода из зоны и последующего использования этой ориентации в генераторе.

Также, для собственного удобства и контроля, сделаем префаб zoneEntry. Он не участвует в генераторе и его можно потом удалить вообще. Но он помогает контролировать точку входа при создании нового префаба зоны, чтобы не потерять из виду в пылу дизайнерской страсти. Этот префаб — точная противоположность zoneExit-а. Он начинается строго в , и тянется вдоль Z вперед, представляя собой какую-нибудь узнаваемую фигуру:

Его мы размещаем в наших префабах зон строго в 0.0.0 и направлении forward (Z), строим дальше всю зону исключительно в положительной плоскости по Z (по X и Y при этом ограничений нет)

Размещаем zoneExit-ы в наших префабах зон так, чтобы начало предполагаемой последующей зоны встало именно так, как нам нужно. Мы знаем одно — кончик «стрелочки» zoneExit, её originPoint, по-замыслу совпадет с новой зоны, а направление нашей стрелочки — укажет ориентацию следующей зоны относительно выхода этой. Я для простоты вращал exitPoint-ы только по Y, это и логично — смысла следующий коридор наклонять относительно горизонта нет. Мы же бегать хотим 🙂

Если мы правильно все поставили, то в результате генерации зоны скрепятся довольно точно:

И в зависимости от того, на какой угол по Y была повернута zoneExit — наш генератор возьмет этот угол за основу и повернет следующую зону на него же:

Таким образом, в зависимости от положения zoneExit-ов в каждом префабе зоны — у нас будет строится несетчатая и довольно разнообразная геометрия уровня. Все будет зависеть ТОЛЬКО ОТ количества разнообразных префабов зон!

Дальше — Больше!

Вся суть генератора — в отсутствии единого генератора как такового. Главный участник генерации у нас — префаб генератора зоны. Он не содержит геометрии, только скрипт генератора одной (!) зоны. После появления, он инстансит из массива префабов случайный префаб зоны себе в дочерние объекты, обходит все его zoneExit-ы, с некоторой вероятностью спавнит в них свои копии, указывая им position и rotation соответствующих exitZone-ов, и замолкает. Первый префаб мы кладем просто на уровень в глобальную точку . У меня к ней придвинута статичная зона джунглей, где стартует игрок.

Ограничение на размер уровня хранится в глобальной переменной maxZonesCount, а также каждый префаб инкрементирует глобальный счетчик zonesCount в случае, если он не превысит максимальный предел. Если следующая зона должна быть последней ( текущее значение zonesCount == maxZonesCount-1), то префаб вместо следующей зоны генерит Финальную Зону (зону босса например, или как в моей игре — зону с дверью, от которой нужно найти ключи), инкрементирует zonesCount последний раз, и дальше остальные префабы уже не могут ничего строить. В силу невозможности определения последовательности отработки скриптов в инстансах — все происходит достаточно случайно и зона босса может появиться где угодно.

Генерация почти закончена. Однако, в силу описанного выше механизма «вероятности» спавна на месте zoneExit-а нового префаба (типа RandomRange(0,5)>6), не все zoneExit-ы будут обработаны их генераторами для генерации в них следующих зон. Поэтому на сцене останется много свободных неудаленных zoneExit-ов — по сути, дырок в пустоту. Вот как раз префаб финальной зоны (босса) их всех соберет и заспавнит на них тупиковые зоны (это могут быть тупики, комнаты с лутом, секреты — все что угодно, что не имеет выхода. Даже комнаты с порталами). Согласно удобным инструментам Unity, все zoneExit-ы имеют тэг «zoneExit», по которому финальная зона их и находит, и, согласно такому же алгоритму позиционирования, как и основном генераторе, спавнит на их месте зоны тупиков.

Всё, генерация геометрии завершена. Но на этом процесс не заканчивается…

Наполняем геометрию

Каждый префаб зоны у нас определяет только геометрию — стены, пол, иногда потолок. Но нам же интересно, чтобы было еще и визуальное разнообразие! Поэтому для каждого префаба зоны мы делаем кучу префабов пропсов. Я их все строю в редакторе прямо внутри префаба, расставляю так, чтобы потом спавнить префаб пропсов прямо внутри префаба геометрии — и все стояло на своих местах. В игре у меня 5—6 префабов окружения для каждого типа зоны. Простейший скрипт propsSpawner в каждом префабе геометрии содержит паблик-массив префабов наборов пропсов, задача его — заспавнить случайный из них себе в дочерний объект. То же самое с врагами.

И опять — чем больше разнообразных префабов — тем разнообразнее генерация!

Не все так радужно

Ну и о минусах. Без них ничего не бывает.

Во-первых, главный минус — нужно много контента. Чем больше — тем лучше, разнообразие будет зависеть от этого сильно. На то оно и Content-Based.

Во-вторых, это все еще существующая проблема оверлаппинга зон. В принципе, она решаема. Я планировал добавить каждому префабу зоны объект-контроллер с колижин-боксом, покрывающим весь префаб и в случае, если при генерации два таких объекта пересеклись — перезапускать всю генерацию заново. Это увеличит время «загрузки» уровня, но все же позволит полностью избавиться от проблемы. У себя же я частично решил это введя длиииииинные спуски вниз, чтобы развести зоны по вертикали друг от друга.

В-третьих, это уже моя личная проблема — разобраться с навмешами внутри этих префабов, а так же с offmesh-links для того, чтобы враги умели гнаться за тобой между зонами. Но это уже личные мелочи. У меня враги дальше зоны префаба не выбегают…

Если в описанном алгоритме найдете еще что-либо из минусов — буду рад их обсудить 🙂

Учебное пособие по Endless Runner для Unity

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

Endless Runner — это тип игры, в которой игрок постоянно движется вперед, набирая очки и избегая препятствий. Основная цель — достичь конца уровня, не попадая в препятствия и не сталкиваясь с ними, но часто уровень повторяется бесконечно, постепенно увеличивая сложность, пока игрок не столкнется с препятствием.

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

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

Чтобы создать бесконечный раннер в Unity, нам нужно будет создать платформу с препятствиями и контроллер игрока.

Шаг 1: Создайте платформу

Начнем с создания плиточной платформы, которая позже будет сохранена в Prefab:

• Создайте новый GameObject и назовите его «TilePrefab»
• Создайте новый куб (GameObject -> 3D Object -> Cube)
• Переместите куб внутри объекта «TilePrefab», измените его положение на (0, 0, 0) и масштабируйте до (8, 0,4, 20).

• При желании вы можете добавить рельсы по бокам, создав дополнительные кубы, например:

Что касается препятствий, у меня будет 3 варианта препятствий, но вы можете сделать столько, сколько необходимо:

• Создайте 3 GameObject внутри объекта «TilePrefab» и назовите их «Obstacle1», «Obstacle2» и «Obstacle3»
• Для первого препятствия создайте новый куб и переместите его внутрь объекта «Obstacle1».
• Масштабируйте новый куб примерно до той же ширины, что и платформа, и уменьшите его высоту (игроку придется подпрыгнуть, чтобы избежать этого препятствия).
• Создайте новый Материал, назовите его «RedMaterial» и измените его цвет на Красный, затем назначьте его Кубу (это нужно для того, чтобы препятствие отличалось от основной платформы).

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

• И, наконец, «Obstacle3» будет дубликатом «Obstacle1» и «Obstacle2», объединенных вместе.

• Теперь выберите все объекты внутри препятствий и измените их тег на «Finish», это понадобится позже для обнаружения столкновения между игроком и препятствием.

Чтобы создать бесконечную платформу, нам понадобится пара скриптов, которые будут обрабатывать пул объектов и активацию препятствий:

• Создайте новый скрипт, назовите его «SC_PlatformTile» и вставьте в него приведенный ниже код:

SC_PlatformTile.cs

using System.Collections; using System.Collections.Generic; using UnityEngine; public class SC_PlatformTile : MonoBehaviour < public Transform startPoint; public Transform endPoint; public GameObject[] obstacles; //Objects that contains different obstacle types which will be randomly activated public void ActivateRandomObstacle() < DeactivateAllObstacles(); System.Random random = new System.Random(); int randomNumber = random.Next(0, obstacles.Length); obstacles[randomNumber].SetActive(true); >public void DeactivateAllObstacles() < for (int i = 0; i < obstacles.Length; i++) < obstacles[i].SetActive(false); >> >

• Создайте новый скрипт, назовите его «SC_GroundGenerator» и вставьте в него приведенный ниже код:

SC_GroundGenerator.cs

using System.Collections; using System.Collections.Generic; using UnityEngine; using UnityEngine.SceneManagement; public class SC_GroundGenerator : MonoBehaviour < public Camera mainCamera; public Transform startPoint; //Point from where ground tiles will start public SC_PlatformTile tilePrefab; public float movingSpeed = 12; public int tilesToPreSpawn = 15; //How many tiles should be pre-spawned public int tilesWithoutObstacles = 3; //How many tiles at the beginning should not have obstacles, good for warm-up ListspawnedTiles = new List(); int nextTileToActivate = -1; [HideInInspector] public bool gameOver = false; static bool gameStarted = false; float score = 0; public static SC_GroundGenerator instance; // Start is called before the first frame update void Start() < instance = this; Vector3 spawnPosition = startPoint.position; int tilesWithNoObstaclesTmp = tilesWithoutObstacles; for (int i = 0; i < tilesToPreSpawn; i++) < spawnPosition -= tilePrefab.startPoint.localPosition; SC_PlatformTile spawnedTile = Instantiate(tilePrefab, spawnPosition, Quaternion.identity) as SC_PlatformTile; if(tilesWithNoObstaclesTmp >0) < spawnedTile.DeactivateAllObstacles(); tilesWithNoObstaclesTmp--; >else < spawnedTile.ActivateRandomObstacle(); >spawnPosition = spawnedTile.endPoint.position; spawnedTile.transform.SetParent(transform); spawnedTiles.Add(spawnedTile); > > // Update is called once per frame void Update() < // Move the object upward in world space x unit/second. //Increase speed the higher score we get if (!gameOver && gameStarted) < transform.Translate(-spawnedTiles[0].transform.forward * Time.deltaTime * (movingSpeed + (score/500)), Space.World); score += Time.deltaTime * movingSpeed; >if (mainCamera.WorldToViewportPoint(spawnedTiles[0].endPoint.position).z < 0) < //Move the tile to the front if it's behind the Camera SC_PlatformTile tileTmp = spawnedTiles[0]; spawnedTiles.RemoveAt(0); tileTmp.transform.position = spawnedTiles[spawnedTiles.Count - 1].endPoint.position - tileTmp.startPoint.localPosition; tileTmp.ActivateRandomObstacle(); spawnedTiles.Add(tileTmp); >if (gameOver || !gameStarted) < if (Input.GetKeyDown(KeyCode.Space)) < if (gameOver) < //Restart current scene Scene scene = SceneManager.GetActiveScene(); SceneManager.LoadScene(scene.name); >else < //Start the game gameStarted = true; >> > > void OnGUI() < if (gameOver) < GUI.color = Color.red; GUI.Label(new Rect(Screen.width / 2 - 100, Screen.height / 2 - 100, 200, 200), "Game Over\nYour score is: " + ((int)score) + "\nPress 'Space' to restart"); >else < if (!gameStarted) < GUI.color = Color.red; GUI.Label(new Rect(Screen.width / 2 - 100, Screen.height / 2 - 100, 200, 200), "Press 'Space' to start"); >> GUI.color = Color.green; GUI.Label(new Rect(5, 5, 200, 25), "Score: " + ((int)score)); > >

• Прикрепите скрипт SC_PlatformTile к объекту «TilePrefab».
• Назначьте объекты «Obstacle1», «Obstacle2» и «Obstacle3» массиву препятствий.

Для начальной и конечной точек нам нужно создать 2 GameObject, которые должны быть размещены в начале и конце платформы соответственно:

• Назначьте переменные Start Point и End Point в SC_PlatformTile.

• Сохраните объект «TilePrefab» в Prefab и удалите его из сцены.
• Создайте новый GameObject и назовите его «_GroundGenerator»
• Прикрепите скрипт SC_GroundGenerator к объекту «_GroundGenerator».
• Измените положение основной камеры на (10, 1, -9) и измените ее вращение на (0, -55, 0).
• Создайте новый GameObject, назовите его «StartPoint» и измените его позицию на (0, -2, -15).
• Выберите объект «_GroundGenerator» и в SC_GroundGenerator назначьте переменные Main Camera, Start Point и Tile Prefab.

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

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

Шаг 2: Создайте игрока

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

• Создайте новую сферу (GameObject -> 3D Object -> Sphere) и удалите ее компонент Sphere Collider.
• Назначьте ему ранее созданный «RedMaterial».
• Создайте новый GameObject и назовите его «Player»
• Переместите сферу внутри объекта «Player» и измените ее положение на (0, 0, 0).
• Создайте новый скрипт, назовите его «SC_IRPlayer» и вставьте в него приведенный ниже код:

SC_IRPlayer.cs

using System.Collections; using System.Collections.Generic; using UnityEngine; [RequireComponent(typeof(Rigidbody))] public class SC_IRPlayer : MonoBehaviour < public float gravity = 20.0f; public float jumpHeight = 2.5f; Rigidbody r; bool grounded = false; Vector3 defaultScale; bool crouch = false; // Start is called before the first frame update void Start() < r = GetComponent(); r.constraints = RigidbodyConstraints.FreezePositionX | RigidbodyConstraints.FreezePositionZ; r.freezeRotation = true; r.useGravity = false; defaultScale = transform.localScale; > void Update() < // Jump if (Input.GetKeyDown(KeyCode.W) && grounded) < r.velocity = new Vector3(r.velocity.x, CalculateJumpVerticalSpeed(), r.velocity.z); >//Crouch crouch = Input.GetKey(KeyCode.S); if (crouch) < transform.localScale = Vector3.Lerp(transform.localScale, new Vector3(defaultScale.x, defaultScale.y * 0.4f, defaultScale.z), Time.deltaTime * 7); >else < transform.localScale = Vector3.Lerp(transform.localScale, defaultScale, Time.deltaTime * 7); >> // Update is called once per frame void FixedUpdate() < // We apply gravity manually for more tuning control r.AddForce(new Vector3(0, -gravity * r.mass, 0)); grounded = false; >void OnCollisionStay() < grounded = true; >float CalculateJumpVerticalSpeed() < // From the jump height and gravity we deduce the upwards speed // for the character to reach at the apex. return Mathf.Sqrt(2 * jumpHeight * gravity); >void OnCollisionEnter(Collision collision) < if(collision.gameObject.tag == "Finish") < //print("GameOver!"); SC_GroundGenerator.instance.gameOver = true; >> >

• Прикрепите скрипт SC_IRPlayer к объекту «Player» (вы заметите, что он добавил еще один компонент под названием Rigidbody)
• Добавьте компонент BoxCollider в объект «Player».

• Поместите объект «Player» немного выше объекта «StartPoint», прямо перед камерой.

Нажмите Play и используйте клавишу W, чтобы подпрыгнуть, и клавишу S, чтобы присесть. Цель состоит в том, чтобы избежать красных препятствий: