A* problem

Started by rkennedy9064 November 15, 2010 06:28 PM

6 comments, last by rkennedy9064 14 years ago

Author

104

November 15, 2010 06:28 PM

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

*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/

Palidine

1,315

November 15, 2010 07:19 PM

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 listfunction (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 parentyou either have a path or don't

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

-me

Palidine

1,315

November 15, 2010 07:25 PM

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

rkennedy9064

Author

104

November 15, 2010 07:29 PM

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?

Palidine

1,315

November 15, 2010 07:33 PM

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

Palidine

1,315

November 15, 2010 07:36 PM

Also, the first thing you should do is pop the lowest F score on the open list and then add neighbors to the open list. I'm not sure what effects doing that in the reverse as you are doing will have.

<a href="http://en.wikipedia.org/wiki/A*_search_algorithm>http://en.wikipedia.org/wiki/A*_search_algorithm

-me

rkennedy9064

Author

104

November 15, 2010 07:51 PM

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

rkennedy9064

Author

104

November 15, 2010 08:09 PM

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

A* problem

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

A* problem

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines