# JPS - ASTAR dokumentacja

## Skład zespołu:

* Damian Kolaska
* Kamil Przybyła

## Ilustracja grafu


## Prezentacja działania

Uruchamiamy procedurę poszukującą ścieżki `Path` z wierzchołka `a`. Użytkownik będzie mógł wybierać który wierzchołek ma zostać odwiedzony z listy maksymalnie 4-elementowej, a głębokość przeszukiwań będzie równa 2.

Do kolejki został dodany jedynie węzeł początkowy, więc użytkownik może wybrać tylko jeden węzeł. Podejmujemy jedyną możliwą decyzję.

Z listy `Nodes` zostanie wybrany element o indeksie 1.

Do kolejki dodano węzły dostępne z odwiedzonego węzła `a`, a głębokość przeszukiwania została zwiększona.

Węzeł `a` jest umieszczony w `ClosedSet`, ponieważ był już odwiedzony. Sugerujemy algorytmowi aby w pierwszej kolejności odwiedził węzeł `b`, pozostawiając punkt wyboru.

Z listy `Nodes` zostanie wybrany element o indeksie 1.

Kolejka została poszerzona o sąsiadów węzła `b`.

Zmuszamy algorytm do odwiedzenia węzła `g`, z którego nie ma możliwości wyjścia.

Z listy `Nodes` zostanie wybrany element o indeksie 2.

Głębokość przeszukiwań zostaje przekroczona i nie zezwalamy na zwiększenie jej, co skutkuje nawrotem do procedury `choose_element`.

Interpreter wraca do punktu wyboru, w którym wybierał element z listy `[1, 2]` i tym razem zostanie wybiera element o indeksie 2.

Dzięki nawrotowi głębokość została zmniejszona. Kolejka tym razem zawiera węzły sąsiadujące z `c`.

W `ClosedSet` widzimy, że rzeczywiście został odwiedzony węzeł `c`. Prowadzimy algorytm ścieżką przechodzącą przez węzeł `d`, ale nie ma to szczególnego znaczenia.

Wybrany zostaje element o indeksie 2.

Znów została przekroczona maksymalna głębokość przeszukiwania. Tym razem zgadzamy się na zwiększenie jej, aby algorytm był w stanie dostać się do celu.

Zostaje wywołana ta sama procedura `search_A_star`, ale ze zwiększonym limitem głębokości, zatem nie jesteśmy pytani o zwiększenie limitu.

Węzeł `d` został odwiedzony i dodano jego sąsiadów do kolejki. Wybieramy węzeł `m` jako następny, aby algorytm zakończył swe działanie.

Wybrany zostaje jedyny z możliwych elementów i wyświetlana jest odkryta ścieżka w grafia (`a->c->d->m`).

## Opis funkcji
**start_A_star(InitState, PathCost, N, MaxDepth)**
Główna funkcja uruchamiająca procedurę. Parametr *N* określa maksymalną liczbę węzłów przedstawianych użytkownikowi, **MaxDepth** z kolei wyznacza maksymalną głębokość przeszukiwania.

start_A_star(InitState, PathCost, N, MaxDepth) :-
	score(InitState, 0, 0, InitCost, InitScore),
	search_A_star( [node(InitState, nil, nil, InitCost, InitScore ) ], [ ], PathCost, N, 0, MaxDepth).

**search_A_star(Queue, ClosedSet, PathCost, N, Depth, MaxDepth)**
Podobnie jak w przypadku **start_A_star** funkcja przyjmuje dodatkowe paramtery *N* i *MaxDepth*. Poza tym na wejściu dostaje także *Depth* określającą obecną głębokość przeszukiwania.

search_A_star(Queue, ClosedSet, PathCost, N, Depth, MaxDepth) :-
	my_trace(1, search_A_star, 1, ['Queue'/Queue, 'Depth'/Depth]),
	Depth =< MaxDepth,
	fetch(Node, Queue, ClosedSet, N),
	continue(Node, Queue, ClosedSet, PathCost, N, Depth, MaxDepth).
    
