在 2D 数组中实现 A* 寻路

Question

我正在制作 2D 图块地图，现在正在尝试实现 A* 寻路。我正在关注 A* 的维基百科伪代码。

除了算法决策中出现一些奇怪的行为之外，一切进展顺利。

到目前为止我的代码：

void Pathfinding(Point from, Point destination) {

    goalNode = new Node(destination, 0, 0);
    startNode = new Node(from, 0, ManhattanDistance(from, destination));

    open = new List<Node>();            //list of nodes
    closed = new List<Node>();
    open.Add(startNode);                //Add starting point

    while(open.Count > 0) {

        node = getBestNode();                   //Get node with lowest F value
        if(node.position == goalNode.position) {
            Debug.Log("Goal reached");
            getPath(node);
            break;
        }
        removeNode(node, open);
        closed.Add(node);

        List<Node> neighbors = getNeighbors(node);
        foreach(Node n in neighbors) {
            float g_score = node.G + 1;
            float h_score = ManhattanDistance(n.position, goalNode.position);
            float f_score = g_score + h_score;

            if(isValueInList(n, closed) && f_score >= n.F) 
                continue;

            if(!isValueInList(n, open) || f_score < n.F) {
                n.parent = node;
                n.G = g_score;
                n.G = h_score;
                if(!isValueInList(n, open)) {
                    map_data[n.position.x, n.position.y] = 4;
                    open.Add(n);
                }
            }
        }
    }
}

运行这段代码的结果：

蓝色是打开列表中的节点，绿色是选择到目标节点的路径。

解决方案：

void Pathfinding(Point from, Point destination) {

    goalNode = new Node(destination, 0, 0);
    startNode = new Node(from, 0, ManhattanDistance(from, destination));

    open = new List<Node>();            //list of nodes
    closed = new List<Node>();
    open.Add(startNode);                //Add starting point

    while(open.Count > 0) {

        node = getBestNode();                   //Get node with lowest F value
        if(node.position == goalNode.position) {
            Debug.Log("Goal reached");
            getPath(node);
            break;
        }
        removeNode(node, open);
        closed.Add(node);

        List<Node> neighbors = getNeighbors(node);
        foreach(Node n in neighbors) {
            float g_score = node.G + 1;
            float h_score = ManhattanDistance(n.position, goalNode.position);
            float f_score = g_score + h_score;

            if(isValueInList(n, closed) && f_score >= n.F) 
                continue;

            if(!isValueInList(n, open) || f_score < n.F) {
                n.parent = node;
                n.G = g_score;
                n.H = h_score;
                if(!isValueInList(n, open)) {
                    map_data[n.position.x, n.position.y] = 4;
                    open.Add(n);
                }
            }
        }
    }
}

Answer 1

首先，您的打开节点应该按降序“排序”，而在您的代码中 - 没有排序。您计算距离 (g) 和启发式 (h)，但从未实际使用它。您应该考虑使用有序容器而不是列表（因为每次迭代中对列表进行排序效率不高） 其次，您不将启发式值存储在节点中

n.G = h_score;

应该是

n.H = h_score;

Answer 2