Предыдущая часть:
Прошлая часть называлась "Коридоры", а эта "Дороги", знаете почему? Потому что Dorogue :)
В общем, алгоритм для построения коридоров, намеченный в прошлой части, я задвинул пока в пыльный угол, так как у него есть неприятные затыки, с которыми нет особого желания разбираться.
Немного поразмыслив, решил делать похожий, но без недостатков. Он будет саморегулироваться, исключая тупиковые случаи.
Описание алгоритма
Дорога строится от стенки до стенки. В этой статье я строю её всегда от верхней до нижней стенки. Это не ограничение, просто сокращается количество кода и объяснений.
Возьмём карту местности:
Чёрные клетки – начальная часть дороги (выбирается случайным образом на верхней стенке). Серые клетки – свободное пространство. Красные клетки – свободное, но запрещённое для строительства пространство. Карта сразу огорожена ими, так как коридор не должен проходить вплотную к какой-либо стенке (выглядит неэстетично).
Далее делается шаг: мы смотрим на блок, состоящий из 3*3 клеток, в центре которого находится последняя поставленная клетка:
Из центральной клетки можно продвинуться влево, вниз или вправо, при условии что эти клетки свободны.
Случайным образом выбираем одну из них, и пишем туда чёрную клетку. Оставшиеся в списке клетки делаем недоступными, потому что дорога там проходить уже заведомо не может (она не должна соприкасаться сама с собой):
Затем перемещаем координаты блока так, чтобы последняя добавленная клетка снова стала в нём центральной, и повторяем шаг.
Маршрут можно закончить, когда центральная клетка блока окажется вплотную к финишной стене.
Собственно, это всё!
Тупики
Алгоритм может довольно легко зайти в тупик:
Это в принципе не плохо, если карта предполагает наличие тупиков. Но у меня дорога должна идти одной непрерывной ниткой от стены к стене.
Поэтому, если алгоритм заходит в тупик, он предпринимает обратные действия. Так как он знает, какая клетка была заполнена последней, и может узнать, какая была до неё (это единственная чёрная клетка в одном из 4-х направлений), то может просто вернуть всё назад. Он освобождает клетки, которые ранее пометил как недоступные. Но при этом уже использованные чёрные клетки он помечает как недоступные, чтобы не попасть в них ещё раз.
Таким образом алгоритм будет возвращаться назад по своим же следам, пока не выпутается из тупика.
Я не храню дерево ветвлений, поэтому большое пространство может оказаться помеченным как недоступное и алгоритм туда больше никогда не зайдёт (хотя и мог бы). Но пока получается нормально и так.
Масштабы
На достаточно большой карте алгоритм может порождать весьма затейливые маршруты:
Ну или давайте сразу жахнем:
Красные области на карте – следы возврата назад. Я решил их оставить, так как они создают впечатление, будто это действительно некая местность. Например, там может расти лес.
Это всё здорово, но вернёмся к главному вопросу – как быть с коридорами? Ведь им не нужна такая безумная запутанность.
Здесь всё оказалось довольно просто. Если взять маленький кусочек карты, то и маршруты будут получаться вполне похожие на коридоры:
Кроме того, можно ввести систему весов, которые будут влиять на случайный выбор в нужном направлении, чтобы получать более прямые линии.
Но в принципе это всё уже неважно, и можно теперь заняться следующими вопросами.
Вы можете поиграть с алгоритмом онлайн по следующий ссылке:
https://js.do/nandakoryaaa/routes3
Физический размер карты 500*500 пикселов. Чтобы изменить её логический размер, используйте константу FIELD_WIDTH на 12-й строчке:
Максимум это 500. Тогда размер одной клетки будет 1*1 пиксел, и карта будет иметь размер 500*500 клеток. Минимум это около 5 (чтобы был вменяемый результат). Тогда размер одной клетки будет 100*100 пикселов, а карта будет иметь размер 5*5 клеток.
Вы можете очистить карту кнопкой CLEAR, и затем нажимать на кнопку STEP, чтобы строить её шаг за шагом.
Читайте дальше: