I want to implement a maze solving algorithm in Prolog. Therefore i searched for some maze solving algorithms and found the following: http://www.cs.bu.edu/teaching/alg/maze/
FIND-PATH(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
I already build a matrix in prolog, which represents a maze and where 0 is open and 1 is the wall, for example (starting position would be (2|1) and the goal is located at (4|1)):
11111
10001
10101
Further more i defined a clause named mazeDataAt(Coord_X, Coord_Y, MazeData, Result)
, which gives me the value of the matrix on a certain position.
So far. But now i have a problem implementing that algorithm in prolog. I already tried "the dirty way" (translate it one by one by use of nested if statements), but that escalated complexity and i don't think it's the way you do it in prolog.
So i tried this:
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).
But this attempt didn't work like expected.
Actually, is this a correct prolog implementation of the algorithm above? How can i see if this approach really finds a path through the maze? Therefore how can i record the path or get the solution path (what is done by marking / unmarking the path in the algorithm above)?
Thank you very much for your help!
Thanks to your answers! I adopted a more prolog like solution (see here) to solve my problem. So i now have:
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).
So far, this works. And i think i understand why the prolog way is much better. But now i have a small problem left.
I want my knowledge base be "dynamic". I can't define all the edges for every single waypoint in the maze. Therefore i wrote a clause named is_adjacent([X1, Y1], [X2, Y2])
which is true when [X1, Y1]
is a neighbor of [X2, Y2]
.
I also have a list Waypoints = [[2, 1], [2, 2]| ...]
which contains all possible waypoints in my maze.
Now the question: How can i use this to make my knowledge base "dynamic"? So that i can use it in the go
clause for finding the path?
Thanks for your help!
Ok, now i got all waypoints as facts:
w(2, 1).
w(2, 2).
...
I took the solution from Boris in one of his answers:
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.
After that, I updated the go
clause, so that it fits:
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).
But if i try to ask go(2, 1, 19, 2, R)
prolog enters an infinite loop. If i try something easier like go(2, 1, 3, 8, R)
it works and i get the solution path in R
.
What am i doing wrong? What did i forget?
(this answer uses the same path finding algorithm as this answer)
EDIT 2
Indeed, if your input is just which cells of the rectangular matrix are not walls, you would need to somehow translate this to rules of the kind "you can get from A to B". If your waypoints are then:
w(2,1).
w(2,2).
etc, then you can translate the algorithm you originally pointed to into a Prolog rule like this:
% 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
Note two things:
next_w
. When d
is called, it uses next_w
to generate the four possible neighbor squares (assuming you can only go up/down/left/right) and then checks whether this square is indeed a waypoint. You would not need to check both ways any more.ANOTHER EDIT: Full code
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).
You can call it with
? go(0,0,5,4,[],Path).
and you should get the two possible solutions.
In other words, I think your problem is the semicolon; it is no longer necessary, because you explicitly create all possible moves.