% Maze Generator in Prolog % Joe Wingbermuehle % 2010-09-26 % Size of the maze. Must be odd. get_size(39, 23). % Get an offset into the list representing the maze. get_offset(X, Y, Offset) :- get_size(W, _), Offset is Y * W + X. % Split a list into the part before and after the specified index. split(0, [_|A], [], A). split(N, [H|T], [H|B], A) :- NextN is N - 1, split(NextN, T, B, A). % Get the value of the maze. get_value(X, Y, M, V) :- get_offset(X, Y, Offset), nth0(Offset, M, V). % Set a value in the maze. set_value(X, Y, V, In, Out) :- get_offset(X, Y, Offset), split(Offset, In, Before, After), append(Before, [V], Temp), append(Temp, After, Out). % Display the maze. show_block(wall) :- write('[]'). show_block(space) :- write(' '). show_maze(0, _) :- true. show_maze(X, [H|T]) :- show_block(H), get_size(W, _), NX is X - 1, ( NX mod W =:= 0 -> nl, show_maze(NX, T); show_maze(NX, T) ). show_maze(M) :- get_size(W, H), T is W * H, show_maze(T, M). % Initialize the maze. init_maze(0, []). init_maze(X, M) :- T is X - 1, init_maze(T, S), M = [wall|S]. init_maze(M) :- get_size(W, H), T is W * H, init_maze(T, Temp), set_value(1, 1, space, Temp, M). % Carve the maze at the specified coordinates. carve_maze_at(X, Y, Dir, Count, In, Out) :- ( Dir =:= 0 -> DX is 1, DY is 0; Dir =:= 1 -> DX is 0, DY is 1; Dir =:= 2 -> DX is -1, DY is 0; Dir =:= 3 -> DX is 0, DY is -1 ), X1 is X + DX, Y1 is Y + DY, X2 is X1 + DX, Y2 is Y1 + DY, get_size(W, H), ( X2 > 0, Y2 > 0, X2 < W, Y2 < H, get_value(X1, Y1, In, wall), get_value(X2, Y2, In, wall) -> set_value(X1, Y1, space, In, M1), set_value(X2, Y2, space, M1, M2), NextDir is random(3), carve_maze_at(X2, Y2, NextDir, 0, M2, Out) ; ( Count < 3 -> NextCount is Count + 1, NextDir is (Dir + 1) mod 4, carve_maze_at(X, Y, NextDir, NextCount, In, Out) ; Out = In ) ). % Carve the maze. carve_maze(X, Y, In, Out) :- Dir is random(3), get_size(W, H), ( X < W, Y < H -> carve_maze_at(X, Y, Dir, 0, In, Temp), NextX is X + 2, carve_maze(NextX, Y, Temp, Out) ; ( X =:= W, Y < H -> carve_maze_at(X, Y, Dir, 0, In, Temp), NextY is Y + 2, carve_maze(1, NextY, Temp, Out) ; set_value(1, 0, space, In, M1), set_value(W - 2, H - 1, space, M1, Out) ) ). carve_maze(In, Out) :- carve_maze(1, 1, In, Out). % Generate and display a maze. maze :- init_maze(EmptyMaze), carve_maze(EmptyMaze, Maze), show_maze(Maze), halt. maze.