Pim Schwippert Pim Schwippert - 2 months ago 12
C# Question

Objects in list get removed when applying Dijkstra's Algorithm implementation

I didn't know how to formulate the question title any better without getting too descriptive, I'm sorry in advance...

Anyhow, my problem is the following.

I have a List NodeList, and a secondary List named Unvisited.

I use the Method GetPath on the Unvisited list (it's an implementation of Dijkstra's Pathfidning Algorithm). But for some weird reason when I draw the texture stored in the Nodes in the NodeList some of the nodes (particularly, the nodes used to trace a path between) get removed.

I am looking for an explanation why the Nodes get removed from the NodeList even when I clearly set Unvisited equal NodeList...

EDIT: If there is any code that is missing to understand the problem, ask and I will edit!

Relevant Code:

public class Hotel
{
public List<Node> nodeList;

//constructor loadscontent and initialises list, ommitted here.

public void BuildHotel(ContentManager content)
{
for (int i = 0; i < 5; i++)
{
GuestRoom temp = new GuestRoom(100 + i, content, new Point(64 + (i * 64), 128), new Point(2, 1));
nodeList.Add(new Node(temp, new Point(64 + (i * 64), 128)));
}

// add edges between some nodes
for (int i = 0; i < 4; i++)
{
AddEdge(nodeList[i].Room.RoomId, nodeList[i + 1].Room.RoomId, 2);
}

guest = new Guest(content);
guest.Setpath(100, 104, nodeList);
}


}
class PathFinding
{
public List<Node> Unvisited;
public List<Node> Visited;
private Stack<Node> _temp = new Stack<Node>();

public Stack<Node> GetPath(int startroom, int finalroom, List<Node> nodeList)
{
Unvisited = nodeList;
Node startNode = Unvisited.DefaultIfEmpty(null).FirstOrDefault(x => x.Room.RoomId == startroom);
Node finalNode = Unvisited.DefaultIfEmpty(null).FirstOrDefault(x => x.Room.RoomId == finalroom);

if (startNode == null || finalNode == null)
{
Console.WriteLine("At least one of the nodes does not exist");
return null;
}

startNode.Distance = 0;

Node currentNode = startNode;

while (!IsVisited(currentNode, finalNode))
{
currentNode = Unvisited.Aggregate((l, r) => l.Distance < r.Distance ? l : r);
}

//reverse nodes in queue
Queue<Node> reversedqueue = MakePath(startNode, currentNode, finalNode);
for (int i = 0; i < MakePath(startNode, currentNode, finalNode).Count; i++)
{
_temp.Push(reversedqueue.Dequeue());
}
return _temp;
}
}

public class SimulationScreen : Screen
{
private Hotel hotel;
//.. other methods ommited.
public override void Activate(bool instancePreserved)
{
if (!instancePreserved)
{
if (_content == null)
_content = new ContentManager(ScreenManager.Game.Services, "Content");

ScreenManager.Game.ResetElapsedTime();
}
hotel = new Hotel(_content);
}
}


Visual Representation on the bug
Visual Representation on the bug
Without the pathfinder turned on
Without the pathfinder turned on

Answer

Your problem is right here:

Unvisited = nodeList;

That's the problem, I have looked through my entire solution and there is not a single place where the nodes get removed from the NodeList ._. any removal from the list is from the Unvisited list... :s

After that assignment, any removal from the Unvisited list removes from the nodeList. List is a reference type, so when you change its value with an assignment you're really changing which object it refers to. Unvisited and nodeList both refer to the same object after this. To avoid this, instantiate a new List using the old one rather than assigning both lists to the same reference:

Unvisited = new List<Node>(nodeList);