c# - SortedSet 插入元素乱序

问题描述

我编写了一个 A* 的实现，它依赖于在 sortedSet 中按节点的 F 分数对节点进行排序。

在某些情况下，排序似乎在“Min”值处插入一个 Node 对象，而其比较的“F”值实际上是第二低而不是 Min，如所述。我完全困惑为什么会这样。我相信它会导致导致 nodeTree.Remove 和 nodeTree.RemoveWhere 失败的连锁反应，但这可能是问题的实际原因，老实说我不确定 - 虽然我不知道如何解决它它是。

这是使用的比较器。我认为我不完全确定如何实现这些相对明显，但我认为这应该按我的意图工作。

    public class FValueFirst : Comparer<PathfindingAgent.Node>
    {
        public override int Compare(PathfindingAgent.Node x, PathfindingAgent.Node y)
        {
            int result = x.F.CompareTo(y.F);

            if (result == 0)
            {
                result = y.G.CompareTo(x.G);
            }
            
            if(x == y)
            {
                result = 0;
            }
            return result;
        }
    }

这是 Node 对象，供参考。

        public class Node
        {
            public Cell cell;
            public float G;
            public float H;
            public bool Opened;
            public bool Closed;
            public Node Previous;
            public float F { get => G + H; }
        }

这就是它发生的函数。结果是确定的，谢天谢地。根据当前的 destID 和网格障碍物的特定布局，它总是会在同一次迭代中失序。

        public void PathTo(Vector3Int destID)
        {
            SortedSet<Node> nodeTree = new SortedSet<Node>(new FValueFirst());
            Vector3Int radius = PathfindingGrid.Instance.GridRadius;
            NodeGrid = new Node[radius.x * 2 + 1, radius.y * 2 + 1, radius.z * 2 + 1];
            Node startNode = new Node()
            {
                cell = PathfindingGrid.Cells[CurrentID.x, CurrentID.y, CurrentID.z],
                G = 0,
                H = 0
            };
            Node endNode = new Node()
            {
                cell = PathfindingGrid.Cells[destID.x, destID.y, destID.z],
                G = 0,
                H = 0
            };
            Vector3Int sID = startNode.cell.ID;
            Vector3Int eID = endNode.cell.ID;
            NodeGrid[sID.x, sID.y, sID.z] = startNode;
            NodeGrid[eID.x, eID.y, eID.z] = endNode;

            if (endNode.cell.IsOccupied) return;

            nodeTree.Add(startNode);
            int iterations = 0;
            while(true)
            {
                Node node;
                node = nodeTree.Min;
                node.Closed = true;
                nodeTree.RemoveWhere(n => n == node);
                if(node == nodeTree.Min)
                {
                    throw new Exception($"Incorrect node was removed from the tree");
                }

                if (node == endNode)
                {
                    List<Node> chain = BacktraceChain(node);
                    Debug.Log($"Path found from {CurrentID} to {destID} with score {endNode.G} traversing {chain.Count} cells in {iterations} iterations");
                    DrawLine(chain, Color.white);
                    break;
                }
                List<Node> neighbours = GetNeighbours(node);
                foreach(Node neighbour in neighbours)
                {
                    if (neighbour == startNode || neighbour.Closed) continue;

                    float newg = Vector3Int.Distance(node.cell.ID, neighbour.cell.ID) + node.G;

                    if (!neighbour.Opened || newg < neighbour.G)
                    {
                        neighbour.G = newg;
                        neighbour.H = ManhattanHeuristic(neighbour, endNode);
                        neighbour.Previous = node;

                        if(!neighbour.Opened)
                        {
                            nodeTree.Add(neighbour);
                            neighbour.Opened = true;
                        }
                        else
                        {
                            nodeTree.RemoveWhere(n => n == neighbour);
                            nodeTree.Add(neighbour);
                        }
                    }
                }
                iterations++;
            }
        }

标签： c#sortingsortedseticomparer

对于后代，我解决了这个问题 - 这是由于我对 SortedList 类型缺乏经验。

在函数末尾附近发现的这段代码是罪魁祸首

                    if (!neighbour.Opened || newg < neighbour.G)
                    {
                        neighbour.G = newg;
                        neighbour.H = ManhattanHeuristic(neighbour, endNode);
                        neighbour.Previous = node;

                        if(!neighbour.Opened)
                        {
                            nodeTree.Add(neighbour);
                            neighbour.Opened = true;
                        }
                        else
                        {
                            nodeTree.RemoveWhere(n => n == neighbour);
                            nodeTree.Add(neighbour);
                        }

具体来说，树中的项目不能将其比较值修改到它不再在该索引中正确比较的程度。该项目必须首先从列表中删除、修改和重新添加。

我事后的猜测是，虽然在修改后立即删除，但由于修改，树无法充分遍历以访问目标项目。

因此，我的解决方案是简单地重新排列块，以便分别在修改的任一侧进行删除和添加，如下所示：

                    if (!neighbour.Opened || newg < neighbour.G)
                    {
                        if (neighbour.Opened)
                        {
                            if (!nodeTree.Remove(neighbour)) throw new Exception($"{neighbour} was not removed from tree"); 
                        }
                        else
                        {
                            neighbour.Opened = true;
                        }
                        neighbour.G = newg;
                        neighbour.H = ManhattanHeuristic(neighbour, endNode);
                        neighbour.Previous = node;
                        nodeTree.Add(neighbour);
                    }

c# - SortedSet 插入元素乱序

问题描述

解决方案

推荐阅读