Issues with Pathfinding in Prolog

Question

So I have a prolog program here that takes an input like this:

mazepath(X,Y,Maze,Path,Score)
mazepath( 1, 1,  [[ o,  e,  j,  p,  o],
     [ o,  j,  o,  o,  o],
     [ o,  j, mt,  j,  o],
     [ o,  o,  e, o, o],
     [ p,  o,  j, mb,  o]], Path, Score).

Where pretty much all you need to know is j's are walls basically. What I need to do is from starting in the top right of the map (1,1) I need to find a p, an e, then find the mb, then find the mt in that order. Here is my current code:

mazePath(X,Y,Maze,Path,Score) :-
    curVal(X,Y,Maze,V0), %Get the value of the starting point
    findMasterball(X,Y,V0,Maze,Path,PathMB), %Find a path to the Masterball.
    nth1(1,PathMB,Room0), %Use the path generated by findMasterball to get the starting point for findMewtoo
    nth1(1,Room0,Xk),
    nth1(1,Room0,Yk),
    curVal(Xk,Yk,Maze,V1), %Get the value of the Masterball point
    findMewtoo(Xk,Yk,V1,Maze,[[Xk,Yk]],PathM), %Found masterball, starting for Mewtoo
    nth1(1,PathM,Room1), %Now find pika
    nth1(1,Room1,Xs),
    nth1(1,Room1,Ys),
    curVal(Xs,Ys,Maze,V2), %Get the value of the 
    findPika(Xs,Ys,V2,Maze,[[Xs,Ys]]). %Find pika

% findMasterball - recursive predicate that searches for the Masterball
% X,Y - current location
% Val - current value of location
% PathMB - Path traveled so far
% newPath - Path returned
%
%Base Case
findMasterball(_,_,Val,_,PathMB,PathMB) :-
    Val == 'mb',
    length(PathK,L),
    format('~w ~w',['\nPATH TO THE Masterball: ', PathK]),
    format('~w ~w',['\nLENGTH OF PATH: ', L]).

%Recursive Case
findMasterball(X,Y,_,Maze,PathMB,newPath) :-
    nth1(1,Maze,R), %Get width and height of the maze
    length(R,W),
    length(Maze,H),
    nextMove(X,Y,Xn,Yn,Maze,W,H), %Find the next legal move
    curVal(Xn,Yn,Maze,NVal), %Get the value of the next location
    \+ memberchk([Xn,Yn],PathMB), %Make sure we have not traveled to this location before


findMewtoo(_,_,Val,_,PathM,PathM) :-
    Val == 'mt',
    length(PathM,L),
    format('~w ~w',['\n\nPATH TO THE SWORD: ', PathM]),
    format('~w ~w',['\nLENGTH OF PATH: ', L]).

%Recursive Case
findMewtoo(X,Y,_,Maze,PathM,rPathM) :-
    nth1(1,Maze,R), %Get width and height of the maze
    length(R,W),
    length(Maze,H),
    nextMove(X,Y,Xn,Yn,Maze,W,H), %Find the next legal move
    curVal(Xn,Yn,Maze,NVal), %Get the value of the next location
    \+ memberchk([Xn,Yn],PathM), %Make sure we have not traveled to this location before
    findMewtoo(Xn,Yn,NVal,Maze,[[Xn,Yn]|PathM],rPathM). %Recursive call with the next location/value

% findPika - recursive predicate that searches for Pikachoo
% X,Y - current location
% Val - current value of location
% PathPika - Path traveled so far
%
%Base Case
findPika(_,_,Val,_,PikaPath) :-
    Val == 'p',
    length(PikaPath,L),
    format('~w ~w',['\n\nPATH TO THE DUNGEON LORD: ', PikaPath]),
    format('~w ~w',['\nLENGTH OF PATH: ', L]).

