Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (498)
Games in Android Showcase (117)
games submitted by our members
Games in WIP (563)
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* path finding  (Read 1301 times)
0 Members and 1 Guest are viewing this topic.
Offline Porlus

Junior Member





« Posted 2014-04-09 20:55:02 »

Hi all,

I don't mean to create a topic regarding the exact same subject as another topic on the front page, but I didn't want to hijack their's. :p
Anyway, I've been implementing A* path finding from a tutorial found here: http://web.mit.edu/eranki/www/tutorials/search/
I've been going off the algorithm detailed at the bottom of that page and was just wondering where the final path is.
In other implementations of this algorithm, there was an open, closed and final path list. I understand most of the algorithm, but once it's been designed, how do I access the final list of nodes?

Thanks Smiley
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 800
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #1 - Posted 2014-04-09 21:03:10 »

Backtrack from the destination to the visited neighbour (recursively) with the lowest accumulated cost. When you reached zero, you reached the starting point.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Porlus

Junior Member





« Reply #2 - Posted 2014-04-09 21:12:07 »

Oh, I think I originally misread the pseudo code. Am I right in thinking the path is in the closed list once this has ended?
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline UprightPath
« Reply #3 - Posted 2014-04-09 21:27:22 »

Yes and no. The correct path is a subset of the closed list. This means that all nodes from start to finish will appear in the closed list. However, the closed list contains every visited node.

From a quick glance as the pseudocode that was posted in your link, to get your path you're going to treat the end node as a sort of linked list and backtrack through path using node.parent to construct it. Something like:
1  
2  
3  
4  
5  
6  
List<Node> path = new ArrayList<Node>();
Node node = goalNode;
while (node.parent != null) {
    path.add(node);
    node = node.parent
}

Offline Porlus

Junior Member





« Reply #4 - Posted 2014-04-09 21:36:31 »

Oh yeah, of course. Tongue That makes sense. Sorry for not getting that's what you meant, Riven. :x I'm knackered today.
Offline Porlus

Junior Member





« Reply #5 - Posted 2014-04-09 21:36:50 »

Thanks guise. Smiley
Offline Porlus

Junior Member





« Reply #6 - Posted 2014-04-14 13:50:22 »

Hi all, I'm just trying to implement this algorithm that I've mentioned above, but it seems to be stuck loading endlessly.

Here's my source: http://www.java-gaming.org/?action=pastebin&id=896

At the moment I'm declaring it with the start and goal nodes set to (0, 0) and (10, 5) respectively. Can anyone spot the reason why it's loading out?

Thanks!
Offline Gibbo3771
« Reply #7 - Posted 2014-04-14 14:04:20 »

Hi all, I'm just trying to implement this algorithm that I've mentioned above, but it seems to be stuck loading endlessly.

Here's my source: http://www.java-gaming.org/?action=pastebin&id=896

At the moment I'm declaring it with the start and goal nodes set to (0, 0) and (10, 5) respectively. Can anyone spot the reason why it's loading out?

Thanks!

1  
open.add(start);


At no point do you remove start from the open list, therefore its size is always > 0. Infinite loop.

Also when you are creating your NodeMap, if you have one...are you predefining a bunch of nodes that are automatically closed?

EDIT:

Also I have no idea if my way is more efficient, but I have each node store an array of neighbours instead of doing that in the loop, my nodes are all initialized at game start so that only gets done once.

Also from what I see you have no predefined nodemap, I suggest you make one. Surely you have obstacles? If so, get a node map made.

EDIT 2:

Actually now that I think of it, why is start even on the open list? It is not an option, you are already there. It should be on the closed list.

"This code works flawlessly first time and exactly how I wanted it"
Said no programmer ever
Offline Porlus

Junior Member





« Reply #8 - Posted 2014-04-14 14:09:53 »

All the tutorials I've looked at have told me to add the start node to the open list. :x
The start node is removed almost immediately because it is the node with the lowest f value in the open list and that node is removed at the beginning of the loop.
Offline Gibbo3771
« Reply #9 - Posted 2014-04-14 14:16:12 »

All the tutorials I've looked at have told me to add the start node to the open list. :x
The start node is removed almost immediately because it is the node with the lowest f value in the open list and that node is removed at the beginning of the loop.

Ah right I see where that is removed now, fair enough.

Regardless you are stuck in that loop, it seems your open list is never actually empty therefore your path is never actually found.

I suggest slapping a bunch of print statements in each part of the code where the search is complete, the loop should break or when a node is removed. As well as print the size of open each time one of those happens.

That should help you pinpoint, my pathfinder is quite a bit different. Hella lot easier to read, probably just because I wrote it  Tongue.

EDIT: Oops yeah, I add my start node to the open list as well! Shows the last time I looked over this code LOL.

"This code works flawlessly first time and exactly how I wanted it"
Said no programmer ever
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Porlus

Junior Member





« Reply #10 - Posted 2014-04-14 14:24:02 »

Yeah, I've tried adding in a few print statements to help shed some light but it's a bit overwhelming and I'm not sure what I'm supposed to be looking for. Sad
Offline Gibbo3771
« Reply #11 - Posted 2014-04-14 14:51:32 »

Just to let you know I am trying to find the problem lol.

"This code works flawlessly first time and exactly how I wanted it"
Said no programmer ever
Offline UprightPath
« Reply #12 - Posted 2014-04-14 15:04:15 »

I caught the problem I think.

