В проектe Пирог – напомню, что это Rogue на Питоне, следовательно Pyrogue – было сделано клиент-серверное взаимодействие. При этом рассматривались различные варианты генерации карты. Всё это можно найти в прошлых выпусках, но предварительная реализация делалась на JavaScript для онлайн-примеров.
Пора добавить в сам Пирог хоть какую-то генерацию карты, чтобы можно было идти дальше. Но тут меня посетила ещё одна идея, как это можно сделать, и проиллюстрирую я её конечно опять с помощью JS :)
В оригинальном Rogue каждый уровень состоял из 9 комнат, расположенных примерно по сетке 3*3 (некоторые комнаты были вырожденные и становились коридорами). Сама комната всегда прямоугольная.
Я решил взять те же 9 комнат, но накидать их без сетки, в полностью случайном порядке. Это привело к тому, что часть комнат, как и раньше, стоит отдельно, а часть наложилась друг на друга. Результатом такого наложения становятся самые разные неровные формы.
Между ними достаточно провести коридоры, и уровень готов. Но тут довольно случайно я сделал вывод цветных прямоугольников и кое-что заметил:
При том, что суммарная форма получается неровной, она состоит из чётких прямоугольников, каждый из которых можно представить как отдельное помещение. Для этого нужно нарисовать стенки:
Теперь, несмотря на внешнюю неровность, внутренность помещений становится хорошо структурированной и похожей на план некой квартиры. Нужно только добавить двери в межкомнатные стены.
Могут получаться даже внутренние комнаты, которые идеально подойдут на роль каких-то запечатанных секретов.
Связность
Надо определить, какие комнаты связаны друг с другом через внутренние стенки, а какие полностью изолированы. Во внутренних стенках надо сделать проходы, а между изолированными комнатами построить коридоры.
Задача немного усложняется тем, что два прямоугольника могут наложиться друг на друга крест-накрест, и тогда один из прямоугольников окажется разделённым на 2 части, каждая из которых становится отдельной комнатой.
Если бы я действовал геометрическими методами и держал список комнат-прямоугольников, мне пришлось бы разбираться с тем, как прямоугольники режутся на части и в результате порождают новые или наоборот полностью исчезают.
Я выбрал другой подход, об эффективности которого можно только догадываться, но я буду стараться сделать хорошо в его рамках.
Действовать я буду как нейросеть, то есть находить в предоставленном массиве определённые элементы. Поэтому кода много, но он дубовый и последовательный, где каждая секция выполняет свою узкую задачу.
После рисования комнат я делаю скан карты и раскрашиваю каждую область алгоритмом заливки, который был описан тут:
Получается что-то вроде:
Любая замкнутая область гарантированно окажется залитой своим, и только своим цветом, что будет отличать её от других областей. (На деле это не цвета, а просто идентификаторы разных областей, цвета я использую для наглядности).
Далее я опять сканирую карту и нахожу в ней стенки, у которых с двух сторон находятся какие-то цвета. Это внутренние стенки, потому что у внешних цвет может быть только с одной стороны. Все такие клетки я заношу в отдельный список, чтобы потом с ними разобраться. Попутно составляю списки связности. Например, если у стенки слева находится зелёный цвет, а справа жёлтый, то зелёная комната связана с жёлтой.
Также я нахожу внешние стенки. У них с одной стороны цвет, а с другой пусто. Он этих стенок можно строить коридоры. Их я тоже заношу в отдельный список.
Теперь карта выглядит так:
Я пометил на ней и найденные внутренние стенки (которые можно к примеру сразу снести), и внешние.
Следующим этапом все области, связанные через внутренние стенки, должны стать одного цвета. Для этого я добавляю связанные цвета в определённые пулы. Например, если зелёный связан с жёлтым, то они образуют один пул. Далее, если красный связан либо с жёлтым, либо с зелёным, он попадает в один пул с ними, и т.д. Пулы могут объединяться, когда у них находится общий цвет. На рисунке ниже рядом с картой в виде легенды показаны образованные пулы.
Далее осталось заменить цвета на карте. Все цвета, которые попадают в один пул, меняются на ключевой цвет этого пула. В результате получается:
Далее межкомнатные стенки можно или оставить настоящими стенками, проделав в них проходы, или полностью убрать, тогда в финале получим что-то такое:
Отдельные точки внутри помещений это оставленные алгоритмом углы стен. Их также можно убрать, либо представить, что это, скажем, колонны, или какие-то инсталляции.
Но пока важнее сделать следующий этап – провести коридоры между теми помещениями, которые изолированы друг от друга. Сам алгоритм построения коридора от точки до точки есть, но как можно догадаться, проблема в выборе правильных точек.