title: A* bug (A star search algorithm)
body: <p>I have started to study algorithms and software development and, as a small self evaluation project I have decided to write the A* search algorithm in C++. It uses Qt and OpenGL for the visual part (but that is not important).</p>
  <p>Using mostly this source:
  <a href="https://web.archive.org/web/20171022224528/http://www.policyalmanac.org:80/games/aStarTutorial.htm" rel="nofollow noreferrer">A* Pathfinding for Beginners</a></p>
  <p>I have write a small app, however I am have found a bug that I cant fix. It appears that for some reason the parent of a node close to the wall is set to the wall.(?) And the parent of the wall is set to the the start point(?) because of the way I am storing the info.</p>
  <p>I have used a stateMatrix[][] where</p>
  <pre><code>1 = entrance green;
  2 = exit;
  3 = wall and;
  4 = path;
  </code></pre>
  <p>I have also used matrix to represent openNodes and closedNode. The closedNodes matrix is bool matrix the openNode matrix also stores some info:</p>
  <p>The openNodes instructions are:</p>
  <pre><code>openNodes[100][100][6];
  0 - bool open or closed
  1 - F
  2 - G
  3 - H
  4 - parentX
  5 - parentY
  </code></pre>
  <p>I know that there are better ways to code this but I have not yet got to this lesson ;)</p>
  <p>Here is the code of the astar file:</p>
  <pre><code>#include &lt;math.h&gt;
  #include &quot;apath.h&quot;
  
  aPath::aPath()
  {
      gridSize = 100;
  
      int i, j, k;
  
      for(i = 0; i &lt; gridSize; i++)
          for(j = 0; j &lt; gridSize; j++)
          {
              stateMatrix[i][j] = 0;
              for(int k = 0; k &lt; 6; k++) openNodes[i][j][k] = 0;
              closedNodes[i][j] = 0;
          }
  
      targetX = targetY =
              openX = openY = entranceX = entranceY = 0;
  }
  
  void aPath::start()
  {
      bool testOK = false;
      int G = 0;
  
      openNodes[entranceX][entranceY][0] = 1;
      openNodes[entranceX][entranceY][2] = 14;
      openNodes[entranceX][entranceY][3] = euclidean(entranceX,
                                                     entranceY);
      openNodes[entranceX][entranceY][1] =
              openNodes[entranceX][entranceY][2] +
              openNodes[entranceX][entranceY][3];
      openNodes[entranceX][entranceY][4] = entranceX;
      openNodes[entranceX][entranceY][5] = entranceY;
  
      int i, j, x, y;
  
      while(closedNodes[targetX][targetY] == 0)
      {
          searchLessOpen();
          closedNodes[openX][openY] = 1;
          openNodes[openX][openY][0] = 0;
          //Check the 8 squares around
          for(i = openX - 1; i &lt;= openX + 1; i++)
              for(j = openY - 1; j &lt;= openY + 1; j++)
              {
                  //check if the square is in the limits,
                  //is not a wall and is not in the closed list
                  if((i  &gt;= 0) &amp;&amp; (j &gt;= 0)  &amp;&amp;
                          (i &lt; gridSize) &amp;&amp; (j &lt; gridSize) &amp;&amp;
                          (stateMatrix[i][j] != 3) &amp;&amp;
                          (closedNodes[i][j] == 0))
                  {
                      //G calculus. If it is in the edge it costs more
                      x = i - openX + 1;
                      y = j - openY + 1;
                      if((x == 0 &amp;&amp; y == 0) ||
                              (x == 0 &amp;&amp; y == 2) ||
                              (x == 2 &amp;&amp; y == 0) ||
                              (x == 2 &amp;&amp; y == 2))
                      {
                          G = 14;
                      }
                      else G = 10;
  
                      //check if node is already open
                      if(openNodes[i][j][0] == 0)
                      {
                          openNodes[i][j][0] = 1;
                          openNodes[i][j][2] = G;
                          openNodes[i][j][3] = euclidean(i,j);
                          openNodes[i][j][1] = openNodes[i][j][2] + openNodes[i][j][3];
                          openNodes[i][j][4] = openX;
                          openNodes[i][j][5] = openY;
                      }
                      else //if node is open, check if this path is better
                      {
                          if(G &lt; openNodes[i][j][2])
                          {
                              openNodes[i][j][2] = G;
                              openNodes[i][j][1] = openNodes[i][j][2] + openNodes[i][j][3];
                              openNodes[i][j][4] = openX;
                              openNodes[i][j][5] = openY;
                          }
                      }
                  }
              }
      }
  
      reconstruct();
  }
  
  void aPath::reconstruct()
  {
      bool test = false;
  
      int x = openNodes[targetX][targetY][4];
      int y = openNodes[targetX][targetY][5];
  
      do
      {
          stateMatrix[x][y] = 4;
          x = openNodes[x][y][4];
          y = openNodes[x][y][5];
  
          if(x == entranceX &amp;&amp; y == entranceY) test = true;
  
      } while(test == false);
  }
  
  int aPath::euclidean(int currentX, int currentY)
  {
      int dx = targetX - currentX;
      int dy = targetY - currentY;
  
      return 10*sqrt((dx*dx)+(dy*dy));
  }
  
  void aPath::searchLessOpen()
  {
      int F = 1000000;
      int i, j;
  
      for(i = 0; i &lt; gridSize; i++)
          for(j = 0; j &lt; gridSize; j++)
          {
              if(openNodes[i][j][0] == 1)
              {
                  if(openNodes[i][j][1] &lt;= F)
                  {
                      F = openNodes[i][j][1];
                      openX = i;
                      openY = j;
                  }
              }
          }
  }
  </code></pre>
  <p>Does anyone know what I am doing wrong?</p>
  <p>Thanks.
  Edit: Here are some pictures:</p>
  <p><img src="https://i.stack.imgur.com/dLuIA.png" alt="" />
  <img src="https://i.stack.imgur.com/KCr3L.png" alt="" /></p>