C# XNA A* 寻路敌人卡在对面的墙上

Question

我的游戏中有一个由节点组成的二维网格。我有使用 A* 寻路算法跟随玩家的敌人(使用 H 的对角线距离启发式，因为允许对角线移动)。

寻路几乎在所有时间都有效，但是，当玩家和敌人正好位于墙的相对(对角线、垂直或水平)两侧时，敌人会卡住并停止移动。

从下面的截图你可以看到在这个场景中找到的路径，由于某种原因，路径相反方向的节点也被添加到路径中:

下面是我的 F、G 和 H 计算代码(在我的节点类中):

// Calculates distance cost from current node to an adjacent node.
public void CalculateG(Node nodeTarget)
{
    // If the node is diagonal to the current node, its cost of movement is higher.
    if (TileX != nodeTarget.TileX && TileY != nodeTarget.TileY)
    {
        intG = 14;
    }
    else intG = 10;
}

// Calculates H cost using the diagonal shortcut method.
public void CalculateH(Node nodeTarget)
{
    int intXDiff = Math.Abs(TileX - nodeTarget.TileX);
    int intYDiff = Math.Abs(TileY - nodeTarget.TileY);

    if (intXDiff > intYDiff)
        intH = 14 * intYDiff + 10 * (intXDiff - intYDiff);
    else intH = 14 * intXDiff + 10 * (intYDiff - intXDiff);
}

public void CalculateF()
{
    intF = intG + intH; // F = G + H
}

我的寻路类代码如下所示:

public class Path
{
    private List<Node> PathOfNodes; // Stores the path of nodes to follow to the destination.

    public List<Node> NodePath
    {
        get { return PathOfNodes; }
    }

    // Constructor takes the starting node, destination and the grid to generate the path.
    public Path(Node Start, Node Destination, GridLayer grid)
    {
        List<Node> openNodes = new List<Node>(); // Creates a list of possible nodes for the path.
        List<Node> closedNodes = new List<Node>(); // Creates a list of nodes confirmed for the path.

        openNodes.Add(Start); //  Step 1: Adds the current node to the possibilities list.

        // Loops while the destination is not on the closed list and while the open nodes list is not empty.
        while (!closedNodes.Contains(Destination) && openNodes.Any())
        {
            // Sorts the open list according to f scores.
            openNodes.Sort((node, otherNode) => node.F.CompareTo(otherNode.F));
            Node nodeCurrent = openNodes[0]; // The node with the lowest F score is set as the current node.

            openNodes.Remove(nodeCurrent);
            closedNodes.Add(nodeCurrent); // The current node is moved to the closed list.

            // Creates a list containing all the nodes adjacent to the current node.
            List<Node> adjacentNodes = AddAdjacentNodes(grid, nodeCurrent);

            CheckAdjacentNodes(adjacentNodes, ref closedNodes, ref openNodes, nodeCurrent, Destination);
        }
        EstablishPath(closedNodes);
    }

    // Adds all the adjacent nodes from above the current node turning clockwise.
    public List<Node> AddAdjacentNodes(GridLayer grid, Node nodeCurrent)
    {
        int intCol = nodeCurrent.TileX / nodeCurrent.TileWidth;
        int intRow = nodeCurrent.TileY / nodeCurrent.TileHeight; // Gets the current node's indices.

        List<Node> adjacentNodes = new List<Node>(); // Stores the nodes adjacent to the current node.
        // The if statements check whether the node is within the grid before adding the node.
        if (intRow - 1 >= 0)
            adjacentNodes.Add(grid.Nodes[intCol, intRow - 1]); // Above
        if ((intCol + 1 < 21 && intRow - 1 >= 0) && (grid.Nodes[intCol + 1, intRow].Traversable) && (grid.Nodes[intCol, intRow - 1].Traversable))
            adjacentNodes.Add(grid.Nodes[intCol + 1, intRow - 1]); // Diagonally Right Up
        if (intCol + 1 < 21)
            adjacentNodes.Add(grid.Nodes[intCol + 1, intRow]); // Right
        if (intCol + 1 < 21 && intRow + 1 < 12 && (grid.Nodes[intCol + 1, intRow].Traversable) && (grid.Nodes[intCol, intRow + 1].Traversable))
            adjacentNodes.Add(grid.Nodes[intCol + 1, intRow + 1]); // Diagonally Right Down
        if (intRow + 1 < 12)
            adjacentNodes.Add(grid.Nodes[intCol, intRow + 1]); // Below
        if (intCol - 1 >= 0 && intRow + 1 < 12 && (grid.Nodes[intCol - 1, intRow].Traversable) && (grid.Nodes[intCol, intRow + 1].Traversable))
            adjacentNodes.Add(grid.Nodes[intCol - 1, intRow + 1]); // Diagonally Left Down
        if (intCol - 1 >= 0)
            adjacentNodes.Add(grid.Nodes[intCol - 1, intRow]); // Left
        if (intCol - 1 >= 0 && intRow - 1 >= 0 && (grid.Nodes[intCol - 1, intRow].Traversable) && (grid.Nodes[intCol, intRow - 1].Traversable))
            adjacentNodes.Add(grid.Nodes[intCol - 1, intRow - 1]); // Diagonally Left Up

        return adjacentNodes;
    }

