Путешествие через лабиринт 20x20 с 2 входами и 2 выходами

Question

Я пытаюсь совершить путешествие по лабиринтам. Длина лаборатории. 20x20 и имеет два входа и два восточных.

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) , [ ]) . 

У меня есть это:

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

но когда я использую его, он выходит из строя. Может ли кто-нибудь сказать мне, как я могу заставить его работать, пожалуйста?

Answer 1

Непонятно, как работает ваша модель. Например,

• Что такое east/2?
• Что такое entrance1/2 или entrance2/2?
• Что такое exit1/2 или exit2/2?

Однако ваша модель, по-видимому, определяет лабиринт как сетку с определенными ячейками, обозначенными как стены, входы или выходы. Кроме того, вы, кажется, определяете вещи в отрицательных терминах, а не определяете связи между каждой ячейкой.

Но в любом случае найти путь через лабиринт - это просто обход графика, что-то вроде этого.

Во-первых, некоторые определения:

• Клетки обозначены как X/Y пары таким образом: X:Y.

• wall/1
  определяет ячейки, которые являются стенами.

• entrance/1
  определяет ячейки, отмеченные как входы. Я раздаю явные выходы здесь: можно пройти в любом направлении через дверной проем.

Оба этих предиката принимают одну пару X:Y в качестве единственного аргумента.

Таким образом, чтобы найти путь через лабиринт, мы можем сделать что-то вроде этого:

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! 

найти путь легко:

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! 

Определение у того или нет, мы посетили номер просто. Это должно быть очевидно:

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

Определение смежности, вероятно, является наиболее сложным упражнение:

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