CODEWITHSUNDEEP
javaalgorithma-star
JavaCake
JavaCake

Reputation: 4115

A-star implementation in Java

I am trying to implement A* in Java but i have hit a brick wall and basically dont know how to proceed from this point.

I am currently following the pseudocode from Wikipedia.

My node is constructed like so:

static class Node {
    int col;
    int row;
    int g;
    int h;
    int f;
    public Node(int col, int row, int g, int h) {
        this.col = col;
        this.row = row;
        this.g = g;
        this.h = h;
        this.f = g+h;
    }
}

Its important to notice that f is calculated when the Node is created.

My current A* code, which is uncomplete:

public void makeAstar(MapParser parsedMap) {
        // create the open list of nodes, initially containing only our starting node
        ArrayList<Node> openList = new ArrayList<Node>();
        // create the closed list of nodes, initially empty
        Map closedMap = new Map(rowSize, columnSize, "Closed map");
        // Fill closedMap with 0's
        closedMap.buildMapWithValue(0); 
        // Create neighbourlist
        ArrayList<Node> neighbourList = new ArrayList<Node>();

        // Some vars
        int rowTemp = 0;
        int colTemp = 0;
        int currentCost = 0;
        int tempCost = 0;

        //TODO hardcore cost! rowTemp+colTemp

        // Initialize with the first node
        openList.add(new Node(0,0,9,this.getMapValue(0, 0)));

        while(!openList.isEmpty()) {
            // Consider the best node, by sorting list according to F
            Node.sortByF(openList);
            Node currentNode = openList.get(0);
            openList.remove(0);

            // Stop if reached goal (hardcoded for now)
            if(currentNode.getCol() == 4 && currentNode.getRow() == 4) {
                System.out.println("Reached goal");
                break;
            }

            // Move current node to the closed list
            closedMap.setMapValue(currentNode.getRow(), currentNode.getCol(), 1);

            // Get neighbours
            rowTemp = currentNode.getRow()-1;
            colTemp = currentNode.getCol();
            if(!currentNode.isTopRow()) {  // Add value ^
                neighbourList.add(new Node(rowTemp, colTemp,rowTemp+colTemp,this.getMapValue(rowTemp, colTemp)));
            } 

            rowTemp = currentNode.getRow();
            colTemp = currentNode.getCol()-1;
            if(!currentNode.isRightColumn()) { // Add value <
                neighbourList.add(new Node(rowTemp, colTemp,rowTemp+colTemp,this.getMapValue(rowTemp, colTemp)));
            }

            rowTemp = currentNode.getRow();
            colTemp = currentNode.getCol()+1;
            if(currentNode.isLeftColumn()) { // Add value >
                neighbourList.add(new Node(rowTemp, colTemp,rowTemp+colTemp,this.getMapValue(rowTemp, colTemp)));
            }

            rowTemp = currentNode.getRow()+1;
            colTemp = currentNode.getCol();
            if(currentNode.isBottomColumn()) { // Add value v
                neighbourList.add(new Node(rowTemp, colTemp,rowTemp+colTemp,this.getMapValue(rowTemp, colTemp)));
            }

            // As long as the neighbour list is not empty
            while(!neighbourList.isEmpty()) {
                Node temp = neighbourList.get(0);
                neighbourList.remove(0);

                if(!isNotInClosedMap(temp.getRow(), temp.getCol())) {
                    continue;
                }

                //Stuck here !          

            }   
        }           
    }

The comment on the last line is basically where i have ended, which is equivalent to something near for each neighbor in neighbor_nodes(current) in the pseudocode. Furthermore i understand that G is the total cost from the start node, but how can i calculate this value?

As some might notice im adding a hardcoded G value on initial creation of the neighbours row+col, this with respect that the start position is 0,0.

Upvotes: 1

Views: 5944

Answers (1)

Patricia Shanahan
Patricia Shanahan

Reputation: 26185

I think the calculation you are looking for is:

tentative_g_score := g_score[current] + dist_between(current,neighbor)

The implication is that you need each node to store the score along the best path to it that has been found so far. You have a new score for the current node, and the objective is to update the best scores for each of its neighbors if the path through the current node is better than the best previous score for the neighbor node.

I'm not sure of the significance of your hard coded G value relative to the algorithm. If you already know the best case cost of getting to each node I don't think you need A*.

I strongly recommend refactoring to rename your fields to match the identifiers in the pseudo-code you are working from. That would make it easier to see how your code does and does not relate to the pseudo-code. It can also help to interleave the pseudo-code as comments.

Upvotes: 1

Related Questions