Journey through Labyrinth 20x20 with 2 enters and 2 exits

Question

I try to make journey through a labyrinth. Length of lab. is 20x20 and it have two entrance and two east.

entrance(1,3).

east(4,5).

enter1(20,8).

enter2(15,4).

exit1(14,2).

exit2(2,8).

wall(1,1).
wall(1,2).
wall(1,4).
wall(1,5).
wall(2,2).
wall(2,2).
wall(2,4).
wall(2,5).
wall(3,1).
wall(3,2).
wall(3,5).
wall(4,1).
wall(4,2).
wall(4,3).
wall(5,1).
wall(5,2).
wall(5,3).
wall(5,4).
wall(4,5).

member(X,[X|_]).
member(X,[_|T]) :- member(X,T) .

go(ZX,ZY,CZ,ZY) :- CX is ZX + 1, not(wall(CX,ZY)), CX < 21, CX > 0.
go(ZX,ZY,CZ,ZY) :- CX is ZX - 1, not(wall(CX,ZY)), CX < 21, CX > 0.
go(ZX,ZY,ZX,CY) :- CY is ZY + 1, not(wall(ZX,CY)), CY < 21, CY > 0.
go(ZX,ZY,ZX,CY) :- CY is ZY - 1, not(wall(ZX,CY)), CY < 21, CY > 0.

find_way( a(X,Y)  , a(X,Y) , P ) :-
  write(P).
find_way( a(X,JY) , a(I,J) , P ) :-
  go(X,Y,NI,NJ) ,
  not( member(a(NI, NJ) , P ) ,
  find_way( a(NI,NJ) , a(I,J) , [a(NI,NJ),P] ).

way :-
  entrance(X,Y) ,
  east(S,K) ,
  find_way( a(X,Y) , a(S,K) , [ ] ) .

I have this:

find_way(enter1(20,8),exit1(14,2), P).

but when i use it, it fails. Can anybody tell me, how can I make it work, please?

Answer 1

It's not exactly clear how your model works. For instance,

• what is east/2?
• what is entrance1/2 or entrance2/2?
• what is exit1/2 or exit2/2?

However, your model seems to define the maze as a grid with certain cells marked as walls, entrances or exits. Further, you seem to define things in negative terms, rather than defining the connections between each cell.

But either way, finding a path through a maze is just a graph traversal, something like this.

First, some definitions:

• Cells are denoted as an X/Y pair thus: X:Y.

• wall/1
  defines the cells that are walls.

• entrance/1
  defines the cells that are marked as entrances. I'm dispensing with an explicit exits here: one can travel either direction through a doorway.

Both of these predicates take a single X:Y pair as their single argument.

So, to find a path through the maze, we can do something like this:

find_path_through_maze( P ) :- % to find a path through a maze, 
  entrance(X,Y) ,              % - we first need to find an entrance
  explore( X:Y , [] , V ) ,    % - and then we go exploring, seeding it with an empty list of visited cells
  reverse(V,P)                 % once we're done, we reverse the path we got and unify it with the result
  .                            % Easy!

Finding a path is easy:

explore( X:Y , [V|Vs] , [X:Y|V] ) :-  % we can exit the maze via any entrance
  entrance(X:Y) ,                     % - though note the stricture that the visited list has to be non-empty
  .                                   % 
explore( X:Y , V , P ) :-             % otherwise
  adjacent(X:Y,X1:Y1) ,               % - we find an adjacent room
  \+ visited(X1:Y1,V) ,               % - that we haven't yet visited
  explore_maze( X1:Y1 , [X:Y|V] , P ) % - and [recursively explore that
  .                                   % Easy!

Determining whether or not we've visited a room is simple, too. It should be self-explanatory:

visited( X:Y , [X:Y|_] ) :- ! .
visited( X:Y , [V|Vs]  ) :-
  V \= X:Y ,
  visited(X:Y,Vs)
  .

Determining adjacency is probably the most complicated exercise:

adjacent( X:Y , X1:Y1 ) :-        % an adjacent room is computed by
  offset( Offset_X , Offset_Y ) , % - getting an pair of offsets
  X1 is X + Offset_X ,            % - incrementing the X value by its offset
  between(1,20,X1) ,              % - the result must be within the valid domain of X
  Y1 is Y + offset_Y ,            % - incrementing the Y value by its offset
  between(1,20,Y1) ,              % - the result must be within the valid domain of Y
  \+ wall(X1,Y1)                  % - Make sure we don't walk into a wall
  .                               %

offset( -1 , -1 ) .
offset( -1 ,  0 ) .
offset( -1 ,  1 ) .
offset(  0 , -1 ) .
offset(  0 ,  1 ) .
offset(  1 , -1 ) .
offset(  1 ,  0 ) .
offset(  1 , -1 ) .