/*--------------------------------------------------------------*/ 
/* Themis Panayiotopoulos, March 2018				*/ 
/* themis.panayiotopoulos3@gmail.com				*/
/* Artificial Intelligence and Virtual Reality Laboratory	*/
/* School of Information and Communication Technologies 	*/
/* Department of Informatics					*/
/* 8th Semester - Distributed Artificial Intelligence Course	*/
/* Pathfinder3 : Depth first Map Path Finder	v 3		*/
/* run go1, go2, go3, go4 as example queries			*/
/*--------------------------------------------------------------*/
	
:- dynamic([max_depth/1]).

/*--------------------------------------*/
/* Pathfinder version 3			*/
/* Depth First pathfinder for a map 	*/
/* there is Cost to walk over map cells	*/
/* Cost is computed when we walk on 	*/
/* a cell and not when we leave a cell	*/
/* therefore the cost of start is not 	*/
/* added to total path cost		*/
/* X-axis counts columns (left to right)*/
/* Y-axis counts lines (top to bottom)	*/
/*--------------------------------------*/

/*----------- D A T A ----------*/

% X	 1 2 3 4 5 6 7 8 9 0 1	 Y
mymap([	[r,h,h,h,g,g,g,w,w,w,w],%1
	[r,r,h,g,g,h,g,g,w,w,w],%2
	[g,r,r,r,r,v,r,r,r,w,w],%3
	[g,r,h,m,m,r,g,g,w,w,w],%4
	[g,r,t,t,g,r,r,r,g,g,g],%5
	[g,t,t,t,g,t,t,t,w,w,w] %6
     ]).

%  Symbol Meaning Q
%  r=road, g=grass, v=village, h=hill
%  t=tree, m=mountain, w=water 
%  Symbol Cost
%  cost = r/1, g/2, h/3, v/4, t/5, m/8, w/10
%

cost(r,1).
cost(g,2).
cost(h,3).
cost(v,4).
cost(t,5).
cost(m,8).
cost(w,10).

% Other Data

max_depth(8).

/*----- E X A M P L E   Q U E R I E S ------*/

go1 :- go_pathfinder((1,1),(6,3)),!.
go2 :- go_pathfinder((1,1),(3,6)),!.

go3 :- 
	retract(max_depth(8)),
	assert(max_depth(12)),
	go_pathfinder((1,1),(8,5)),
	retract(max_depth(12)),
	assert(max_depth(8)),!.
	
go4 :- /* wait a bit, it takes 7 sec, on my pc */
	retract(max_depth(8)),
	assert(max_depth(16)),
	go_pathfinder((1,1),(11,6)),
	retract(max_depth(16)),
	assert(max_depth(8)),!.

go_pathfinder(Start,Finish) :-
	mymap(M),
	get_time(STime),
	findminpath(Start,Finish,Path,Cost),
	get_time(FTime),
	print_map_path(M,Path), 
	write('With Cost = '),write(Cost),nl,
	Time1 is FTime-STime,
	Time is float_integer_part(Time1),
	write('and it took me ... '),
	write(Time),
	write(' sec '),nl,!.


/*----- P A T H   F I N D E R ----------*/

/*------ P A T H   F I N D E R Calling predicates ------*/

/*------------------------------------------------------*/
/* !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!*/
/* IMPORTANT NOTE : We use max_depth to help the path   */
/* finder to find answers fast. If we put max_depth, 	*/
/* say, 100, the path finder will examine paths of 	*/
/* greater lengths and will take much more time to 	*/
/* get the minimum cost path (many more paths also)	*/
/* if we make the road to go around the map we must 	*/
/* change max_depth for the algorithm to work properly	*/
/*------------------------------------------------------*/

/*------------------------------------------------------*/
/* find a path, press ';' for next path			*/
/*------------------------------------------------------*/
findpath(Start,Finish,Path,Cost) :-
 	max_depth(MaxC),
 	path(Start,Finish,1,MaxC,[Start],Path,Cost).

/*------------------------------------------------------*/
/* find the minimum cost path				*/
/*------------------------------------------------------*/
findminpath(Start,Finish,Path,MinCost) :-
	findall(P/C, findpath(Start,Finish,P,C),L),
	strange_minlist(L,Path,MinCost),!.

/*------------------------------------------------------*/
/* print a path, press ';' for next path		*/
/*------------------------------------------------------*/
printpath(Start,Finish,Path,Cost) :-
 	printpath(Start,Finish,Path,Cost),
	mymap(M),
	print_map_path(M,Path).

/*------------------------------------------------------*/
/* print the minimum cost path				*/
/*------------------------------------------------------*/
printminpath(Start,Finish,Path,Cost) :-
	findminpath(Start,Finish,Path,Cost),
	mymap(M),
	print_map_path(M,Path), 
	write('With Cost = '),write(Cost),nl,!.

/*----------- P A T H   F I N D E R Main ---------------*/
/*------------------------------------------------------*/
/* path(Start,Finish,Count,MaxCount,Visited,Path,Cost)	*/
/* Start = Start Path Position				*/
/* Finish = Finish Path Position			*/
/* Count = Depth Counter (should start with 1)		*/
/* MaxCount = Max Depth allowed				*/
/* Visited = List of already Visited nodes		*/
/* Path = Path returned from path finding algorithm	*/
/* Cost = Total Cost of the Path			*/
/*------------------------------------------------------*/

