Prolog 中的寻路问题

Question

所以我这里有一个序言程序接受这样的输入：

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).

几乎所有你需要知道的就是 j's 基本上是墙。我需要做的是从地图 (1,1) 的右上角开始，我需要找到一个 p，一个 e，然后找到 mb，然后依次找到 mt。这是我当前的代码：

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).

现在，当我将代码加载到 SWI 时，我的代码 "complies" 很好，但是当我用上面的测试调用 mazepath 时，一些奇怪的事情发生了。当我追踪它时，它正在查看相邻的方块，看我们是否可以走到一个方块。它从 (1,1) 开始，因此 (1,0) 和 (0,1) 应该在尝试走到那里时失败。好吧，他们这样做了，但是当我的程序查看 (0,1) 时，inBounds 失败，然后整个程序 returns false 而不是继续寻找路径。我不明白为什么它只看 (1,1) 周围的空间而不是移动到一个开放的空间并再次寻找大师球。有任何想法吗？

Answer 1

您的代码存在编译问题：

findMasterball/6 的递归情况：在最后一个子句 \+ memberchk([Xn,Yn],PathMB) 之后有一个逗号而不是句点。
findPika/5 的递归情况：在最后一个子句 \+ memberchk([Xn,Yn],PikaPath) 之后有一个逗号而不是句点。

您的代码也存在语义问题：

在findMewtoo/6中，最后一个参数是rPathM在头部和递归调用：这是一个原子，不是变量，这几乎肯定不是你想。将 r 更改为 R.
同样的问题存在于findMasterball/6，参数newPath在头部。

解决所有这些问题后，您仍然会注意到 SWI-Prolog 告诉您：

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]

这意味着那些行（对应于规则头）的那些变量在整个规则中只使用了一次，这几乎肯定意味着这是一个错误：因为Prolog是关于变量之间的关系，它几乎总是一个变量只出现一次是没有意义的。这要么意味着我们不关心那个变量的值（在这种情况下用 _ 匿名），要么你的程序是错误的，因为一些变量没有被正确使用。

Prolog 中的寻路问题

Issues with Pathfinding in Prolog

prolog

path-finding