An implementation of the Recursive Backtracker maze generation algorithm in Erlang

maze.erl

-module(maze).
-export([generate/2,north/3,south/3,west/3,east/3,visualize/1]).

% Generate and return a maze of width W and height H.
generate(W,H) -> try_directions(random:uniform(W)-1, random:uniform(H)-1, directions(), {width,W,height,H,0}).

% Returns true if there is a passage north from the given position in the maze.
north(X,Y,Maze) -> at(X,Y,Maze) band 2#1 =/= 0.

% Returns true if there is a passage south from the given position in the maze.
south(X,Y,Maze) -> at(X,Y,Maze) band 2#10 =/= 0.

% Returns true if there is a passage west from the given position in the maze.
west(X,Y,Maze) -> at(X,Y,Maze) band 2#100 =/= 0.

% Returns true if there is a passage east from the given position in the maze.
east(X,Y,Maze) -> at(X,Y,Maze) band 2#1000 =/= 0.

% Return a list of the available direction bits, in random order.
directions() -> lists:sort(fun(_,_) -> random:uniform(2) == 1 end, [1, 2, 4, 8]).

% Return the bitmask representing the exit directions available at the given
% location in the maze.
at(X,Y,{width,W,height,_,Data}) -> (Data bsr ((W * Y + X) * 4)) band 2#01111.

% Indicate that a passage exits the given maze position in the given Direction
% (a bitmask).
set(Direction,X,Y,{width,W,height,H,Data}) ->
  {width,W,height,H,(Data bor (Direction bsl ((W * Y + X) * 4)))}.

opposite(1) -> 2;
opposite(2) -> 1;
opposite(4) -> 8;
opposite(8) -> 4.

dx(4) -> -1;
dx(8) ->  1;
dx(_) ->  0.

dy(1) -> -1;
dy(2) ->  1;
dy(_) ->  0.

valid(X, Y, Maze={width,W,height,H,_}) when X >= 0, Y >= 0, X < W, Y < H -> at(X, Y, Maze) == 0;
valid(_, _, _) -> false.

try_directions(_, _, [], Maze) -> Maze;
try_directions(X, Y, [Direction|Directions], Maze) ->
  case valid(X+dx(Direction), Y+dy(Direction), Maze) of
    true ->
      try_directions(X, Y, Directions,
        try_directions(X+dx(Direction), Y+dy(Direction), directions(),
          set(Direction, X, Y,
          set(opposite(Direction), X+dx(Direction), Y+dy(Direction), Maze))));
    false -> try_directions(X, Y, Directions, Maze)
  end.

% Build an ASCII-art visualization of the given maze.
visualize(Maze={width,W,height,_,_}) -> 
  io:format("+~s~n", [string:copies("-+", W)]),
  visualize(0,Maze).

visualize(H,{width,_,height,H,_}) -> [];
visualize(Y,Maze) ->
  io:format("|"),
  visualizeCell1(0,Y,Maze).

visualizeCell1(W,_,{width,W,height,_,_}) -> io:format("~n");
visualizeCell1(X,Y,Maze) ->
  case east(X,Y,Maze) of
    true  -> io:format("  ");
    false -> io:format(" |")
  end,
  visualizeCell1(X+1,Y,Maze).

visualizeRow2(Y,Maze) ->
  io:format("+"),
  visualizeCell2(0,Y,Maze).

visualizeCell2(W,_,{width,W,height,_,_}) -> io:format("~n");
visualizeCell2(X,Y,Maze) ->
  case south(X,Y,Maze) of
    true  -> io:format(" +");
    false -> io:format("-+")
  end,
  visualizeCell2(X+1,Y,Maze).