| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Центр помощи > [Prolog] Генерация лабиринтов |
| Автор: PIZDELNIK 7.12.2007, 19:09 |
| Есть алгоритм Recursive backtracker The depth-first search algorithm of maze generation is frequently implemented using backtracking: Mark the current cell as 'Visited' If the current cell has any neighbours which have not been visited Choose one of the unvisited neighbours Push the current cell on the stack Knock down the wall between the current cell and the chosen cell Make the chosen cell the current cell Recursively call this function else Pop the last current cell off the stack Backtrack to the previous execution of this function Вот его реализация втупую make_lab(Start, X, Y1, Stack):-neighbour(Start, X, Z), not(null(Z)), random_choose(Z, Z1), kill_wall(Start, Z1, X, Y, X3, X4), make_lab(X4, Y, Y1, [X3|Stack]). make_lab(Start, X, Y, [S1|Stack]):-neighbour(Start, X, Z), null(Z), make_lab(S1, X, Y, Stack). make_lab(Start, X, X, []):-neighbour(Start, X, Z), null(Z). Как реализовать этот алгоритм без переменной Stack, используя встроенный бэктрекинг? Есть лабиринт-список элементов вида X-Y:(A, B, C, D), где XY-координаты клетки, а ABCD ее стороны find_way(From, From, [], X). find_way(From, To, [Y|Way], X):- connect(From, Y, X), member(Y, X), not(member(Y, Way)), find_way(Y, To, Way, X). find_way(From, To, [Y|Way], X):- connect(From, Y, X), member(Y, X), find_way(Y, To, Way, X). connect(X1-Y:(0, _, _, _):1, X2-Y:(_, _, 0, _):1, X):- K is X1-1, X2=K, member(X2-Y:(_, _, 0, _):1, X). connect(X1-Y:(_, _, 0, _):1, X2-Y:(0, _, _, _):1, X):- K is X1+1, X2=K, member(X2-Y:(0, _, _, _):1, X). connect(X-Y1:(_, 0, _, _):1, X-Y2:(_, _, _, 0):1):- K is Y1+1, Y2=K, member(X-Y2:(_, _, _, 0):1, X). connect(X-Y1:(_, _, _, 0):1, X-Y2:(_, 0, _, _):1):- K is Y1-1, Y2=K, member(X-Y2:(_, 0, _, _):1, X). Как написать поиск пути в лабиринте, приведенный выше циклится ? |