/* maze(Height, Width) generates and displays a pseudo-randomly-generated */
/* Height by Width maze. */
maze(Height, Width):-
Height > 0,
Width > 0,
maze_1([c(0,0)], [c(0,0)], Height, Width, Maze),
output(Height, Width, Maze).
/* maze_1([c(0,0)], [c(0,0)], Height, Width, Maze) is true if Maze is a */
/* list of the cell-connections defining a pseudo-randomly-generated */
/* Height by Width maze. */
maze_1([], _, _, _, []):-!.
maze_1(Stack, Used0, Height, Width, [x(Cell,NewCell)|Maze]):-
Used0 = [Cell|Used],
neighbours(Cell, Height, Width, [], Neighbours),
difference(Neighbours, Used, Neighbours1),
rand_remove(Neighbours1, NewCell, _), !,
maze_1([NewCell|Stack], [NewCell|Used0], Height, Width, Maze).
maze_1([Cell|Stack], Used, Height, Width, Maze):-
maze_1(Stack, [Cell|Used], Height, Width, Maze).
/* Try replacing the previous clause by the following clause */
/*
maze_1(Stack, Used, Height, Width, Maze):-
rand_remove(Stack, Cell, Stack1),
maze_1(Stack1, [Cell|Used], Height, Width, Maze).
*/
neighbours(Cell, Height, Width, Neighbours0, Neighbours):-
down_neighbour(Cell, Height, Neighbours0, Neighbours1),
right_neighbour(Cell, Width, Neighbours1, Neighbours2),
left_neighbour(Cell, Neighbours2, Neighbours3),
up_neighbour(Cell, Neighbours3, Neighbours).
down_neighbour(c(X,Y), Height, Cells, [c(X,Y1)|Cells]):-
Y < Height - 1, !,
Y1 is Y + 1.
down_neighbour(_, _, Cells, Cells).
right_neighbour(c(X,Y), Width, Cells, [c(X1,Y)|Cells]):-
X < Width - 1, !,
X1 is X + 1.
right_neighbour(_, _, Cells, Cells).
left_neighbour(c(X,Y), Cells, [c(X1,Y)|Cells]):-
X > 0, !,
X1 is X - 1.
left_neighbour(_, Cells, Cells).
up_neighbour(c(X,Y), Cells, [c(X,Y1)|Cells]):-
Y > 0, !,
Y1 is Y - 1.
up_neighbour(_, Cells, Cells).
/* output(Height, Width, Maze) outputs the Height by Width maze defined by */
/* the cell-connections in Maze. */
/* (A wall is represented by '#'; a path by ' ') */
output(Height, Width, Maze):-
Height1 is 2 * Height - 2,
Width1 is 2 * Width - 2,
Width2 is 2 * Width - 1,
write('#'), write(' '), copies(Width2, '#'), nl,
output_1(Height1, Width1, Maze),
copies(Width2, '#'), write(' '), write('#'), nl.
output_1(-1, _, _):-!.
output_1(Height, Width, Maze):-
write('#'),
output_row(Height, Width, Maze),
write('#'), nl,
Height1 is Height - 1,
output_1(Height1, Width, Maze).
output_row(Y, Width, Maze):-
Y mod 2 =:= 0, !,
output_even_row(Width, Y, Maze).
output_row(Y, Width, Maze):-
output_odd_row(Width, Y, Maze).
output_even_row(-1, _, _):-!.
output_even_row(X, Y, Maze):-
X mod 2 =:= 1,
X1 is X - 1,
X2 is X + 1,
X1_2 is X1 // 2,
X2_2 is X2 // 2,
Y2 is Y // 2,
\+ member(x(c(X1_2,Y2), c(X2_2,Y2)), Maze),
\+ member(x(c(X2_2,Y2), c(X1_2,Y2)), Maze), !,
write('#'),
output_even_row(X1, Y, Maze).
output_even_row(X, Y, Maze):-
write(' '),
X1 is X - 1,
output_even_row(X1, Y, Maze).
output_odd_row(-1, _, _):-!.
output_odd_row(X, Y, Maze):-
X mod 2 =:= 1, !,
write('#'),
X1 is X - 1,
output_odd_row(X1, Y, Maze).
output_odd_row(X, Y, Maze):-
Y1 is Y - 1,
Y2 is Y + 2,
Y1_2 is Y1 // 2,
Y2_2 is Y2 // 2,
X2 is X // 2,
\+ member(x(c(X2,Y1_2), c(X2,Y2_2)), Maze),
\+ member(x(c(X2,Y2_2), c(X2,Y1_2)), Maze), !,
write('#'),
X1 is X - 1,
output_odd_row(X1, Y, Maze).
output_odd_row(X, Y, Maze):-
write(' '),
X1 is X - 1,
output_odd_row(X1, Y, Maze).
/* copies(N, S) outputs N copies of S. */
copies(0, _):-!.
copies(N, S):-write(S), N1 is N - 1, copies(N1, S).
/* rand_int(I, J) is true if J is a pseudo-random non-negative integer */
/* less than I. */
rand_int(I, J):-I > 0, J is int(rand(I)).
/* rand_remove(Xs, X, Ys) is true if X is a pseudo-randomly chosen member */
/* of the list Xs, and Ys are the remaining elements. */
rand_remove(Xs, X, Ys):-
length(Xs, M),
rand_int(M, N),
rand_remove_1(Xs, X, 0, N, Ys).
rand_remove_1([X|Ys], X, N, N, Ys):-!.
rand_remove_1([Y|Xs], X, N0, N, [Y|Ys]):-
N1 is N0 + 1,
rand_remove_1(Xs, X, N1, N, Ys).
/* difference(Xs, Ys, Zs) is true if Zs is the list of the set of elements */
/* in the difference of the sets of elements in lists Xs and Ys. */
difference([], _, []).
difference([X|Xs], Ys, Zs):-member(X, Ys), !, difference(Xs, Ys, Zs).
difference([X|Xs], Ys, [X|Zs]):-difference(Xs, Ys, Zs).