проблема лабиринта и алгоритм рекурсивного возврата

я хочу реализовать алгоритм рекурсивного возврата для решения проблемы лабиринта, но я не могу понять команду 2.3 («удалить стену между текущей ячейкой и выбранной ячейкой»), поможет ли мне это?

  1. Пометить текущую ячейку как «Посещенную»
  2. If the current cell has any neighbours which have not been visited
    1. Choose randomly one of the unvisited neighbours
    2. добавить текущую ячейку в стек
    3. удалить стену между текущей ячейкой и выбранной ячейкой
    4. Сделать выбранную ячейку текущей ячейкой
    5. Рекурсивно вызвать эту функцию
  3. else
    1. remove the last current cell from the stack
    2. Возврат к предыдущему выполнению этой функции

Редактировать На самом деле я хочу, чтобы алгоритм решал проблему лабиринта с помощью стека.


algorithm maze
person Babak Fakhriloo    schedule 09.12.2010    source источник
comment
Откуда у вас этот алгоритм? Предположительно, это попытка решить реальный лабиринт с твердыми стенами, которые нельзя убрать! Удаление стены изменило бы лабиринт и, следовательно, сделало бы алгоритм решения лабиринта несколько бесполезным. Также нет другой инструкции, чтобы поставить стену обратно.   -  person El Ronnoco    schedule 09.12.2010
comment
en.wikipedia.org/wiki/Maze_generation_algorithm   -  person Babak Fakhriloo    schedule 09.12.2010
comment
а, так это алгоритм генерации лабиринта, а не решатель лабиринта. Из вашего вопроса у меня сложилось впечатление, что это была попытка решить существующий лабиринт.   -  person El Ronnoco    schedule 09.12.2010
comment
Я действительно хочу найти лучший способ добраться до места назначения. Думаете, это правильный алгоритм?   -  person Babak Fakhriloo    schedule 09.12.2010
comment
dev — вам нужен алгоритм решения лабиринта, например, en.wikipedia.org/wiki/Maze_solving_algorithm   -  person El Ronnoco    schedule 09.12.2010

Ответы (3)


arrow_upward
4
arrow_downward

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

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

person Niki Yoshiuchi    schedule 09.12.2010
comment
Я думаю, что ошибаюсь. Я хочу решить лабиринт, используя стек, а затем найти лучший способ и возможные способы. - person Babak Fakhriloo; 09.12.2010
comment
+1 за осознание того, что поколение не решает! Меня тоже удивил. Можно было бы переименовать/переформулировать вопрос. - person El Ronnoco; 09.12.2010
comment
@persian dev — вам нужен алгоритм решения лабиринта, например, en.wikipedia.org/wiki/Maze_solving_algorithm - person El Ronnoco; 09.12.2010
comment
В этом случае просто относитесь к лабиринту как к графу и выполняйте DFS (стек) или BFS (очередь). - person Niki Yoshiuchi; 09.12.2010

arrow_upward
1
arrow_downward

Ваш алгоритм для режима god. Обычно вы должны делать

  1. Если текущая ячейка является выходом, то завершено
  2. If the current cell has any neighbours which have not been visited that are not walls
    1. Choose randomly one of the unvisited non-wall neighbours
    2. добавить текущую ячейку в стек
    3. ничего
    4. Сделать выбранную ячейку текущей ячейкой
    5. Рекурсивно вызвать эту функцию
  3. else
    1. remove the last current cell from the stack
    2. Возврат к предыдущему выполнению этой функции
person ruslik    schedule 09.12.2010
comment
я использую 0 для ячеек без стен и 1 для ячеек стен, как в следующем массиве: {0,0,0} {0,0,1} .... - person Babak Fakhriloo; 09.12.2010
comment
Этот алгоритм не для режима бога, он для генерации лабиринта. режим бога не требует никакой рандомизации (и на самом деле ваш алгоритм поиска тоже не требует). - person Niki Yoshiuchi; 09.12.2010
comment
Что вы имеете в виду под клетками стенок? каждая ячейка будет иметь 4 стены, хотя все они (кроме краев) будут общими с другими ячейками. Я бы сказал, что вам нужно записать верхнюю и правую стены камеры (или северную и восточную), если хотите. Это будут нижняя и левая (или южная и западная) стены двух ячеек сверху и справа соответственно. - person El Ronnoco; 09.12.2010
comment
@El Ronnoco: это означает, что вся камера используется как стена. - person ruslik; 09.12.2010
comment
@руслик. Ах я вижу. Таким образом, каждая вторая ячейка на каждой оси — это комната. Имеет смысл. - person El Ronnoco; 10.12.2010

arrow_upward
0
arrow_downward

Удаление стены просто означает удаление стены! Вы начинаете с сетки ячеек, каждая из которых полностью окружена 4 стенами. Когда вы перемещаетесь случайным образом (2.1), вы удаляете стену, соединяющую ячейки.

person El Ronnoco    schedule 09.12.2010