% This heuristic is intended to work by imitating the forward-backward proof technique by simultaneously 
% working from the start and end of the maze. The heuristic is 'solved'
% when both directions meet at the same point. While working on this, the fact that the distance between the
% start and end was divisible by 2 meant that merely moving both the CurrentForwardLocation and CurrentBackwardLocation
% at the same time would not work, as the two pass through each other without solving in this case. As a result, I created a check 
% for if the CurrentBackwardLocation was equal to the CurrentForwardLocation after only moving the forward location. 
% This allowed the program to complete the solve rule properly, returning the backward path and forward path to the user;
% using the write method, I was able to output the entire Path from start to end using the forward-backward technique.


% Row 1
wall([X,1]) :- X =\= 2.
% Row 2
wall([X,2]) :- X = 1; X = 4; X = 6.
% Row 3
wall([X,3]) :- X = 1; X = 2; X = 6.
% Row 4
wall([X,4]) :- X =\= 3,X =\= 5.
% Row 5
wall([X,5]) :- X = 1; X = 4; X = 6.
% Row 6
wall([X,6]) :- X =\= 2.
% Start / end
start([2,1]).
end([2,6]).
% Maze Size
mazeSize([6,6]).

badSpot([X,Y]) :- wall([X,Y]).
badSpot([X,Y]) :- X < 1; Y < 1.
badSpot([X,Y]) :- mazeSize([W, H]), (X > W; Y > H).

%up
move([CurrX, CurrY], [CurrX, NextY]) :- NextY is CurrY - 1.
%down
move([CurrX, CurrY], [NextX, NextY]) :- NextY is CurrY + 1, NextX = CurrX.
%left
move([CurrX, CurrY], [NextX, NextY]) :- NextY = CurrY, NextX is CurrX - 1.
%right
move([CurrX, CurrY], [NextX, NextY]) :- NextY = CurrY, NextX is CurrX + 1.


% checks if backward and forward paths have converged
solve(ForwardCurrentLocation, _, ForwardPath, BackwardCurrentLocation, _, BackwardPath) :-
        ForwardCurrentLocation = BackwardCurrentLocation,
        ForwardPath = [ForwardCurrentLocation],
        BackwardPath = [BackwardCurrentLocation].


solve(ForwardCurrentLocation, ForwardBeenThere, ForwardPath, BackwardCurrentLocation, BackwardBeenThere, BackwardPath) :-
        % first 'or' block in case backward and forward paths pass through each other rather than intersecting properly, as in this example
        (move(ForwardCurrentLocation, NewForwardLocation),
        \+badSpot(NewForwardLocation),
        \+member(NewForwardLocation, ForwardBeenThere),
        NewForwardLocation = BackwardCurrentLocation,

        solve(NewForwardLocation, [NewForwardLocation | ForwardBeenThere], RestOfForwardPath, CurrentBackwardLocation, [CurrentBackwardLocation | BackwardBeenThere], RestOfBackwardPath), 
        ForwardPath = [ForwardCurrentLocation | RestOfForwardPath],
        BackwardPath = [RestOfBackwardPath]
        );

        % second 'or' block works in all other cases, when distance from start and end is not symmetrical
        (move(ForwardCurrentLocation, NewForwardLocation),
        \+badSpot(NewForwardLocation),
        \+member(NewForwardLocation, ForwardBeenThere),

        move(BackwardCurrentLocation, NewBackwardLocation),
        \+badSpot(NewBackwardLocation),
        \+member(NewBackwardLocation, BackwardBeenThere),

        solve(NewForwardLocation, [NewForwardLocation | ForwardBeenThere], RestOfForwardPath, NewBackwardLocation, [NewBackwardLocation | BackwardBeenThere], RestOfBackwardPath), 
        ForwardPath = [ForwardCurrentLocation | RestOfForwardPath],
        BackwardPath = [BackwardCurrentLocation | RestOfBackwardPath]).


% convenience rule (2 parameters!)
solve(ForwardPath, BackwardPath) :- 
        start(ForwardStart), 
        end(BackwardStart), 
        solve(ForwardStart, [ForwardStart], ForwardPath, BackwardStart, [BackwardStart], BackwardPath),

        last(ForwardPath, Last),
        reverse(BackwardPath, Reversed),
        Reversed = [_ | EndOfPath],
        
        write("The forward path is: "), write(ForwardPath),
        write(".\nThe backward path is: "), write(BackwardPath),
        write(".\nThe intersection point is: "), write(Last),
        write(".\nThe path from start to end is: "),
        write(ForwardPath), write(EndOfPath), write("\n").


drawCell(Column, Row, _) :- wall([Column, Row]), write("X"), !.
drawCell(Column, Row, _) :- start([Column, Row]), write("S"), !.
drawCell(Column, Row, _) :- end([Column, Row]), write("E"), !.
drawCell(Column, Row, Path) :- member([Column, Row], Path), write("P"), !.
drawCell(_, _, _) :- write("O").

drawRow(Row, Path) :- drawCell(1, Row, Path), tab(1), drawCell(2, Row, Path), tab(1), 
        drawCell(3, Row, Path), tab(1), drawCell(4, Row, Path), tab(1), 
        drawCell(5, Row, Path), tab(1), drawCell(6, Row, Path), nl.
                
draw :- drawRow(1, []), drawRow(2, []), drawRow(3, []), drawRow(4, []), drawRow(5, []), 
        drawRow(6, []).
draw(Path) :- drawRow(1, Path), drawRow(2, Path), drawRow(3, Path), drawRow(4, Path),
        drawRow(5, Path), drawRow(6, Path).