/*  ROUTE.PL  */
 
 
:- module route.
 
:- public route/3.
 
 
/*
SPECIFICATION
-------------
 
This is a route-finding module for the trading game. It uses best-first
search to find the best route from one square to another.
 
 
PUBLIC route( S1+, S2+, Route- ):
 
S1 and S2 are square numbers. Route will be instantiated to the shortest
route between the two squares; if they are not connected, the predicate
fails. It does not do any error checking, so illegal square numbers, etc
may have undefined results.
*/
 
 
/*
IMPLEMENTATION
--------------
 
The code is adapted from program 18.7 in "The Art of Prolog" by Sterling
and Shapiro. Changes are:
 
1) I have specialised the predicate to the trading game, so it assumes
it can call "adjacent" for instance instead of "move", and it doesn't call
"legal". Also the goal is now passed as an argument.
 
2) The evaluation function is distance squared, and frontiers are sorted
in ascending order of value (a change to the 2nd clause of insert), not
descending order.
 
3) update_frontier had a bug, by which if "member(State1,History)"
succeeded, its negation failed, thus causing the whole 1st clause to
fail. I have remedied this with the if.
 
4) Treatment of history was naff, in that the initial state is put into
the history list by route (S&S state that this is necessary), but it
gets put in again in the recursive call to solve_best. It had indeed to
go in so that update_frontier would work, but this is more neatly
handled by passing [S0|History] rather than History to it.
*/
 
 
:- needs
   distance_2 / 3,
   findall / 3,
   member / 2,
   reverse / 2.
 
 
route( S1, S2, Route ) :-
    distance_2( S1, S2, Value ),
    solve_best( [state(S1,[],Value)], S2, [], Route ).
 
 
solve_best( [state(Goal,Path,Value)|Frontier], Goal, History, Moves ) :-
    reverse( Path, Moves ),
    !.
 
solve_best( [state(S0,Path,Value)|Frontier], Goal, History, FinalPath ) :-
    findall( SNext, adjacent(S0,SNext), Nexts ),
    update_frontier( Nexts, S0, Goal, Path, [S0|History], Frontier, Frontier1 ),
    solve_best( Frontier1, Goal, [S0|History], FinalPath ).
 
 
update_frontier( [S1|RestSs], S0, Goal, Path, History, F, F1 ) :-
    distance_2( S1, Goal, Value ),
    (
        not( member(S1,History) )
    ->
        insert( state(S1,[S1|Path],Value), F, F0 ),
        update_frontier( RestSs, S0, Goal, Path, History, F0, F1 )
    ;
        update_frontier( RestSs, S0, Goal, Path, History, F, F1 )
    ).
 
update_frontier( [], S0, Goal, P, H, F, F ).
 
 
/*  insert( S+, States+, NewStates- ):
        Insert S into States giving NewStates, such that S is placed
        in correct order (ascending) of value.
*/
insert( S0, [], [S0] ) :- !.
 
insert( S0, [S1|Ss], [S0,S1|Ss] ) :-
    less_than( S0, S1 ),
    !.
 
insert( S0, [S1|Ss], [S0|Ss] ) :-
    equals( S1, S0 ),
    !.
 
insert( S0, [S1|Ss], [S1|Ss1] ) :-
    !,
    insert( S0, Ss, Ss1 ).
 
 
equals( state(S0,P,V), state(S0,P1,V) ).
 
 
less_than( state(S1,P1,V1), state(S2,P2,V2) ) :-
    S1 \= S2,
    V1 < V2.
 
 
:- endmodule.
