Create a path in a grid in prolog

Question

I have to create a path between two given points in a grid in Prolog. The code I have so far is:

createPath(GridSize, BeginPosition, EndPosition, VisitedPoints, Path):-
    nextStep(BeginPosition, NextStep, GridSize),
    (
        NextStep \== EndPosition,
    ->
        nonmember(NextStep, VisitedPoints),
        add(NextStep, VisitedPoints, NewVisitedPoints),
        add(NextStep, Path, NewPath),
        createPath(GridSize, NextStep, EndPosition, NewVisitedPoints, NewPath)
    ;
        ???
    ).

A little bit of explanation of my code:

GridSize is just an integer. If it is 2, the grid is a 2x2 grid. So all the grids are square.

The BeginPosition and EndPosition are shown like this: pos(X,Y).

The function nextStep looks for a valid neigbor of a given position. The values of X and Y have to be between 1 and the grid size. I've declared 4 different predicates of nextStep: X + 1, X - 1, Y + 1 and Y - 1. This is the code:

nextStep(pos(X,Y),pos(X1,Y),GridSize):-
    X1 is X + 1,
    X1 =< GridSize.
nextStep(pos(X,Y),pos(X1,Y),_):-
    X1 is X - 1,
    X1 >= 1.
nextStep(pos(X,Y),pos(X,Y1),GridSize):-
    Y1 is Y + 1,
    Y1 =< GridSize.
nextStep(pos(X,Y),pos(X,Y1),_):-
    Y1 is Y - 1,
    Y1 >= 1.

nonmember returns true if a given element doesn't occur in a given list.

add adds an element to a given list, and returns the list with that element in it.

Another thing to know about VisitedPoints: Initially the BeginPosition and EndPosition are stored in that list. For example, if I want to find a path in a 2x2 grid, and I have to avoid point pos(2,1), then I will call the function like this:

createPath(2, pos(1,1), pos(2,2), [pos(1,1),pos(2,2),pos(2,1)], X).

The result I should get of it, should be:

X = [pos(1,2)]

Because that is the point needed to connect pos(1,1) and pos(2,2). My question is, how can I stop the code from running when NextStep == EndPosition. In other words, what do I have to type at the location of the '???' ? Or am I handling this problem the wrong way?

I'm pretty new to Prolog, and making the step from object oriented languages to this is pretty hard.

I hope somebody can answer my question.

Kind regards,

Walle

CapelliC CapelliC · Accepted Answer · 2012-11-05T13:11:35

I think you just placed the 'assignment' to path at the wrong place

createPath(GridSize, BeginPosition, EndPosition, VisitedPoints, Path):-
    nextStep(BeginPosition, NextStep, GridSize),
    (
        NextStep \== EndPosition,
    ->
        nonmember(NextStep, VisitedPoints),
        add(NextStep, VisitedPoints, NewVisitedPoints),
        % add(NextStep, Path, NewPath),
        % createPath(GridSize, NextStep, EndPosition, NewVisitedPoints, NewPath)
        createPath(GridSize, NextStep, EndPosition, NewVisitedPoints, Path)
    ;
        % ???
        % bind on success the output variable, maybe add EndPosition
        Path = VisitedPoints
    ).

Maybe this is not entirely worth an answer, but a comment would be a bit 'blurry'

Create a path in a grid in prolog

1 Answers