Предыдущая часть:
В предыдущей части я рассматривал команды обновления между клиентом и сервером, но чтобы их по-настоящему сделать, нужно чтобы было что обновлять.
То есть надо построить уровень.
Я также упоминал на подготовительных этапах, что в Пироге предполагаются тематические уровни, дизайн которых будет существенно отличаться, а так как они процедурно генерируемые, то должны отличаться и алгоритмы, которые их генерируют.
Начать я решил с чего попроще, а именно стандартного алгоритма Rogue. Он генерирует 3*3 прямоугольные комнаты, чьи размеры и пропорции выбираются случайно, а также некоторые комнаты могут отсутствовать.
Между комнатами строятся коридоры.
Я заглянул в исходный код Rogue, чтобы убедиться, что не упускаю что-то важное, а также проверить, насколько мои предположения об алгоритме расходятся с реальностью.
Сами комнаты действительно генерируются как случайные прямоугольники, при этом есть карта уровня, которая покрывает весь алфавитно-цифровой экран:
Аналогом клетки служит структура PLACE, в которой хранятся различные флаги для пола, монстров и т.п.
Коридоры делаются путём проведения случайных же линий с поворотами в некоторых местах. Для этого строится связный граф. Алгоритм я глянул лишь мельком, убедившись, что он довольно сложный, и значит я не упустил никакого сверхпростого решения. Дальше буду делать сам.
Разбиения комнат
Я сделал генерацию прямоугольной комнаты. Её внутренние клетки пока не заполняются, а создаются только 4 стены в виде линий, описываемых параметрами (x, y, w, h). Линии либо горизонтальные, либо вертикальные, поэтому у них либо h=0 (высота), либо w=0 (ширина).
Далее я решил добавить в комнаты разбиения линий. Если взять любой из углов комнаты:
и рассечь каждую прилегающую к нему сторону на 2 части, то от мест рассечения можно провести ещё две перпендикулярные линии, сделав выемку в прямоугольнике:
Это создаст новый угол. Затем процесс можно повторить. Берем любой другой угол, снова делим его, получается ещё один угол и т.д.
Я написал демо-версию алгоритма на JavaScript, чтобы была возможность тестировать его онлайн. Ссылка:
https://js.do/nandakoryaaa/681269
В зависимости от выбора точек рассечения и количества итераций получаются различные очертания комнат (хотя комнатами их назвать уже нельзя, скорее это пещеры).
и т.д.
В алгоритме бывают накладки – полигон (назовём его теперь уже так) может самопересекаться. Но эти проблемы будут решены позже.
Алгоритм (вкратце)
Полигон это зацикленный список граней, следующих друг за другом и имеющих направление. Например, первоначальная комната состоит из 4-х граней: вправо, вниз, влево, вверх.
Зацикленность означает, что для каждой грани существует следующая. Если мы берём последнюю грань, то следующая для неё – первая.
Таким образом, можно взять любую случайную грань в списке, взять следующую грань, и построить из них угол. Возможные типы углов определяются возможными комбинациями граней: вправо-вниз, вниз-влево, влево-вверх, и т.д. Для каждого типа угла известно, из какой его грани в каком направлении надо выводить новую грань.
После того как получены две новые грани, они вставляются в список между двумя родительскими гранями.
Собственно, всё.
Немного разные характерные очертания полигонов получаются, если всегда делить грани ровно пополам, или же выбирать случайную точку. Это также можно будет использовать в дальнейшем для настройки генератора комнат. Поменять можно здесь:
Дальше надо будет поработать над проходами между комнатами.
Читайте дальше: