java - Java 中的一流实现

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 是起始节点的总成本，但我如何计算这个值？

有些人可能会注意到我在初始创建邻居 row+col 时添加了一个硬编码的 G 值，相对于起始位置是 0， 0。

Answer 1

我认为您要查找的计算是:

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

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

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

我强烈建议重构以重命名您的字段以匹配您正在使用的伪代码中的标识符。这将使您更容易看到您的代码如何与伪代码相关以及如何不相关。它还可以帮助将伪代码作为注释插入。