Problems building A* algorithm

Question

I am trying to build an app implementing A*, and I am having trouble working on the logic. The method here takes in 4 ints (startX/Y, goalX/Y) and then using the A* algorithm, it will build an ArrayList and return it, so the main method can take iterate through and display the path A* builds. But what I am getting is a jumpy path that eventually builds a very thick path to the goal node. Can anybody pinpoint where my mistake is.

Note: open and closed are priority queues and Tile implements comparable.

public ArrayList<Tile> findPath(int sX, int sY, int gX, int gY)
{
    ArrayList<Tile> path = new ArrayList<Tile>();

    open.offer(gameMap[sX][sY]);
    Tile currentNode = gameMap[sX][sY];
    Tile goalNode = gameMap[gX][gY];

    int cX;
    int cY;

    while(open.size() > 0){
        currentNode = open.poll();
        closed.offer(currentNode);
        path.add(currentNode);

        cX = currentNode.getX();
        cY = currentNode.getY();

        if(currentNode == goalNode){
            break;
        }
        if((cX > 0 && cX < gameMap.length - 1) && (cY > 0 && cY < gameMap.length -1)){
            for(int i = -1; i < 2; i++){
                for(int j = 1; j > -2; j--){
                    if(i == 0 && j == 0){}
                    else{

                        if((gameMap[cX + i][cX + j].type != 1) && !closed.contains(gameMap[cX + i][cX + j])){

                            if(!open.contains(gameMap[cX + i][cX + j])){
                                open.offer(gameMap[cX + i][cX + j]);
                                gameMap[cX + i][cX + j].parent = currentNode;

                            }
                        }
                    }

                }

            }

        }

    }

    //         while(currentNode != gameMap[sX][sY]){
    //             path.push(currentNode);
    //             currentNode = currentNode.parent;
    //         }

    return path;
}

Answer 1

I've not completely entered in the details of your implementation, but it comes to my mind that the way in which you are inserting the nodes in OPEN might be a cause of trouble:

if(!open.contains(gameMap[cX + i][cX + j])){
     open.offer(gameMap[cX + i][cX + j]);
     gameMap[cX + i][cX + j].parent = currentNode;
}

Your goal here is to manage avoiding repeated elementes in your OPEN list, but it might happen that sometimes you have to replace the element because you have encountered a way in which you reach it with a better cost. In this case you need to remove the node already inserted in OPEN and reintroduce it with a lower cost (and thus with highest priority). If you do not allow this, you might be generating suboptimal paths as it seems to be your case.

Additionaly, some logic of the algorithm is missing. You should store the accumulated cost from the start, G, and the estimated cost to goal, H, for each node you create. The OPEN list is ordered according to the value of G+H, which I didn't notice in your code to be done this way. Anyway, I recommend you to take a look of some existing implementation of A* like one of the Hipster4j library to have more details on how this works.

Hope my answer helped!

Answer 2

First off, I don't think your closed set needs to be a priority queue. It's just a set of nodes that have been looked at.

You seem to be missing the core part of how A* works, which is why I think this path finder is not working to well for you.

Here's the main idea:

Have a heuristic function that guesses how far away the destination is. Ideally, that function will be admissible, meaning that it will never overestimate the distance.

For tile grids, this can be done using manhattan distance (x difference + y difference) since that is the minimum distance, so it will always be admissible.

Whenever you take a tile out of your open list and add it to the closed set, you need to update the known value of how far away the neighboring tiles are (keeping the lowest known value). Since you have the known value for the tile you are putting in the closed set, you just add 1 to all the neighbors' known values.

By updating these values, the open list may shift order (which is why a priority queue is a good choice here). The heuristic value will probably remain the same, but the known value will get more refined.

Once you reach the destination, you will have a set of closed nodes that all have a known distance. You then backtrack from the destination, looking at each neighbor that is also in the closed set and choosing the one with the lowest known distance.

In terms of how to implement this, you may want to consider having your Tile class be wrapped in another class called SearchTile or something like that. It could look like this:

//You may not want to use public variables, depending on your needs
public class SearchTile implements Comparable<SearchTile> {
    public final Tile tile;
    //These need to be updated
    public int knownDistance = 0;
    public int heuristicDistance = 0;

    public SearchTile(final Tile tile) {
        this.tile = tile;
    }

    @Override
    public int compareTo(final SearchTile other) {
        if (knownDistance + heuristicDistance > other.knownDistance + other.heuristicDistance) {
            return 1;
        } else if (knownDistance + heuristicDistance < other.knownDistance + other.heuristicDistance) {
            return -1;
        } else {
            return 0;
        }
    } 
}

The cool thing about A* is that in the ideal case, it should go straight to the destination. In cases with walls, it will take the best guess and as long as the heuristic is admissible, it will come up with the optimal solution.