Out of local stack error being thrown in list of lists

Question

My input: A list of lists with 0s and 1s. 0s being walkable blocks and 1s being walls. My starting point (1,1) and my ending point (for now we will use (2,2)).

My output: The pathway taken to get from 1,1 to 2,2.

My issue: I am accessing something out of index and I do not understand why.

Here is my code:

maze([[0, 1, 0, 0],
  [0, 0, 0, 0],
  [0, 1, 0, 0],
  [0, 1, 0, 1],
  [0, 0, 0, 0]]).

checkfor(X,Y,Maze) :-
    nth1(Y, Maze, R),
    nth1(X, R, 0),
    assertz(w(X,Y)).

findadjacentsquare(OldX,OldY,X,Y,Maze) :-
    nextmove(OldX,OldY,X,Y),
    checkfor(X,Y,Maze).

nextmove(OldX,OldY,OldX,Y) :-
    Y is OldY+1.
    %Y >= 0,
    %Y < 5.
nextmove(OldX,OldY,X,OldY) :-
    X is OldX+1.
    %X >= 0,
    %X < 5.
nextmove(OldX,OldY,OldX,Y) :-
    Y is OldY-1.
    %Y >= 0,
    %Y < 5.
nextmove(OldX,OldY,X,OldY) :-
    X is OldX-1.
    %X >= 0,
    %X < 5.

citypath(X,Y,X,Y,Maze,Path) :-
  write(Path).
citypath(OldX,OldY,X,Y,Maze,Path) :-
  findadjacentsquare(OldX,OldY,X1,Y1,Maze),
  citypath(X1,Y1,X,Y,Maze,[w(X1,Y1)|Path]).

So when calling it here is what I'm doing:

maze(M1), citypath(1,1,2,2,M1,Path)

Now I don't have any of the logic in here to save the path yet, but that isn't the issue. My issue is when I run this it is getting the out of local stack error and I can't seem to figure out why. I tried to hard-code constraints in the nextmove statements but that doesn't seem to be working either.

Answer 1

In your definition, better remove the assertz/1. And add using path/4.

nextstep(Maze,S0,S1) :-
   S0 = X0-Y0,
   S1 = X1-Y1,
   findadjacentsquare(X0,Y0,X1,Y1,Maze).

mazepath(Path) :-
   maze(Maze),
   path(nextstep(Maze), Path, 1-1,2-2).

?- mazepath(Path).
   Path = [1-1,1-2,1-3,1-4,1-5,2-5,3-5,3-4,3-3,4-3,4-2,4-1,3-1,3-2,2-2]
;  Path = [1-1,1-2,1-3,1-4,1-5,2-5,3-5,3-4,3-3,4-3,4-2,3-2,2-2]
;  Path = [1-1,1-2,1-3,1-4,1-5,2-5,3-5,3-4,3-3,3-2,2-2]
;  Path = [1-1,1-2,2-2]
;  false.

So the idea here is to reuse a generic predicate for path finding. That handles all the details of loop-checking.

Since you tried to use assert: This is quite possible too, but it requires a lot of additional overhead. For example, you need to initialize the state. You need to make sure that the code remains re-entrant such that multiple searches are possible simultaneously. And so on ... Brief, keeping your code clean is often a preferable approach.