search_A_star(Queue, ClosedSet, PathCost, N, Depth, MaxDepth) :-
	Depth > MaxDepth,
	write("Limit korków osiągnięty. Wprowadź tak, aby zwiększyć limit."), nl,
	read(Input),
	Input = tak,
	NewMaxDepth is MaxDepth + 1,
	search_A_star(Queue, ClosedSet, PathCost, N, Depth, NewMaxDepth).

**continue(Node, RestQueue, ClosedSet, Path, N, Depth, MaxDepth)**

continue(node(State, Action, Parent, Cost, _), _, ClosedSet, path_cost(Path, Cost), _, _, _) :-
	goal( State), !,
	build_path(node(Parent, _ ,_ , _ , _ ) , ClosedSet, [Action/State], Path) .

continue(Node, RestQueue, ClosedSet, Path, N, Depth, MaxDepth) :-
	expand(Node, NewNodes),
	insert_new_nodes(NewNodes, RestQueue, NewQueue),
	NewDepth is Depth + 1,
	search_A_star(NewQueue, [Node | ClosedSet ], Path, N, NewDepth, MaxDepth).

**fetch_n(Nodes, N, Queue, ClosedSet)**
Procedura wyjmuje pierwsze *N* węzłów nienależących do *ClosedSet* z kolejki *Queue*. Wynik umieszcza w *Nodes*.

fetch_n([], 0, _, _).
fetch_n([], _, [], _).

fetch_n([H | RestNodes], N, [H | RestQueue], ClosedSet) :-
	N \= 0,
	\+ member(H, ClosedSet), !,
	NewN is N - 1,
	fetch_n(RestNodes, NewN, RestQueue, ClosedSet).

fetch_n(Nodes, N, [ _ |RestQueue], ClosedSet) :-
	N \= 0,
	fetch_n(Nodes, N, RestQueue, ClosedSet).

**choose_element(X, ChoiceList)**
Wybiera element z *ChoiceList* i umieszcza go w *X*.

choose_element(X, [X | _]) :-
	my_trace(1, choose_element, 1, ['X'/X]).
choose_element(X, [_ | Rest]) :-
	choose_element(X, Rest).

**select_nth(Node, Nodes, Index)**
Wybiera *Nodes[Index]* i umieszcza go w *Node*.

select_nth(Node, [Node | _], 1).
select_nth(Node, [_ | Rest], Idx) :-
	Idx \= 1,
	NewIdx is Idx - 1,
	select_nth(Node, Rest, NewIdx).

**fetch(Node, Queue, ClosedSet, N)**
Wyciąga *N* elementów z kolejki *Queue*, prezentuje je użytkownikowi, prosząć aby podał kolejność odwiedzania węzłów. Następnie zwraca kolejne węzły zgodnie z kolejnością zdefiniowaną przez użytkownika.

Procedury **expand**, **score**, **insert_new_nodes**, **insert_p_queue**, **build_path** oraz **del** pozostają bez zmian.

## Kod źródłowy programu

:- include('my_trace.pl').

start_A_star(InitState, PathCost, N, MaxDepth) :-
	score(InitState, 0, 0, InitCost, InitScore),
	search_A_star( [node(InitState, nil, nil, InitCost, InitScore ) ], [ ], PathCost, N, 0, MaxDepth).

search_A_star(Queue, ClosedSet, PathCost, N, Depth, MaxDepth) :-
	my_trace(1, search_A_star, 1, ['Queue'/Queue, 'Depth'/Depth]),
	Depth =< MaxDepth,
	fetch(Node, Queue, ClosedSet, N),
	continue(Node, Queue, ClosedSet, PathCost, N, Depth, MaxDepth).

search_A_star(Queue, ClosedSet, PathCost, N, Depth, MaxDepth) :-
	Depth > MaxDepth,
	write("Limit korków osiągnięty. Wprowadź tak, aby zwiększyć limit."), nl,
	read(Input),
	Input = tak,
	NewMaxDepth is MaxDepth + 1,
	search_A_star(Queue, ClosedSet, PathCost, N, Depth, NewMaxDepth).

continue(node(State, Action, Parent, Cost, _), _, ClosedSet, path_cost(Path, Cost), _, _, _) :-
	goal( State), !,
	build_path(node(Parent, _ ,_ , _ , _ ) , ClosedSet, [Action/State], Path) .

