title: A Star Search Algorithm Almost Working
body: <p>I'm working on an implementation of the A* Search Algorithm in Java, and it's not quite working correctly. Here is my algorithm code:</p>
  
  <pre><code>    public List&lt;Tile&gt; calculatePath(Tile start, Tile goal) {
      Node current = new Node(start, null, 0, getDistance(start, finish));
      openList.add(current);
      while (openList.size() &gt; 0) {
          Collections.sort(openList, nodeSorter);
          current = openList.get(0);
          if (current.tile instanceof FinishTile) {
              List&lt;Tile&gt; path = new ArrayList&lt;Tile&gt;();
              while (current.parent != null) {
                  path.add(current.tile);
                  current = current.parent;
              }
              openList.clear();
              closedList.clear();
              return path;
          }
          openList.remove(current);
          closedList.add(current);
          for (int i = 0; i &lt; 9; i++) {
              if (i == 4) continue;
              int x = current.tile.getX(Tile.TILE_PRECISION);
              int y = current.tile.getY(Tile.TILE_PRECISION);
              int xi = (i % 3) - 1;
              int yi = (i / 3) - 1;
              Tile at = getTile(x + xi, y + yi);
              if (at == null) continue;
              if (at instanceof WallTile || tileInList(closedList, at)) continue;
              if (!tileInList(openList, at)) openList.add(new Node(at, current, getDistance(start, at), getDistance(at, finish)));
          }
      }
      return null;
  }
  </code></pre>
  
  <p>The Node class is as follows:</p>
  
  <pre><code>public class Node {
  
  public Tile tile;
  public Node parent;
  public final int fCost, gCost, hCost;
  
  public Node(Tile tile, Node parent, int gCost, int hCost) {
      this.tile = tile;
      this.parent = parent;
      this.fCost = gCost + hCost;
      this.gCost = gCost;
      this.hCost = hCost;
  }
  </code></pre>
  
  <p>}</p>
  
  <p>And here is the path that it produces:</p>
  
  <p><img src="https://i.imgur.com/wIAYpy2.png" alt="AStar"></p>
  
  <p>As you can see, it doesn't choose the optimal path (almost does). Can anyone see any obvious errors in my code, or do you think the error lies somewhere else? Thanks for any help. :)</p>