C# script makes unity freeze on ArrayList.Add()

Hi all,

I’m trying to implement an A* pathfinding algorithm. Unity freezes and doesn’t even show debug messages before the line that seems to make it crash.

Any help would be greatly appreciated!

Thanks,

Maarten

public ArrayList FindRoute()
{
	Debug.Log("This message doesn't even show when unity crashes");
	
	if (start == null || end == null) return null;
	
	Component[] nodes;
	nodes = GetComponentsInChildren<Node>();
	foreach(Node n in nodes)
	{
		n.f_score = 0;
		n.g_score = 0;
		n.cameFrom = null;
	}

	Node current = start;
	ArrayList closedSet = new ArrayList();
	ArrayList openSet = new ArrayList();
	openSet.Add(current);
	
	while (openSet.Count != 0)
	{
		foreach (Node n in openSet)	if (n.f_score < current.f_score) current = n;
		
		if (current == end) return ReconstructPath();
						
		openSet.Remove(current);
		closedSet.Add(current);
		
		foreach(GameObject g in current.neighbours)
		{
			Node n = g.GetComponent<Node>();
			if (closedSet.Contains(n)) continue;
				
			float tentative_g_score = current.g_score + Vector3.Distance(current.transform.position, n.transform.position);
			if (openSet.Contains(n) == false || tentative_g_score < n.g_score)
			{

				// IF I COMMENT THIS LINE AWAY IT STOPS CRASHING
				openSet.Add(n);

				n.cameFrom = current;
				n.g_score = tentative_g_score;
				n.f_score = n.g_score + Vector3.Distance(n.transform.position, end.transform.position);
			}
		}
	}
	
	return null;
}

It’s not crashing, it’s in an infiinite loop because the open set never completely empties.

From what I know of A* I’m a bit worried about why you would doubly include a node in the open set. (which happens here if the tentative_g_score < consider nodes g_score.

I’m figuring that isn’t a good plan and either as soon as a node has been seen then all of its instances should be removed from the openset or you shouldn’t add them in the first place.

You could achieve that by replacing:

 openSet.Remove(current);

With

 while(openSet.Contains(current))
     openSet.Remove(current);

Of you could drop that tentative g score test by changing

if (openSet.Contains(n) == false || tentative_g_score < n.g_score)

to

 if (!openSet.Contains(n))

I thought of one further point on this kind of problem - you are better of running this code through the MonoDevelop debugger as logging doesn’t show up until Unity get’s the code back into its main loop - infinite loops are therefore hard to debug with logging code which comes as a surprise to a lot of developers (it tripped me up when I first saw it anyway!)

A refresher for those wishing to debug their code using MonoDevelop (on a Mac at least):

  • In MonoDevelop got to menu Run > Attach To Process
  • Choose Unity Editor
  • Set your breakpoints by clicking in the left hand Gutter in MonoDevelop
  • Switch to Unity and run your game
  • When it breaks (on Mac, default key mappings) you can use Command Shift O to step over, Command Shift I to step in and Command Enter to resume.
  • You can quick watch a variable by hovering over it
  • There are full watch lists, and a call stack available - see the MonoDevelop menus

Thanks! I thought that should be it, but the solution didn’t help though. Also I get to see none of the debug messages (could be that they’re only posted after completion of the script?)

My new code (none of the debug msg’s are logged and unity still freezes.

	public ArrayList FindRoute()
{
	Debug.Log("finding route");
	
	if (start == null || end == null) return null;
	
	Component[] nodes;
	nodes = GetComponentsInChildren<Node>();
	foreach(Node n in nodes)
	{
		n.f_score = 0;
		n.g_score = 0;
		n.cameFrom = null;
	}

	Node current = start;
	ArrayList closedSet = new ArrayList();
	ArrayList openSet = new ArrayList();
	openSet.Add(current);
	
	int numberOpen = openSet.Count;
	while (numberOpen > 0)
	{
		foreach (Node n in openSet)	if (n.f_score < current.f_score) current = n;
		
		if (current == end) return ReconstructPath();
						
		while(openSet.Contains(current)) openSet.Remove(current);
		closedSet.Add(current);
		
		foreach(GameObject g in current.neighbours)
		{
			Node n = g.GetComponent<Node>();
			if (closedSet.Contains(n)) continue;
				
			float tentative_g_score = current.g_score + Vector3.Distance(current.transform.position, n.transform.position);
			if (openSet.Contains(n) == false || tentative_g_score < n.g_score)
			{
				n.cameFrom = current;
				n.g_score = tentative_g_score;
				n.f_score = n.g_score + Vector3.Distance(n.transform.position, end.transform.position);
				openSet.Add(n);
			}
		}
		numberOpen = openSet.Count;
		Debug.Log("in open set: " + numberOpen);
	}
	
	return null;
}