c# - 跳点搜索比 XNA 中的常规 A* 慢的 A*？

Question

编辑:

为了帮助看这个问题的人成为回答者，我会注意到这个问题似乎是在跳转的对角线情况下。当递归运行时，该方法中的什么会导致速度变慢？

编辑结束。

在我开发的 XNA 游戏中，我使用 A* + JPS 算法在每一帧的统一方形网格上导航。我了解了 JPS here和 here .但是，当我运行游戏时，帧率下降。帧率太低，以至于无法玩游戏。删除对跳跃点搜索“跳跃”的调用，并改为使用常规 A*，解决了足够大的正方形尺寸的问题。根据这篇文章，JPS 应该比常规 A* 更有效。速度变慢的原因似乎是在“对角线情况”中对 Jump 的两次调用(Jump 方法的第 15-29 行)。

很明显，我的实现一定有问题/效率低下。但它是什么？

代码:

Jump方法是JPS递归跳转功能的实现。

    public Vector2? Jump(Vector2 current, Vector2 direction, Vector2 start, Vector2 end)
    {
        // Position of new node we are going to consider:
        Vector2 next = current + direction * SquareSize;

        // If it's blocked we can't jump here
        if (IsBlocked(next))
            return null;

        // If the node is the goal return it
        if (next.X == end.X && next.Y == end.Y) 
            return next;

        // Diagonal Case   
        if (direction.X != 0 && direction.Y != 0) 
        {
            Vector2 horizontalBehind = current - new Vector2(direction.X * SquareSize, 0);
            Vector2 verticalBehind = current - new Vector2(0, direction.Y * SquareSize);
            if (IsBlocked(horizontalBehind) || IsBlocked(verticalBehind))
            {
                return current;
            }
            // Check in horizontal and vertical directions for forced neighbors
            // This is a special case for diagonal direction
            if (Jump(next, new Vector2(direction.X, 0), start, end) != null || Jump(next, new Vector2(0, direction.Y), start, end) != null)
            {
                return current;
            }
        }
        else
        {
            // Horizontal case
            if (direction.X != 0)
            {
                Vector2 topBehind = current - new Vector2(direction.X * SquareSize, SquareSize);
                Vector2 above = current - new Vector2(0, SquareSize);
                Vector2 bottomBehind = current + new Vector2(-direction.X * SquareSize, SquareSize);
                Vector2 below = current + new Vector2(0, SquareSize);
                if (IsBlocked(topBehind) || IsBlocked(above) || IsBlocked(bottomBehind) || IsBlocked(below))
                {
                    return current;
                }
            }
            else
            {
                Vector2 leftBehind = current - new Vector2(SquareSize, direction.Y * SquareSize);
                Vector2 left = current - new Vector2(SquareSize, 0);
                Vector2 rightBehind = current + new Vector2(-SquareSize, direction.Y * SquareSize);
                Vector2 right = current - new Vector2(SquareSize, 0);
                if (IsBlocked(leftBehind) || IsBlocked(left) || IsBlocked(rightBehind) || IsBlocked(right))
                {
                    return current;
                }
            }
        }
        // If forced neighbor was not found try next jump point
        return Jump(next, direction, start, end);
     }

    #endregion
}

Navigate是实现A*的方法，从'start'参数到'end'参数。

PriorityQueue 是基于this article 的通用实现.它的入队和出队方法具有 O(log2(n)) 复杂度。

    public Vector2? Navigate(Vector2 start, Vector2 end)
    {
        PriorityQueue<float, Vector2> openSet = new PriorityQueue<float, Vector2>();
        List<Vector2> closedSet = new List<Vector2>(10);
        Dictionary<Vector2, Vector2> cameFrom = new Dictionary<Vector2, Vector2>(10);
        Dictionary<Vector2, float> gScores = new Dictionary<Vector2, float>(10);
        gScores[start] = 0;
        openSet.Enqueue(H(start, end), start);
        while (openSet.Count != 0)
        {
            Vector2 current = openSet.Dequeue().Value;
            if (WorldMap.InSquare(current) == WorldMap.InSquare(end))
                return ReconstructPath(cameFrom, current, start);
            List<Vector2> neighbours = WorldMap.GetNeighbours(current, start, end);
            closedSet.Add(current);
            foreach(Vector2 neighbour in neighbours)
            {
                if (closedSet.Contains(neighbour))
                    continue;
                float tenativeGScore = gScores[current] + Vector2.Distance(current, neighbour);
                if(!gScores.ContainsKey(neighbour) || gScores[neighbour] > tenativeGScore)//Discover a new node || Find a better path to a node
                {
                    cameFrom[neighbour] = current;
                    gScores[neighbour] = tenativeGScore;
                    float fScore = tenativeGScore + H(neighbour, end);//Calculate F.
                    openSet.Enqueue(fScore, neighbour);
                }
            }
        }
        return null;
    }

GetNeighbours 是一种返回节点“向量”的邻居的方法。A* 版本:

    public List<Vector2> GetNeighbours(Vector2 point, Vector2 start, Vector2 end)
    {
        Vector2[] directions = new Vector2[8];
        List<Vector2> neighbours = new List<Vector2>(8);
        directions[0] = Vector2.UnitX;//right
        directions[1] = -Vector2.UnitX;//left
        directions[2] = Vector2.UnitY;//down
        directions[3] = -Vector2.UnitY;//up
        directions[4] = Vector2.UnitX + Vector2.UnitY;//down right
        directions[5] = -Vector2.UnitX + Vector2.UnitY;//down left
        directions[6] = Vector2.UnitX - Vector2.UnitY;//up right
        directions[7] = -Vector2.UnitX - Vector2.UnitY;//up left
        foreach(Vector2 direction in directions)
        {
            Vector2 neighbour = point + direction * SquareSize;
            if (!IsBlocked(neighbour))
                neighbours.Add(neighbour);
        }
        return neighbours;
    }

