java - A* catch if unpossible to reach a point -

i implemented simple a* , noticed infity loop if 4 spots around character filled. current stuck how work start running nearest possible spot. guesses on it? (sorry long code)

the a*

private node astarsearch(int startx, int starty) {         openlist.clear();         closelist.clear();         successor.clear();         node startnode = new node(null, startx, starty, 0, 0);         openlist.add(startnode);         while (openlist.size() != 0) {             // sort list             collections.sort(openlist, nodecomperator);             node q = openlist.remove(0); // first object             int qx = q.x;             int qy = q.y;             // start adding successors             // left              node left = createneighbor(q, qx - 1, qy);             if (left != null && !closelist.contains(left))                 successor.add(left);              // right             node right = createneighbor(q, qx + 1, qy);             if (right != null && !closelist.contains(right))                 successor.add(right);              // // down             node down = createneighbor(q, qx, qy - 1);             if (down != null && !closelist.contains(down))                 successor.add(down);              //             node = createneighbor(q, qx, qy + 1);             if (up != null && !closelist.contains(up))                 successor.add(up);              // calc             (node suc : successor) {                 if (suc.x == (int) this.screen.character.mappos.x                         && suc.y == (int) this.screen.character.mappos.y)                     return suc;                 boolean add = true;                 if (betterin(suc, openlist)) // openlist und der                     add = false;                 if (betterin(suc, closelist)) // closedlist                     add = false;                 if (add)                     openlist.add(suc);             }             closelist.add(q);         }         return null;     }    private node createneighbor(node parrent, int x, int y) {         if (x >= 0 && y >= 0 && x < this.screen.map.width                 && y < this.screen.map.height                 && this.screen.map.maparray[x][y] != config.cantmoveonposition                 && this.screen.map.maparray[x][y] != config.monsterstate) {             node n = new node(parrent, x, y);             n.g = calcg(n);             n.h = calch(n, (int) this.screen.character.mappos.x,                     (int) this.screen.character.mappos.y);             return n;         }         return null;     }      private float calcg(node n) {             node p = n.getparrent();             return p.g + 1;         }          private float calch(node n, int targetx, int targety) {             float dx = math.abs(n.x - targetx);             float dy = math.abs(n.y - targety);             return (float) math.sqrt((float) (dx * dx) + (dy * dy));         }          private boolean betterin(node n, list<node> l) {             (node no : l) {                 if (no.x == n.x && no.y == n.y && (no.g + no.h) <= (n.g + n.h))                     return true;             }             return false;         } 

my node:

public class node {     public int x, y;     public float g, h;     private node parrent;      public node(node parrent, int x, int y, float g, float h) {         this.parrent = parrent;         this.x = x;         this.y = y;         this.g = g;         this.h = h;     }      public node(node parrent, int x, int y) {         this.parrent = parrent;         this.x = x;         this.y = y;     }      public node getparrent() {         return parrent;     }      public void setparrent(node parrent) {         this.parrent = parrent;     }     @override     public boolean equals(object o) {         // override different compare         return ((node) o).x == this.x && ((node) o).y == this.y;     }      @override     public int hashcode() {         // if x , y same same         return x + y;     } } 

if use nodes blocked give them high h not walk correct anymore dont know whats going wrong here.

your a* algorithm seems little bit screwy. code's not clear -- up, down, left, right repeat same section (which should broken out method).

it's not clear whether "discovered" nodes represented -- should set -- whereas have "open", "closed" , "successor".

checking each of up,down,left,right neighbors should factored out method, call 4 times neighborx , neighbory positions.

there isn't single clear line correctly tests whether given neighbor (it's neighbor, not successor) has been "discovered".

neither sure post-processing of successors. viz:

        // calc         (node suc : successor) {             if (suc.x == (int) this.screen.character.mappos.x                     && suc.y == (int) this.screen.character.mappos.y)                 return suc;             boolean add = true;             if (betterin(suc, openlist)) // openlist und der                 add = false;             if (betterin(suc, closelist)) // closedlist                 add = false;             if (add)                 openlist.add(suc);         } 

since sort "open nodes" on every iteration & pick probable best, doesn't make sense me & may erroneous.

presumably algorithm should terminate promptly, when 4 directions around character blocked. failure terminate implies openlist not processed correctly/ or incorrect nodes being added.

put log4j logging in & write simple unit-test verify it's correct behaviour in these conditions.

---

i recommend rolling 'createneighbor', 'discovered check' , 'add successor list' code 1 method exploreneighbor( node q, int offsetx, int offsety).

i've improved style & variable naming somewhat. should move towards using getters -- getx(), gety() example.

exploreneighbor( q, -1, 0);  // left exploreneighbor( q, +1, 0);  // right exploreneighbor( q, 0, -1);  // exploreneighbor( q, 0, +1);  // down  protected boolean exploreneighbor (node parent, int offsetx, int offsety) {     int x = q.getx() + offsetx;     int y = q.gety() + offsety;     if (x < 0 || x >= screen.map.width)         return null;     if (y < 0 || y >= screen.map.height)         return false;     int content = screen.map.maparray[x][y];     if (content == contents.cantmoveonposition ||             content == contents.monsterstate) {         return false;     }      // represent neighbor position;     //       node n = new node(parent, x, y);     n.g = calcg(n);     n.h = calch(n, (int) this.screen.character.mappos.x,             (int) this.screen.character.mappos.y);      // check if discovered yet;     //     if (discoveredset.contains( n)) {         // queued or visited.         return false;     }      // queue exploration.     openqueue.add( n);     return true; } 

good luck..