Простая реализация метода генерации лабиринта (случайная DFS)

Question

Простая реализация метода генерации лабиринта (случайная DFS)

В интервью мой интервьюер задал мне этот вопрос:

Разработайте функцию для генерации случайного лабиринта

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

он должен принять размер лабиринта (квадратный лабиринт NxN)
он должен состоять только из Стен и Пути
для простоты алгоритму не нужно устанавливать вход и выход

Я опубликую ответ с решением, чтобы другие люди могли найти этот вопрос.

Пример сгенерированного лабиринта:

. # # . # . . . . .
. . . . . . # # # .
# . # # # # . . . .
. # . . . . # . # .
. # . # # . # . # .
. # . # . . # . . #
. . . # . # . # . .
. # . # . . . # # .
# . . . # . # . . .
. . # . # . . . # .

1

depth-first-search java maze php recursion

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Простой рандомизированный 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:

# . . # . . . # . . . . . # . . . . . . . # . # .
. # . # # # . . . # # # . . # # . # # # . . . . .
. # . . . . # . # . . . # . . . # . . . . # . # .
. . # # # . # . . # . # # # # . . . # # . # . . #
. # . . # . . # . # . . # . # # # # . . # . # . .
. . # . # # . # . . # . . . . . . # . # . . . # .
# . . . . # . . # . . # . # . # # . . . . # # . .
. . # # . . # . . # . # . # . . . . # # . . # . #
. # . . # . # . # . . # . . # # . # . . # . # . .
. . . # . . # . . . # . . # . # . # . # . . . # .
# # . # . # . # # # . # # . . . . # . # . # # . .
. . . # . . . . . . . . # . # # # # . . . # # . #
# # # . . # # # # . # . . . # . . . . # # . . . #
. . . # # . . . . # # . # . # . # # # # # . # # .
. # . . . . # # . # . . # . # . . . . # . . # . .
. . # . # # . . . . # # # . . # # # # . . # # # .
# . . # . . . # # . . . . # . # . . . . # . # # .
. # . . # . # . # # . # . . . # . # # # . . . . .
. . # . . # . . . . # . # # . # . # . . # # . # .
# . . # . . . # # . # . . . . # . . # . . . . # .
. . # . . # # . # . . # # . # . # . . # . # # . .
# . . . # . . . . # . . . # . . # # . # . # . # #
# # . # . . # . # . # # . # # . . . . # . . . . .
# . . . # # # . . . # # . . # # . # # . # # # # .
. . # . . . . . # . . . # . . . . . . . . . . . .

Если вы хотите «более симпатичный» лабиринт, вы можете просто добавить полные стены к границе лабиринта

3