Вся подборка по рогаликам:
Прошло уже много времени, поэтому немного освежу тему.
Тезисы для построения коридоров я описал в этом материале:
Но реализовать указанную там схему не получилось. Точнее, я просто не хотел делать поиск пути в графе, поэтому следующей попыткой были дороги с алгоритмом, похожим на клеточный автомат:
Они получились довольно симпатичные, но я решил оставить их для других целей (а именно, для настоящих дорог), а коридоры сделать всё-таки через поиск пути в графе.
Можно сразу посмотреть онлайн, что получилось:
https://js.do/nandakoryaaa/routes
Обратить внимание нужно на существенные части: рекурсивную функцию step() и класс PointMap.
Как это работает
Область от входа до выхода заполнена клетками (так как вся карта состоит из клеток).
Данное множество клеток можно представить как граф. Каждая клетка это вершина графа, и она соединена со своими соседями по горизонтали и вертикали. Так что переходя из клетки в клетку, мы путешествуем по вершинам графа.
Если двигаться из клетки входа в случайную соседнюю клетку, затем из неё также в случайную соседнюю, то рано или поздно мы придём либо в клетку выхода, либо в тупик. Именно это и происходит в Дорогах, но там мы владеем только текущей ситуацией в клетке. Поэтому при попадании в тупик часть пройденного пути откатывается назад по собственным следам, а пройденные клетки помечаются как негодные, чтобы в них нельзя было попасть ещё раз.
Это приводит к довольно специфичному рисунку дороги:
Алгоритм поиска пути в графе тоже перебирает связи (направления), доступные из текущей вершины (клетки). Но если в одном из направлений произошла неудача, он отбрасывает это направление, а клетки, которые там были, остаются свободными. Поэтому такой алгоритм сможет исследовать все возможные варианты путей из текущей клетки. Более подробно рассмотрим ниже.
Р А З Р Я Д К А
Как уже говорилось, каждая клетка это вершина графа. Клетки, стоящие рядом, создают плотную сетку, по которой коридор может свернуть в любой момент. Чтобы придать ему более структурированные очертания, я использую набор горизонтальных и вертикальных линий, которые накладываются поверх клеток:
Количество и расположение линий можно задать случайным или фиксированным образом, и это повлияет на структуру коридора. Вершинами графа становятся только те клетки, которые находятся на пересечениях линий:
Рекурсия
Рекурсивные функции можно хорошо понимать, но конкретная реализация часто вызывает затруднения, особенно когда возникает какой-то неуловимый баг.
Разберём построение рекурсивной функции step() с нуля.
На вход функция получает текущую вершину point и ссылку на компонент, который предоставляет доступ к карте – pointMap.
Первичная задача данной функции очень проста: выяснить, является ли текущая вершина финальной. Для этого делается запрос к карте:
pointMap.isEndPoint(point)
И в случае успеха наша миссия закончена. Функция возвращает текущую вершину как результат. Это точка выхода из рекурсии.
Если же этого не произошло, функция обращается к карте и метит данную вершину как занятую.
pointMap.setReservedPoint(point)
Затем функция запрашивает у карты список направлений, в которых можно двигаться из текущей вершины.
И далее, пока мы не получили непустой результат (res) и список направлений не пуст, мы выбираем одно случайное направление, сразу удаляем его из списка, и находим новую вершину (nextPoint) в этом направлении.
Если эта вершина не занята (что опять же спрашивается у карты: pointMap.isPointReserved(nextPoint)), то мы переходим в рекурсию, где всё начинается сначала с новой вершиной.
При переходе в рекурсию все предыдущие вызовы функции step() ещё не завершены. Каждый вызов хранит в стеке свою текущую вершину и эта вершина также зарезервирована в карте, которая общая для всех.
Поэтому алгоритм не может использовать занятые клетки повторно.
Когда функция возвращает наконец результат в виде финальной точки, то предыдущая функция получает его и добавляет к нему свою точку – ведь именно из неё мы пришли в финальную. Функция возвращает эту информацию в предыдущий вызов, который тоже добавляет свою текущую точку, и т.д.
В конечном итоге мы будем иметь массив вершин, которые описывают маршрут движения.
Если какое-то направление вернуло пустой результат, это значит, что там не просто нет пути, а точно нет вообще никакого пути. Функция будет перебирать оставшиеся направления. Если путь так и не найден, функция освободит занятую вершину и вернёт пустой результат, который является в свою очередь результатом для какого-то направления из предыдущего вызова (начинайте читать этот абзац с начала). Это также точка выхода из рекурсии.