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.

false · Accepted Answer · 2022-08-19T10:45:40.053

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.

Tasos Papastylianou · Answer 2 · 2016-10-27T00:21:43.233

"Now I don't have any of the logic in here to save the path yet, but that isn't the issue"

No, that is the issue. Specifically, the reason you're getting into an out of stack error is because the logic of the code forces you to keep going back and forth between positions (3,5) and (4,5) indefinitely.

When you're at (3,5) the first nextmove predicate fails, and the second one succeeds, so you set x=4. The move succeeds and you proceed to calculate the next move starting from (4,5).
When you're at (4,5), the first three nextmove predicates fail, and the fourth one succeeds, so you set x=3. The move succeeds and you proceed to calculate the next move starting from (3,5)
And so on forever.

The way to avoid this is to also check your path so far, in your checkfor predicate, and make your current move fail if this path has been encountered before. (assuming that the rules of the game forbid you from visiting the same position twice and you're trying to find an acyclic route instead -- note that this is simply acyclic, and not necessarily the shortest one).

In other words:

First time you're at (3,5) position, the first nextmove predicate fails, but the second provisionally "succeeds", so you move to (4,5).
From (4,5) the first three nextmove predicates fail, but the fourth succeeds, attempting to push you back to (3,5). However, checkfor detects this is in the path already, and fails. Because there are no more nextmove predicates to try, the whole findadjacentsquare predicate fails.
This causes you to backtrack all the way to where it all went wrong, i.e. the second nextmove predicate of move (3,5), which as it turns out didn't succeed down the line after all. So prolog will now proceed to try the third nextmove predicate. Your pawn will now move up into (3,4) instead, the move succeeds, and you continue from there.

etc.

Other miscellaneous advice:

Try xpce with the guitracer; makes the whole debugging process very easy to visualise!
Your assert statement is useless here and does nothing: there's no reason to modify your database by asserting new facts, since you're not independently checking against those facts anywhere later on in your code. Instead you're appending the unified waypoints to a list in an accumulator pattern (which is exactly what you should be doing, but has nothing to do with checking against existing / asserted facts in your database).
At the point of your query, it doesn't make sense to pass an uninitialised Path argument, since your 'base case' predicate prints the accumulated list which is a bunch of waypoints appended to your initial input, therefore your initial input needs to be something specific. You should pass an empty list, or at least the first point, i.e. w(1,1).

Out of local stack error being thrown in list of lists

2 Answers2