path((X,Y),(X,Y),_,_,_,[(X,Y)],0). 
path(Current,Finish,C,MaxC,Visited,[Current|Path],Cost) :- 
	move(Current,Next),
	valid(Next,Element),
	cost(Element,Element_Cost),
	not(member(Next,Visited)),
	C1 is C+1, C1=<MaxC, 
	path(Next,Finish,C1,MaxC,[Next|Visited],Path,Rest_Cost),
	Cost is Rest_Cost+Element_Cost.


 
/*------- Possible Moves----------------*/

move((X,Y),(X1,Y)) :- X1 is X+1. %right
move((X,Y),(X1,Y)) :- X1 is X-1. %left
move((X,Y),(X,Y1)) :- Y1 is Y+1. %down
move((X,Y),(X,Y1)) :- Y1 is Y-1. %up

/*------- Valid Moves----------------*/
valid((X,Y),E) :- 
	mapmaxXY(MaxX,MaxY),
	0<X, X=<MaxX, 0<Y,Y=<MaxY, % inside map
	mymap(M), get_map_element(M,X,Y,E).

/*------- L I B R A R Y ---------------*/


/*--------------------------------------*/
/* get_nth_element(List,N,E) 		*/
/* ?- get_nth_element([a,b,c],2,X)	*/
/* X=b					*/
/*--------------------------------------*/
get_nth_element([X|_],1,X) :- !.
get_nth_element([_|Xs],N,E) :-
	N1 is N-1, 
	get_nth_element(Xs,N1,E).

/*--------------------------------------*/
/* change_nth_element(L,N,NewE,NewL) 	*/
/* ?- change_nth_element([a,b,c],2,f,L)	*/
/* L=[a,f,c]				*/
/*--------------------------------------*/
change_nth_element([_|Xs],1,E,[E|Xs]):- !.
change_nth_element([X|Xs],N,E,[X|Ys]) :-
	N1 is N-1, 
	change_nth_element(Xs,N1,E,Ys).

/*----------------------------------------------*/
/* strange_minlist(List,P,C)			*/
/* List = [Path1/Cost1,Path2/Cost2,...]		*/
/* a list of paths with their costs		*/
/* Returns the path P with minimum cost C	*/
/*----------------------------------------------*/
strange_minlist([P/C],P,C).
strange_minlist([_/Cost|Rest],Path1,Cost1) :-
	strange_minlist(Rest,Path1,Cost1),
	Cost1=<Cost, !.
strange_minlist([Path/Cost|Rest],Path,Cost) :-
	strange_minlist(Rest,_,Cost1),
	Cost<Cost1.

/*----------------------------------------------*/
/* get_map_element(Map,X,Y,E)			*/
/* Returns in E the content of Map at (X,Y)	*/
/*----------------------------------------------*/
get_map_element(Map,X,Y,E) :-
	get_nth_element(Map,Y,Line),
	get_nth_element(Line,X,E).

/*------------------------------------------------------*/
/* change_map_element(Map,X,Y,NewE,NewMap)		*/
/* NewMap is like Map except that it contains		*/
/* a new value NewE in the position (X,Y)		*/
/* ?- change_map_element([[a,b,c],[d,e,f]],1,2,r,M).	*/
/* M=[[a,b,c],[r,e,f]]					*/
/*------------------------------------------------------*/
change_map_element(Map,X,Y,NewE,NewMap) :-
	get_nth_element(Map,Y,Line),
	change_nth_element(Line,X,NewE,NewLine),
	change_nth_element(Map,Y,NewLine,NewMap).

/*----------------------------------------------*/
/* mapmaxXY(MaxX,MaxY)				*/
/* Returns in 					*/
/* MaxX : maximum length of mymap on X axis 	*/
/* MaxY : maximum length of mymap on Y axis 	*/
/*----------------------------------------------*/
mapmaxXY(MaxX,MaxY) :- 
	mymap(M),
	length(M,MaxY),
	M=[Line|_],
	length(Line,MaxX).

/*----------------------------------------------*/
/* printlist(List)			 	*/
/* Prints on screen the elements of a list one	*/
/* by one with 3 spaces between			*/
/*----------------------------------------------*/
printlist([]) :- nl, !.
printlist([X|Xs]) :- 
	write(X), write('   '),printlist(Xs).

/*----------------------------------------------*/
/* print_map(Map)			 	*/
/* Prints on screen the elements of a Map 	*/
/*----------------------------------------------*/
print_map([]) :- nl, !.
print_map([X|Xs]) :- 
	printlist(X), print_map(Xs).

/*----------------------------------------------*/
/* print_map_path(Map,Path)		 	*/
/* Prints on screen the elements of a Map along	*/
/* with the path on it with '*'			*/
/*----------------------------------------------*/
print_map_path(Map,Path) :- 
	make_new_map_path(Map,Path,PathMap),
	print_map(PathMap).

/*----------------------------------------------*/
/* make_new_map_path(Map,Path,PathMap)	 	*/
/* PathMap is Map except the positions of Path	*/
/* where it has got '*'				*/
/*----------------------------------------------*/
make_new_map_path(Map,[],Map) :- !.
make_new_map_path(Map,[(X,Y)|Rest],NewMap) :-
	change_map_element(Map,X,Y,'*',HMap),
	make_new_map_path(HMap,Rest,NewMap).


