Пролог алгоритм решения лабиринта

Question

Я хочу реализовать алгоритм решения лабиринта в Прологе. Поэтому я искал некоторые алгоритмы решения лабиринта и нашел следующее: http://www.cs.bu.edu/teaching/alg/maze/

НАЙТИ-ПУТЬ (x, y):

if (x,y outside maze) return false
if (x,y is goal) return true
if (x,y not open) return false
mark x,y as part of solution path
if (FIND-PATH(North of x,y) == true) return true
if (FIND-PATH(East of x,y) == true) return true
if (FIND-PATH(South of x,y) == true) return true
if (FIND-PATH(West of x,y) == true) return true
unmark x,y as part of solution path
return false 

Я уже построил матрицу в прологе, которая представляет лабиринт и где 0 открыт, а 1 - стена, например (начальная позиция будет (2|1), а цель расположена в (4|1)):

11111
10001
10101

Более того, я определил пункт с именем mazeDataAt(Coord_X, Coord_Y, MazeData, Result), что дает мне значение матрицы на определенной позиции.

До сих пор. Но теперь у меня проблема с реализацией этого алгоритма в прологе. Я уже пробовал "грязный путь" (переводить его один за другим, используя вложенные операторы if), но это усложняло задачу, и я не думаю, что это так, как вы делаете это в прологе.

Итак, я попробовал это:

isNotGoal(X, Y) :- 
    X = 19, Y = 2.

notOpen(X, Y, MazeData) :-
    mazeDataAt(X, Y, MazeData, 1). 

findPath(X, Y, MazeData) :- 
    isNotGoal(X, Y),
    notOpen(X, Y, MazeData),
    increase(Y, Y_New),
    findPath(X, Y_New, MazeData),
    increase(X, X_New),
    findPath(X_New, Y, MazeData),
    decrease(Y, Y_New),
    findPath(X, Y_New, MazeData),
    decrease(X, X_New),
    findPath(X, Y_New, MazeData).

Но эта попытка не сработала, как ожидалось.

На самом деле, это правильная реализация пролога алгоритма выше? Как я могу увидеть, если этот подход действительно находит путь через лабиринт? Поэтому, как я могу записать путь или получить путь решения (что делается путем маркировки / снятия пометки пути в алгоритме выше)?

Большое спасибо за Вашу помощь!

//ОБНОВИТЬ

Спасибо за ваши ответы! Я принял решение, более похожее на пролог (см. Здесь), чтобы решить мою проблему. Итак, теперь у меня есть:

d([2,1], [2,2]).
d([2,2], [1,2]).
d([2,2], [2,3]).

go(From, To, Path) :-
go(From, To, [], Path).

go(P, P, T, T).
go(P1, P2, T, NT) :-
    (d(P1, P3) ; d(P3, P2)),
    \+ member(P3, T),
    go(P3, P2, [P3|T], NT).

Пока это работает. И я думаю, что понимаю, почему путь пролога намного лучше. Но теперь у меня осталась небольшая проблема.

Я хочу, чтобы моя база знаний была "динамичной". Я не могу определить все края для каждой путевой точки в лабиринте. Поэтому я написал статью под названием is_adjacent([X1, Y1], [X2, Y2]) что верно, когда [X1, Y1] сосед [X2, Y2],

У меня тоже есть список Waypoints = [[2, 1], [2, 2]| ...] который содержит все возможные путевые точки в моем лабиринте.

Теперь вопрос: как я могу использовать это, чтобы сделать мою базу знаний "динамичной"? Так что я могу использовать его в go пункт для поиска пути?

Спасибо за вашу помощь!

// ОБНОВЛЕНИЕ 2

Хорошо, теперь я получил все путевые точки как факты:

w(2, 1).
w(2, 2).
...

Я взял решение у Бориса в одном из его ответов:

