Databases
StackOverflow2013
Postsdbo
POHow do you identify natural and forced neighbors in Jump Point Search?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POHow do you identify natural and forced neighbors in Jump Point Search?
    primarykey
    data
    text
    <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>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. This table or related slice is empty.
    1. USBruno Ayllon
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. POHow do you identify natural and forced neighbors in Jump Point Search?
      1. This table or related slice is empty.
      1. VTUpMod
    1. COAnyone ? I knew this algorithm was fairly recent and , because of that, not so well known, but isn't there anyone who already implemented it ?
      singulars
      1. POHow do you identify natural and forced neighbors in Jump Point Search?
      1. USBruno Ayllon
    2. COI have looked at Jump Point Search, but decided it was inappropriate for the type of path finding I need for my game. I implemented Bidirectional A* instead. Then I took one look at your (**Copy-Paste** code, and decided that I didn't need that aggravation either. Haven't you heard of DNY: Don't Repeat Yourself? If you improve your code you will win (at least) two ways - more people will be interested in looking at it, and you probably have a 50% chance of finding your bug.
      singulars
      1. POHow do you identify natural and forced neighbors in Jump Point Search?
      1. USPieter Geerkens
    3. COAlready solved the bug. Basically, I could simplify this to a few lines of code by using enums and some operations with modulo. One thing I didn't understand though, Peter, Bidirectional Pathfinding starts one search at the beginning and one at the end and alternates between them. When they coincide, the final path is built. But it might take longer for the paths to overlap, normally longer than normal pathfinding and consuming more resources. Maybe your map representation is most suited for this approach. In that case, could you go into details ? (Not trying to be sarcastic, just curious).
      singulars
      1. POHow do you identify natural and forced neighbors in Jump Point Search?
      1. USBruno Ayllon
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload