Prolog maze solving algorithm

algorithmmazeprologrecursion

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!

//UPDATE

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!

//UPDATE 2

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?

Best Answer

(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:

I am using a 4-argument rule for the possible moves from a square (so adjust accordingly)
The magic happens in 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.

Related Solutions

.net – the best algorithm for overriding GetHashCode

I usually go with something like the implementation given in Josh Bloch's fabulous Effective Java. It's fast and creates a pretty good hash which is unlikely to cause collisions. Pick two different prime numbers, e.g. 17 and 23, and do:

public override int GetHashCode()
{
    unchecked // Overflow is fine, just wrap
    {
        int hash = 17;
        // Suitable nullity checks etc, of course :)
        hash = hash * 23 + field1.GetHashCode();
        hash = hash * 23 + field2.GetHashCode();
        hash = hash * 23 + field3.GetHashCode();
        return hash;
    }
}

As noted in comments, you may find it's better to pick a large prime to multiply by instead. Apparently 486187739 is good... and although most examples I've seen with small numbers tend to use primes, there are at least similar algorithms where non-prime numbers are often used. In the not-quite-FNV example later, for example, I've used numbers which apparently work well - but the initial value isn't a prime. (The multiplication constant is prime though. I don't know quite how important that is.)

This is better than the common practice of XORing hashcodes for two main reasons. Suppose we have a type with two int fields:

XorHash(x, x) == XorHash(y, y) == 0 for all x, y
XorHash(x, y) == XorHash(y, x) for all x, y

By the way, the earlier algorithm is the one currently used by the C# compiler for anonymous types.

This page gives quite a few options. I think for most cases the above is "good enough" and it's incredibly easy to remember and get right. The FNV alternative is similarly simple, but uses different constants and XOR instead of ADD as a combining operation. It looks something like the code below, but the normal FNV algorithm operates on individual bytes, so this would require modifying to perform one iteration per byte, instead of per 32-bit hash value. FNV is also designed for variable lengths of data, whereas the way we're using it here is always for the same number of field values. Comments on this answer suggest that the code here doesn't actually work as well (in the sample case tested) as the addition approach above.

// Note: Not quite FNV!
public override int GetHashCode()
{
    unchecked // Overflow is fine, just wrap
    {
        int hash = (int) 2166136261;
        // Suitable nullity checks etc, of course :)
        hash = (hash * 16777619) ^ field1.GetHashCode();
        hash = (hash * 16777619) ^ field2.GetHashCode();
        hash = (hash * 16777619) ^ field3.GetHashCode();
        return hash;
    }
}

Note that one thing to be aware of is that ideally you should prevent your equality-sensitive (and thus hashcode-sensitive) state from changing after adding it to a collection that depends on the hash code.

As per the documentation:

You can override GetHashCode for immutable reference types. In general, for mutable reference types, you should override GetHashCode only if:

You can compute the hash code from fields that are not mutable; or

You can ensure that the hash code of a mutable object does not change while the object is contained in a collection that relies on its hash code.

The link to the FNV article is broken but here is a copy in the Internet Archive: Eternally Confuzzled - The Art of Hashing

Problem with Maze Algorithm

what seems to be missing is the check if X&Y has already been marked as part of the solution, and if so we abort. (this should be somewhere on point 3.5)

If not a maze with a possible loop somewhere would run indefinately and blow up the stack

by the way, from what I read the algorithm is based on a maze with only 1 solution