В интервью мой интервьюер задал мне этот вопрос:
Разработайте функцию генерации случайного лабиринта
Это довольно сложный вопрос, который нужно решить за 30 минут, если вы еще не решили этот вопрос. В Интернете есть много решений, но ни один из них не кажется простым. Метод должен уважать это ограничение:
Я отправлю ответ с помощью решения, чтобы другие люди смогли найти этот вопрос.
Пример сгенерированного лабиринта:
. # # . # . . . . . . . . . . . # # # . # . # # # # . . . . . # . . . . # . # . . # . # # . # . # . . # . # . . # . . # . . . # . # . # . . . # . # . . . # # . # . . . # . # . . . . . # . # . . . # . Простую рандомизированную DFS можно использовать для создания лабиринта. Для запуска лабиринта с полной стеной инициализируется размер NxN, затем эта функция пересекает лабиринт и добавляет путь, когда это возможно:
function generateMaze(&$maze, $point) { $dirs = [ [0,-1], [1,0], [0,1], [-1,0], ]; shuffle($dirs); foreach($dirs as $dir) { $newPoint = [$point[0] + $dir[0], $point[1] + $dir[1]]; if (isGoodPath($maze, $newPoint)) { $maze[$newPoint[0]][$newPoint[1]] = '.'; generateMaze($maze, $newPoint); } } return $maze; }
Ключом к решению этой проблемы является хорошая реализация функции isGoodPath() эта функция просто проверяет, находится ли новый путь внутри лабиринта, и если мы можем удалить стены (то есть мы не можем иметь два параллельных соседних «свободного» пути)
Вы можете выполнить полную реализацию здесь: https://ideone.com/oufifB
Лабиринт 25×25:
# . . # . . . # . . . . . # . . . . . . . # . # . . # . # # # . . . # # # . . # # . # # # . . . . . . # . . . . # . # . . . # . . . # . . . . # . # . . . # # # . # . . # . # # # # . . . # # . # . . # . # . . # . . # . # . . # . # # # # . . # . # . . . . # . # # . # . . # . . . . . . # . # . . . # . # . . . . # . . # . . # . # . # # . . . . # # . . . . # # . . # . . # . # . # . . . . # # . . # . # . # . . # . # . # . . # . . # # . # . . # . # . . . . . # . . # . . . # . . # . # . # . # . . . # . # # . # . # . # # # . # # . . . . # . # . # # . . . . . # . . . . . . . . # . # # # # . . . # # . # # # # . . # # # # . # . . . # . . . . # # . . . # . . . # # . . . . # # . # . # . # # # # # . # # . . # . . . . # # . # . . # . # . . . . # . . # . . . . # . # # . . . . # # # . . # # # # . . # # # . # . . # . . . # # . . . . # . # . . . . # . # # . . # . . # . # . # # . # . . . # . # # # . . . . . . . # . . # . . . . # . # # . # . # . . # # . # . # . . # . . . # # . # . . . . # . . # . . . . # . . . # . . # # . # . . # # . # . # . . # . # # . . # . . . # . . . . # . . . # . . # # . # . # . # # # # . # . . # . # . # # . # # . . . . # . . . . . # . . . # # # . . . # # . . # # . # # . # # # # . . . # . . . . . # . . . # . . . . . . . . . . . .
Если вы хотите «более красивый» лабиринт, вы можете просто добавить полные стены к границе лабиринта