Динамическая мутация лабиринта

Question

У меня есть идея создать еще одну игру-лабиринт. Однако есть ключевое отличие: лабиринт меняется на лету во время игры. Когда я думаю о проблеме, мне приходят в голову следующие ограничения:

1. есть главный маршрут в лабиринте, который никогда не меняется
2. основной маршрут - единственный маршрут, который ведет к финишу
3. мутация лабиринта не должна блокировать пути назад к основному маршруту

Также было бы неплохо управлять (влияет на сложность игры):

1. сколько лабиринта изменяется во время одной мутации
2. опционально отключить ограничение # 3 (то есть игрок может быть заблокирован в лабиринте на некоторое время)

EDIT: Вопрос: можете ли вы предложить алгоритм (или дать свои идеи) для описанного поколения / мутации лабиринта, который не будет нарушать данные ограничения?

Answer 1

Вы можете:

1. Заблокировать путь случайным образом (или использовать некоторые хитрые критерии).

2. Сканировать лабиринт, чтобы увидеть, если онбыла разделена на 2 области, которые больше не связаны.

3. Если отключено, вы можете случайно разбить стену, если она соседствует с обеими областями.

Если ваш лабиринт имеет только один путь между любыми двумя точками, шаг 2 всегда будет разбивать лабиринт, и поэтому всегда будет необходим # 3.

Answer 2

Это, наверное, довольно просто. Сгенерируйте лабиринт, используя стандартный алгоритм поиска по глубине . Сохраните список ячеек, которые формируют (единственный) путь от начала до выхода в списке. Когда вы решите изменить лабиринт, сделайте следующее:

1. Сброс всего лабиринта до состояния по умолчанию (все стены на месте), за исключением любой ячейки вдоль критического пути и, при желании, нескольких ячеек в пределах прямой видимости текущего местоположения игрока.
2. Повторно выполнить алгоритм поиска в ширину с самого начала, с одной модификацией: при выборе того, кого не посещать, исследовать, предпочитайте ребра, у которых уже удалена стена.

Модификация на втором шаге гарантирует, что алгоритм сначала исследует существующие пути, затем добавляет боковые переходы и так далее. Нет даже необходимости сохранять критический путь, если вы этого не хотите - вы можете восстановить весь лабиринт, за исключением того, где стоит пользователь, и он останется действительным.

Я думаю, это всегда должно создавать корректное дерево так же, как исходный алгоритм, но я не уверен на 100% о последствиях сохранения ячеек вокруг пользователя, которые могут не быть на критическом пути. Я уверен, что перенастроенный лабиринт всегда будет решаем с того места, где стоит пользователь.

Это тоже довольно изящная идея. Мне нравится идея, что лабиринт существенно переставляет себя там, где пользователь не смотрит. Если вы делаете это от первого лица, вы даже можете использовать вид камеры, чтобы изменить стены позади пользователя, когда он не смотрит!

Answer 3

Составьте график, соединяющий все ячейки лабиринта и проходные соединения между ними. Чтобы изменить лабиринт, сначала выберите случайную стену, чтобы сбить с ног, которая генерирует новое ребро на графике. Затем найдите в графе цикл, содержащий это ребро, и удалите в этом цикле случайное ребро, не являющееся основным путем, которое возведет ребро где-нибудь еще.

Этот алгоритм гарантирует, что если все ячейки были доступны в начале, они останутся таковыми. Вы, вероятно, хотите эту функцию, так что вы никогда не сможете попасть в ловушку.