1  
2  
3  
4  
5  
6  
Node[] successors = new Node[] {
               new Node(q, q.x, q.y + 1),
               new Node(q, q.x, q.y - 1),
               new Node(q, q.x + 1, q.y),
               new Node(q, q.x - 1, q.y)
         };


You have no range check here. So you'll be creating nodes that extend out into negative infinity and positive infinity.

Offline Kefwar

Senior Member


Medals: 5
Projects: 1



« Reply #13 - Posted 2014-04-14 15:12:27 »

I've debugged the code and I noticed that node q is the begin location everytime.

EDIT: My fault, forgot to do
1  
start.f = manhattanDistance(start, goal);
Offline UprightPath
« Reply #14 - Posted 2014-04-14 15:21:36 »

And another problem:

1  
2  
3  
      Node q = null;
      while(open.size() > 0) {
         q = null;


You need to set q == null at the start of each loop.

Offline Kefwar

Senior Member


Medals: 5
Projects: 1



« Reply #15 - Posted 2014-04-14 15:28:19 »

I got it working to find the path:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
public class AStarTest {

   public static void main(String[] args) {
      new AStarTest();
   }
   
   private AStar astar;
   
   public AStarTest() {
      astar = new AStar(new Node(0,1), new Node(5,9));
      astar.listNodes();
   }
}


and the path:
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
5 : 9
4 : 9
3 : 9
2 : 9
1 : 9
0 : 9
0 : 8
0 : 7
0 : 6
0 : 5
0 : 4
0 : 3
0 : 2


what I changed:
1  
2  
3  
            if(!found1 && !found2 && node.f <= q.f) {
               open.add(node);
            }


This is not the way to fix it with obstakles, but you can see what goes wrong
Offline Gibbo3771
« Reply #16 - Posted 2014-04-14 15:35:09 »

You really need to rethink all your variable names, this could have been avoided if you where not messing around with variable called n, q, f and h and what not, I know what they are but it is still annoying as hell, for instance:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
Node q; > Node current;

Node[] successors = new Node[] { new Node(q, q.x, q.y + 1),
               new Node(q, q.x, q.y - 1), new Node(q, q.x + 1, q.y),
               new Node(q, q.x - 1, q.y) };

>

Node[] currentNeighbours = new Node[] { new Node(q, q.x, q.y + 1),
               new Node(q, q.x, q.y - 1), new Node(q, q.x + 1, q.y),
               new Node(q, q.x - 1, q.y) };

      for (Node neighbour: currentNeighbours ) {
            if (neighbour.equals(goal)) {
               last = node;
               break;
            }


Just a though, it will greatly help you think.

Also more comments, lots more.

"This code works flawlessly first time and exactly how I wanted it"
Said no programmer ever
Offline UprightPath
« Reply #17 - Posted 2014-04-14 15:37:37 »

There were several other issues in the code that I found during exploration.

What you got here:
1  
2  
3  
            if(!found1 && !found2 && node.f <= q.f) {
               open.add(node);
            }

This is not the way to fix it with obstakles, but you can see what goes wrong

Won't help because of some of the other typo issues, primarily:
1  
2  
3  
node.g = q.g + manhattanDistance(node, q);
            node.h = manhattanDistance(node, goal);
            node.f = node.g + node.h;

Which is computing the g value wrong for all nodes (G value is the ACTUAL TRAVELED DISTANCE!) so this is giving bad values.

This file: http://www.java-gaming.org/?action=pastebin&id=898 gives you the right value and has some other misc corrections. You still end up exploring negative areas though. This version also cuts out when the F of the 'next shortest path' is greater than the best (Which is an important part of A*. Cheesy)

Edit: Changing the link to one that high lights the changes.

Offline Porlus

Junior Member





« Reply #18 - Posted 2014-04-14 18:33:13 »

Thanks for all your help. Smiley I'll try this out and reply back.
Offline Porlus

Junior Member





« Reply #19 - Posted 2014-04-14 18:54:15 »

All works great. Cheesy Thanks for everyone's help. Hey UprightPath, when you say the next shortest path, wouldn't that always be greater than the shortest path? Also, do you know how I would solve that problem?
Offline UprightPath
« Reply #20 - Posted 2014-04-15 00:03:05 »

When each node takes only 1 to move between (A flat cost map) then you don't need to do anything. It's when you have maps of different costs (Say, moving from a road to a swamp in a strategy game, or going up stairs or something) then you have to worry about it.

What you can do when it comes to the out of bounds things is use some method call to get the nodes:
1  
2  
3  
4  
5  
6  
7  
8  
private static Node nullNode = new Node(-1, -1);
public Node getNode(Node parent, int x, int y) {
if(x < 0 || x >= boundsX || y < 0 || y >= boundsY) {
return nullNode
} else {
return new Node(parent, x, y);
}
}

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.

radar3301 (12 views)
2014-09-21 23:33:17

BurntPizza (30 views)
2014-09-21 02:42:18

BurntPizza (22 views)
2014-09-21 01:30:30

moogie (20 views)
2014-09-21 00:26:15

UprightPath (28 views)
2014-09-20 20:14:06

BurntPizza (33 views)
2014-09-19 03:14:18

Dwinin (48 views)
2014-09-12 09:08:26

Norakomi (74 views)
2014-09-10 13:57:51

TehJavaDev (103 views)
2014-09-10 06:39:09

Tekkerue (50 views)
2014-09-09 02:24:56
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!