Pathfinding in SWI-Prolog (Generate and Test Method)

Question

Ok, so I am trying to build a path-finding SWI-Prolog program that takes the grid to traverses' properties from facts in the knowledge base:

y_max(Ymax).
x_max(Xmax).
pick_up(Y,X).

So for example, the code below represents a grid below it here:

y_max(6).
x_max(6).
pick_up(4,4).
pick_up(3,2).

% 6 | | | | | |F|
%   -------------
% 5 | | | | | | |
%   -------------
% 4 | | | |P| | |
%   -------------
% 3 | |P| | | | |
%   -------------
% 2 | | | | | | |
%   -------------
% 1 |L| | | | | |
%    1 2 3 4 5 6

% (Note that coordinates will be in the form [Y,X].

Where F is to be the start of the path, being [6,6], L is to be the end of the path, [1,1], and the path should be so that as many pick_up "objects" are picked up along the path as possible. so in this case an "ideal" solution would be:

% 6 | | | | |X|F|
%   -------------
% 5 | | | |X|X| |
%   -------------
% 4 | |X|X|P| | |
%   -------------
% 3 |X|P| | | | |
%   -------------
% 2 |X| | | | | |
%   -------------
% 1 |L| | | | | |
%    1 2 3 4 5 6

where the path P would be: P = [[6,6],[6,5],[5,5],[5,4],[4,4],[4,3],[4,2],[3,2],[3,1],[2,1],[1,1]]

my main relation will be:

solve(P,A) :-

which will return, based on the knowledge base giving the graph, an ideal (shortest) path P, and A, with A being the number of pickup objects picked up by the path (which should be the maximum number of pickup objects that can be picked up.

I am trying to do this using a generate and test type approach. Because the length of the path cannot be known based on the knowledge base (as far as I'm aware), I'm assuming I will have to recursively generate and test coordinates? I'm trying to do this exercise without using any libraries to really get a grasp on this style of Prolog programming, where I generate and test the path.

Here is what I have so far, but I just can't seem to get it right. Instead it just gives me ERROR: Out of Global stack each time.

% FACTS
y_max(6).
x_max(6).
pick_up(5,5).
pick_up(4,4).
pick_up(2,2).

solve(A,P) :-
   y_max(Y), x_max(X), aggregate_all(count,pick_up(O,E),C),
   A = C, append(P,[Y,X],Np), build_path(Y,X,Y,X,P),                                                                                                                                         
   % I'm assuming at this point the list is generated, now to test...
   member([Y,X],P), is_last([1,1],P), member([O,E],P).

% cases to end recursion - not sure if I'm doing this part correctly...                                                                                                                                        
build_path(Y,X,1,2,P) :- append(P,[1,1],Q), P = Q.
build_path(Y,X,2,1,P) :- append(P,[1,1],Q), P = Q.

% recursive case                                                                                                                                                                                               
build_path(Y,X,PrevY,PrevX,P) :-
   integer(NextY), integer(NextX),
   NextY =< Y, NextY >= 1,
   NextX =< X, NextY >= 1,
   (  (NextY =:= PrevY-1, NextX =:= PrevX)
   ;  (NextY =:= PrevY+1, NextX =:= PrevX)
   ;  (NextY =:= PrevY, NextX =:= PrevX+1)
   ;  (NextY =:= PrevY, NextX =:= PrevX-1)
   ),
   append(P,[NextY,NextX],Np),
   build_path(Y,X,NextY,NextX,Np).

is_last([Y,X],[H|[]]) :- H = [Y,X].
is_last([Y,X],[H|T]) :- is_last([Y,X],T).

So, what am I doing wrong? I can't seem to find a similar example online that would give me the right idea. I'm assuming I'm just over-complicating things or am not expressing certain information to Prolog properly. I apologize if my solution is full of errors. I'm just trying to get a grasp on Prolog currently.

Tomas By Tomas By · Accepted Answer · 2018-04-14T16:56:11

Here is a version of build_path/N that seems to work.

build_path(MaxY,MaxX,Y0,X0,P0,P,Is0,Is) :-
  ( Y0 = 1, X0 = 1 ->
    P = P0, Is = Is0
  ; ( Y is Y0 - 1, X is X0
    ; Y is Y0 + 1, X is X0
    ; Y is Y0, X is X0 + 1
    ; Y is Y0, X is X0 - 1 ),
    Y =< MaxY, Y >= 1, X =< MaxX, X >= 1, \+ member(Y-X,P0),
    append(P0,[Y-X],P1),
    ( pick_up(Y,X) -> Is1 = [Y-X|Is0] ; Is1 = Is0 ),
    build_path(MaxY,MaxX,Y,X,P1,P,Is1,Is) ).

You need to make sure it stops when it hits the end square, so you need to use if-then-else, or a cut.

I added a list of picked up items, so now you just need to find the optimal combination of path and list.

Pathfinding in SWI-Prolog (Generate and Test Method)

2 Answers