C# StackOverflowException

Hi want to create a scene via script. I write numbers in an two dimensional array. and in the method Start I read out the array and create cubes.
I generate a maze with this recursiv algorithm and i got an
StackOverflowException: The requested operation caused a stack overflow.
Maze.rek (Int32 x, Int32 y) (at Assets/Maze1.cs:64)

Code (csharp):

1.  
2. public void rek(int x,int y){
3.            
4.         field[y,x]=3; // mark cell as visited  
5.         int[,] koord = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // these are the directions left right up down
6.         int[] ran = {0,1,2,3};     
7.         //random
8.         // shuffle ran array
9.         //
10.        
11.         for(int i=0;i<4;i++){ // do all directions lef,t right, down and up in a random order
12.  
13.             int x2 = koord[ran[i],0];
14.             int y2 = koord[ran[i],1];
15.  
16.             if(field[y+y2*2,x+x2*2]!=3){ // if the next cell next the cell not marked ...
17.                 field[y+y2,x+x2]=3; // ...clear the wall between this two cells.
18.                 rek(y+y2*2,x+x2*2); // idea jump to the next next cell. !! here is the stackoverflow but dont know why?!
19.             }
20.         }
21.         return;
22. }
23.  
24.  
25.  

Where is my issue?


this should be the result i tested this in a C++ program.

 

You call rek inside your for loop with parameters who seem to increase the for bounds for the next rek iteration, this will proceed until your stack is overflowing.

 

It keeps on generating forever, you need to limit how many times it runs rek

 

You got the arguments swapped on the recursive call to "rek", which gives it the potential to get into an infinite loop. Fixing that may remove the overflow.

Otherwise, it is possible that your stack in C# simply isn't deep enough to cope with this algorithm, in which case you need to choose a non- or less-recursive algorithm.

 

ok thx =) now i have more opinions.
write in rek a conditon to abort.
or write the code iterativ.
or size up the stack from c# is it possible, read something about 1MB ?
thats why iam confiued in c++ no problem with this rek methode

---
ok i solved it with an non recursiv algorithm and it works fine thx.
result.

 

hmm this iterativ algorithm above is fail, its to randomly. it creates mazes with no solution to pass it.
i wrote a new one.

----

Code (csharp):

1.  
2.     public void iter(){
3.    
4.         list.Add(new Node(2,2,0)); //list  in construktor. List<Node> list;
5.        
6.         do{
7.             Node n=list[0]; //Node is class with attributes x,y,p; p is direction from where the path goes
8.             list.RemoveAt(0);
9.             int y=n.getY();
10.             int x=n.getX();
11.             int p=n.getP();
12.            
13.             this.field[y,x]=3; // mark cell as visited
14.             if(p==1){this.field[y-1,x]=3;} // direction
15.             if(p==2){this.field[y,x+1]=3;}
16.             if(p==3){this.field[y+1,x]=3;}
17.             if(p==4){this.field[y,x-1]=3;}
18.            
19.             if(this.field[y-2,x]==0  this.field[y-1,x]==0){ //if next next cell noch visited an the next cell to...
20.                 Node node = new Node(y-2,x,3); // create node
21.                 if(!list.Contains(node)){list.Add(node);} //if node not in list add them.
22.             } //down
23.             if(this.field[y+2,x]==0  this.field[y+1,x]==0){
24.                 Node node = new Node(y+2,x,1);
25.                 if(!list.Contains(node)){list.Add(node);}
26.             } //up
27.             if(this.field[y,x-2]==0  this.field[y,x-1]==0){
28.                 Node node = new Node(y,x-2,2);
29.                 if(!list.Contains(node)){list.Add(node);}
30.             } //right
31.             if(this.field[y,x+2]==0  this.field[y,x+1]==0){
32.                 Node node = new Node(y,x+2,4);
33.                 if(!list.Contains(node)){list.Add(node);}
34.             } //left
35.            
36.             //shuffle      
37.             for (int i = 0; i < list.Count; i++) {
38.                 Node temp = list[i];
39.                 int randomIndex = Random.Range(0, list.Count-1);
40.                 list[i] = list[randomIndex];
41.                 list[randomIndex] = temp;
42.             }
43.             //
44.            
45.             //Debug.Log(list.Count);
46.            
47.         }while(list.Count>0);
48.     }
49.  
50.  

but now is the problem that iterativ algorithm freezes unity.exe and i dont know why where is my issue now.

i thought so
start with a node in array
mark in array with number 3
collect all next next cell if there is number 0 in it. add the next neigbours to list.
delete the current node from list.

so i got a path through the maze because all neighbours are in the list. so the maze has a solution. but it freezes. realy dont know why. need help ?
thanks.

 

I am just picking an example from your code: Line 19 and 20.
You create a completely new node. Now you ask, is this node already in the list and the answer is always no, because you have created a new one, that's why it will always be added. C# compares the references by default, but you can replace it with your own comparison. You find a pretty good example how to deal with it here: http://msdn.microsoft.com/en-us/library/bhkz42b3.aspx

 

ok Thanks a lot. I understood these examples. I forgot to override the Equal method.

but now freeze unity.exe still. Want to shuffle the list. With these Code. but freeze... hmmm.
Whats wrong?

Code (csharp):

1.  
2.             for (int i = 0; i < list.Count; i++) {
3.                 Node temp = list[i];
4.                 int randomIndex = Random.Range(0, list.Count-1);
5.                 list[i] = list[randomIndex];
6.                 list[randomIndex] = temp;
7.                 }
8.  
9.  

THANK YOU!

 

There is one major issue I am facing: Your code is not easily readable for other developers.

Here is an example from line 13:

Code (csharp):

1. this.field[y-1,x]=3;

One thing I don't get is, why do you use y first and then x? Maybe it makes sense, but it is clearly a point where you may get trouble.
Assigning 3 with the meaning that it is visited is - sorry - stupid. When you come back to this code in three months or in a year, you will need a lot more time to get comfortable with your code.

It will be more readable if you use your own enum instead of an int for the field state:

Code (csharp):

1. public enum FieldState {
2.     Unvisited,
3.     Visited,
4.     ...
5. }

Further line 38 should be:

Code (csharp):

1. int randomIndex = Random.Range(0, list.Count);

If you have a crash, you should have a look at the editor log to understand and isolate the issue:
http://docs.unity3d.com/Documentation/Manual/LogFiles.html

 

You can attach MonoDevelop to the Unity Editor to work out why your code is stuck. Another option is to make the function into a coroutine, put a yield in the loop, and use Debug.Log to print debugging data (e.g. the entire maze state after each update) to the console. Then you can read the log to see what your code did, and hopefully see where it goes wrong.

Also, following on from what Dantus said, what's the order of parameters to Node's constructor - is it really y first then x? Bearing in mind that this is exactly what you got wrong in your first post (passing the arguments to the function in the wrong order), it does seem to be something you should be more careful with.

 

The iterativ algorithm I deleted.
OK I inverted the x and y that was the issue... and the condition to abort was not there.
so it works.

Code (csharp):

1.  
2. public void rek(int x,int y){
3.     if(this.field[x,y]==(int)Mark.visited){return;}
4.     this.field[x,y]=(int)Mark.visited;//mark the field
5. ...
6. }
7.  
8.  

Thanks to all your comments! Now u can close Thread!.