A* Pathfinding Algorithm -- finding a path, but not optimal best path

Question

I'm working on an A* algorithm. This is the code for the pathfinding method. For reference, this is the board I am working with: https://i.sstatic.net/ORBqb.png Each color tile represents a different heuristic value. For some unknown reason, it finds a path every single time, just not always the correct path. Here is the code for the pathfinding method. If anyone needs any clarifications, I'd be happy to provide them.

public List<Point> findPath(Point start, Point end) {

    //declarations and instantiations
    List<PathState> closedList = new ArrayList<PathState>();    //the nodes already considered
    List<PathState> openList = new ArrayList<PathState>();      //nodes to be considered
    openList.add(new PathState(start, end, tm));                //add starting point
    PathState current = openList.get(0);

    while(!current.isGoal()){
        //sort open list to find the pathstate with the best hscore(sorts by hscore)
        Collections.sort(openList);
        current = openList.get(openList.size() - 1);
        closedList.add(current);
        openList.remove(current);

        //get the valid children of current node
        List<PathState> children = current.getChildren();;

        if(!current.isGoal()){              
            for(int i = 0; i < children.size(); i++){
                if(!closedList.contains(children.get(i))){
                    if(openList.contains(children.get(i))){
                        if(openList.get(openList.indexOf(children.get(i))).getgScore() > children.get(i).getgScore()){
                            //child is already on the open list, but this node has lower g value
                            //change g value and parent of node on open list
                            openList.get(openList.indexOf(children.get(i))).setG(children.get(i).getgScore());
                            openList.get(openList.indexOf(children.get(i))).changeParent(current);
                    }
                    }else{
                        //child not in closed list
                        openList.add(children.get(i));

                        //repaint the terrain panel with shades
                        tp.addAstarState(children.get(i));
                        tp.repaint();
                        try {
                            Thread.sleep(25);
                        } catch(Exception e) {
                            e.printStackTrace();
                        }
                    }
                }
            }
        }
    }
    //returns the path from winning node to start for output
    return current.getPath();
}

Have you tried visualising the path taken in steps, and printing to the console the logic defining the steps taken? Also, just to check, what happens if you change the operator from greater than to less than in (openList.get(openList.indexOf(children.get(i))).getgScore() > children.get(i).getgScore())? — Mapsy
– Mapsy, Commented Dec 10, 2014 at 3:43
what is your function to estimate the distance to destination? That's probably in getScore() function — mohsaied
– mohsaied, Commented Dec 10, 2014 at 4:03

mohsaied · Accepted Answer · 2014-12-10 04:11:53Z

A* is basically Djikstra's algorithm but you direct your search to the destination by combining your distance function with an estimate of the remaining distance.

At node x, the cost or "score" is (distance_so_far) for djikstra

at A*, it is (distance_so_far + estimate_of_remaining_distance)

To make sure that A* finds the shortest path, the estimate_of_remaining_distance must be a true lower bound. That means it must always be less than the actual remaining distance. That means, you can never overestimate this distance otherwise it becomes an inexact heuristic in which case it won't necessarily find the shortest path.

This is a good reference: http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html

It links to this reference which explains more about heuristic functions: http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html

Collectives™ on Stack Overflow

A* Pathfinding Algorithm -- finding a path, but not optimal best path

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related