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

Question

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

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

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

下面是我的 F、G 和 H 计算代码（在我的节点 class 中）：

// 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
}

我的寻路class代码如下：

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

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

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

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

    if (!openNodes.Contains(node))

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

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

对于其余部分，您的代码似乎还不错，尽管在探路者中通常很难发现错误。希望对您有所帮助，有任何问题请尽管提问。

Answer 2

首先，感谢 J4stM4rt 确定我进行了无用的比较（整数 A < 整数 A + 正整数），感谢 Eric Lippert 建议我应该将启发式设置为 0 以识别问题。

我的第一个问题是我没有为路径累积 g 分数。在我的 G 分数计算方法中，我需要 intG = 10（或 14）+ targetNode.G.

第二个问题是 J4stM4rt 提到的问题，我正在检查节点的 g 分数是否大于自身 + 另一个节点的 g 分数，这总是正确的。

最后一个问题是在建立路径方法中，我将封闭列表中每个节点的父节点添加到路径中，而不是从末尾开始，然后将每个后续父节点添加到路径中，直到到达起点。您可以在下面看到对我的代码的更正：

G-分数计算：

        // Calculates distance cost from start node to an adjacent node.
    public void CalculateG(Node nodeTarget)
    { // The g-score is cumulative so the target node's score is also added.
        // If the node is diagonal to the current node, its cost of movement is higher.
        if (TileX != nodeTarget.TileX && TileY != nodeTarget.TileY)
        {
            intG = nodeTarget.G + 14;
        }
        else intG = nodeTarget.G + 10;
    }

建立路径方法：

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

        // Start at the end of the path.
        Node nodeToAdd = closedNodes[closedNodes.Count - 1];
        while (!PathOfNodes.Contains(nodeStart))
        { // Add each node's parent until the start is reached.
            PathOfNodes.Add(nodeToAdd);
            nodeToAdd = nodeToAdd.Parent;
        }

        PathOfNodes.Remove(null); // Remove the final null node (as the final node had no parent).
    }

G分数比较（这实际上可能仍然是错误的，我尝试将其更改为（node.G（从当前节点的父节点移动到该节点的成本）< nodeCurrent.G（从节点移动的成本当前节点的父节点）+计算从当前节点移动到该节点的g）但是，这导致我的敌人再次卡住，所以我将其更改为以下内容并且看起来工作正常：

if (node.G < nodeCurrent.G)
                    {
                        // Make the node's parent the current node's parent and recalculate its values.
                        node.Parent = nodeCurrent;
                        node.CalculateG(nodeCurrent);
                        node.CalculateF();
                    }

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

C# XNA A* Pathfinding Enemies Stuck Opposite Walls

c#

algorithm

xna

nodes

path-finding