title: How do you identify natural and forced neighbors in Jump Point Search?
body: <p>I am trying to implement Jump Point Search, an optimization on A* that reduces the number of nodes in the open list by na average of 20x,  as well as memory consumption. The algorithm was implemented according to the original research paper and some online tutorials, but the program enters an infinite recursion loop when searching for natural and forced neighbors, which causes a stack overflow. Pathfinding A* is already working and I am just adding the JPS functions to it. </p>
  
  <p>Here is the code for those functions:</p>
  
  <pre><code>void Movement::GetNaturalNeighbors(std::vector&lt;Node&gt;&amp; output, Node&amp; currentNode)
  {
      int nextX = currentNode.pos.x + currentNode.direction.x;
      int nextY = currentNode.pos.y + currentNode.direction.y;
  
      // Straight line pruning excludes all neighbors except the one directly in front of currentNode
      if(!g_terrain.IsWall(nextX, nextY))
      {       
          Map[nextX][nextY].parent = &amp;Map[currentNode.pos.x][currentNode.pos.y];
          Map[nextX][nextY].direction.x = Map[nextX][nextY].parent-&gt;direction.x;
          Map[nextX][nextY].direction.y = Map[nextX][nextY].parent-&gt;direction.y;
          Map[nextX][nextY].heurCost = GetHeuristicCost(nextX, nextY);
          // Movement cost for diagonals is square root of 2
          Map[nextX][nextY].movCost = currentNode.movCost + 1.0f;
          Map[nextX][nextY].pos.x = nextX;
          Map[nextX][nextY].pos.y = nextY;
          if ((Map[nextX][nextY].movCost + Map[nextX][nextY].heurCost) &lt; (currentNode.movCost + currentNode.heurCost))
          {
              output.push_back(Map[nextX][nextY]);
          }
      }
  
      int dirX = currentNode.direction.x;
      int dirY = currentNode.direction.y;
  
      // If we are moving diagonally, add the adjacent nodes in the same direction
      if(dirX!= 0 &amp;&amp; dirY!=0)
      {
          if((dirY == +1) &amp;&amp;(!g_terrain.IsWall(currentNode.pos.x+ neighborX[TOP], currentNode.pos.y+ neighborY[TOP])))
          {
              int naturalNeighborX = currentNode.pos.x+ neighborX[TOP];
              int naturalNeighborY = currentNode.pos.y+ neighborY[TOP];
              Map[naturalNeighborX][naturalNeighborY].direction.x = neighborX[TOP];
              Map[naturalNeighborX][naturalNeighborY].direction.y = neighborY[TOP];
              Map[naturalNeighborX][naturalNeighborY].parent = &amp;Map[currentNode.pos.x][currentNode.pos.y];
              Map[naturalNeighborX][naturalNeighborY].heurCost = GetHeuristicCost(nextX, nextY);
              // Movement cost for diagonals is square root of 2
              Map[naturalNeighborX][naturalNeighborY].movCost = currentNode.movCost + 1.41421f;
              Map[naturalNeighborX][naturalNeighborY].pos.x = naturalNeighborX;
              Map[naturalNeighborX][naturalNeighborY].pos.y = naturalNeighborY;
              if ((Map[naturalNeighborX][naturalNeighborY].movCost + Map[naturalNeighborX][naturalNeighborY].heurCost) &lt; (currentNode.movCost + currentNode.heurCost))
              {
                  output.push_back(Map[naturalNeighborX][naturalNeighborY]);
              }
          }
          else if(!g_terrain.IsWall(currentNode.pos.x+ neighborX[BOTTOM], currentNode.pos.y+ neighborY[BOTTOM]))
          {
              int naturalNeighborX = currentNode.pos.x+ neighborX[BOTTOM];
              int naturalNeighborY = currentNode.pos.y+ neighborY[BOTTOM];
              Map[naturalNeighborX][naturalNeighborY].direction.x = neighborX[BOTTOM];
              Map[naturalNeighborX][naturalNeighborY].direction.y = neighborY[BOTTOM];
              Map[naturalNeighborX][naturalNeighborY].parent = &amp;Map[currentNode.pos.x][currentNode.pos.y];
              Map[naturalNeighborX][naturalNeighborY].heurCost = GetHeuristicCost(nextX, nextY);
              // Movement cost for diagonals is square root of 2m
              Map[naturalNeighborX][naturalNeighborY].movCost = currentNode.movCost + 1.41421f;
              Map[naturalNeighborX][naturalNeighborY].pos.x = nextX;
              Map[naturalNeighborX][naturalNeighborY].pos.y = nextY;
              if ((Map[naturalNeighborX][naturalNeighborY].movCost + Map[naturalNeighborX][naturalNeighborY].heurCost) &lt; (currentNode.movCost + currentNode.heurCost))
              {
                  output.push_back(Map[naturalNeighborX][naturalNeighborY]);
              }
          }
  
          if((dirX == +1) &amp;&amp; (!g_terrain.IsWall(currentNode.pos.x+ neighborX[RIGHT], currentNode.pos.y+ neighborY[RIGHT])))
          {
              int naturalNeighborX = currentNode.pos.x+ neighborX[RIGHT];
              int naturalNeighborY = currentNode.pos.y+ neighborY[RIGHT];
              Map[naturalNeighborX][naturalNeighborY].direction.x = neighborX[RIGHT];
              Map[naturalNeighborX][naturalNeighborY].direction.y = neighborY[RIGHT];
              Map[naturalNeighborX][naturalNeighborY].parent = &amp;Map[currentNode.pos.x][currentNode.pos.y];
              Map[naturalNeighborX][naturalNeighborY].heurCost = GetHeuristicCost(nextX, nextY);
              // Movement cost for diagonals is square root of 2
              Map[naturalNeighborX][naturalNeighborY].movCost = currentNode.movCost + 1.41421f;
              Map[naturalNeighborX][naturalNeighborY].pos.x = naturalNeighborX;
              Map[naturalNeighborX][naturalNeighborY].pos.y = naturalNeighborY;
              if ((Map[naturalNeighborX][naturalNeighborY].movCost + Map[naturalNeighborX][naturalNeighborY].heurCost) &lt; (currentNode.movCost + currentNode.heurCost))
              {
                  output.push_back(Map[naturalNeighborX][naturalNeighborY]);  
              }
          }
          else if(!g_terrain.IsWall(currentNode.pos.x+ neighborX[LEFT], currentNode.pos.y+ neighborY[LEFT]))
          {
              int naturalNeighborX = currentNode.pos.x+ neighborX[LEFT];
              int naturalNeighborY = currentNode.pos.y+ neighborY[LEFT];
              Map[naturalNeighborX][naturalNeighborX].direction.x = neighborX[LEFT];
              Map[naturalNeighborX][naturalNeighborX].direction.y = neighborX[LEFT];
              Map[naturalNeighborX][naturalNeighborX].parent = &amp;Map[currentNode.pos.x][currentNode.pos.y];
              Map[naturalNeighborX][naturalNeighborX].heurCost = GetHeuristicCost(nextX, nextY);
              // Movement cost for diagonals is square root of 2
              Map[naturalNeighborX][naturalNeighborY].movCost = currentNode.movCost + 1.41421f;
              Map[naturalNeighborX][naturalNeighborY].pos.x = nextX;
              Map[naturalNeighborX][naturalNeighborY].pos.y = nextY;
              if ((Map[naturalNeighborX][naturalNeighborY].movCost + Map[naturalNeighborX][naturalNeighborY].heurCost) &lt; (currentNode.movCost + currentNode.heurCost))
              {
                  output.push_back(Map[naturalNeighborX][naturalNeighborY]);
              }
          }
      }
  
  }
  
  
  void Movement::GetForcedNeighbors(std::vector&lt;Node&gt;&amp; output, Node&amp; currentNode)
  {
      int dir_x = currentNode.direction.x;
      int dir_y = currentNode.direction.y;
  
      int nextNodeX = currentNode.pos.x + dir_x;
      int nextNodeY = currentNode.pos.y + dir_y;
  
  
      // Forced neighbors only exist for diagonal moves
      if((dir_x != 0) &amp;&amp; (dir_y != 0))
      {
          // Check for diagonal forced neighbors
  
          if(dir_x == +1)
          {
              // Does the top right diagonal have any forced neighbors ?
              if(g_terrain.IsWall(nextNodeX + neighborX[TOP_RIGHT], nextNodeY + neighborY[TOP_RIGHT]) &amp;&amp; !g_terrain.IsWall(nextNodeX + neighborX[TOP], nextNodeY + neighborY[TOP]))
              {   
                  Map[nextNodeX][nextNodeY].direction.x = neighborX[TOP];
                  Map[nextNodeX][nextNodeY].direction.y = neighborY[TOP];
                  Map[nextNodeX][nextNodeY].parent = &amp;Map[currentNode.pos.x][currentNode.pos.y];
                  Map[nextNodeX][nextNodeY].heurCost = GetHeuristicCost(nextNodeX, nextNodeY);
                  // Movement cost for diagonals is square root of 2
                  Map[nextNodeX][nextNodeY].movCost = currentNode.movCost + 1.41421f;
                  Map[nextNodeX][nextNodeY].pos.x = nextNodeX;
                  Map[nextNodeX][nextNodeY].pos.y = nextNodeY;
  
                  if ((Map[nextNodeX][nextNodeY].movCost + Map[nextNodeX][nextNodeY].heurCost) &lt; (currentNode.movCost + currentNode.heurCost))
                  {
                      output.push_back(Map[nextNodeX][nextNodeY]);
                  }
              }
  
              // Does the bottom right diagonal have any forced neighbors ?
              if(g_terrain.IsWall(nextNodeX + neighborX[BOTTOM_RIGHT], nextNodeY + neighborY[BOTTOM_RIGHT]) &amp;&amp; !g_terrain.IsWall(nextNodeX + neighborX[BOTTOM], nextNodeY + neighborY[BOTTOM]))
              {   
                  Map[nextNodeX][nextNodeY].direction.x = neighborX[BOTTOM];
                  Map[nextNodeX][nextNodeY].direction.y = neighborY[BOTTOM];
                  Map[nextNodeX][nextNodeY].parent = &amp;Map[currentNode.pos.x][currentNode.pos.y];
                  Map[nextNodeX][nextNodeY].heurCost = GetHeuristicCost(nextNodeX, nextNodeY);
                  // Movement cost for diagonals is square root of 2
                  Map[nextNodeX][nextNodeY].movCost =  currentNode.movCost + 1.41421f;
                  Map[nextNodeX][nextNodeY].pos.x = nextNodeX;
                  Map[nextNodeX][nextNodeY].pos.y = nextNodeY;
  
                  output.push_back(Map[nextNodeX][nextNodeY]);
              }
  
          }
  
          if(dir_x == -1)
          {
              // Does the top left diagonal have any forced neighbors ?
              if(g_terrain.IsWall(nextNodeX + neighborX[TOP_LEFT], nextNodeY + neighborY[TOP_LEFT]) &amp;&amp; !g_terrain.IsWall(nextNodeX + neighborX[TOP], nextNodeY + neighborY[TOP]))
              {
                  Map[nextNodeX][nextNodeY].direction.x = neighborX[TOP];
                  Map[nextNodeX][nextNodeY].direction.y = neighborY[TOP];
                  Map[nextNodeX][nextNodeY].parent = &amp;Map[currentNode.pos.x][currentNode.pos.y];
                  Map[nextNodeX][nextNodeY].heurCost = GetHeuristicCost(nextNodeX, nextNodeY);
                  // Movement cost for diagonals is square root of 2
                  Map[nextNodeX][nextNodeY].movCost = ((dir_x == 0) || (dir_y == 0))? currentNode.movCost + 1.0f: currentNode.movCost + 1.41421f;
                  Map[nextNodeX][nextNodeY].pos.x = nextNodeX;
                  Map[nextNodeX][nextNodeY].pos.y = nextNodeY;
  
                  output.push_back(Map[nextNodeX][nextNodeY]);
              }
  
              // Does the bottom left diagonal have any forced neighbors ?
              if(g_terrain.IsWall(nextNodeX + neighborX[BOTTOM_LEFT], nextNodeY + neighborY[BOTTOM_LEFT]) &amp;&amp; !g_terrain.IsWall(nextNodeX + neighborX[BOTTOM], nextNodeY + neighborY[BOTTOM]))
              {
                  Map[nextNodeX][nextNodeY].direction.x = neighborX[BOTTOM];
                  Map[nextNodeX][nextNodeY].direction.y = neighborY[BOTTOM];
                  Map[nextNodeX][nextNodeY].parent = &amp;Map[currentNode.pos.x][currentNode.pos.y];
                  Map[nextNodeX][nextNodeY].heurCost = GetHeuristicCost(nextNodeX, nextNodeY);
                  // Movement cost for diagonals is square root of 2
                  Map[nextNodeX][nextNodeY].movCost = ((dir_x == 0) || (dir_y == 0))? currentNode.movCost + 1.0f: currentNode.movCost + 1.41421f;
                  Map[nextNodeX][nextNodeY].pos.x = nextNodeX;
                  Map[nextNodeX][nextNodeY].pos.y = nextNodeY;
  
                  output.push_back(Map[nextNodeX][nextNodeY]);
              }
          }
      }
  }
  </code></pre>
  
  <p>Everything else follows the logic of the original document, but these two functions are the only two I am unsure about. Both the creators and many tutorials do not explain in depth how to identify them.</p>
  
  <p>My implementation of A* stores the world information in a 2D matrix called Map instead of employing a closed list. The open list is merely a vector of what nodes to open. Nodes contain their x and y positions, heuristic cost and movement cost (more commonly known as given cost) and the direction the player was facing in when he stepped on the tile. The player only moves in x and y.</p>
  
  <p>I apologize for the wall of text, but this is my first post and I wanted to post as much relevant information as possible. </p>