Java-Gaming.org Hi ! Featured games (91) games approved by the League of Dukes Games in Showcase (804) Games in Android Showcase (239) games submitted by our members Games in WIP (868) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials Pages: 
 ignore  |  Print A Star path finding  (Read 3153 times) 0 Members and 1 Guest are viewing this topic. daslee

Senior Newbie  Medals: 1
Exp: 4 years  « Posted 2014-07-21 21:28:28 »

Hello. I've been trying to make A Star path finding, but unfortunately, failed. I looked at the pseudo code in this site: http://wiki.gamegardens.com/Path_Finding_Tutorial and tried to make it in java. Here is what I got:

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77  78 `private void findPath(){   float startX = x, startY = y; //start position is player position   float destX = destination.getX(), destY = destination.getY();      //create the open list of nodes, initially containing only our starting node   openList.clear();   openList.add(new Tile(0, false, startX, startY));    //create the closed list of nodes, initially empty   closedList.clear();      boolean reachedGoal = false;   while(!reachedGoal){ //while we have not reached our goal      //consider the best node in the open list (the node with the lowest f value)      Tile lowest = lowestFInOpen();      if(lowest.getX() == destX && lowest.getY() == destY){ //if this node is the goal         //then we're done         reachedGoal = true;      }else{         //move the current node to the closed list and consider all of its neighbors         closedList.add(lowest);         ArrayListneighbors = getNeighbors(lowest);         for(Tile neighbor : neighbors){ //for each neighbor            if(closedList.contains(neighbor)){ //if this neighbor is in the closed list               if(lowest.G < neighbor.G){ //and our current g value is lower                  //then update the neighbor with the new, lower, g value                   //change the neighbor's parent to our current node                  double dx = lowest.getX() - neighbor.getX();                  double dy = lowest.getY() - neighbor.getY();                  double G = Math.abs(Math.sqrt((dx * dx) + (dy * dy)));                  neighbor.G = G;                  neighbor.parent = lowest;               }            }else if(openList.contains(neighbor)){ //this neighbor is in the open list               if(lowest.G < neighbor.G){ //and our current g value is lower                  //then update the neighbor with the new, lower, g value                   //change the neighbor's parent to our current node                  double dx = lowest.getX() - neighbor.getX();                  double dy = lowest.getY() - neighbor.getY();                  double G = Math.abs(Math.sqrt((dx * dx) + (dy * dy)));                  neighbor.G = G;                  neighbor.parent = lowest;               }            }else{ //this neighbor is not in either the open or closed list               //add the neighbor to the open list and set its g value               double dx = lowest.getX() - neighbor.getX();               double dy = lowest.getY() - neighbor.getY();               double distance = Math.abs(Math.sqrt((dx * dx) + (dy * dy)));               neighbor.G = distance;               openList.add(neighbor);            }         }      }   }}   private ArrayListgetNeighbors(Tile tile){   ArrayListneighbors = new ArrayList();   for(Tile temp : World.getInstance().getTiles()){      //32 cost - orthogonal, 45.25 - diagonal, so if from parent tile to other tile distance is < 50, it's neighbor      double dx = temp.getX() - tile.getX();      double dy = temp.getY() - tile.getY();      double distance = Math.abs(Math.sqrt((dx * dx) + (dy * dy)));      if(distance < 50)         neighbors.add(temp);   }   return neighbors;}   private Tile lowestFInOpen(){   Tile lowest = new Tile(0, false);   lowest.F = Double.MAX_VALUE;   for(int i=0; i

And nothing happens, this loop goes forever. I just noticed that openList size increases to 5, and closedList size increases to the infinity. Where is the problem?
And actually in that pseudo code I didn't noticed where the F value of nodes is being updated, maybe this is the problem?  Riven

« JGO Overlord »         Medals: 1371
Projects: 4
Exp: 16 years   Re: A Star path finding « Reply #1 - Posted 2014-07-21 21:35:00 »

Try to get a feel for the topic you're dealing with by implementing flood-fill, and then Dijkstra. Once you grasp that (which doesn't mean you just converted pseudo code to java code), you can easily cope with A*.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
Pages: 
 ignore  |  Print

 princec 10x Ali-RS 6x philfrei 5x VaTTeRGeR 5x KaiHH 5x mudlee 5x elect 4x Rain8 3x SteveSmith 2x hansolo_ 2x gouessej 2x ral0r2 1x saocrinn 1x Akazan 1x Apo 1x 