Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (539)
Games in Android Showcase (133)
games submitted by our members
Games in WIP (603)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  A Star path finding  (Read 891 times)
0 Members and 1 Guest are viewing this topic.
Offline 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);
         ArrayList<Tile>neighbors = 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 ArrayList<Tile>getNeighbors(Tile tile){
   ArrayList<Tile>neighbors = new ArrayList<Tile>();
   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<openList.size(); i++){
      if(openList.get(i).F < lowest.F){
         lowest = openList.get(i);
      }
   }
   return lowest;
}


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?  Roll Eyes
Online Riven
« League of Dukes »

« JGO Overlord »


Medals: 842
Projects: 4
Exp: 16 years


Hand over your head.


« 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
Pages: [1]
  ignore  |  Print  
 
 

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

rwatson462 (37 views)
2014-12-15 09:26:44

Mr.CodeIt (31 views)
2014-12-14 19:50:38

BurntPizza (62 views)
2014-12-09 22:41:13

BurntPizza (99 views)
2014-12-08 04:46:31

JscottyBieshaar (60 views)
2014-12-05 12:39:02

SHC (74 views)
2014-12-03 16:27:13

CopyableCougar4 (77 views)
2014-11-29 21:32:03

toopeicgaming1999 (138 views)
2014-11-26 15:22:04

toopeicgaming1999 (127 views)
2014-11-26 15:20:36

toopeicgaming1999 (38 views)
2014-11-26 15:20:08
Resources for WIP games
by kpars
2014-12-18 10:26:14

Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!