title: A* path finding runs forever in certain cases
body: <p>I've written up an A* pathfinding algorithm in java using this pseudo-code. For some cases it works fine, but for some it hangs forever and adds an infinite number of nodes to the open list. Is this a problem with my execution of the pseudo-code, or with the pseudo-code itself? I've tried a bunch of print statements for debugging, but I'm having trouble even pinning down the problem. Here is my A* code:</p>
  
  <pre><code>import java.awt.Point;
  import java.util.ArrayList;
  import java.util.Collections;
  
  public class AStar {
  
      Point[] adjacents = {new Point(0,1),new Point(1,1), new Point(1,0), new Point(1,-1), new Point(0,-1), new Point(-1,-1), new Point(-1,0), new Point(-1,1)};
  
      public Node[] calculatePH(Node startNode, Node endNode, int[][] map) {
          // Initialize both open and closed list
          ArrayList&lt;Node&gt; open = new ArrayList&lt;Node&gt;();
          ArrayList&lt;Node&gt; closed = new ArrayList&lt;Node&gt;();
          // Add the start node
          open.add(startNode);
          // Loop until you find the end
          while(!open.isEmpty()) {
              // Get the current node
              Node currentNode = open.get(0);
              for(Node n : open) {
                  if(n.f&lt;currentNode.f) {
                      currentNode = n;
                  }
              }
  
              open.remove(currentNode);
              closed.add(currentNode);
  
              // Found the goal
              if(currentNode.equals(endNode)) {
                  ArrayList&lt;Node&gt; path = new ArrayList&lt;Node&gt;();
                  Node current = currentNode;
                  while(current!=null) {
                      path.add(current);
                      current = current.parent;
                  }
                  Collections.reverse(path);
                  return path.toArray(new Node[path.size()]);
              }
  
              // Generate children
  
              ArrayList&lt;Node&gt; children = new ArrayList&lt;Node&gt;();
              for(Point p : adjacents) {
                  Point childpos = currentNode.getLocation();
                  childpos.translate(p.x, p.y);
  
                  //Checks to ensure that the node is on the actual field, so we don't ram into a field tech lol
                  if((childpos.y&gt;(map.length-1)) || (childpos.y&lt;0) || (childpos.x&gt;(map[0].length-1)) || (childpos.x&lt;0)) {
                      continue;
                  }
  
                  //Checks to ensure that the node is "walkable", or basically just not inside a wall or object.
                  if(map[childpos.y][childpos.x] != 0) {
                      continue;
                  }
  
                  Node child = new Node(currentNode,childpos);
                  children.add(child);
              }
  
              for(Node n : children) {
                  // Child is on the closedList
                  if(closed.indexOf(n)&gt;-1) {
                      continue;
                  }
  
                  n.g = currentNode.g + currentNode.distance(n);
                  n.h = n.distance(endNode);
                  n.f = n.g+n.h;
                  boolean inFlag = false;
                  for(Node m : open) {
                      if((n==m) &amp;&amp; (n.g&gt;m.g)) {
                          inFlag = true;
                      }
                  }
  
                  if(!inFlag) {
                      open.add(n);
                  }
              }
          }
  
          return new Node[0];
      }
  }
  </code></pre>
  
  <p>And the Node class, which is a subclass of java.awt.Point with some extra stuff.</p>
  
  <pre><code>import java.awt.Point;
  import java.util.ArrayList;
  
  public class Node extends Point { //Extends Point for conveinince and 
      //neatness. Maybe just use a has-a relationship if this breaks.
  
      public Node(Node Parent, Point loc) {
          super(loc);
          this.parent = Parent;
      }
  
      public Node(Point loc) {
          super(loc);
  
      }
  
      void translate(Point p){
          translate(p.x,p.y);
      }
  
      public Node parent;
  
      public double f;
      public double g;
      public double h;
  
      public String toString() {
  
          return "("+x+","+y+")";
      }
  }
  </code></pre>
  
  <p>I'm using a maze which is 27 tall and 54 wide, a start point at (0,0) and a goal at (24,24), and It currently has two obstacles. In this case it works fine:</p>
  
  <p><a href="https://i.stack.imgur.com/BtPvI.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/BtPvI.png" alt="enter image description here"></a></p>
  
  <p>But in this case it hangs forever. The only difference is that the second obstacle extends down 1 row further.</p>
  
  <p><a href="https://i.stack.imgur.com/gTX8W.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/gTX8W.png" alt="enter image description here"></a></p>
  
  <p>Any help at all would be seriously appreciated, and please let me know if I should change the question or add more info.</p>
  
  <p>EDIT: It's not pretty, but here is the int[][] containing the map data for the <em>non-functioning</em> version.</p>
  
  <pre><code>int[][] map ={
          {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, 
          {0,1,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, 
          {0,1,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
          {0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, 
          {0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, 
          {0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, 
          {0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, 
          {0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
          {0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, 
          {0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, 
          {0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
          {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
          {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
          {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
          {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
          {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
          {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
          {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
          {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
          {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
          {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
          {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
          {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
          {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
          {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
          {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
          {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}
         };
  </code></pre>