Dictionary Key as object returning KeyNotFoundError-CodePudding

I am trying to implement Dijkstras path finding algorithm in Unity. I have a dictionary distances containing all the possible Nodes that can be walked on which is obtained from GridData.WalkableNodes. When trying to obtain the distance of the found neighbours for a given Node, I am not able to obtain the distance value from the distances dictionary for some reason. It gives me a KeyNotFoundError. Am I doing something wrong but using the Node object as the key? In my testing, you can use an Object as the key to retrieve a value from a dictionary so I do not think this is the issue.

Script files can be seen on pastebin GridData.cs Dijkstra.cs

Dictionary<Node, int> distances = GridData.WalkableCells.ToDictionary(x => x, x => int.MaxValue);

foreach (Node neighbour in neighbours)
{

    if (!visited.Contains(neighbour.Position))
    {
        int dist = distances[currentCell]   1;

        if (dist < distances[neighbour]) // Key not found happens here!
        {
            distances[neighbour] = dist;

            priorityQueue.Enqueue(neighbour, dist);
            visited.Add(neighbour.Position);

            neighbour.parentNode = currentCell;
            parents.Add(neighbour);
        }
    }
}

If I use Vector3 instead of a Node as the key, it seems to work but I do not understand why it does not work when using Node.

Dictionary<Vector3, int> distances = GridData.WalkableCells.ToDictionary(x => x.Position, x => int.MaxValue);

foreach (Node neighbour in neighbours)
{

    if (!visited.Contains(neighbour.Position))
    {
        int dist = distances[currentNode.Position]   1;

        if (dist < distances[neighbour.Position]) 
        {
            distances[neighbour.Position] = dist;

            priorityQueue.Enqueue(neighbour, dist);
            visited.Add(neighbour.Position);

            neighbour.parentNode = currentCell;
            parents.Add(neighbour);
        }
    }
}

Node class

public class Node
{
    public Vector3 Position { get; set; }
    public CellType CellType { get; set; }
    public int Cost { get; set; }
    public Node parentNode {get; set;}

public Node(Vector3 position, CellType cellType, int cost)
{
    Position = position;
    CellType = cellType;
    Cost = cost;
}
}

CodePudding user response：

You are using new Node to fill your hashmap and lists.

Therefore these newly crated Nodes are o course not the exact same instances as the ones added into your dictionary!

It works for Vector3 because it implements IEquatable<Vector3> and also GetHashCode.

If you don't explicitly override Equals then by default reference equality is used (see object.Equals)

You should either simply use the positions as keys since as you already figured out it already implements it. Or just make sure to implement it as well and use the position as hash code provider:

public class Node : IEquatable<Node>
{
    public Vector3 Position { get; set; }
    public CellType CellType { get; set; }
    public int Cost { get; set; }
    public Node parentNode {get; set;}

    public Node(Vector3 position, CellType cellType, int cost)
    {
        Position = position;
        CellType = cellType;
        Cost = cost;
    }

    public override int GetHashCode()
    {
        return Position.GetHashCode();
    }

    public bool Equals(Node other)
    {
        if (ReferenceEquals(null, other))
        {
            return false;
        }

        if (ReferenceEquals(this, other))
        {
            return true;
        }

        return GetHashCode() == other.GetHashCode();
    }

    public override bool Equals(object obj)
    {
        if (ReferenceEquals(null, obj))
        {
            return false;
        }

        if (ReferenceEquals(this, obj))
        {
            return true;
        }

        if (obj.GetType() != this.GetType())
        {
            return false;
        }

        return Equals((Node)obj);
    }
}

if you want to take the other properties like Celltype and Cost etc also into account and can have multiple nodes on the same position you can simply extend it doing e.g.

public override int GetHashCode()
{
    return HashCode.Combine(Position, Cost, CellType);
}

according to your needs.