SWISH -- SWI-Prolog for SHaring

% Author: Ahmed Nouralla

% All project scripts in one file, modified for online testing
% Tested on https://swish.swi-prolog.org/

% Instructions:
% 1. Copy-paste this file contents into the online environment
% 2. Simply write "test." in the shell, and click run to test, multiple tests produce different maps!
% 3. Check the maps/comments at the end of the file for custom testing

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% :- ['common.pl'].

% to indicate facts that will change dynamically.
:- dynamic(home/1).
:- dynamic(covid/1).
:- dynamic(protection/1).
:- dynamic(home_m/1).
:- dynamic(covid1/1).
:- dynamic(covid2/1).
:- dynamic(protection1/1).
:- dynamic(protection2/1).

actor(location(8, 0)). % actor initial location.

% generates a valid (non-trivial) map
gen_map :-
    random_between(0, 5, Hx),
    random_between(3, 8, Hy), 
    random_between(0, 8, C1x),
    random_between(0, 8, C1y), 
    random_between(0, 8, C2x),
    random_between(0, 8, C2y),
    random_between(0, 8, P1x),
    random_between(0, 8, P1y),
    random_between(0, 8, P2x),
    random_between(0, 8, P2y),
    
    assert(home_m(location(Hx, Hy))),
    assert(covid1(location(C1x, C1y))),
    assert(covid2(location(C2x, C2y))),
    assert(protection1(location(P1x, P1y))),
    assert(protection2(location(P2x, P2y))),
    actor(A), home_m(H), covid1(C1), covid2(C2), protection1(P1), protection2(P2),
	
    % validates the map
    (
        (
            H = C1; H = C2; H = P1; H = P2; C1 = C2; C1 = P1; C1 = P2; C2 = P1; C2 = P2; P1 = P2; H = A; P1 = A; P2 = A; C1 = A; C2 = A; 
            distance(H, C1, 1); distance(H, C2, 1); distance(P1, C1, 1); distance(P2, C1, 1); distance(P1, C2, 1); distance(P2, C2, 1);
            distance(location(8, 0), C1, 1); distance(location(8, 0), C2, 1) 
        ) -> (retract(home_m(H)), retract(covid1(C1)), retract(covid2(C2)), retract(protection1(P1)), retract(protection2(P2)), gen_map) ; true
    ).

% invokes the generate map rule, and stores the results as dynamic facts
get_random_map :-
    gen_map,
    home_m(H),
    covid1(C1),
    covid2(C2),
    protection1(P1),
    protection2(P2),
    
    assert(covid(C1)),
    assert(covid(C2)),

((covid_zone(H); covid_zone(P1); covid_zone(P2); covid_zone(location(8, 0))) -> throw('Invalid map') ; true),

assert(home(H)),
    assert(protection(P1)),
    assert(protection(P2)),

write('Generated map:'), nl, % sorry but this was faster to write :D
    v(0, 0),v(0, 1),v(0, 2),v(0, 3),v(0, 4),v(0, 5),v(0, 6),v(0, 7),v(0, 8),
    v(1, 0),v(1, 1),v(1, 2),v(1, 3),v(1, 4),v(1, 5),v(1, 6),v(1, 7),v(1, 8),
    v(2, 0),v(2, 1),v(2, 2),v(2, 3),v(2, 4),v(2, 5),v(2, 6),v(2, 7),v(2, 8),
    v(3, 0),v(3, 1),v(3, 2),v(3, 3),v(3, 4),v(3, 5),v(3, 6),v(3, 7),v(3, 8),
    v(4, 0),v(4, 1),v(4, 2),v(4, 3),v(4, 4),v(4, 5),v(4, 6),v(4, 7),v(4, 8),
    v(5, 0),v(5, 1),v(5, 2),v(5, 3),v(5, 4),v(5, 5),v(5, 6),v(5, 7),v(5, 8),
    v(6, 0),v(6, 1),v(6, 2),v(6, 3),v(6, 4),v(6, 5),v(6, 6),v(6, 7),v(6, 8),
    v(7, 0),v(7, 1),v(7, 2),v(7, 3),v(7, 4),v(7, 5),v(7, 6),v(7, 7),v(7, 8),
    v(8, 0),v(8, 1),v(8, 2),v(8, 3),v(8, 4),v(8, 5),v(8, 6),v(8, 7),v(8, 8).
    
