A Maze Generator

/* 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).

LPA Index     Home Page

Valid HTML 4.01 Strict