SortedSet 插入元素未排序

Question

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

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

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

    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++;
            }
        }

Answer 1

为了后代，我解决了这个问题 - 这是因为我对 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);
                    }

SortedSet 插入元素未排序

SortedSet inserting element out of sort

c#

sorting

icomparer

sortedset