Prolog Maze Pathfinding

user_8173991 0
Viewed 54

Hey guys so I'm having a bit of an issue with writing a pathfinding functor to go from one square to the other. I can't figure out how to tell if a square has a neighbouring square.

The maze is a 5x5 grid with black squares denoting a wall.

square([1,1], white). square([1,2], white). square([1,3], white). square([1,4], white). square([1,5], white). 
square([2,1], white). square([2,2], black). square([2,3], black). square([2,4], black). square([2,5], white). 
square([3,1], white). square([3,2], black). square([3,3], white). square([3,4], black). square([3,5], white). 
square([4,1], white). square([4,2], black). square([4,3], white). square([4,4], white). square([4,5], white). 
square([5,1], white). square([5,2], white). square([5,3], white). square([5,4], white). square([5,5], white).

So far I've tried something like this:

neighbour([X,Y],[A,B]) :- 
    A is X + 1,
    B is Y + 1,
    square([X,Y], white), 
    square([A,B], white).

neighbour([X,Y],[A,B]) :- 
    A is X - 1,
    B is Y - 1,
    square([X,Y], white), 
    square([A,B], white).

neighbour([X,Y],[A,B]) :- 
    A is X + 1,
    B is Y - 1,
    square([X,Y], white), 
    square([A,B], white).

neighbour([X,Y],[A,B]) :- 
    A is X - 1,
    B is Y + 1,
    square([X,Y], white), 
    square([A,B], white).

neighbour([X,Y],[A,B]) :- 
    square([X,Y], white), 
    square([A,B], white), 
    A is X + 1;
    square([X,Y], white), 
    square([A,B], white),
    B is Y + 1.

neighbour([X,Y],[A,B]) :- 
    square([X,Y], white), 
    square([A,B], white), 
    A is X - 1;
    square([X,Y], white), 
    square([A,B], white),
    B is Y + 1.

neighbour([X,Y],[A,B]) :- 
    square([X,Y], white), 
    square([A,B], white), 
    A is X + 1;
    square([X,Y], white), 
    square([A,B], white),
    B is Y - 1.

neighbour([X,Y],[A,B]) :- 
    square([X,Y], white), 
    square([A,B], white), 
    A is X - 1;
    square([X,Y], white), 
    square([A,B], white),
    B is Y - 1.

route(X, Y, [X, Y]) :- neighbour(X, Y).
route(X, Z, [X | Route]) :- neighbour(X, Y), route(Y, Z, Route).

But when I call Route with say something like: Route([3,3], [1,5], Route). I end up with an incorrect list.

If anyone has any ideas or knows a better way of representing the likes of the maze, I'd really appreciate it!

path-finding prolog maze
2 Answers

Can express as:

square_black(X, 2) :-
    between(2, 4, X).

square_black(2, 3).
square_black(2, 4).
square_black(3, 4).

square_white(X, Y) :-
    between(1, 5, X),
    between(1, 5, Y),
    \+ square_black(X, Y).

neighbour(s(X, Y), s(X1, Y1)) :-
    % Determine delta of position
    member(XD, [-1, 0, 1]),
    member(YD, [-1, 0, 1]),
    % Prevent staying in same place
    \+ (XD = 0, YD = 0),
    % Calculate new position
    X1 is X + XD,
    Y1 is Y + YD,
    % Ensure new position is valid
    square_white(X1, Y1).

% The route from a place to the same place is empty
route([], X, X).
route([X|T], X, Z) :-
    neighbour(X, Y),
    route(T, Y, Z).

Result in swi-prolog:

?- length(R, _), route(R, s(3,3), s(1,5)).
R = [s(3,3),s(4,4),s(3,5),s(2,5)] ;
R = [s(3,3),s(4,3),s(4,4),s(3,5),s(2,5)] ;
R = [s(3,3),s(4,4),s(3,5),s(2,5),s(1,4)] ;
R = [s(3,3),s(4,4),s(4,5),s(3,5),s(2,5)] ;
R = [s(3,3),s(4,3),s(3,3),s(4,4),s(3,5),s(2,5)]
...
user_176283360

To understand your problem ask for neighbors of one place:

?- neighbour([1,1],N).
   N = [2,1]
;  N = [2,5], unexpected
;  N = [1,2]
;  N = [5,2], unexpected
;  N = [1,2]
;  N = [5,2], unexpected
;  N = [2,1]
;  N = [2,5], unexpected
;  false.

Is really 5,2 a neighbour of 1,1? Definitely not. So neighbour([1,1],[5,2]). should actually fail. I put some effort and removed clause after clause, until I just had one single clause:

neighbour([X,Y],[A,B]) :-
    square([X,Y], white), 
    square([A,B], white), 
    A is X + 1;
    square([X,Y], white), 
    square([A,B], white),
    B is Y + 1.

?- neighbour([1,1],[5,2]).
   true, unexpected
;  false.

The problem here is the formatting of the clause, it actually means:

neighbour([X,Y],[A,B]) :-
   (  square([X,Y], white), 
      square([A,B], white), 
      A is X + 1
   ;  square([X,Y], white), 
      square([A,B], white),
      B is Y + 1
   ).

So only one of the coordinates needs to be related. That is not enough. Always put the ; in front, never at the end. (Some older top level loops show the ; at the end which may explain this error. Newer systems like Scryer put it right in front)

user_7728680
Related