node(a,45,95).
node(b,90,95).
node(c,15,85).
node(d,40,80).
node(e,70,80).
node(f,25,65).
node(g,65,65).
node(h,45,55).
node(i,5,50).
node(j,80,50).
node(l,65,45).
node(m,25,40).
node(n,55,30).
node(o,80,30).
node(p,25,15).
node(q,80,15).
node(r,55,10).


edge(a,b,45).
edge(a,c,32).
edge(a,d,16).
edge(a,e,30).
edge(b,e,25).
edge(d,e,30).
edge(c,d,26).
edge(c,f,23).
edge(c,i,37).
edge(d,f,22).
edge(f,h,23).
edge(f,m,25).
edge(f,i,25).
edge(i,m,23).
edge(e,f,48).
edge(e,g,16).
edge(e,j,32).
edge(g,h,23).
edge(g,l,20).
edge(g,j,22).
edge(h,m,25).
edge(h,n,27).
edge(h,l,23).
edge(j,l,16).
edge(j,o,20).
edge(l,n,19).
edge(l,o,22).
edge(m,n,32).
edge(m,p,25).
edge(n,p,34).
edge(n,r,20).
edge(o,n,25).
edge(o,q,15).
edge(p,r,31).




aStar(Orig,Dest,Cam,Custo):-
    aStar2(Dest,[(_,0,[Orig])],Cam,Custo).

aStar2(Dest,[(_,Custo,[Dest|T])|_],Cam,Custo):-
	reverse([Dest|T],Cam).

aStar2(Dest,[(_,Ca,LA)|Outros],Cam,Custo):-
	LA=[Act|_],
	findall((CEX,CaX,[X|LA]),
		(Dest\==Act,edge(Act,X,CustoX),\+ member(X,LA),
		CaX is CustoX + Ca, estimativa(X,Dest,EstX),
		CEX is CaX +EstX),Novos),
	append(Outros,Novos,Todos),
	sort(Todos,TodosOrd),
	aStar2(Dest,TodosOrd,Cam,Custo).

estimativa(Nodo1,Nodo2,Estimativa):-
	node(Nodo1,X1,Y1),
	node(Nodo2,X2,Y2),
	Estimativa is sqrt((X1-X2)^2+(Y1-Y2)^2).