Recursive Quadtree causing sudden fail

Question

Got a problem with creating a Quadtree in Unity, on my Start function I create an instance of one Quadtree, the idea is that the quadtree subdivides itself into 4 children per node.

The problem is that as soon as I hit play Unity crashes instantly. Not like a freeze it just fails and disappears on Mac OSX.

I can't understand because I can't see how it could be a infinite loop as the max_level will stop that.

 public class Quadtree {
         
         public Quadtree[] children = null;
         
         public int m_max_level = 4;
         public int m_level = 0;
         
         public Quadtree(int maxLevel, int level){
             m_max_level = maxLevel;
             m_level = level;
             Divide();
         }
         
         public void Divide(){
             if(m_level < m_max_level){
                 children = new Quadtree[4];
                 for(int i = 0; i < children.Length; i++){
                     children[i] = new Quadtree(m_max_level,m_level++);
                 }

} } }

Answer 1

The answer is quite simple. You use the post increment operator. As you might / should know the post increment operator evaluates the value of the variable before it's actually increasing the value. So when calling:

     children[i] = new Quadtree(m_max_level, m_level++);

when m_level is "0" it will pass the value 0 to the constructor and then increment the value. This will effectively always pass the original value to each recursion without any change.

Use either the pre increment operator or increment the value before you call the constructor.

     // pre increment
     children[i] = new Quadtree(m_max_level, ++m_level);

Since you actually don't need the incremented value inside the class the usual way is to do it like this:

     children[i] = new Quadtree(m_max_level, m_level + 1);

edit
Another very common way for recursive break conditions is to count backwards:

 public class Quadtree
 {
     public Quadtree[] children = null;
 
     public Quadtree(int maxLevel)
     {
         if (maxLevel > 0)
             Divide(maxLevel - 1);
     }
     
     public void Divide(int maxLevel)
     {
         children = new Quadtree[4];
         for(int i = 0; i < children.Length; i++)
         {
             children[i] = new Quadtree(maxLevel);
         }
     }
 }

Recursive Quadtree causing sudden fail

1 Reply

Your answer

Follow this Question

Related Questions