% visualize the element at location(X, Y)
v(X, Y) :-
    (
        (
            (home(location(X, Y)) -> write('H') ; false);
            (covid(location(X, Y)) -> write('C') ; false);
            (protection(location(X, Y)) -> write('P') ; false);
            (X = 8, Y = 0 -> write('A') ; false)
        );
        write('+')
    ),
    (Y = 8 -> nl; true).

% appends a direct (reversed) path from current location(A, B) (list head) to home
% used after getting protection to construct a path home directly. 
gen_path([location(A, B)|T], Result) :-
    home(location(C, D)),
    (
        (A=:=C, B=:=D -> Result = [location(A, B)|T]; false);
        (A<C, B<D -> Ap1 is A+1, Bp1 is B+1, gen_path([location(Ap1, Bp1), location(A, B)|T], Result));
        (A>C, B>D -> Am1 is A-1, Bm1 is B-1, gen_path([location(Am1, Bm1), location(A, B)|T], Result));
        (A<C, B>D -> Ap1 is A+1, Bm1 is B-1, gen_path([location(Ap1, Bm1), location(A, B)|T], Result));
        (A>C, B<D -> Am1 is A-1, Bp1 is B+1, gen_path([location(Am1, Bp1), location(A, B)|T], Result));
        (A=:=C, B<D -> Bp1 is B+1, gen_path([location(A, Bp1), location(A, B)|T], Result));
        (A=:=C, B>D -> Bm1 is B-1, gen_path([location(A, Bm1), location(A, B)|T], Result));
        (A<C, B=:=D -> Ap1 is A+1, gen_path([location(Ap1, B), location(A, B)|T], Result));
        (A>C, B=:=D -> Am1 is A-1, gen_path([location(Am1, B), location(A, B)|T], Result))
    ).

% checks if a location is valid. 
location(X, Y) :-
    between(0, 8, X),
    between(0, 8, Y).

% checks if a location is a covid zone.
covid_zone(location(X, Y)) :-
    covid(location(X, Y));
    (covid(location(A, B)), distance(location(X, Y), location(A, B), 1)).
    
% direct distance between two locations
distance(location(A, B), location(C, D), Result) :-
    Result is max(abs(A-C), abs(B-D)).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% :- ['backtracking.pl'].

best_run(13). % shortest path (to the nearest non-covid object) max length + 1.
best_path([]). % to store final answer

% to indicate facts that will change dynamically.
:- dynamic(best_run/1). 
:- dynamic(best_path/1).

/*
    Actor move rule: succeeds if moved to a valid location and the actor is safe from covid.
        move(A, D, B, P): moves actor from point A in direction D to reach point B
        P indicates whether the actor is protected or not.
*/
move(location(X, Y), delta(Dx, Dy), location(Xn, Yn), P) :-
    X_2 is X + Dx,
    Y_2 is Y + Dy,
    location(X_2, Y_2),
    (
        \+ covid_zone(location(X_2, Y_2));
        P =:= 1
    ),
    Xn is X_2,
    Yn is Y_2.

% checks if a delta vector is valid.
delta(Dx, Dy) :-
    \+ (Dx == 0, Dy == 0),
    between(-1, 1, Dx),
    between(-1, 1, Dy).

% direction aliases to make my life easier
l(delta(0, -1)).
r(delta(0, 1)).
u(delta(-1, 0)).
d(delta(1, 0)).
ul(delta(-1, -1)).
ur(delta(-1, 1)).
bl(delta(1, -1)).
br(delta(1, 1)).

% backtracking routine, second parameter stores the path till the moment.
go(StepCount, [H|T], NextMove, Protected) :-

% Optimization: breaks if there was a path discovered before that is shorter than current.
    best_run(B),
    StepCount < B,

% NextMove was legal, actor is now in some location(Ax, Ay) after the move.
    move(H, NextMove, location(Ax, Ay), Protected),

% that new location was not visited before.
    \+ memberchk(location(Ax, Ay), T),
    
    % append the new location to the path.
    append([location(Ax, Ay), H], T, Path),
    
    % is the new location a protection zone? if so, mark the actor as protected.
    (protection(location(Ax, Ay)) -> P is 1 ; P is Protected),