    // Checks the adjacent node list for nodes to be added to the open list/closed list.
    private void CheckAdjacentNodes(List<Node> adjacentNodes, ref List<Node> closedNodes, ref List<Node> openNodes, Node nodeCurrent, Node destinationNode)
    {
        foreach (Node node in adjacentNodes)
        { // Checks each node to see if it is traversable and not already on the closed list.
            if (node.Traversable && !closedNodes.Contains(node))
            {
                // If the node is not on the open list, add it, set its parent as the current node and calculate its F, G, and H values.
                if (!openNodes.Contains(node))
                {
                    openNodes.Add(node);
                    node.Parent = nodeCurrent;
                    node.CalculateG(nodeCurrent);
                    node.CalculateH(destinationNode);
                    node.CalculateF();
                }
                else // If the node was already on the open list...
                {
                    // If its G cost of the node is lower than its parent + its own...
                    if (node.G < node.G + node.Parent.G)
                    {
                        // Make the node's parent the current node and recalculate its values.
                        node.Parent = nodeCurrent;
                        node.CalculateG(nodeCurrent.Parent);
                        node.CalculateF();
                    }
                }
            }
        }
    }

    private void EstablishPath(List<Node> closedNodes)
    {
        PathOfNodes = new List<Node>(); // Stores the path for the entity to follow to its target.

        for (int intNodeIndex = closedNodes.Count - 1; (intNodeIndex > 1); intNodeIndex--)
        {
            // Starting from the top of the closed list, add each node's parent to the path
            // until the starting node is reached (index is 0).
            PathOfNodes.Add(closedNodes[intNodeIndex].Parent);
        }
        PathOfNodes.Remove(null); // Remove the final null node (as the final node has no parent).
    }
}

我认为节点的 G 分数与自身及其父节点的 G 分数之间的比较存在问题。我不确定我是否在比较后使用正确的相邻节点重新计算 G 分数。如果有人可以更清楚地说明这一点，那将非常有帮助。我关注的文章是: https://www.gamedev.net/resources/_/technical/artificial-intelligence/a-pathfinding-for-beginners-r2003

但是，我认为我没有在我的代码中正确实现这一步:

If it is on the open list already, check to see if this path to that square is better, using G cost as the measure. A lower G cost means that this is a better path. If so, change the parent of the square to the current square, and recalculate the G and F scores of the square.

请让我知道此问题所需的任何其他信息。 提前致谢。

编辑:我没有为与墙壁碰撞的敌人设置任何碰撞检测。敌人沿着路径向节点路径列表中的最后一个节点移动。

编辑:我的G计算错误，分数没有累加。

正确累积 G 分数后，它现在可以在所有 4 个方向上寻找路径(启发式设置为 0)。我猜这意味着所有关闭的列表节点都被添加到我的最终路径中，这意味着我的建立路径方法存在问题。

红色数字表示节点的 f 分数，蓝色数字表示节点父节点的 f 分数(因此您可以分辨出哪个节点是其父节点)。 After correctly accumulating the G scores, it's now finding paths in all 4 directions (with the heuristic set to 0).

编辑:我已经解决了这个问题。我很快就会提交一个答案，但基本上，我的建立路径方法没有做它应该做的事情。它不是从封闭列表中添加所有内容，而是应该从封闭列表的末尾开始，从末尾通过父链，直到添加起始节点。

Answer 1

我确实在您的代码中发现了一些缺陷。这可能不是问题所在，但我们希望是这样。

当您检查该节点是否优于 openlist 中的其他节点时，您正在做一些奇怪的事情。该 if 语句甚至永远不会触发，因为某物永远不会小于其自身 + 正整数。此外，您甚至还没有设置节点的 G 成本。因此，您也无法检查它。这段代码可能会导致错误(除非 G 有一个标准值)。

但是我认为这段代码甚至没有达到。因为我怀疑这段代码总是触发:

    if (!openNodes.Contains(node))

你知道为什么吗？ 我可以看到您试图实现的想法，但开放集中没有该节点的另一个精确副本。首先，因为 openset 中的节点有它们的 G、H 和 F 成本集，而你正在检查的节点没有(所以它们不一样)。因此，如果它们中有相同的数据，我认为它仍然不会触发，因为这两个节点在您的计算机中都有另一个位置(不是 100% 确定这部分)。这也适用于检查节点是否在封闭集中。

您应该做的是检查 openlist 中是否有与您正在检查的节点位置相同的节点。如果该节点已经在列表中，那么您应该计算我们正在处理的节点的 G 成本。并检查 G-cost 是否小于当前列表中的 G-cost，并相应地更改 parent 等。

对于其余部分，您的代码看起来还不错，尽管在探路者中通常很难发现错误。希望这对您有所帮助，如果您有任何问题，请随时提出。