跳点搜索版本:

    public List<Vector2> GetNeighbours(Vector2 point, Vector2 start, Vector2 end)
    {
        Vector2[] directions = new Vector2[8];
        List<Vector2> neighbours = new List<Vector2>(8);
        directions[0] = Vector2.UnitX;//right
        directions[1] = -Vector2.UnitX;//left
        directions[2] = Vector2.UnitY;//down
        directions[3] = -Vector2.UnitY;//up
        directions[4] = Vector2.UnitX + Vector2.UnitY;//down right
        directions[5] = -Vector2.UnitX + Vector2.UnitY;//down left
        directions[6] = Vector2.UnitX - Vector2.UnitY;//up right
        directions[7] = -Vector2.UnitX - Vector2.UnitY;//up left
        foreach(Vector2 direction in directions)
        {
        //The only difference between this GetNeighbours and the other one 
        //is that this one calls Jump here.
            Vector2? jp = Jump(point + direction * SquareSize, direction, start, end);
            if (jp != null)
                neighbours.Add((Vector2)jp);
        }
        return neighbours;
    }

InSqaure 是一种返回表示 Vector2 所在正方形的 Vector2 的方法。它的复杂度为 O(1)。

IsBlocked 是一种方法，用于检查 Vector2 是否在 map 内部，以及它是否位于被阻挡的正方形中(“被阻挡”表示正方形中有障碍物)。它具有 O(log2(n)) 复杂度。

附加信息:

• 我目前只在目标和起点之间没有障碍物的情况下检查这个。这意味着 JPS 算法仅扩展 1 个正方形。同时，常规 A* 扩展 8 以找到从 (100, 100) 到 (0, 0) 的路径，但在找到 (100, 100) 到 (-800, -580) 之间的距离时扩展 2325 个方 block 。在后一种情况下，帧率明显下降，导致游戏几乎无法玩。
• 帧速率已解锁。
• 在小于大约 1200 个方格的网格中没有明显的卡顿现象，游戏的帧速率略有下降，最高可达 1600 左右。

如果需要更多信息，我会很乐意提供，

提前致谢!

Answer 1

在我的游戏中，我使用 A* 进行立体寻路。这需要更多的处理时间，但实现的构建方式几乎不可见。

        public void FixedUpdate()
    {
        if (calculating && openSet.Count > 0 && calculatingStep < 240)
            PathfindingStep(navDestination, navAccurancyFactor);
        else calculating = false;//...
    }

FixedUpdate 每秒调用 50 次。

       private void PathfindingBegin(Vector3 destination)
    {
        navAccurancyFactor = (1 + (Vector3.Distance(walkerTransform.position, destination) / (accurancy * 5)));
        navDestination = destination;
        calculatingStep = 0;
        calculating = true;
        closedSet = new List<PathNode>();
        openSet = new List<PathNode>();
        Vector3 startPos;
        if (path.Count > 0)
            startPos = path.Last();
        else
            startPos = walkerTransform.position;
        // Шаг 2.
        PathNode startNode = new PathNode()
        {
            Position = startPos,
            CameFrom = null,
            PathLengthFromStart = 0,
            HeuristicEstimatePathLength = GetHeuristicPathLength(walkerTransform.position, destination)
        };
        openSet.Add(startNode);
    }

调用 PathfindingBegin 开始，接下来每帧调用 PathfindingStep onse 来构建路径。

        private void PathfindingStep(Vector3 destination, float accuracyFactor)
    {
        calculatingStep++;
        PathNode currentNode;
        // Шаг 3.
        currentNode = openSet.OrderBy(node => node.EstimateFullPathLength).First();
        // Шаг 4.
        if (Vector3.Distance(currentNode.Position, destination) <= accurancy * accuracyFactor)
        {
            PathfindingComplete(CollapsePath(GetPathForNode(currentNode)).ToArray());
            return;
        }
        // Шаг 5.
        openSet.Remove(currentNode);
        closedSet.Add(currentNode);
        // Шаг 6.
        List<PathNode> neighbours = GetNeighbours(currentNode, destination, accuracyFactor);
        foreach (PathNode neighbourNode in neighbours)
        {
            // Шаг 7.
            if (closedSet.Count(node => node.Position == neighbourNode.Position) > 0)
                continue;
            PathNode openNode = openSet.Find(node => node.Position == neighbourNode.Position);
            // Шаг 8.
            if (openNode == null)
                openSet.Add(neighbourNode);
            else if (openNode.PathLengthFromStart > neighbourNode.PathLengthFromStart)
            {
                // Шаг 9.
                openNode.CameFrom = currentNode;
                openNode.PathLengthFromStart = neighbourNode.PathLengthFromStart;
            }
        }
    }

最后调用 PathfindingComplete 应用路径。或者如果目的地不可用。

        private void PathfindingComplete(Vector3[] pathPoints)
    {
        if (pathPoints != null)
        {
            status = DriverStatus.Navigating;
            foreach (Vector3 x in pathPoints)
            {
                //Debug.Log(x);
                path.Enqueue(x);
            }
            BuildPathArrows();
        }
        calculating = false;
    }

附言我们可以在 https://github.com/DaniilChikish/SpaceComander 找到所有项目