/*--------------------------------------------------------------*/ 
/* 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	*/
/* Pathfinder4 : (DFS + A*) search map Path finder		*/
/* run dfgo1, dfgo2, dfgo3, dfgo4 				*/
/*     asgo1, asgo2, asgo3, asgo4 				*/
/* or go1, go2, go3, go4					*/
/* as example queries						*/
/* It works but i still work on it (A* is slow see go4)		*/
/* wait for new version						*/
/*--------------------------------------------------------------*/
	
:- dynamic([max_depth/1,start/1,finish/1]).

/*----------------------------------------------*/
/* Pathfinder version 4 			*/
/* Depth First Search pathfinder for a map 	*/
/* A* Search Path finder 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)		*/
/*----------------------------------------------*/

/*----------------------------------------------*/
/*		P A R A M E T E R S		*/
/*----------------------------------------------*/

depth_first(yes).
a_star(no).
max_depth(8).
start((1,1)).
finish((6,3)).

/*----------- 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
%  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

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

go1 :- dfgo1, asgo1.
dfgo1 :- go_dfspathfinder((1,1),(6,3)),!.
asgo1 :- go_astarpathfinder((1,1),(6,3)),!.

go2 :- dfgo2, asgo2.
dfgo2 :- go_dfspathfinder((1,1),(3,6)),!.
asgo2 :- 
	retract(finish((6,3))), assert(finish((3,6))),
	go_astarpathfinder((1,1),(3,6)),
	retract(finish((3,6))), assert(finish((6,3))), !.

go3 :-	dfgo3, asgo3.
dfgo3 :- retract(max_depth(8)),
	assert(max_depth(12)),
	go_dfspathfinder((1,1),(8,5)),
	retract(max_depth(12)),
	assert(max_depth(8)),!.
asgo3 :- 
	retract(finish((6,3))), assert(finish((8,5))),
	go_astarpathfinder((1,1),(8,5)),
	retract(finish((8,5))), assert(finish((6,3))), !.
	
go4 :-	dfgo4, asgo4.
dfgo4 :- /* wait a bit, it takes 8 sec, on my pc */
	retract(max_depth(8)),
	assert(max_depth(16)),
	go_dfspathfinder((1,1),(11,6)),
	retract(max_depth(16)),
	assert(max_depth(8)),!.
asgo4 :- 
	retract(finish((6,3))), assert(finish((11,6))),
	go_astarpathfinder((1,1),(11,6)),
	retract(finish((11,6))), assert(finish((6,3))), !.

go_dfspathfinder(Start,Finish) :-
	wr_df,
	mymap(M),
	get_time(STime),
	find_dfsminpath(Start,Finish,Path,Cost),
	get_time(FTime),
	print_map_path(M,Path),
	horizontal,
	write('Path='),nl,printlist(Path),	
	write('With Cost = '),write(Cost),nl,
	Time1 is FTime-STime,
	% Time is float_integer_part(Time1),
	write('and it took me ... '),
	write(Time1),
	write(' sec '),nl,!.

go_astarpathfinder(Start,Finish) :-
	wr_as,
	mymap(M),
	get_time(STime),
	assearch(Start,Finish,[Start],Reverse,Cost),
	get_time(FTime),
	reverse(Reverse,Path),
	print_map_path(M,Path), 
	horizontal,
	write('Path='),nl,printlist(Path),	
	write('With Cost = '),write(Cost),nl,
	Time1 is FTime-STime,
	% Time is float_integer_part(Time1),
	write('and it took me ... '),
	write(Time1),
	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			*/
/*------------------------------------------------------*/
find_dfspath(Start,Finish,Path,Cost) :-
 	max_depth(MaxC),
 	dfspath(Start,Finish,1,MaxC,[Start],Path,Cost).

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

/*------------------------------------------------------*/
/* print a path, press ';' for next path		*/
/*------------------------------------------------------*/
print_dfspath(Start,Finish,Path,Cost) :-
 	find_dfspath(Start,Finish,Path,Cost),
	mymap(M),
	print_map_path(M,Path),
	write('With Cost = '),write(Cost),nl.

