koobas.hobune.stream
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))
On reflection the word Set is the key here. Its supposed be a set that can only contain one value of each type - that (weirdly) means the first solution with the while loop is the best bet (as it most closely simulates a set) or you could switch the two ArrayLists to being .NET HashSet.
using System.Collections.Generic;
...
var openSet = new HashSet<object>();
var closedSet = new HashSet<object>();
The you don't have to change any of the rest of the code.
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;
}
Can you convert this to a comment (under the more menu) as it isn't an answer!
Firstly you won't see the debug messages in an infinite loop - fun huh?
Ok hang on I can see another problem. The current node is just endlessly considered in that foreach (Node n in openset) loop
Try this:
current = openSet[0];
foreach(Node n in openSet)
{
if(n.f_score < current.f_score)
{
current = n;
}
}
Of if you want to use a bit of Linq
using System.Linq;
using System.Collections.Generic;
current = openSet.OrderBy(n=>n.f_score).First();
Or even better
current = openSet.Aggregate(openSet[0], (v,n)=>n.f_score < v.f_score ? n : v);
