Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (491)
Games in Android Showcase (112)
games submitted by our members
Games in WIP (556)
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* Pathfinding  (Read 720 times)
0 Members and 1 Guest are viewing this topic.
Offline roseslayer

Junior Member


Medals: 1



« Posted 2013-07-18 16:59:13 »

Hello evryone,

I was couple of days ago working on the Villagers-system. For example: I made a villager that is going to chop a tree and then going back to his home. But for this I needed first some sort of pathfinding. I tried to do something with this tutorial:
A* pathfinding tutorial.
So I coded in what he said (atleast how I think it must be):
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  
79  
80  
81  
public class FindPath {
   private boolean isFindingPath = false;
   private List<Point> openList = new ArrayList<Point>();
   private List<Point> closedList = new ArrayList<Point>();
   private List<Point> path = new ArrayList<Point>();
   
   public List<Point> findPath(Point start, Point end) {
      isFindingPath = true;

      openList.clear();
      closedList.clear();
      path.clear();
       
      checkNodesAroundPoint(start);
       closedList.add(start);
       closedList.add(searchLowestF(start, end));
       
       while(isFindingPath){
         checkNodesAroundPoint(searchLowestF(start, end));
          closedList.add(searchLowestF(start, end));
       }
       for (Point p : closedList) {
          Game.level.alterTile((int)p.getX(), (int)p.getY(), Tile.POSIONGRASS);
       }
       
       return path;
   }
   
   public void checkNodesAroundPoint(Point search){
       for(int x = (int)search.getX() - 1; x <= (int)search.getX() + 1; x++){
           for(int y = (int)search.getY() - 1; y <= (int)search.getY() + 1; y++){
              if(!openList.contains(new Point(x,y))){
                 if(Game.level.isTileWalkable(x, y)){
                    openList.add(new Point(x,y));
                    Game.level.alterTile(x, y, Tile.ROCK);
                 }
              }
           }
       }
   }
   
   public Point searchLowestF(Point start, Point end){
      Point lowestF = new Point(10, 10);
      int lowestFInList = -1;
      int g = 0;
      int h = 0;
      int f = 0;
     
      for (Point p : openList) {
         if(p.getX() == start.getX() || p.getY() == start.getY()){
            g = 10;
         } else {
            g = 14;
         }
         if(p.getX() <= end.getX() && p.getY() <= end.getY()){
            h = (((int)end.getX() - (int)p.getX()) + ((int)end.getY() - (int)p.getY()))* 10;
         } else if(p.getX() > end.getX() && p.getY() <= end.getY()){
            h = (((int)p.getX() - (int)end.getX()) + ((int)end.getY() - (int)p.getY()))* 10;
         } else if(p.getX() <= end.getX() && p.getY() > end.getY()){
            h = (((int)end.getX() - (int)p.getX()) + ((int)p.getY() - (int)end.getY()))* 10;
         } else if(p.getX() > end.getX() && p.getY() > end.getY()){
            h = (((int)p.getX() - (int)end.getX()) + ((int)p.getY() - (int)end.getY()))* 10;
         }
         
         if(h == 0){
            isFindingPath = false;
         }
         
         f = g + h;
         
         if(lowestFInList == -1){
            lowestFInList = f;
            lowestF = p;
         } else if(f < lowestFInList){
            lowestFInList = f;
            lowestF = p;
         }        
      }
      return lowestF;
   }
}

I wrote the code myself, only I think I've done many things wrong but atleast I tried it.

The things I had no idea to do was how you can see wich "g" it is (for diagonal 14 and for horizontal, vertical 10.)
and how you can return the good path. (I am now altering the tiles to see what the code is actually doing.)

If someone can explain it to me, how I can reach my 2 goals, then tell it! Don't send the code if you can explain it. I am still learning java, by writing and thinking myself I learn more then copying other peoples work.

Already thanks!
-RoseSlayer

Fundamentum W.I.P.
Offline pjt33
« Reply #1 - Posted 2013-07-18 21:48:36 »

ArrayList is the wrong data structure to use: people may talk about "open list" and "closed list", but you should be using a priority queue to represent the open list, and probably HashSet for the closed list.

But more importantly, you don't use closedList for anything, so I expect that your main loop never terminates. No point should ever be in both the open and the closed list.
Offline roseslayer

Junior Member


Medals: 1



« Reply #2 - Posted 2013-07-19 14:25:45 »

ArrayList is the wrong data structure to use: people may talk about "open list" and "closed list", but you should be using a priority queue to represent the open list, and probably HashSet for the closed list.

But more importantly, you don't use closedList for anything, so I expect that your main loop never terminates. No point should ever be in both the open and the closed list.