continue(Node, RestQueue, ClosedSet, Path, N, Depth, MaxDepth) :-
	expand(Node, NewNodes),
	insert_new_nodes(NewNodes, RestQueue, NewQueue),
	NewDepth is Depth + 1,
	search_A_star(NewQueue, [Node | ClosedSet ], Path, N, NewDepth, MaxDepth).

fetch_n([], 0, _, _).
fetch_n([], _, [], _).

fetch_n([H | RestNodes], N, [H | RestQueue], ClosedSet) :-
	N \= 0,
	\+ member(H, ClosedSet), !,
	NewN is N - 1,
	fetch_n(RestNodes, NewN, RestQueue, ClosedSet).

fetch_n(Nodes, N, [ _ |RestQueue], ClosedSet) :-
	N \= 0,
	fetch_n(Nodes, N, RestQueue, ClosedSet).

choose_element(X, [X | _]) :-
	my_trace(1, choose_element, 1, ['X'/X]).
choose_element(X, [_ | Rest]) :-
	choose_element(X, Rest).

select_nth(Node, [Node | _], 1).
select_nth(Node, [_ | Rest], Idx) :-
	Idx \= 1,
	NewIdx is Idx - 1,
	select_nth(Node, Rest, NewIdx).

fetch(Node, Queue, ClosedSet, N) :-
	fetch_n(Nodes, N, Queue, ClosedSet),
	my_trace(1, fetch, 1, ['ClosedSet'/ClosedSet, 'Nodes'/Nodes]),
	write("Wprowadź listę wyboru:"), nl,
	read(ChoiceList),
	choose_element(ChoosedElement, ChoiceList),
	select_nth(Node, Nodes, ChoosedElement).

expand(node(State, _ ,_ , Cost, _ ), NewNodes)  :-
	findall(node(ChildState, Action, State, NewCost, ChildScore) ,
			(succ(State, Action, StepCost, ChildState),
			    score(ChildState, Cost, StepCost, NewCost, ChildScore)),
			NewNodes).


score(State, ParentCost, StepCost, Cost, FScore)  :-
	Cost is ParentCost + StepCost ,
	hScore(State, HScore),
	FScore is Cost + HScore.


insert_new_nodes( [ ], Queue, Queue).

insert_new_nodes( [Node|RestNodes], Queue, NewQueue) :-
	insert_p_queue(Node, Queue, Queue1),
	insert_new_nodes( RestNodes, Queue1, NewQueue).


insert_p_queue(Node, [ ], [Node]) :- !.

insert_p_queue(node(State, Action, Parent, Cost, FScore),
		[node(State1, Action1, Parent1, Cost1, FScore1)|RestQueue],
			[node(State1, Action1, Parent1, Cost1, FScore1)|Rest1] )  :-
	FScore >= FScore1,  ! ,
	insert_p_queue(node(State, Action, Parent, Cost, FScore), RestQueue, Rest1).

insert_p_queue(node(State, Action, Parent, Cost, FScore),  Queue,
				[node(State, Action, Parent, Cost, FScore)|Queue]).


build_path(node(nil, _, _, _, _), _, Path, Path) :- !.

build_path(node(EndState, _, _, _, _), Nodes, PartialPath, Path) :-
	del(Nodes, node(EndState, Action, Parent, _, _), Nodes1) ,
	build_path( node(Parent,_ ,_ , _ , _ ) , Nodes1, [Action/EndState|PartialPath],Path).


del([X|R],X,R).
del([Y|R],X,[Y|R1]) :-
	X\=Y,
	del(R,X,R1).

succ(a, ab, 2, b).
succ(b, bf, 3, f).
succ(a, ac, 3, c).
succ(b, bg, 4, g).
succ(c, cd, 2, d).
succ(d, dm, 1, m).
succ(c, ce, 3, e).
succ(e, em, 5, m).
succ(f, fm, 3, m).

goal(m).

hScore(a, 4).
hScore(b, 4).
hScore(f, 7).
hScore(g, 1).
hScore(m, 0).
hScore(c, 3).
hScore(d, 1).
hScore(e, 4).