Prolog: Finding path in a maze

Question

Let's say we have a robot that is on a Chess Board and can move like a King can.

The board is with coords from [1,1] to [8,8].

The starting position is [1,1] the final is [8,8]. There is a list X that contains lists of obstacle's coords for example [[1,4],[2,5],[5,6]]. The problem is: is there a possible way for the robot to move from the starting to the final position.

I made this predicates:

path([A,B],_):- A is 8, B is 8.
path([A,B],X):- 
        possibleMoves(A,B,L), % possibleMoves returns a list of all the possible coords that
        the robot can go to. (Example for [1,1] are [[0,1],[0,0],[2,1]...])

        member([Ex,Ey],L), % member generates all the possible members from the list L
        not(member([Ex,Ey],X)), % if this member is not member of the "forbidden ones"
        Ex<9,Ex>0,Ey<9,Ey>0, % and its coords are on the board
        path([Ex,Ey],X).


isTherePath(X):- possibleMoves(1,1,L),
                 member(E,L),
                 path(E,X).

But there is a mistake and it does not return any value. The recursion never stops I can't find why.

What is the intention of the first line? It will always assign 8's to A and B. I guess you want to compare instead of assigning. — Eugene Sh., Nov 20 '14 at 20:32

score 2 · Accepted Answer · edited May 23 '17 at 12:04

2

Define in one predicate, what a valid step is - including all restrictions you have. Stick to this naming convention: X0 the "first" value, X the "last" value

step(Forbidden,[X0,Y0],[X,Y]) :-
   possibleMoves(X0,Y0,L), % rather: possibleMove([X0,Y0],L),
   member([X,Y],L),
   between(1,8,X),
   between(1,8,Y),
   non_member([X,Y],Forbidden).

Now you have a path with:

 ..., closure0(step(Forbidden), S0,S), ...

closure0/3 takes care of cycles.

edited May 23 '17 at 12:04

Community

1
1

answered Nov 20 '14 at 20:43

false

10,264
13
101
209

1

Thanks but I can't use closure I have to make my own predicate. Can't I make a predicate `step` that could check if the coords that I am at the moment are the final coords. And if I am not I would use this step that you defined. – chnging Nov 20 '14 at 22:24

Prolog: Finding path in a maze

1 Answers1