/*------------------------------------------------------*/
/* print the minimum cost path				*/
/*------------------------------------------------------*/
print_dfsminpath(Start,Finish,Path,Cost) :-
	find_dfsminpath(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 ---------------*/

/*--------------------------------------------------------------*/
/* Depth First Search Path Finding (dfspath)			*/
/*--------------------------------------------------------------*/
/* dfspath(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				*/
/*--------------------------------------------------------------*/

wr_df :- nl,
	write('Depth First Search Path Finding Algorithm'),nl,
	horizontal,nl.

dfspath((X,Y),(X,Y),_,_,_,[(X,Y)],0). 
dfspath(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, 
	dfspath(Next,Finish,C1,MaxC,[Next|Visited],Path,Rest_Cost),
	Cost is Rest_Cost+Element_Cost.

/*--------------------------------------------------------------*/
/* A* SEARCH Path Finding (assearch)				*/
/*--------------------------------------------------------------*/
/* Part of the A* Algorithm has been copied from the book	*/
/* (but has been modified to work properly)			*/
/* I.Vlahavas,P.Kefalas,N.Basileiadis,F.Kokkoras,I.Sakellariou  */
/* Texnhth Nohmosunh (B' Ekdosh),Ekdoseis Gartaganh,		*/
/* Thessaloniki, 2005 http://aibook.csd.auth.gr			*/
/*--------------------------------------------------------------*/

wr_as :- nl,
	write('A* Path Finding Search Algorithm'),nl,
	horizontal,nl.

assearch(S0,Goal,[S0],Q,Cost) :-
	evaluation(S0,Goal,[S0],V),
	astar([V-[S0]],Goal,Q,Cost).

astar([Cost-[Goal|Path]|_],Goal,[Goal|Path],Cost).
astar([V-[State|Path]|RestPaths],Goal,Solution,Cost):-
	nl, write('Expanding best state :'), write(V-State),nl,
	expand(V-[State|Path],Goal,NewPaths),
	nl, write('Expanded to :'), write(NewPaths),nl,
	append(NewPaths,RestPaths,Frontier),
	keysort(Frontier,OrderedFrontier),
	astar(OrderedFrontier,Goal,Solution,Cost).

expand(_-[State|Visited],Goal,NewPaths):-
	findall(NewCost-[NewState,State|Visited],
			(
			asnext_state(State,NewState,_),
			asno_loop(NewState,Visited),
			evaluation(NewState,Goal,[NewState,State|Visited],NewCost)
			),
		NewPaths).

evaluation(State,Goal,Path,Cost):-
	mymap(M),
	g(M, Path, G),
	h(State,Goal,H),
	Cost is G+H.

/*------------------------------------------------------*/
/* Computation of the Cost so far			*/
/*------------------------------------------------------*/
g(M, [_],0) :- !.
g(M, [(X,Y)|Path], G) :-
	get_map_element(M,X,Y,E),
	cost(E,Cost),
	g(M, Path, RestCost),
	G is Cost+RestCost,!.

/*------------------------------------------------------*/
/* Heuristic h(State,GoalState,Value)			*/
/*------------------------------------------------------*/
h((X1,Y1),(X2,Y2),Value) :-
	Value is abs(X2 - X1) + abs(Y2 - Y1).

asnext_state(Current,Next,Cost) :- 
	move(Current,Next),
	valid(Next,Element),
	cost(Element,Cost).

asno_loop(S,Visited) :-
      \+member(S,Visited).
      
/*======================================================*/


 
/*------- 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([]) :- !.
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).

/*------------------------------------------------------*/
/* General Library					*/
/*------------------------------------------------------*/

ifthen(Condition,RunMe) :- call(Condition), !, call(RunMe).
ifthen(_,_).

ifthenelse(Condition,RunMe,_) :- call(Condition), !, call(RunMe).
ifthenelse(_,_,RunMe) :- call(RunMe).

case([C|_],[R|_]) :- call(C), !, call(R).
case([_|Conditions],[_|Rest]) :- case(Conditions,Rest).
case([],[]) :- !.

/*------------------------------------------------------*/
/* fordo(Start,Step,Finish,Goal) 			*/
/*------------------------------------------------------*/
fordo(Start,Step,Finish,Goal) :- Start>Finish.
fordo(Start,Step,Finish,Goal) :- 
	call(Goal),
	NewStart is Start+Step,
	fordo(NewStart,Step,Finish,Goal).

	
/*------------------------------------------------------*/
/* cls = clear screen (oldies but goodies :xD)		*/
/*------------------------------------------------------*/
cls :- fordo(1,1,25,nl).

write_solution([],_):- nl,!.
write_solution([X|Xs],N):-
	write(X),write(','),
	M is N+1, K is N mod 18, ifthen(K=0,nl), write_solution(Xs,M).

/*------------------------------------------------------*/
/* wait = wait till i press a key			*/
/*------------------------------------------------------*/
wait :- get_char(_).
wait(Text,Key) :- write_list(Text), get_char(Key).

horizontal :- 
	mapmaxXY(MaxX,_), N is MaxX*4, fordo(1,1,N,write('=')), nl.

/*------------------------------------------------------*/
/* draw Map						*/
/*------------------------------------------------------*/
drawMap :- cls, maxy(N), draw_map(1,N).
draw_map(1,N) :- korniza_start, map_element_line(1), korniza_mid, draw_map(2,N).
draw_map(M,N) :- M<N, map_element_line(M), korniza_mid, K is M+1, draw_map(K,N).
draw_map(M,N) :- M is N-1, map_element_line(M), draw_map(N,N).
draw_map(N,N) :- map_element_line(N), korniza_finish.

map_element_line(Line) :- 
	mymap(Map), mapline(Map,Line,Elements),
	maxx(N),
	show_line(1,N,Elements).
	
show_line(_,_,[]) :- grid_column,nl.
show_line(K,N,[E|Es]) :- grid_column,write(E), K1 is K+1, show_line(K1,N,Es).

korniza_start :- maxx(N), map_korniza_start(1,N).
map_korniza_start(1,N) :- grid_up_left, grid_line, map_korniza_start(2,N).
map_korniza_start(M,N) :- M=<N,grid_up, grid_line, K is M+1, map_korniza_start(K,N).
map_korniza_start(N,N) :- grid_up_right, nl.

korniza_mid :- maxx(N), map_korniza_mid(1,N).
map_korniza_mid(1,N) :- grid_mid_left, grid_line, map_korniza_mid(2,N).
map_korniza_mid(M,N) :- M=<N, grid_mid, grid_line, K is M+1, map_korniza_mid(K,N).
map_korniza_mid(N,N) :- grid_mid_right, nl.

korniza_finish :- maxx(N), map_korniza_finish(1,N).
map_korniza_finish(1,N) :- grid_down_left, grid_line, map_korniza_finish(2,N).
map_korniza_finish(M,N) :- M=<N, grid_down, grid_line, K is M+1, map_korniza_finish(K,N).
map_korniza_finish(N,N) :- grid_down_right, nl.


grid_up_left 	:- put_code(42). %put_code(2).
grid_up_right 	:- put_code(42). %put_code(2).
grid_up 	:- put_code(42). %put_code(22).
grid_mid_left 	:- put_code(42). %put_code(25).
grid_mid_right 	:- put_code(42). %put_code(23).
grid_mid 	:- put_code(45). %put_code(16).
grid_down_left 	:- put_code(42). %put_code(3).
grid_down_right :- put_code(42). %put_code(4).
grid_down 	:- put_code(42). %put_code(21).
grid_line 	:- put_code(45). %put_code(6).
grid_column 	:- put_code(124). %put_code(5).


show_codes(N,N) :- write_one_code(N).
show_codes(M,N) :- write_one_code(M), K is M+1, show_codes(K,N).
write_one_code(N) :- write('{'),write(N),write(','),put_code(N),write('} ').













