Sign in to follow this  
rkennedy9064

A* problem

Recommended Posts

rkennedy9064    104
Ive been working on implementing an A* algorithim for practice and seem to have run into a problem. Ive gotten it to work for any path that does not involve walls, and a few wall cases, but on certain tests it freezes up. If I make the wall too long it just seems to get stuck on one node and can't continue even though there is a path. If anyone has any suggestions it would be greatly appreciated. This is my code so far


public void findPath(){
closed.add(start);
AStarNode currentNode = start;

while(!closed.contains(end)){
for(int x = -1; x <= 1; x++){
for(int y = -1; y <= 1; y++){
if(this.isValidNode(currentNode.getX() + x, currentNode.getY() + y)){
AStarNode temp = board[currentNode.getX() + x][currentNode.getY() + y];
if(!closed.contains(temp) && temp.isWalkable()){
if(!open.contains(currentNode)){
temp.setParent(currentNode);
temp.setScore(currentNode, end);
temp.setColor(Color.yellow);
board[temp.getX()][temp.getY()] = temp;
open.add(temp);
}
}
}
}
}

currentNode = open.first();
open.remove(open.first());
board[currentNode.getX()][currentNode.getY()] = currentNode;
closed.add(currentNode);

if(open.isEmpty()){
break;
}
}

for(AStarNode node : closed){
board[node.getX()][node.getY()].setColor(Color.BLACK);
}

this.repaint();
}







This is a picture of a case where the path is found
Working

Here is a picture where the path fails and freezes up
Not working


*Edit*
Pictures don't seem to be working so here are links
Working: http://img18.imageshack.us/i/workingastar.png/
Not Working: http://img408.imageshack.us/i/notworkingastar.png/

Share this post


Link to post
Share on other sites
Palidine    1315
I don't see you adding to the closed list ever formatting was screwed up. I see it now.
I can't see the implementation of setScore, but are you setting f, g and h correctly?
I don't see you resetting the score of a node already on the open list when you discover a shorter route to it.
It looks like you're linearly iterating your world nodes instead of exploring neighbors. nevermind, you are iterating neighbors.
I don't see you picking the smallest F score of the open list.

Basically, you seem to have most of the algorithm pretty wrong. The wikipedia A* page is pretty awesome, you should check it out.

But in pseudo-code it's pretty close to this:

add the start to the open list

function (keep calling this until path found or all nodes exhausted):
- find the lowest f score on the open list
- if it's the goal, you've found a path (just backtrack parents)
- add it to the closed list
- add it's neighbors to the open list if they're not already there
with current node as parent
- if the neighbor is already there, re-evaluate it's score with
the current node as parent, if it's less, update it's score
and set current node to parent

you either have a path or don't


A very common optimization is to make your open list a binary heap.

-me

Share this post


Link to post
Share on other sites
Palidine    1315
Also, your working example is not actually working. That's definitely not the shortest path. The shortest path is the diagonal. But anyway, you just need to implement the algorithm correctly as I point out above [smile].

-me

Share this post


Link to post
Share on other sites
rkennedy9064    104
I add to the closed list right after the nested for loop to check the neighbors and I use a sorted set so I take the lowest F from the list by making the next current Node = open.first();

Java

currentNode = open.first();
open.remove(open.first());
board[currentNode.getX()][currentNode.getY()] = currentNode;
closed.add(currentNode);




This is my setScore code
Java

public void setScore(AStarNode prev, AStarNode end)
{
this.g = prev.getG() + (prev.getX() - this.x == 0
|| prev.getY() - this.y == 0 ? 10 : 14);
this.h = 10 * (Math.abs(this.x - end.getX())
+ Math.abs(this.y - end.getY()));
this.f = g + h;
}



And when you talk about re-evaluatiing the neighbors that are already in the list. Does the just mean I would use my current nodes g score and add it to the cost of moving to that neighbor, then if that is less then the neighbors node its a better path and I update it making that neighbors parent the node I'm currently on?

Share this post


Link to post
Share on other sites
Palidine    1315
Yeah, made a ton of edits in my original post. your code formatting is screwed up and I read it wrong [smile]

Quote:
Original post by rkennedy9064
And when you talk about re-evaluatiing the neighbors that are already in the list. Does the just mean I would use my current nodes g score and add it to the cost of moving to that neighbor, then if that is less then the neighbors node its a better path and I update it making that neighbors parent the node I'm currently on?


Correct. This seems to be the most likely cause of error. Just make sure you do this calculation as a temporary so that if it's not smaller, you don't affect what's in there.

Is your open list automatically sorted somewhere? I don't see the implementation of your open list, but when you take the first element you must ensure that it's the smallest F score in the list. Again, a binary heap is the most common implementation of an open list.

-me

Share this post


Link to post
Share on other sites
rkennedy9064    104
K I'll try those things, I use the built in TreeSet with a custom comparator for my set so it sorts them. I make sure all the nodes have an indivudal x,y so if the x,y == x,y then their the same otherwise I put them in order of their f score

Share this post


Link to post
Share on other sites
rkennedy9064    104
Is this the implementation you were talking about with the node switching?

Java

public void findPath(){
open.add(start);

while(!closed.contains(end)){
AStarNode currentNode = open.first();
closed.add(currentNode);
open.remove(currentNode);

for(int x = -1; x <= 1; x++){
for(int y = -1; y <= 1; y++){
if(this.isValidNode(currentNode.getX() + x, currentNode.getY() + y)){
AStarNode temp = board[currentNode.getX() + x][currentNode.getY() + y];
if(!closed.contains(temp) && temp.isWalkable()){
if(!open.contains(temp)){
temp.setParent(currentNode);
temp.setScore(currentNode, end);
temp.setColor(Color.yellow);
board[temp.getX()][temp.getY()] = temp;
open.add(temp);
}
else{
int tempCost = currentNode.getG() + ((currentNode.getX() - temp.getX() == 0 || currentNode.getY() - temp.getY() == 0) ? 10 : 14);
if(tempCost < temp.getG()){
temp.setParent(currentNode);
temp.setScore(currentNode, end);
board[temp.getX()][temp.getY()] = temp;
}
}
}
}
}
}

if(open.isEmpty()){
break;
}
}

for(AStarNode node : closed){
board[node.getX()][node.getY()].setColor(Color.BLACK);
}

this.repaint();
}




Also I ran some output to see what nodes were being checked when the program got stuck. For some reason it hits the wall and it seems to check the node below it and then somehow jump above it and continually check that node. Here is a picture if your interested and the output

http://img602.imageshack.us/i/notworkingastar.png/

java.awt.Point[x=1,y=4] true
java.awt.Point[x=2,y=4] true
java.awt.Point[x=3,y=4] true
java.awt.Point[x=3,y=5] true
java.awt.Point[x=3,y=3] true
java.awt.Point[x=2,y=5] true
java.awt.Point[x=2,y=5] true
java.awt.Point[x=2,y=5] true
java.awt.Point[x=2,y=5] true
java.awt.Point[x=2,y=5] true

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this