java - A* Pathfinding issue -

i looked on numerous articles on a* pathfinding , after looking @ pseudo-code, have tried make own.

i have node class:

private int x, y;  //the cost of movement (g) , heuristic (h) private int g;  private node parent;  public node(int x, int y) {     this.x = x;     this.y = y; }  public node(int x, int y, node parent) {     this.x = x;     this.y = y;     this.parent = parent;     this.g = parent.getg() + 1; }  public boolean equals(node node) {     return (this.x == node.getx() && this.y == node.gety() && this.parent.equals(node.getparent())); }  public int getx() {     return x; }  public void setx(int x) {     this.x = x; }  public int gety() {     return y; }  public void sety(int y) {     this.y = y; }  public node getparent() {     return parent; }  public void setparent(node parent) {     this.parent = parent; }  public int getf(node goal) {     return g + geth(goal); }  public int getg() {     return g; }  public void setg(int g) {     this.g = g; }  public int geth(node goal) {     int dx = math.abs(this.x - goal.getx());     int dy = math.abs(this.y - goal.gety());     return (dx + dy); } 

}

pathfinding:

public path getpath(node start, node goal) {     arraylist<node> openset = new arraylist<node>();     arraylist<node> closedset = new arraylist<node>();      //add current position open set     openset.add(start);      while(!openset.isempty()) {         //current node = node lowest f score         node current = getnodewithlowestscore(openset, goal);         closedset.add(current);         openset.remove(current);          if(closedset.contains(goal)) {             system.out.println("path found.");             break;         }          arraylist<node> adjacentnodes = getadjacentnodes(current, closedset);          for(node n : adjacentnodes) {             if(closedset.contains(n)) {                 continue;             }              if(!openset.contains(n)) {                 n.setparent(current);                 openset.add(n);             }else{                 if(n.getf(goal) > (current.getg() + n.geth(goal))) {                     n.setparent(current);                 }             }         }     }     return null; }  public node getnodewithlowestscore(arraylist<node> openset, node goal) {     node lowest = openset.get(0);      for(int = 0; < openset.size(); i++) {          node n = openset.get(i);         int nscore = n.getf(goal);          if(nscore < lowest.getf(goal)) {             lowest = n;         }     }     return lowest; }  public arraylist<node> getadjacentnodes(node node, arraylist<node> closedset) {     arraylist<node> nodes = new arraylist<node>();      nodes.add(new node(node.getx() + 1, node.gety(), node));     nodes.add(new node(node.getx() - 1, node.gety(), node));     nodes.add(new node(node.getx(), node.gety() + 1, node));     nodes.add(new node(node.getx(), node.gety() - 1, node));      for(int = 0; < nodes.size(); i++) {         if(nodes.get(i) == null || closedset.contains(nodes.get(i))) {             nodes.remove(i);         }     }     return nodes; } 

}

it's not working, , if print out size of open or closed set, numbers soar high. tested 30x30 2d grid, starting 10, 10 (start) 30, 30 (goal).

the changes made far:

getadjacentnodes method ->

    arraylist<node> nodes = new arraylist<node>();      nodes.add(new node(node.getx() + 1, node.gety(), node));     nodes.add(new node(node.getx() - 1, node.gety(), node));     nodes.add(new node(node.getx(), node.gety() + 1, node));     nodes.add(new node(node.getx(), node.gety() - 1, node));      for(int = 0; < nodes.size(); i++) {         int x = nodes.get(i).getx();         int y = nodes.get(i).gety();         if(!((x > 0 && x < 30) && (y > 0 && y < 30))) {             nodes.remove(i);         }     }     return nodes; } 

the getpath method -> (inside while(openset not empty) method)

        node current = getnodewithlowestscore(openset, goal);         openset.remove(current);          if(current.equals(goal)) {             system.out.println("path found.");             break;         }else{             closedset.add(current);             arraylist<node> adjacentnodes = getadjacentnodes(current, closedset);              for(node n : adjacentnodes) {                 if(closedset.contains(n) && (n.getg() > current.getg())) {                     n.setg(current.getg());                     n.setparent(current);                 }else if(openset.contains(n) && (n.getg() > current.getg())) {                     n.setg(current.getg());                     n.setparent(current);                 }else{                     openset.add(n);                 }             }         }     } 

your major problem small detail in

public boolean equals(node node) {     return (this.x == node.getx() && this.y == node.gety()           && this.parent.equals(node.getparent())); } 

in conjunction with

if(!openset.contains(n)) {     n.setparent(current);     openset.add(n); } 

it's hard spot , took me while figure out.

arraylist<>().contains(object o) internally uses (with of indexof) method object().equals(object o), takes object parameter.

your node().equals(node n) method uses node parameter, not overwriting object().equals(object o) method want overwrite.

to solve should change method to:

public boolean equals(object o) {     if(!(o instanceof node)) return false;     return (this.x == node.getx() && this.y == node.gety()           && this.parent.equals(node.getparent())); } 

i don't know if there more problems code since have not real clue how call , how path class looks , on. tried (0, 0) (3, 2) , @ least terminated , sizes seemed smaller after fix.

some nullpointerexceptions occured when calling node().getparent() though, maybe should have @ that. example in equals(object o) this.parent might null, should check beforehand.

good luck!