generate_maze(Width, Height, Maze):-
    (Height =< 2; Width =< 2) -> writeln("Width and Height must be greater than 2!"), Maze = invalid;
    Height mod 2 =\= 1, Width mod 2 =\= 1 -> writeln("Width and Height must be odd integers"), Maze = invalid;
    length(Cols,Height),
    Maze =.. [c|Cols],
    make_rows(Maze,Width,Height, 1),
    make_outer_walls(Maze, Width, Height),
    room_divide(Maze, 1, Height, 1, Width),
    set_start_and_exit(Maze, Width, Height),
    display_maze(Maze),
    !.

% start doing the maze

room_divide(Maze, N, S, W, E):-
    Distance = 3,
    abs(N - S) > Distance, abs(W - E) > Distance ->
    divide_(Maze, N, S, W, E, Row, Col),
    %display_maze(Maze), get_single_char(_),
    room_divide(Maze, Row, S, Col, E),
    room_divide(Maze, Row, S, W, Col),
    room_divide(Maze, N, Row, Col, E),
    room_divide(Maze, N, Row, W, Col)
    ;
    true.

divide_(Maze, N, S, W, E, Row, Col):-
    set_vertical_wall(Maze, W, E, N, S, Col),
    set_horizontal_wall(Maze, N, S, W, E, Row),
    set_holes(Maze, N, S, W, E, Row, Col).

set_holes(Maze, N, S, W, E, Row, Col):-
    random_between(1,4,Dir),
    (Dir =\= 1 -> set_vertical_hole(Maze, Col ,N , Row); true),
    (Dir =\= 2 -> set_vertical_hole(Maze, Col ,Row, S); true),
    (Dir =\= 3 -> set_horizontal_hole(Maze, Row, W, Col); true),
    (Dir =\= 4 -> set_horizontal_hole(Maze, Row, Col, E); true).

set_horizontal_hole(Maze, RowIndex, Left, Right):-
    L is (Left + 1) // 2,
    R is (Right - 1) // 2,
    random_between(L, R, Mult),
    ColIndex is 2 * Mult,
    arg(RowIndex, Maze, Row),
    setarg(ColIndex, Row, ' ').

set_vertical_hole(Maze, ColIndex, Up, Down):-
    U is (Up + 1) // 2,
    D is (Down - 1) // 2,
    random_between(U, D, Mult),
    RowIndex is 2 * Mult,
    arg(RowIndex, Maze, Row),
    setarg(ColIndex, Row, ' ').

set_vertical_wall(Maze, Left, Right, Up, Down, Col):-
    L is (Left + 2) // 2,
    R is (Right - 2) // 2,
    random_between(L, R, Mult),
    Col is 2 * Mult + 1,
    make_vertical_wall(Maze, Col, Up, Down).

make_vertical_wall(Maze, Col, Up, Down):-
    Up =< Down ->
        arg(Up, Maze, Row),
        setarg(Col, Row, '#'),
        succ(Up, U),
        make_vertical_wall(Maze, Col, U, Down);
        true.

set_horizontal_wall(Maze, Up, Down, Left, Right, Row):-
    U is (Up + 2) // 2,
    D is (Down - 2) // 2,
    random_between(U, D, Mult),
    Row is 2*Mult + 1,
    make_horizontal_wall(Maze, Row, Left, Right).

make_horizontal_wall(Maze, RowIndex, Left, Right):-
    Left =< Right ->
    arg(RowIndex, Maze, Row),
    setarg(Left, Row, '#'),
    succ(Left, L),
    make_horizontal_wall(Maze, RowIndex, L, Right);
    true.

% generate the size of the maze
make_rows(_, _, Height, Col):-
    Col > Height.
make_rows(Maze, Width, Height, Col):-
    Col =< Height,
    length(Row, Width),
    CurRow =.. [r|Row],
    setarg(Col, Maze, CurRow),
    succ(Col, NextCol),
    make_rows(Maze, Width, Height, NextCol).

% set everything on the outside to a wall
make_outer_walls(Maze, Width, Height):-
    arg(1, Maze, FirstRow),
    arg(Height, Maze, LastRow),
    FirstRow =.. [r|RowOne],
    LastRow =.. [r|FinalRow],
    maplist(=(#), RowOne),
    maplist(=(#), FinalRow),
/*
    setarg(2, FirstRow, ' '), 
    ExitPoint is Width - 1,
    setarg(ExitPoint, LastRow, ' '),
*/
    % do both walls
    make_outer_vertical_wall(Maze, Width, Height,2).

make_outer_vertical_wall(Maze, Width, Height, Index):-
    Index < Height ->
    arg(Index, Maze, CurRow),
    CurRow =.. [r|Row],
    append([#|Rest], [#], Row),
    maplist(=(' '), Rest),
    succ(Index, NextIndex),
    make_outer_vertical_wall(Maze, Width, Height, NextIndex);
    true.

set_start_and_exit(Maze, Width, Height):-
    W is (Width - 1) // 2,
    random_between(1, W, MultStart),
    random_between(1, W, MultEnd),
    arg(1, Maze, TopRow),
    Start is MultStart * 2,
    setarg(Start, TopRow, ' '),
    arg(Height, Maze, LastRow),
    End is MultEnd * 2,
    setarg(End, LastRow, ' ').

% display maze
display_maze(Maze):-
    functor(Maze, _, Height),
    nl,
    display_maze(Maze, Height, 1).

display_maze(Maze, Height, Index):-
    Index =< Height ->
        arg(Index, Maze, Row),
        Row =.. [r|List],
        writeln(List),
        succ(Index, NextIndex),
        display_maze(Maze, Height, NextIndex);
        nl, true.