Эксперименты с генерацией уровня

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

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

lentinant, у тебя не возникало такой идеи, что если ты сталкиваешься с противником, тебя переносит на поле битвы, и там нужно совершить определённые действия? Плюс, структуру уровней можно сделать как в roguelike-играх.

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

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

lentinant, а в чем сложность с заполнением прямоугольника? За счет разделения алгоритма на две части, одна из которых размечает сегменты, а другая заполняет их, значительно понижается вычислительная сложность каждого из алгоритмов в отдельности.

prog:

lentinant, а в чем сложность с заполнением прямоугольника? За счет разделения алгоритма на две части, одна из которых размечает сегменты, а другая заполняет их, значительно понижается вычислительная сложность каждого из алгоритмов в отдельности.

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

первый алгоритм:

• случайным образом выбираем размер стартовой комнаты
• выбираем кол-во дверей для комнаты, причем минимум дверей желательно уменьшать по мере удаления от стартовой комнаты (или не уменьшать вовсе).
• размечаем "двери" для этой комнаты (не ближе чем на определенном расстоянии друг от друга, если они на одной стороне)
• для каждой двери выбираем комната за ней или коридор
• для комнаты повторяем с пункта выбора размера комнаты
• для коридора - просто прокладываем коридор, ставим в конце дверь и, возможно, добавляем двери на стены.

при разметке комнат желательно проверять чтобы не было пересечения с уже размеченными комнатами, но это не то чтобы обязательно

на выходе получаем массив прямоугольников и точек соединения

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

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

Когда я в последний раз пользовался похожим алгоритмом у меня было примерно такой набор примитивов при разметке:

• зал - большая комната, из которой обязательно ведут только коридоры и из которой не меньше 4 выходов.
• комната - не меньше одного и не больше 3 выходов, минимум один коридор, если на стороне есть "дверь" ведущая в другую комнату, то на этой стороне не может быть других дверей
• коридор - не меньше двух выходов, которые могут вести как в комнаты, так и в коридоры, с боковых сторон двери ведут только в другие коридоры
• тупик - комната или коридор с одним единственным входом, генерируется не ближе 5 сегментов от старта

При этом двери, ведущие в коридор у меня могли быть заблокированы и открывались ключами (сперва в ходе декорирования комнат генерировались ключи, что прибавляло 1 к счетчику, затем, если ключей было больше 1, могли генерироваться двери, что отнимало 1 от счетчика, минимум ключей, после которого появлялись двери, менялся в зависимости от сложности)

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

• срезанные углы (все или по отдельности, на одну или больше ячеек)
• дыра в центре
• отдельные "колонны" из непроходимых ячеек
• разделение комнаты пополам с проходом в центре или двумя проходами ближе к краям (сперва проверить чтобы не перекрыть случайно дверь)

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

простой алгоритм проверки проходимости, которого с головой хватает в таких условиях

• от одной из дверей запускаем "волну", которая перебирает все смежные ячейки и записывает в каждую из них число на 1 больше того, что есть в текущей ячейке, уже пройденные ячейки игнорируются, для перебора используется не рекурсия, а очередь
• когда карта путей будет сгенерирована, проверяем каждую дверь и смотрим можно ли туда дойти (просто по факту того, есть ли там информация для карты путей, в случае слияния комнат чуть сложнее, но тоже все решается путем анализа карты путей)

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

prog, Как представлю, что писалось сразу, на ход мысли - аж мурашки по коже...