d(X0, Y0, X , Y) :-
    w(X0, Y0),
    next_w(X0, Y0, X, Y),
    w(X, Y).

next_w(X0, Y0, X0, Y) :- Y is Y0 + 1.
next_w(X0, Y0, X0, Y) :- Y is Y0 - 1.
next_w(X0, Y0, X, Y0) :- X is X0 + 1.
next_w(X0, Y0, X, Y0) :- X is X0 - 1.

После этого я обновил go пункт, так что он подходит:

go(X1, Y1, X2, Y2, Path) :-
go(X1, Y1, X2, Y2, [], Path).

go(X, Y, X, Y, T, T).
go(X1, Y1, X2, Y2, T, NT) :-
   (d(X1, Y1, X3, Y3) ; d(X3, Y3, X1, Y1)),
\+ member([X3, Y3], T),
go(X3, Y3, X2, Y2, [[X3, Y3]|T], NT).

Но если я попытаюсь спросить go(2, 1, 19, 2, R) пролог входит в бесконечный цикл. Если я попробую что-нибудь попроще go(2, 1, 3, 8, R) это работает, и я получаю путь решения в R,

Что я делаю неправильно? Что я забыл?

Answer 1

(этот ответ использует тот же алгоритм поиска пути, что и этот ответ)

РЕДАКТИРОВАТЬ 2

Действительно, если вы указываете, какие ячейки прямоугольной матрицы не являются стенами, вам нужно как-то перевести это на правила типа "вы можете добраться от А до В". Если ваши путевые точки тогда:

w(2,1).
w(2,2).

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

% it is possible to move from (X0,Y0) to (X,Y)
d(X0,Y0,X,Y) :-
    w(X0,X0), % you can skip this check if you know for sure
              % that your starting point is a valid waypoint
              % or if you want to be able to start from inside
              % a wall :)
    next_w(X0,Y0,X,Y),
    w(X,Y).
% neighboring waypoints
next_w(X0,Y0,X0,Y) :- Y is Y0+1. % go up I guess
next_w(X0,Y0,X0,Y) :- Y is Y0-1. % go down
next_w(X0,Y0,X,Y0) :- X is X0+1. % go left
next_w(X0,Y0,X,Y0) :- X is X0-1. % go right

Обратите внимание на две вещи:

1. Я использую правило 4 аргументов для возможных ходов от квадрата (поэтому отрегулируйте соответственно)
2. Магия происходит в next_w, когда d называется, он использует next_w чтобы сгенерировать четыре возможных соседних квадрата (при условии, что вы можете только идти вверх / вниз / влево / вправо), а затем проверяет, действительно ли этот квадрат является путевой точкой. Вам больше не нужно проверять оба пути.

ДРУГОЕ РЕДАКТИРОВАНИЕ: Полный код

w(0,0).
w(0,1). w(1,1). w(2,1). w(3,1). w(4,1). w(5,1).
        w(1,2).         w(3,2).         w(5,2).
        w(1,3).         w(3,3).         w(5,3).
w(0,4). w(1,4). w(2,4).         w(4,4). w(5,4).
                w(2,5). w(3,5). w(4,5).

d(X0,Y0,X,Y) :- next_w(X0,Y0,X,Y), w(X,Y).
next_w(X0,Y0,X0,Y) :- Y is Y0+1.
next_w(X0,Y0,X,Y0) :- X is X0+1.
next_w(X0,Y0,X0,Y) :- Y is Y0-1.
next_w(X0,Y0,X,Y0) :- X is X0-1.

go(X,Y,X,Y,Path,Path).
go(X0,Y0,X,Y,SoFar,Path) :-
    d(X0,Y0,X1,Y1),
    \+ memberchk( w(X1,Y1), SoFar ),
    go(X1,Y1,X,Y,[w(X1,Y1)|SoFar],Path).

Вы можете позвонить с

? go(0,0,5,4,[],Path).

и вы должны получить два возможных решения.

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