Sp1 is StepCount + 1, % now our move can lead to a solution, try going further
    l(L), r(R), u(U), d(D), ul(UL), ur(UR), bl(BL), br(BR), % get delta aliases defined above
  
    % recursive backtracking calls, optimized to check the paths that are more likely to get actor home faster first.
    home(location(Hx, Hy)),    
    (
        (Hx =< Ax, Hy >= Ay ->
            (
                go(Sp1, Path, UR, P);
                go(Sp1, Path, U, P);
                go(Sp1, Path, R, P);
                go(Sp1, Path, UL, P);
                go(Sp1, Path, BR, P);
                go(Sp1, Path, D, P);
                go(Sp1, Path, L, P);
                go(Sp1, Path, BL, P)
            ) ; true
        ),
        (Hx >= Ax, Hy =< Ay ->
            (
                go(Sp1, Path, BL, P);
                go(Sp1, Path, D, P);
                go(Sp1, Path, L, P);
                go(Sp1, Path, BR, P);
                go(Sp1, Path, UL, P);
                go(Sp1, Path, U, P);
                go(Sp1, Path, R, P);
                go(Sp1, Path, UR, P)
            ) ; true
        ),
        (Hx =< Ax, Hy =< Ay ->
            (
                go(Sp1, Path, UL, P);
                go(Sp1, Path, U, P);
                go(Sp1, Path, L, P);
                go(Sp1, Path, UR, P);
                go(Sp1, Path, BL, P);
                go(Sp1, Path, D, P);
                go(Sp1, Path, R, P);
                go(Sp1, Path, BR, P)
            ) ; true
        ),
        (Hx >= Ax, Hy >= Ay ->
            (
                go(Sp1, Path, BR, P);
                go(Sp1, Path, D, P);
                go(Sp1, Path, R, P);
                go(Sp1, Path, BL, P);
                go(Sp1, Path, UR, P);
                go(Sp1, Path, U, P);
                go(Sp1, Path, L, P);
                go(Sp1, Path, UL, P)
            ) ; true
        )
    ).
        
% base case: maximize score and return if reached home.
go(StepCount, [CurrentLocation|T], _, _) :-
    (
        home(CurrentLocation),
        best_run(B),
        StepCount < B,
        %write(B), nl,
        assert(best_run(StepCount)),
        retract(best_run(B)),
        best_path(BP),
        assert(best_path([CurrentLocation|T])),
        retract(best_path(BP))
    ).

% backtracking initial calls
backtrack :-
    (
        go(0, [location(8, 0)], delta(0, 1), 0);
        go(0, [location(8, 0)], delta(-1, 0), 0);
        go(0, [location(8, 0)], delta(-1, 1), 0)
    ).

% applies algorithm, and writes results
start_backtrack :-
    write("Please allow up to 2 minutes, backtracking is not the best algorithm for shortest path problems!"), nl,
    (backtrack -> true; true),
    best_run(X),
    best_path(P),
    F is 0,
    (P = [] -> (write("No path was found"), F is 1); true),
    F =:= 0 ->
    (
        write('Shortest path length: '),
        write(X), nl, 
        write('Shortest path: '),
        reverse(P, Pr),
        write(Pr), nl,
        assert(best_run(12)), !
    ); true.

% retry if test failed
test_util :-
    \+ start_backtrack -> test_util; true.

% starting point (map has to be defined before usage, check main.pl)
test_bt :-
    time(test_util).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% :- ['astar.pl'].

% to reset facts, on each knowledge base load.
% to indicate facts that will change dynamically.
:- dynamic(s/3).
:- dynamic(answer/1).

% constructs the knowledge base, i.e., builds the graph edges s(from, to, length) from the given map.
construct_kb :-
    location(A, B), location(C, D),
    distance(location(A, B), location(C, D), 1), \+ covid_zone(location(A, B)), \+ covid_zone(location(C, D)),
    assert(s(location(A, B), location(C, D), 1)).

% A* interface for user predicate, get the heruistic and calls the internal utility
astar(Start, End, _, Tmp):-
    heruistic(Start, End, H),
    astar_util([(H, H, 0, [Start])], End, _, Tmp).

