SortedSet.Min is not contained in the SortedSet

Question

I'm currently attempting to use a script for pathfinding in Unity and C#. I'm using a SortedSet to get the closest tile to a destination tile on the game's map. In some scenarios, the SortedSet returns a value that is not a member of the set as the minimum value! It's difficult to post a minimum reproducible example for such a relatively specific problem, so I'll post the script used below:

using System.Collections.Generic;
using UnityEngine;

public class Tile : MonoBehaviour
{
//--------------------PATHFINDING-------------------------

//Neighboring tiles stored in a list. Assigned by tile assignment script
public List<Tile> neighbors;

//The tile which leads to this tile when pathfinding. Found during pathfinding.
public Tile previousPathTile { get; private set; }

//The cost of moving across this tile, based on terrain type
public float traversalCost { get; set; }

//The cost of moving through this tile, including the previous tiles already
//on the path. Found during pathfinding.
public float previousTraversalCost { get; private set; }

//The estimated cost from this tile to the end tile. Found during pathfinding.
public float heuristicCost { get; private set; }

//Finds path from current tile to the destination tile
public List<Tile> pathFind( Tile endTile)
{
    //The path which is returned by this function
    List<Tile> path = new List<Tile>();

    //The tiles which have been encountered but not explored
    SortedSet<Tile> unexploredTiles = new SortedSet<Tile>(new TileSortOrder());

    //The tile which is currently being explored
    Tile currentTile;

    //Make sure that we're not adding infinity to our traversal cost from the start!
    this.previousTraversalCost = 0.0f;

    //How much the heuristic cost should guide the search algorithm. Should be set so that the maximum
    //multiplier will not force a terrain switch.
    float steeringPower = 12.0f;

    //Add the starting tile to the unexploredTiles set of tiles
    unexploredTiles.Add(this);

    //Used to break out of infinite loop on SortedSet error!
    int tmp = 0;

    //Run the pathfinding algorithm
    while (unexploredTiles.Count > 0 && tmp < 250)
    {
        ++tmp;

        //---------------- ERROR OCCURS HERE ---------------------------
        UnityEngine.Debug.Log(unexploredTiles.Min);
        currentTile = unexploredTiles.Min;
        if(!unexploredTiles.Contains(unexploredTiles.Min))
        { UnityEngine.Debug.Log("ERROR: unexploredTiles does not contain its own min! " + currentTile + " " + unexploredTiles.Min); }

        //Attempting to remove here results in an error code return by the function.
        unexploredTiles.Remove(currentTile);
        //----------------------------------------------------------------

        //If we are on the final tile
        if(GameObject.ReferenceEquals(currentTile, endTile))
        {
            //Rebuild the path from end to start, then reverse.
            while (currentTile != null)
            {
                path.Add(currentTile);
                currentTile = currentTile.previousPathTile;
            }
            path.Reverse();

            return path;
        }

        int neighborsSize = currentTile.neighbors.Count;
        for (int i = 0; i < neighborsSize; ++i)
        {
            //The tile which we are checking the pathfinding cost for
            Tile nextTile = currentTile.neighbors[i];

            //Get the distance from the next tile to the destination tile only if it hasn't been obtained already.
            if(nextTile.heuristicCost < 0.0f)
            {
                nextTile.heuristicCost = (endTile.gameObject.transform.position - nextTile.gameObject.transform.position).magnitude * steeringPower;
            }

            //Get the actual traversal cost to the next tile.
            float nextTilePreviousTraversalCostFromThisTile = currentTile.previousTraversalCost + currentTile.traversalCost;

            //If the cost from this tile to the next tile is less than the previous lowest cost
            if ( nextTilePreviousTraversalCostFromThisTile < nextTile.previousTraversalCost )
            {
                nextTile.previousPathTile = currentTile;
                nextTile.previousTraversalCost = nextTilePreviousTraversalCostFromThisTile;
                unexploredTiles.Add(nextTile);
            }
        }
    }
    return path;
}

}

Here's the IComparer used to compare two Tiles:

public class TileSortOrder : IComparer<Tile>
{
    public int Compare(Tile firstTile, Tile secondTile)
    {
        UnityEngine.Debug.Log("Comparing: " + firstTile.gameObject.name + " and: " + secondTile.gameObject.name + (GameObject.ReferenceEquals(firstTile, secondTile) ? "They were equal." : "They were not equal.") );
        if( GameObject.ReferenceEquals(firstTile, secondTile) )
        {
            return 0;
        }
        else
        {
            float tentativeTraversalCostFirst = firstTile.previousTraversalCost + firstTile.heuristicCost;
            float tentativeTraversalCostSecond = secondTile.previousTraversalCost + secondTile.heuristicCost;
            return tentativeTraversalCostFirst < tentativeTraversalCostSecond ? -1 : 1;
        }
    }
}

Here is some sample output produced when the SortedSet.Contains() check fails:

ERROR: unexploredTiles does not contain its own min! tile1247 (Tile) tile1247 (Tile)
UnityEngine.Debug:Log(Object)
Tile:pathFind(Tile) (at Assets/Scripts/Tiles/Tile.cs:211)
InputRouting:runPathPlan() (at Assets/Scripts/InputRouting.cs:312)
InputRouting:Update() (at Assets/Scripts/InputRouting.cs:291)

Any help you may be able to provide is appreciated. I'm very confused as to how the SortedSet.Min value provided could not be a member of the set, and I'm not sure if it's down to me making a silly mistake. Thanks! :-)

Answer 1

From sortedSet documentation

Changing the sort values of existing items is not supported and may lead to unexpected behavior.

The comparer uses previousTraversalCost, and this is updated in the code. Instead of updating the traversalCost you should remove the node and insert a new one.