Java中的A-star实现

Question

我正在尝试用Java实现A*，但我遇到了障碍，基本上不知道如何从这一点开始。

我目前正在关注来自Wikipedia的伪代码。

我的节点是这样构造的：

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;
    }
}

重要的是要注意，f是在创建节点时计算的。

我当前的A*代码，它不完整：

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 !          

            }   
        }           
    }

最后一行的注释基本上就是我结束的地方，相当于伪代码中接近for each neighbor in neighbor_nodes(current)的内容。此外，我知道G是从开始节点开始的总成本，但是我如何计算这个值？

正如一些人可能注意到的那样，im在初始创建邻居row+col时添加了硬编码的G值，这与开始位置是0,0有关。

Answer 1

我想你要找的计算方法是：

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

这意味着您需要每个节点沿着到它的最佳路径存储分数，这是目前为止找到的。您有了当前节点的新分数，目标是如果通过当前节点的路径优于邻居节点以前的最佳分数，则更新每个邻居节点的最佳分数。

我不确定你硬编码的G值相对于算法的重要性。如果您已经知道到达每个节点的最佳情况下的成本，我认为您不需要A*。

我强烈建议通过重构来重命名字段，使其与您正在使用的伪代码中的标识符相匹配。这将使您更容易看到您的代码与伪代码之间的关系。它还可以帮助交错伪代码作为注释。