% A* internal utility (recursive routine)
astar_util([(_, _, P, [X|R1])|R2], End, C, Tmp):-
    findall(
        (Sum, H1, NP, [Z,X|R1]),
        (s(X, Z, 1), not(member(Z, R1)), NP is P+1, heruistic(Z, End, H1), Sum is H1+NP),
        L
    ),
    append(R2, L, R3),
    sort(R3, R4),
    astar_util(R4, End, C, Tmp).

% uses diagonal distance routine, since the player can move in 8 directions.
heruistic(L1, L2, Her):- 
    distance(L1, L2, Her).

% applies algorithm, and writes results
start_astar :-
    home(H),
    findall(_, construct_kb, _),
    (
        (
            once(astar(location(8, 0), H, _, _)),
            answer(Path1),
            retract(answer(Path1)),
            length(Path1, Answer1)
        ); true
    ), % write(Answer1),nl,
    (
        (
            protection1(P1),
            once(astar(location(8, 0), P1, _, _)),
            answer(Path2_tmp),
            retract(answer(Path2_tmp)),
            gen_path(Path2_tmp, Path2),
            length(Path2, Answer2)
        ); true
    ), % write(Answer2),nl,
    (
        (
            protection2(P2),
            once(astar(location(8, 0), P2, _, _)),
            answer(Path3_tmp),
            retract(answer(Path3_tmp)),
            gen_path(Path3_tmp, Path3),
            length(Path3, Answer3)
        ); true
    ), %write(Answer3),nl,
    Spl is min(min(Answer1, Answer2), Answer3) - 1,
    reverse(Path1, Path1_r),
    reverse(Path2, Path2_r),
    reverse(Path3, Path3_r),
    write("Shortest path: "),
    (
        (Answer1-1 =:= Spl -> write(Path1_r); false);
        (Answer2-1 =:= Spl -> write(Path2_r); false);
        (Answer3-1 =:= Spl -> write(Path3_r); false)
    ),
    nl, write("Shortest path length: "), write(Spl), nl.

% starting point (map has to be defined before usage, check main.pl)
test_as :-
    catch(time(once(start_astar)), error(instantiation_error, _), (write("No path was found"), nl)).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% :- ['main.pl'].

% Hard-coded maps for custom testing (check report for visualization)
% TO USE: uncomment the map and comment the line 'once(get_random_map),' in rule 'test'

% Map1 (medium)
% home(location(1,1)).
% covid(location(4,1)).
% covid(location(1,6)).
% protection1(location(4,4)).
% protection2(location(7,7)).
% protection(location(4,4)).
% protection(location(7,7)).

% Map2 (medium)
% home(location(8,8)).
% covid(location(7,3)).
% covid(location(7,6)).
% protection1(location(0,6)).
% protection2(location(0,7)).
% protection(location(0,6)).
% protection(location(0,7)).

% Map3 (hard)
% home(location(1, 7)).
% covid(location(1, 5)).
% covid(location(3, 7)).
% protection1(location(1, 0)).
% protection2(location(8, 8)).
% protection(location(1, 0)).
% protection(location(8, 8)).

% Map4 (hard)
% home(location(8, 5)).
% covid(location(6, 5)).
% covid(location(8, 3)).
% protection1(location(3, 5)).
% protection2(location(8, 8)).
% protection(location(3, 5)).
% protection(location(8, 8)).

% Map5 (impossible)
% home(location(1, 7)).
% covid(location(1, 5)).
% covid(location(3, 7)).
% protection1(location(0, 7)).
% protection2(location(0, 8)).
% protection(location(0, 7)).
% protection(location(0, 8)).

% Map6 (impossible)
% home(location(1, 7)).
% covid(location(5, 1)).
% covid(location(7, 4)).
% protection1(location(0, 7)).
% protection2(location(0, 8)).
% protection(location(0, 7)).
% protection(location(0, 8)).

% Tested on: https://swish.swi-prolog.org/
% Simply write 'test.' and click run to test, multiple tests produce different maps!

test :-
    once(get_random_map),
    nl, write("A* Search"), nl, write("======================"), nl,
    test_as,
    nl, write("Backtracking Search:"), nl, write("======================"), nl,
    test_bt.