В предыдущей части наконец-то были построены какие-то комнаты, между которыми осталось провести коридоры.
Комнаты строились с помощью сканирования содержимого карты, так что здесь продолжу в том же ключе.
Эта задача подразумевает большой объём разнообразных вычислений и проверок, и я пока не вижу способов её упростить. Возможно, это случится уже в процессе. Однако, разбитая на этапы, она не выглядит очень сложной, просто громоздкой:
- Найти вертикальные и горизонтальные стенки, от которых можно построить коридоры.
- От найденных стенок провести по несколько перпендикулярных лучей наружу.
- Все проведённые лучи сравнить друг с другом и найти пересечения со стенками и другими лучами.
- На основе найденных пересечений составить пары потенциальных связей между двумя цветами вида (А, Б).
- Для каждой уникальной пары (А, Б) выбрать одну случайную связь и построить коридор от точки до точки.
1. Нахождение стен
Буду снова сканировать карту в поисках такой конфигурации, когда в клетке находится стенка, а по бокам расположены пустое пространство и какой-либо цвет (т.е. с одной стороны пусто, а с другой закрашенная комната). Если такая клетка найдена, то это начало вертикальной стены. Я смотрю на одну клетку ниже. Если нахожу такую же конфигурацию, тогда смотрю опять ниже, и так пока не просканирую всю стену.
Если же конфигурация клеток слева и справа не найдена, тогда проверяю аналогично сверху и снизу и двигаюсь по одной клетке вправо. Это будет горизонтальная стена.
Найденные стены заносятся в массив в виде структур: цвет, координаты начала, длина и направление. Направление это в какую сторону открыта стена: влево, вправо, вверх или вниз.
Для проверки я наложил на карту найденные стены, использовав толстые чёрные линии:
Как видно, всё определилось правильно, но не все стены нарисованы. Во-первых, отбрасываются те, которые упираются в край карты – от них коридоры не проведёшь. Во-вторых, слишком короткие стены также отбрасываются из эстетических соображений. Коридоры, ведущие от них, будут смотреться некрасиво.
2. Проведение лучей
Имея список стен, можно пройти по нему. Каждая стена отбрасывает от себя наружу несколько линий-лучей:
3. Пересечение лучей
У выпущенного луча есть три варианта:
- Никуда не упирается, ни с кем не пересекается, или упирается в стенку такого же цвета. Такой луч бесполезен и не учитывается.
- Упирается напрямую в стенку другого цвета. Получаем пару стенок (A, B).
- Пересекается с лучом от другой стенки. Если есть точка пересечения, то и коридор можно построить. Также получаем пару стенок (A, B).
Такая картина получается с уже отобранными лучами, у которых есть шансы на соединение комнат:
4. Пары потенциальных связей
Луч от стенки цвета А к стенке цвета Б создает пару (А, Б). Луч от стенки А, который пересекается с лучом от стенки Б, также создаёт пару (А, Б).
Для таких пар создаётся уникальный ключ (А, Б) (для Б, А он тоже будет А, Б, так как не имеет значения, в каком направлении ведётся коридор). По ключу хранится массив, в котором хранятся все пары, соответствующие этому ключу.
Получается такая картина:
Очень много одинаковых пар, но из всего множества нужно выбрать только по одной паре.
5. Случайные связи
Сколько образовалось уникальных ключей (А, Б), столько и должно быть коридоров (в пределе). Для каждого ключа нужно выбрать из массива возможных соединений только одно. Что будет выглядеть примерно так:
После соединения пара цветов (A, Б) становится единым целым, то есть просто (А). Надо удалить все оставшиеся пары (А, Б), а остальные пары, которые были (*, Б) или (Б, *), надо преобразовать в (*, A) или в (A, *). И повторить.
В общем, в результате получается так:
И как можно видеть, это никуда не годится. Технически коричневая комната соединена с зелёной и красной, красная (которая теперь коричневая) с серой, серая (которая теперь тоже коричневая) с розовой, и снова серая (коричневая) с ... как её, ну в общем грязно-голубой. Все связи есть, все комнаты доступны. Но из-за случайного выбора коридоры очень часто будут получаться бессмысленно длинными, что отрицательно скажется на играбельности.
Гораздо логичнее было бы делать их от комнаты к ближайшей комнате.
Придётся поискать другие алгоритмы или доработать этот. Да, не всё так просто!