A* path finding

Game Mechanics
#1

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. :stuck_out_tongue:
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 :slight_smile:

#2

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

#3

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?

#4

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:


List<Node> path = new ArrayList<Node>();
Node node = goalNode;
while (node.parent != null) {
    path.add(node);
    node = node.parent
}
#5

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

#6

Thanks guise. :slight_smile:

#7

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!

#8 
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.

#9

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.

#10

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 :P.

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

#11

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. :frowning:

#12

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

#13

I caught the problem I think.


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.

#14

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

EDIT: My fault, forgot to do

start.f = manhattanDistance(start, goal);
#15

And another problem:


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

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

#16

I got it working to find the path:


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:


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:


				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

#17

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:



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.

#18

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

What you got here:

Won’t help because of some of the other typo issues, primarily:


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*. :D)

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

#19

Thanks for all your help. :slight_smile: I’ll try this out and reply back.

#20

All works great. :smiley: 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?