实现A*寻路算法

Question

我在二维数组中实现 A* 寻路算法的最后一部分时遇到问题。我正在使用 https://www.raywenderlich.com/4946/introduction-to-a-pathfinding 上的教程一直到最后，都有算法的伪代码。我几乎一直能够遵循这段代码直到最后。我的代码和伪代码的区别在于我预先计算了所有节点的所有 G、H 和 F 值。这就是为什么在执行最后一步时遇到困难的原因。这是伪代码：

[openList add:originalSquare]; // start by adding the original position to the open list
do {
currentSquare = [openList squareWithLowestFScore]; // Get the square with the lowest F score

[closedList add:currentSquare]; // add the current square to the closed list
[openList remove:currentSquare]; // remove it to the open list

if ([closedList contains:destinationSquare]) { // if we added the destination to the closed list, we've found a path
    // PATH FOUND
    break; // break the loop
}

adjacentSquares = [currentSquare walkableAdjacentSquares]; // Retrieve all its walkable adjacent squares

foreach (aSquare in adjacentSquares) {

    if ([closedList contains:aSquare]) { // if this adjacent square is already in the closed list ignore it
        continue; // Go to the next adjacent square
    }

    if (![openList contains:aSquare]) { // if its not in the open list

        // compute its score, set the parent
        [openList add:aSquare]; // and add it to the open list

    } else { // if its already in the open list

        // test if using the current G score make the aSquare F score lower, if yes update the parent because it means its a better path

    }
}

} while(![openList isEmpty]); // Continue until there is no more available square in the open list (which means there is no path)

教程说明它是用 Objective-C 编写的，但我的实现是用 C++ 编写的。这是我的 calculatePath 函数：

AStarPath AStarSearch::calculatePath()
{
    if (!wasInit)
    {
        throw "AStarSearch::calculatePath():  A* Search was not initialized!\n";
    }
    /*Create open and closed lists*/
    std::vector<AStarNode*> openList;
    std::vector<AStarNode*> closedList;

    /*Add the start node to the open list*/
    openList.push_back(startNode);

    do
    {
        /*Get square with lowest F score in the open list*/
        AStarNode* currentNode = openList[0];
        for (int index = 0; index < openList.size(); ++index)
        {
            if (openList[index]->getF() < currentNode->getF())
                currentNode = openList[index];
        }

        /*Remove the current node from the open list, add it to the closed list*/
        std::remove(openList.begin(), openList.end(), currentNode);
        closedList.push_back(currentNode);

        /*Check if the destination is in the closed list*/
        if (std::find(closedList.begin(), closedList.end(), endNode) != closedList.end());
        {
            /*Found a path, break the loop*/
            break;
        }

        /*Find walkable and adjacent nodes*/
        std::vector<AStarNode*> walkableAdjacent = getWalkableAdjacentNodes(currentNode->getX(), currentNode->getY());
        for (std::vector<AStarNode*>::iterator it = walkableAdjacent.begin(); it != walkableAdjacent.end(); ++it)
        {
            /*Skip the node if it is in the closed list*/
            if (std::find(closedList.begin(), closedList.end(), *it) != closedList.end())
            {
                /*Skip to next node*/
                continue;
            }
            /*If the node is not in the open list, set it's parent and add it to the open list*/
            if (std::find(openList.begin(), openList.end(), *it) != closedList.end())
            {
                /*Set the parent to the current node*/
                (*it)->setParent(currentNode);
                /*Add the node to the open list*/
                openList.push_back(*it);
            }
            /*If the node is in the open list*/
            else
            {
                //This is the part I'm having trouble with
            }
        }

    } while (!openList.empty());
}

else 语句中应该出现的伪代码已经很有帮助了。

编辑：当我在 else 语句中写这个时我是否正确：

/*Check if the node has a better G value than the current node*/
if ((*it)->getG() < currentNode->getG())
{
    /*Do I have to set a parent here?*/
}

编辑 2：我发现我的问题得到了反对票。有人可以告诉我我做错了什么，这样我就可以纠正自己并在需要时提供更多信息，或者从我的下一个问题中吸取教训吗？

Answer 1

因为我已经预先计算了所有的 G 和 F 值，所以在 else 语句中更新它们没有意义，所以我可以将其留空。

实现A*寻路算法

Implementing A* pathfinding algorithm

c++

algorithm

a-star

path-finding