%Recursive Case
findPika(X,Y,_,Maze,PikaPath) :-
    nth1(1,Maze,R), %Get width and height of the maze
    length(R,W),
    length(Maze,H),
    nextMove(X,Y,Xn,Yn,Maze,W,H), %Find the next legal move. Doors are walkable.
    curVal(Xn,Yn,Maze,NVal), %Get the value of the next location
    \+ memberchk([Xn,Yn],PikaPath), %Make sure we have not traveled to this location before


% X0, Y0 - Current Location
% X, Y - Variables - Next move will be bound to these variables
% Maze  
% W, H - Width and height of the maze
nextMove(X0,Y0,X,Y,Maze,W,H) :-
    adj(X0,Y0,X,Y),
    inBounds(X,Y,W,H).


% Up
adj(X0,Y0,X0,Y) :-
    Y is Y0+1.

% Down
adj(X0,Y0,X0,Y) :-
    Y is Y0-1.

% Right
adj(X0,Y0,X,Y0) :-
    X is X0+1.

% Left
adj(X0,Y0,X,Y0) :-
    X is X0-1.

% Is X,Y within the bounds of the maze
inBounds(X,Y,W,H) :-
    X >= 1,
    Y >= 1,
    X =< W,
    Y =< H.

% Open space. 
roomOpen(X,Y,Maze) :-
    nth1(Y,Maze,R),
    nth1(X,R,'o').

% This is an egg, pick it up
roomOpen(X,Y,Maze) :-
    nth1(Y,Maze,R),
    nth1(X,R,'e').

% Here's pikachoo
roomOpen(X,Y,Maze) :-
    nth1(Y,Maze,R),
    nth1(X,R,'p').

% Is the masterball there? Pick it up & go catch mewtoo!
roomOpen(X,Y,Maze) :-
    nth1(Y,Maze,R),
    nth1(X,R,'mb').

% Is the mewtoo there?  Catch it if you have the masterball!!
roomOpen(X,Y,Maze) :-
    nth1(Y,Maze,R),
    nth1(X,R,'mt').


%Binds the value of the location of X,Y to Val
curVal(X,Y,Maze,Val) :-
    nth1(Y,Maze,R),
    nth1(X,R,Val).

Now, my code "complies" fine when I load it into SWI, but as soon as I call mazepath with the test above something strange is happening. As I trace through it, it is looking at adjacent squares to see if we can walk to one. It starts at (1,1) so (1,0) and (0,1) should fail when trying to walk there. Well they do, but when my program looks at (0,1), inBounds fails, then the entire program returns false instead of continuing and finding a path. I cannot understand why it is only looking at the spaces around (1,1) and not moving to an open one and looking for the masterball again. Any ideas?

Answer 1

There are compilation problems with your code:

• Recursive case of findMasterball/6: you have a comma after the last clause \+ memberchk([Xn,Yn],PathMB) instead of a period.
• Recursive case of findPika/5: you have a comma after the last clause \+ memberchk([Xn,Yn],PikaPath) instead of a period.

There are also semantical problems with your code:

• In findMewtoo/6, the last argument is rPathM in the head and the recursive call: this is an atom, not a variable, which is almost certainly not what you want. Change the r to a R.

• The same problem exists in findMasterball/6, with the argument newPath in the head.

After fixing all this, you will still notice that SWI-Prolog tells you this:

Warning: c:/test.pl:1:
        Singleton variables: [Score]
Warning: c:/test.pl:29:
        Singleton variables: [NewPath,NVal]
Warning: c:/test.pl:67:
        Singleton variables: [NVal]
Warning: c:/test.pl:80:
        Singleton variables: [Maze]

which means that those variables at those lines (corresponding to a rule head) are only used once in the entire rule, which almost certainly means that it is a mistake: since Prolog is about relations between variables, it almost always makes no sense that a variable would appear only once. It either means that we don't care about the value of that variable (in that case anonymize it with _), or that your program is wrong because some variables are not used properly.