Как создать случайный лабиринт pacman

Здравствуйте, я работаю над алгоритмом генерации случайного лабиринта pacman. Я видел пару статей, но не мог сломать логику. Я использую первый алгоритм глубины алгоритма лабиринта, а затем зеркально отражаю лабиринт, чтобы сделать каждый лабиринт симметричным. У меня проблемы с очисткой тупиков. Если это невозможно, я также попытаюсь использовать другой алгоритм, если у кого-то есть своя логика генерации случайного лабиринта. Любая помощь приветствуется. Благодаря

Ответ 1

Я решил свою проблему и хотел поделиться. Для начала я устанавливаю верхнюю строку, первый столбец и последний столбец в качестве стенового препятствия, затем я устанавливаю путь во второй столбец, второй - последний ряд и второй ряд, чтобы он окружал внешнюю стену. Также имейте в виду, что я создаю только 50% лабиринта, поэтому, когда я закончил, я копирую лабиринт, чтобы обе стороны были равны. Затем я создал средний участок, окруженный стеной для области, где появляются призраки. Тогда любая часть лабиринта, на которой не смотрели, я сгенерировал пути, используя алгоритм первого поиска глубины. После этого я знаю, что в лабиринте пакмана нет тупиков. То, что я сделал, это проверить каждую ячейку, которая является частью пути, которым может путешествовать pacman. Если какая-либо ячейка имеет только 1 граничащую ячейку, то это тупик. Если это тупик, посмотрите, может ли он быть подключен к другому пути. Если не установить тупик как стену и снова проверить лабиринт для любых тупиков. После того, как вы выполните эти шаги, у вас будет случайный лабиринт без тупиков, который будет похож на типичный лабиринт pacman.

Ответ 2

Я бы предложил совершить случайную прогулку по dfs в чистой зоне (без какой-либо стены, в n * n-матрице 0), после чего заполнить области, которые не покрыты случайным ходом (сделать их как стена), это также может привести к неиспользуемым пространствам, но это гарантирует долгую прогулку. вы можете установить размер произвольной ходьбы (например, когда размер вашей ходьбы достигнет (n ^ 2)/2, вы можете остановить прогулку).

Ответ 3

Я создал случайный генератор лабиринта PacMan давно на C = 64, используя глубину вначале и устраняя тупики, но недавно мой друг снова попросил моего друга сделать это снова. Нашел лучший способ. Проверьте его на мой сайт

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

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