The second part I was already thinking of, the game was just stuck because he is repeating the same Point, the whole time. so I made an extra void:

1  
2  
3  
4  
   private void changeToClosedList(Point change){
      closedList.add(change);
       openList.remove(change);
   }


But the code sometimes crashes. It is then making so much Points in closedList (and it isn't making anymore points in openList). after a couple of seconds it is at 1.400.000 Points in the closedList. But still exactly the same amount in openList. I made a small screenshot so you can see what's wrong:



The code.
(I now got somesort of the g-part, and that the code isn't shortcutting around corners.)

in the right upper corner there is a minimap on what's happening. the gray colour is openList, the purple colour is closedList and the white colour is an unwalkableTile.

If anyone of you can see what I did wrong in my code, just tell me!

@pjt33, I will research a little bit about HashSset and Priority queue when I am done with like this (slower, not the best) script. If it is working, I can always make it perform better etc.

Thanks for your help
-RoseSlayer.

Fundamentum W.I.P.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline pjt33
« Reply #3 - Posted 2013-07-19 21:26:44 »

The second part I was already thinking of, the game was just stuck because he is repeating the same Point, the whole time. so I made an extra void:

1  
2  
3  
4  
   private void changeToClosedList(Point change){
      closedList.add(change);
       openList.remove(change);
   }


But the code sometimes crashes. It is then making so much Points in closedList (and it isn't making anymore points in openList). after a couple of seconds it is at 1.400.000 Points in the closedList. But still exactly the same amount in openList.
Did you also change checkNodesAroundPoint to not add a point to the open list if it's in the closed list?
Offline samcp12

Junior Member


Medals: 1



« Reply #4 - Posted 2013-07-20 01:45:19 »

The way I managed to implement A* pathfinding into my game was, I would get the tile the player is currently on, have an array of tiles that contains all the tiles (not including un-walkable tiles)adjacent to the tile the player was current on. I then calculated (for each tile around the player) how many 'moves' it would take in total to move from the current tile to the target tile. From that I added the cost of moving from the current tile to the tile I'm currently looking at (I used a similar method to that of that article everyone always seems to link people to Tongue), once I found the tile with the lowest cost I simply moved the player/npc to that tile and simply repeated this process until I was on the target tile. It worked perfectly for what I wanted, just spend a bit of time on it, don't give up easily because that won't get you anywhere, keep working at it and suddenly something will click in your brain and you will figure it out Smiley
Offline roseslayer

Junior Member


Medals: 1



« Reply #5 - Posted 2013-07-20 12:57:23 »

Did you also change checkNodesAroundPoint to not add a point to the open list if it's in the closed list?

Uhm... WOW, how could I miss that. I added that single if-statement and the code works! The only thing I now need to do is: making a path from the Point end to the Point start on the closedList and return it.

The way I managed to implement A* pathfinding into my game was, I would get the tile the player is currently on, have an array of tiles that contains all the tiles (not including un-walkable tiles)adjacent to the tile the player was current on. I then calculated (for each tile around the player) how many 'moves' it would take in total to move from the current tile to the target tile. From that I added the cost of moving from the current tile to the tile I'm currently looking at (I used a similar method to that of that article everyone always seems to link people to Tongue), once I found the tile with the lowest cost I simply moved the player/npc to that tile and simply repeated this process until I was on the target tile. It worked perfectly for what I wanted, just spend a bit of time on it, don't give up easily because that won't get you anywhere, keep working at it and suddenly something will click in your brain and you will figure it out Smiley

Also a smart idea, but I think I will stick to the way I think it will work atm. When the game is about to finish (or when it has a huge performance drain) I will look at all my scripts and see what I can change to let it work faster and better.

[EDIT:]
I thaught by doing it backwards I just switch the openList to closedList and Point start to Point end. But it didn't worked for some reason?

Fundamentum W.I.P.
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

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

The first screenshot will be displayed as a thumbnail.

Nickropheliac (15 views)
2014-08-31 22:59:12

TehJavaDev (23 views)
2014-08-28 18:26:30

CopyableCougar4 (33 views)
2014-08-22 19:31:30

atombrot (41 views)
2014-08-19 09:29:53

Tekkerue (40 views)
2014-08-16 06:45:27

Tekkerue (35 views)
2014-08-16 06:22:17

Tekkerue (25 views)
2014-08-16 06:20:21

Tekkerue (37 views)
2014-08-16 06:12:11

Rayexar (72 views)
2014-08-11 02:49:23

BurntPizza (49 views)
2014-08-09 21:09:32
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

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
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!