How to prevent stack overflow in this recursive path finding algorithm?

Issue

This Content is from Stack Overflow. Question asked by HeyHannibal

I have a function that takes two sets of numbers

([2,2],[6,6]) or ([4,6],[6,12]) etc.

Which represent indexes of elements on a 2D array.
The function takes the first set, and adds 2 randomly to either of the numbers in the array, until it both numbers are equal to the second set.
which results in a “pathAB”, we go from first set to the second and push all the elements into an array.

Then i need to take the second set, and randomly subtract or add 2 to either of the numbers, until they are equal to the first set. I need to find a way back to the starting point [2,2]. The conditions are is that i can’t use any of the numbers that are already used in the ‘PathAB’, or repeat any numbers that where already used while forming the second path. I need to avoid the first path, and “go around it”.

So for input

([2,2], [6,6])

the output would be

  /// First Output
   
  [2, 2], // Point A
  [4, 2],
  [4, 4],
  [4, 6],
  [6, 6], /// Point B
  [6, 8],
  [4, 8],
  [2, 8],
  [2, 6],
  [2, 4],
  [2, 2], /// Point A

or it could be

  /// Second Output 
 
  [2, 2], /// Point A
  [2, 4],
  [4, 4],
  [4, 6],
  [6, 6], /// Point B
  [8, 6],
  [8, 4],
  [6, 4],
  [6, 2],
  [4, 2],
  [2, 2], /// Point A

The whole point is that it should be a Random Path.

I use this function to build random shapes on a two 2D array. To better understand what i’m trying to do, please have a look at the images linked below.

First Output, Second Output

The red line is path A to B, or [2,2] to [6,6]. And the green line is path B to A, or [6,6] to [2,2].

The function i have right now, is able to build a path, 85% of the time
The other 15% of the time, it gives me a stack overflow error. And the wider the distance between points, the higher the chance of stack overflow. The current function only works well for very small distances.

Now to the function itself.

The making of path from A to B, is fairly simple.

  let pathAB = [];
  let startP;

  function makePathAB(a, b, start) {
    if (start) { /// if it's the fist iteration. add the starting point to the PathAB
      pathAB.push(a);
      startP = a;
    }
    if (a[0] === b[0] && a[1] === b[1]) return; /// A === B, path compelete
    if (a[0] > b[0] || a[1] > b[1]) {
      /// A is beyound boundaries of B, start again
      pathAB = [];
      makePathAB(startP, b, true);
    } else {
      let newA = [...a]; // Take a random index 
      let randomElem = randomInt(0, 1);
      newA[randomElem] += 2; /// go down (+2) in a random direction
      pathAB.push(newA);
      makePathAB(newA, b, false); // start next step
    }
  }

I take the starting point, add 2 to to either of the indexes, and then recuresively call the function until A is equal to B. If a0 or a1 is more than b0 b1 then i scrap the whole path and start again.

Then i make an array of strings from pathAB, to compare against the steps of the pathBA

  let compareAB = pathAB.slice(1, pathAB.length - 1).map((item) => item.toString());

Then for the B to A path i use this function

  function makePathBA(b, a, start) {
    if (start) {
      /// if starting, push first step of the path to path arr
      pathBA.push(b);
    }

    if (a[0] === b[0] && a[1] === b[1]) return; /// B === A, path, compareABelete

    if (b[0] < 0 || b[1] < 0 || b[0] > 8 || b[1] > 8) {
      /// B is out of boundaries of either A, or the array itself
      pathBA = [];
      makePathBA(startPB, a, true);
    } else {
      let newB = [...b];
      let randomElem = randomInt(0, 1);
      let plusminus = [2, -2];
      newB[randomElem] = newB[randomElem] + plusminus[randomInt(0, plusminus.length - 1)]; /// randomly go either up(-2) or down(+2)

      let crossed;

      pathBA.forEach((item) => {
        /// Check for path B crossing itself
        if (item.toString() === newB.toString()) {
          pathBA = [];
          crossed = true;
          return;
        }
      });

      /// THE CAUSE OF THE PROBLEM
      compareAB.forEach((item) => {
        /// check for path B crossing path A
        if (item === newB.toString()) {
          pathBA = [];
          crossed = true;
        }
      });

      if (crossed) {
        /// if path B crossed itself or A, start again from 0
        pathBA = [];
        makePathBA(startPB, a, true);
        return;
      } else {
        /// else take the next step
        pathBA.push(newB);
        crossed = false;

        makePathBA(newB, a, false);
        return;
      }
    }
  }

I take the starting point. Randomly either add or subtract 2 from either of the indexes, and if this step crosses either pathAB or itself. If it doesn’t the we go on to the next step. If it does, we start again from the starting point.

THE PROBLEM, lies in the compareAB part of the function. If i don’t include comparison against the AB, or “allow pathBA to cross PathAB”, i never get a stack overflow, and the function fine. But i need the paths not to cross.

How can this be done? How to prevent stack overflow, and possibly make this function work on much larger distances?

P.S The fact that the step between indexes is 2, and not 1, is irrelevant. I just need it to be 2, for building rectangular shapes on the provided array.



Solution

This question is not yet answered, be the first one who answer using the comment. Later the confirmed answer will be published as the solution.

This Question and Answer are collected from stackoverflow and tested by JTuto community, is licensed under the terms of CC BY-SA 2.5. - CC BY-SA 3.0. - CC BY-SA 4.0.

people found this article helpful. What about you?