- Home /
Unity doesn't like generic stacks built through recursion??
I have a bit of code (written in c#) that traverses a 6x6x6 array recursively and puts each item into a stack(using generic stacks of GameObjects) depending on the direction it was encountered from (i.e. if the x-value is increased it is put into the xStack)
The problem is that while it does run, It takes nearly a half an hour inside unity, and I have no idea why. Does unity have a problem with recursion in this fashion?
EDIT
It seems that the problem does not come from the recursion, but rather the hang is occurring when I try to output the contents of the stack to Debug.Log() using this bit of code.
while (xStack.Count > 0)
{
Debug.Log(xStack.Pop());
I've found the problem code, but i still don't know why it is acting this way..
original function
private GameObject match(int x = 0, int y = 0, int z = 0) {
if (x + 1 < 6)
{
xStack.Push(match(x + 1, y, z));
}
if (y + 1 < 6)
{
yStack.Push(match(x, y + 1, z));
}
if (z + 1 < 6)
{
zStack.Push(match(x, y, z + 1));
}
return gemArray[x, y, z];
}
Answer by Mortennobel · Apr 18, 2011 at 07:37 PM
Well first of all, recursion is slow - it should be rewritten to loops (three nested loops in your case). The reason is that each method call needs to be put on the stack - this way a lot memory is waisted. (In some cases, such as tail-recursion the compiler/runtime may be able to make a loop out of it)
But more inportant: Your code is buggy - you access each element more than once. Let's say we used your approach to solve a simple 2x2 array. Your code would iterate the array the following way:
00 0
00 1
0 11
0 01
1 // <-- Node already visited 01
= current node 0 = unvisited node (in the current stack) 1 = visited node
I understand that each element is accessed more than once, this has no test-cases implemented yet, it was simply a test to see if it would be feasible; the final implementation of my algorithm would keep that from happening. Also, this is for 3-d matching game (where the array represents a cube of matchable objects) and if 3 or more are in a row, the are considered a match...to make this work iteratively I would either have to disallow matching around corners or hard-code a series of three separate loops....I know what you mean by three nested loops, I use that for spawning the objects.
But your stack ends up with a size of 1389025 elements!!!!
yeah, actually I was getting 811733....which was likely my issue, I've gotten it down to 21881 by restricting the checks to the faces, but the numbers are still much higher than I need...I'm thinking of creating a struct with the gameObject and three bool variables to show when traversal has already been completed on an index...I'm thinking that should cut down the number to the 456 I'm looking for.
I think I deserve a 'Correct answer' then ;-) At least my guess was quite close :-)