![](https://habrastorage.org/getpro/habr/post_images/e0b/f40/e6c/e0bf40e6c33ed78da13006970a027378.gif)
На этой неделе я начал работать над новой темой: генерацией подземелий и пещер. Я использовал разбиение пространства для генерации комнат, алгоритмы генерации лабиринтов для генерации коридоров и клеточные автоматы для придания пещерам более естествненного внешнего вида.
Разбиение пространства
Существует множество способов генерации комнат для подземелья (случайное размещение, генерация на основе агентов, с использованием separation steering behavior или физического движка, и т.д.). Но мой любимый метод — это разбиение пространства, потому что оно легко контролируется и расширяется.
Способов разбиения пространства тоже очень много: разделение на сетки, двоичное разбиение пространства, разбиение пространства деревом квадрантов, диаграммы Вороного и т.д. Я решил использовать двоичное разбиение пространства, потому что оно хорошо подходит для генерации прямоугольных комнат. Этот метод получил популярность благодаря статье на RogueBasin.
Единственная сложность этого алгоритма — выбор позиции разделения. Если мы не наложим ограничение на позицию разделения, то будем получать странные разбиения пространства:
![](https://habrastorage.org/getpro/habr/post_images/699/f0a/38c/699f0a38c5800499dad98b63e811ace3.gif)
Такого поведения можно избежать несколькими способами. Один из них — ограничить позицию разделения двумя соотношениями длин сторон, например, в интервале от 30% до 70% или от 40% до 60%. Другой способ — использовать вместо равномерного распределения нормальное или биномиальное, благодаря этому повысится вероятность разделения по центру стороны, а не по краям. Эти способы устраняют проблему, но сложно понять, как конкретно параметры влияют на окончательный результат.
Поэтому я использовал другой способ, преимущество которого заключается в том, что он обладает одним параметром и легко понятен: максимальным допустимым соотношением между длиной и шириной ячеек. При сэмплировании нового разделения я сначала вычисляю минимальное и максимальное значения, которые оно может иметь, чтобы соотношение для двух новых ячеек было меньше предельного, а затем выполняю равномерное сэмплирование между этими двумя границами. Вот результат при варьировании максимально допустимого соотношения:
![](https://habrastorage.org/getpro/habr/post_images/cff/6c0/eed/cff6c0eed66a7b26ddad9f3506fc0874.gif)
Хорошие результаты даёт максимальное соотношение от 2.0 до 3.0:
![](https://habrastorage.org/getpro/habr/post_images/531/a66/805/531a66805a7c2e60db79e8eec25badd9.gif)
Генерация комнат
Следующий этап — генерация в каждой ячейке комнаты. Здесь нет особых проблем, я просто задал ограничения, чтобы комнаты не были слишком маленькими и не оказались слишком близко к стенам ячейки.
Вот результаты:
![](https://habrastorage.org/getpro/habr/post_images/4e9/609/782/4e960978275052a4669fda6e7e531ea6.gif)
Выбор рёбер
В генераторах подземелий на основе двоичного разбиения пространства двоичное дерево, использовавшееся на этапе разбиения пространства, обычно используется повторно для генерации коридоров. Я не делал этого, потому что такой подход мне кажется ограничивающим.
Вместо этого на этапе разбиения пространства я строю структуру двусвязного списка рёбер, который позволяет знать, какие ячейки расположены рядом друг с другом. Таким образом я получаю следующие графы:
![](https://habrastorage.org/getpro/habr/post_images/fe1/a31/828/fe1a31828c8ee1abb2a6bb5921d65e07.gif)
У такого подхода есть три преимущества. Первое: если в дальнейшем я захочу изменить способ разбиения пространства, то остальная часть генератора останется действующей, потому что она получает на входе только полурёберную структуру данных. Второе: теперь для выбора рёбер, которые станут коридорами, я могу использовать любой алгоритм генерации лабиринтов. Третья: если я захочу добавить в подземелье петли, то легко смогу это реализовать.
Пока я просто использую алгоритм Крускала и расстояние городских кварталов для выбора рёбер. Вот результаты:
![](https://habrastorage.org/getpro/habr/post_images/095/927/6a4/0959276a4b2a8e10f5a95d7c3c7417f2.gif)
Генерация коридоров
Следующий шаг — генерация коридоров из выбранных рёбер. Наверно, это самая хитрая часть генератора, потому что мне нужно быть аккуратным, чтобы ни один коридор не пересекался с другим.
Вот результаты:
![](https://habrastorage.org/getpro/habr/post_images/240/ac8/5cb/240ac85cb6edcf3a4cd91129b0c22c36.gif)
Генерация пещер
Предыдущие результаты подходили для создания подземелий, склепов и других рукотворных структур, но пещерам и шахтам я хотел придать более природный вид. Классический способ генерации пещер — использование клеточного автомата, как это описано в данной статье на RogueBasin. Большая проблема клеточных автоматов заключается в том, что их результаты не совсем контролируемы.
Я решил всё равно использовать для создания естественного внешнего вида клеточные автоматы, но наложить на них ограничения для получения контролируемого результата. Вместо всего двух состояний: мёртвый и живой, я использую четыре: совершенно точно мёртвый, мёртвый, живой, совершенно точно живой. «Совершенно точные» состояния не могут изменяться в процессе, они используются для ограничения результатов.
Комнаты и коридоры, сгенерированные на предыдущих этапах, заполняются «точно живыми» клетками. То есть у нас всё равно остаются опорные комнаты и мы гарантируем, что они будут соединены друг с другом. Рёбра, которые не были выбраны, заполняются «точно мёртвыми» клетками, чтобы между комнатами не появлялось никаких новых путей. Наконец, вокруг комнат и коридоров мы случайным образом делаем некоторые ячейки живыми. Вот изначальная конфигурация:
![](https://habrastorage.org/getpro/habr/post_images/014/95f/b66/01495fb6695a82de2a9164864b27f08f.png)
Затем мы запускаем клеточный автомат:
![](https://habrastorage.org/getpro/habr/post_images/9e8/408/05e/9e840805e01204122e2eb0252bded4f7.gif)
Вот ещё несколько примеров результатов:
![](https://habrastorage.org/getpro/habr/post_images/3aa/bd6/c9d/3aabd6c9daa127050f84687ef1731e95.gif)
Позже я добавлю заливку для удаления недостижимых частей.
Это первый шаг в длинном пути по созданию генератора интересных подземелий. Я доволен результатами. Особенно я горжусь методом клеточных автоматов с ограничениями, создающим контролируемые и естественные пещеры. Ещё мне нравится то, что каждый этап генерации отделён от остальных и может модифицироваться индивидуально.
Удаление изолированных ячеек
Затем я реализовал заливку для удаления недоступных ячеек:
![](https://habrastorage.org/getpro/habr/post_images/7c3/4bb/f55/7c34bbf55808cd689bc3b7456ea8e2d7.gif)
Множественные коридоры между комнатами
Экспериментируя с параметрами генератора я обнаружил, что если добавить между соединяющимися комнатами немного шума, то получатся интересные результаты.
Вот разница результатов до применения шума к соединяющимся комнатам и сразу после, параметр меняется всего на одну единицу:
![](https://habrastorage.org/getpro/habr/post_images/f7b/f26/263/f7bf2626343bcee26f2afc42e037d314.png)
![](https://habrastorage.org/getpro/habr/post_images/7a6/1de/10c/7a61de10c6b53dab00ede8554a4d78de.png)
Если сделать комнаты немного больше, то результат получится ещё более интересным:
![](https://habrastorage.org/getpro/habr/post_images/ebc/7a8/486/ebc7a8486cbfd1251ac03f87c4cf079b.png)
Здорово, что у нас есть случайность и возникают красивые структуры, но в то же время сохраняется структура графа и обозначения комнат, которые будут полезны:
![](https://habrastorage.org/getpro/habr/post_images/818/658/0ed/8186580ed4aca49f61e2841c7afe043e.png)
Генерация тайлов для пещер
Почти всё своё время я потратил на генерацию тайлов. Это не очень трудно, но для правильной реализации нужны небольшие хитрости.
Вот примеры результатов:
![](https://habrastorage.org/getpro/habr/post_images/7bc/d48/470/7bcd484707cb39ee084496297c9856b4.gif)
Очень здорово то, что можно очень легко переключиться с каменной пещеры на песчаную или ледяную:
![](https://habrastorage.org/getpro/habr/post_images/12b/e53/825/12be53825f1d1c3d9156a98265bd7600.gif)
Следующими этапами генерации подземелья будет добавление декораций и монстров.