114 lines
4.6 KiB
Erlang
114 lines
4.6 KiB
Erlang
-module(maze).
|
|
-record(maze, {g, m, n}).
|
|
-export([generate_default/0, generate_MxN/2]).
|
|
|
|
make_maze(M, N) ->
|
|
Maze = #maze{g = digraph:new(), m = M, n = N},
|
|
lists:foreach(fun(X) -> digraph:add_vertex(Maze#maze.g, X) end, lists:seq(0, M * N - 1)),
|
|
Maze.
|
|
|
|
row_at(V, Maze) -> trunc(V / Maze#maze.n).
|
|
col_at(V, Maze) -> V - row_at(V, Maze) * Maze#maze.n.
|
|
vertex_at(Row, Col, Maze) -> Cell_Exists = cell_exists(Row, Col, Maze), if Cell_Exists -> Row * Maze#maze.n + Col; true -> -1 end.
|
|
cell_exists(Row, Col, Maze) -> (Row >= 0) and (Row < Maze#maze.m) and (Col >= 0) and (Col < Maze#maze.n).
|
|
|
|
adjacent_cells(V, Maze) -> % ordered: left, up, right, down
|
|
adjacent_cell(cell_left, V, Maze)++adjacent_cell(cell_up, V, Maze)++adjacent_cell(cell_right, V, Maze)++adjacent_cell(cell_down, V, Maze).
|
|
|
|
adjacent_cell(cell_left, V, Maze) -> case (col_at(V, Maze) == 0) of true -> []; _Else -> [V - 1] end;
|
|
adjacent_cell(cell_up, V, Maze) -> case (row_at(V, Maze) == 0) of true -> []; _Else -> [V - Maze#maze.n] end;
|
|
adjacent_cell(cell_right, V, Maze) -> case (col_at(V, Maze) == Maze#maze.n - 1) of true -> []; _Else -> [V + 1] end;
|
|
adjacent_cell(cell_down, V, Maze) -> case (row_at(V, Maze) == Maze#maze.m - 1) of true -> []; _Else -> [V + Maze#maze.n] end.
|
|
|
|
connect_all(V, Maze) ->
|
|
lists:foreach(fun(X) -> digraph:add_edge(Maze#maze.g, V, X) end, adjacent_cells(V, Maze)).
|
|
|
|
make_maze(M, N, all_connected) ->
|
|
Maze = make_maze(M, N),
|
|
lists:foreach(fun(X) -> connect_all(X, Maze) end, lists:seq(0, M * N - 1)),
|
|
Maze.
|
|
|
|
maze_parts(Maze) ->
|
|
SPR = Maze#maze.n + 1, % slots per row is #columns + 1
|
|
NPR = (Maze#maze.m * 2) + 1, % # part rows is #(rows * 2) + 1
|
|
[make_part(Maze, trunc(Index/SPR), Index - trunc(Index/SPR) * SPR) || Index <- lists:seq(0, (SPR * NPR) - 1)].
|
|
|
|
draw_part(Part) ->
|
|
case Part of
|
|
{pwall, pclosed} -> io:format("+---");
|
|
{pwall, popen} -> io:format("+ ");
|
|
{pwall, pend} -> io:format("+~n");
|
|
{phall, pclosed} -> io:format("| ");
|
|
{phall, popen} -> io:format(" ");
|
|
{phall, pend} -> io:format("|~n")
|
|
end.
|
|
|
|
has_neighbour(Maze, Row, Col, Direction) ->
|
|
V = vertex_at(Row, Col, Maze),
|
|
if
|
|
V >= 0 ->
|
|
Adjacent = adjacent_cell(Direction, V, Maze),
|
|
if
|
|
length(Adjacent) > 0 ->
|
|
Neighbours = digraph:out_neighbours(Maze#maze.g, lists:nth(1, Adjacent)),
|
|
lists:member(V, Neighbours);
|
|
true -> false
|
|
end;
|
|
true -> false
|
|
end.
|
|
|
|
make_part(Maze, DoubledRow, Col) ->
|
|
if
|
|
trunc(DoubledRow/2) * 2 == DoubledRow -> % --- (even row) making a wall above the cell
|
|
make_part(Maze, trunc(DoubledRow/2), Col, cell_up, pwall);
|
|
true -> % ---otherwise (odd row) making a hall through the cell
|
|
make_part(Maze, trunc(DoubledRow/2), Col, cell_left, phall)
|
|
end.
|
|
|
|
make_part(Maze, _, Col, _, Part_Type) when Col == Maze#maze.n -> {Part_Type, pend};
|
|
make_part(Maze, Row, Col, Direction, Part_Type) ->
|
|
Has_Neighbour = has_neighbour(Maze, Row, Col, Direction),
|
|
if
|
|
Has_Neighbour -> {Part_Type, popen};
|
|
true -> {Part_Type, pclosed}
|
|
end.
|
|
|
|
shuffle([], Acc) -> Acc;
|
|
shuffle(List, Acc) ->
|
|
Elem = lists:nth(random:uniform(length(List)), List),
|
|
shuffle(lists:delete(Elem, List), Acc++[Elem]).
|
|
|
|
processDepthFirst(Maze) ->
|
|
if
|
|
Maze#maze.m * Maze#maze.n == 0 -> [{pwall, pend}];
|
|
true ->
|
|
Visited = array:new([{size, Maze#maze.m * Maze#maze.n},{fixed,true},{default,false}]),
|
|
{_, Path} = processDepthFirst(Maze, -1, random:uniform(Maze#maze.m * Maze#maze.n) - 1, {Visited, []}),
|
|
Path
|
|
end.
|
|
|
|
processDepthFirst(Maze, Vfrom, V, VandP) ->
|
|
{Visited, Path} = VandP,
|
|
Was_Visited = array:get(V, Visited),
|
|
if
|
|
not Was_Visited ->
|
|
Walker = fun(X, Acc) -> processDepthFirst(Maze, V, X, Acc) end,
|
|
Random_Neighbours = shuffle(digraph:out_neighbours(Maze#maze.g, V), []),
|
|
lists:foldl(Walker, {array:set(V, true, Visited), Path++[{Vfrom, V}]}, Random_Neighbours);
|
|
true -> VandP
|
|
end.
|
|
|
|
open_wall(_, {-1, _}) -> ok;
|
|
open_wall(Maze, {V, V2}) ->
|
|
case (V2 > V) of true -> digraph:add_edge(Maze#maze.g, V, V2); _Else -> digraph:add_edge(Maze#maze.g, V2, V) end.
|
|
|
|
generate_MxN(M, N) ->
|
|
Maze = make_maze(M, N),
|
|
Matrix = make_maze(M, N, all_connected),
|
|
Trail = processDepthFirst(Matrix),
|
|
lists:foreach(fun(X) -> open_wall(Maze, X) end, Trail),
|
|
Parts = maze_parts(Maze),
|
|
lists:foreach(fun(X) -> draw_part(X) end, Parts).
|
|
|
|
generate_default() ->
|
|
generate_MxN(9, 9).
|