1

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

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

4

1 回答 1

1

我认为您正在寻找的计算是：

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

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

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

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

于 2012-11-06T17:08:39.947 回答