8 Directional Pathfinding (A*) - 不一致地寻找路径

Question

这里是新手，如果我没有很好地描述问题，请见谅。

我正在尝试创建一个 8 向寻路脚本。我已经学习了教程的大部分内容，但想对其进行更改以使其以一种我更容易理解的方式工作。

GetNeighbours 方法适用于 4 个方向，但不是对角方向。我正在使用字典来索引节点（单元格）中的 x 和 y 值。我知道这样效率不高，但对我来说更容易理解，也更灵活。

无论如何，路径只是有时有效。似乎每当我需要移动到顶行或左行时我都无法获得相邻的单元格。如果我在 tilemap 上打洞，它也会弄乱路径，但只有当我有时走到洞后面时，才会看到图像：不工作：

工作：

任何帮助都会很棒！

    public List<Node> GetNeighbours(Node node)
    {
        List<Node> neighbours = new List<Node>();
        int checkX = node.gridX;
        int checkY = node.gridY;

        //left
        if (nodes.ContainsKey(new Vector2Int(checkX-1, checkY))) 
        {
            neighbours.Add(nodes[new Vector2Int(checkX-1, checkY)]);
        }
        //right
        if (nodes.ContainsKey(new Vector2Int(checkX +1, checkY)))
        {
            neighbours.Add(nodes[new Vector2Int(checkX + 1, checkY)]);
        }
        //up
        if (nodes.ContainsKey(new Vector2Int(checkX, checkY + 1)))
        {
            neighbours.Add(nodes[new Vector2Int(checkX, checkY +1)]);
        }
        //down
        if (nodes.ContainsKey(new Vector2Int(checkX, checkY - 1)))
        {
            neighbours.Add(nodes[new Vector2Int(checkX, checkY - 1)]);
        }

        //top left
        if (nodes.ContainsKey(new Vector2Int(checkX - 1, checkY - 1)) && nodes.ContainsKey(new Vector2Int(checkX, checkY + 1)) && nodes.ContainsKey(new Vector2Int(checkX - 1, checkY - 1)));
        {
            neighbours.Add(nodes[new Vector2Int(checkX -1, checkY + 1)]);
        }
        //top right
        if(nodes.ContainsKey(new Vector2Int(checkX + 1, checkY)) && nodes.ContainsKey(new Vector2Int(checkX, checkY + 1)) && nodes.ContainsKey(new Vector2Int(checkX + 1, checkY + 1)))
        {
            neighbours.Add(nodes[new Vector2Int(checkX + 1, checkY + 1)]);
        }
        //bottom left
        if(nodes.ContainsKey(new Vector2Int(checkX-1, checkY)) && nodes.ContainsKey(new Vector2Int(checkX, checkY -1 )) && nodes.ContainsKey(new Vector2Int(checkX - 1, checkY - 1)))
        {
           neighbours.Add(nodes[new Vector2Int(checkX - 1, checkY - 1)]);
        }
        //bottomright
        if (nodes.ContainsKey(new Vector2Int(checkX +1, checkY)) && nodes.ContainsKey(new Vector2Int(checkX, checkY -1)) && nodes.ContainsKey(new Vector2Int(checkX + 1, checkY - 1)))
        {
            neighbours.Add(nodes[new Vector2Int(checkX + 1, checkY - 1)]);
        }
        
        // Debug.Log("number of neighbours added is: " + neighbours.Count);
        return neighbours;
    }

寻路Class

public class Pathfiding
{
    public static List<Vector2Int> FindPath(Grid grid, Vector2Int startPos, Vector2Int endPos)
    {
        List<Node> nodes_path = _ImpFindPath(grid, startPos, endPos);

        if (!grid.nodes.ContainsKey(startPos) || !grid.nodes.ContainsKey(endPos))
        {
            return null;
        }
        else
        {
            //get nodes and return a list of points
            List<Vector2Int> ret = new List<Vector2Int>();

            if (nodes_path != null)
            {
                foreach (Node n in nodes_path)
                {
                    ret.Add(new Vector2Int(n.gridX, n.gridY)); //load all nodes to check
                }
            }
            return ret;
        }
    }//end FindPath////

    private static List<Node> _ImpFindPath(Grid grid, Vector2Int startPos, Vector2Int endPos)
    {
        Node startNode;
        Node targetNode;

      
            startNode = grid.nodes[startPos];
            targetNode = grid.nodes[endPos];
        

        List<Node> openSet = new List<Node>();
        HashSet<Node> closedSet = new HashSet<Node>();

        openSet.Add(startNode);


        while (openSet.Count > 0)
        {
            Node currentNode = openSet[0];
            for (int i = 1; i < openSet.Count; i++)
            {
                //only check nodes with better f costs
                if (openSet[i].fCost < currentNode.fCost || openSet[i].fCost == currentNode.fCost && openSet[i].hCost < currentNode.hCost)
                {
                    currentNode = openSet[i];
                }
            }

            openSet.Remove(currentNode);
            closedSet.Add(currentNode);

            if (currentNode == targetNode)
            {
                return RetracePath(grid, startNode, targetNode);
            }

            foreach (Node neighbour in grid.GetNeighbours(currentNode))
            {
                if (neighbour.walkPenalty <= 0 || closedSet.Contains(neighbour))
                {
                    continue;
                }

                int newMovementCostToNeighbour = currentNode.gCost + GetDistance(currentNode, neighbour) * (int)(10.0f * neighbour.walkPenalty);

                if (newMovementCostToNeighbour < neighbour.gCost || !openSet.Contains(neighbour))
                {
                    neighbour.gCost = newMovementCostToNeighbour;
                    neighbour.hCost = GetDistance(neighbour, targetNode);
                    neighbour.parent = currentNode;

                    if (!openSet.Contains(neighbour))
                        openSet.Add(neighbour);
                }
            }
        }

        return null;
    }

Answer 1

//top left条件中出现三个错误：

if 语句末尾不应有分号。它使 if 语句无用，更糟糕的是它总是执行下面的块。因此始终存在指向左上角的对角线路径选项。
修复第一个错误后，需要将 if 条件的第一个谓词中的 checkY - 1 更改为 checkY。
并且需要将最后一个谓词中的checkY - 1改为checkY + 1。

//top left
if (nodes.ContainsKey(new Vector2Int(checkX - 1, checkY)) &&
    nodes.ContainsKey(new Vector2Int(checkX, checkY + 1)) &&
    nodes.ContainsKey(new Vector2Int(checkX - 1, checkY + 1)))
{
  neighbours.Add(nodes[new Vector2Int(checkX -1, checkY + 1)]);
}

使用TryGetValue会更好，避免再struct构造和查找：

//top left
if (nodes.ContainsKey(new Vector2Int(checkX - 1, checkY)) &&
    nodes.ContainsKey(new Vector2Int(checkX, checkY + 1)) &&
    nodes.TryGetValue(new Vector2Int(checkX - 1, checkY + 1), out var n))
{
  neighbours.Add(n);
}

我不确定这些是否都是您代码中的直接错误，请尝试一下。

还有一个与对角线移动相关的间接错误。我不明白为什么您需要检查 4 邻域路径以及对角线检查。如果 4 个邻居无论如何都必须存在，为什么要明确添加对角线移动？还是另一个错误，对于对角线移动，实际上应该省略非对角谓词？

8 Directional Pathfinding (A*) - 不一致地寻找路径

8 Directional Pathfinding (A*) - Inconsistently Finding Path

c#

a-star

path-finding

unity3d