title: C# quadtree Efficiency
body: <p>I am relatively new to unity so I decided to start off writing a little platformer physics engine in C# where the primary stat structure is a quadtree. Unfortunately, my generation code is ridiculously slow, taking over 4 seconds to build a quadtree for only 10K objects (ordinary C# objects not GameObjects).</p>
  
  <p>The code is slightly different from an ordinary quad tree; rather than storing objects which overlap regions in a root node, references are stored in each child node which contains the object. Since all of my objects are relatively the same size and the minimum size of a node is twice this size, building the tree in this manner increases the efficiency of the collision algorithm from ~O(N^(3/2)) to ~O(N).</p>
  
  <p>My simple quadtree class is shown below:</p>
  
  <pre><code>using UnityEngine;
   using System.Collections;
   using System.Collections.Generic;
   using System;
  
   public class QuadTree {
  
       public QuadTree parent = null;
       public QuadTree[] childern = null;
       public List&lt;PPObject&gt; objectList = null;
       public BBox bbox = null;
  
       public bool leaf = true;
       public float minSize = 1.0f;
       public float maxObjs = 4;
  
       public float width;
       public float height;
       public Vector3 position;
       public int level;
  
       public QuadTree(QuadTree parent, BBox bbox, int level)
       {
           this.parent = parent;
           this.bbox = bbox;
           this.level = level;
           width = bbox.xmax - bbox.xmin;
           height = bbox.ymax - bbox.ymin;
           position = new Vector3(bbox.xmin + width * 0.5f, bbox.ymin + height * 0.5f, 0.0f);
  
           objectList = new List&lt;PPObject&gt;();
       }
  
       public void Subdivide()
       {
           Profiler.BeginSample("Subdivide");
           float x1 = bbox.xmin;
           float x2 = bbox.xmin + 0.5f * width;
           float x3 = bbox.xmax;
           float y1 = bbox.ymin;
           float y2 = bbox.ymin + height * 0.5f;
           float y3 = bbox.ymax;
  
           Profiler.BeginSample("allocate new quadtrees");
           childern = new QuadTree[4];
           QuadTree tl = new QuadTree(this, new BBox(x1, x2, y2, y3), level + 1);
           QuadTree tr = new QuadTree(this, new BBox(x2, x3, y2, y3), level + 1);
           QuadTree br = new QuadTree(this, new BBox(x2, x3, y1, y2), level + 1);
           QuadTree bl = new QuadTree(this, new BBox(x1, x2, y1, y2), level + 1);
  
           childern[0] = tl;
           childern[1] = tr;
           childern[2] = br;
           childern[3] = bl;
           Profiler.EndSample();
  
           PushToChildern();
  
           leaf = false;
           Profiler.EndSample();
       }
  
       public void PushToChildern()
       {
           Profiler.BeginSample("pushToChildern");
           foreach (QuadTree child in childern)
           {
               foreach (PPObject obj in objectList)
               {
                   child.AddObject(obj);
               }
           }
  
           objectList = null;
           Profiler.EndSample();
       }
  
       public void AddObject(PPObject obj)
       {
           Profiler.BeginSample("addObject");
           if (childern == null)
           {
               if (obj != null)
               {
                   float x1 = obj.position.x;
                   float w1 = obj.bbox.xmax - obj.bbox.xmin;
  
                   float y1 = obj.position.y;
                   float h1 = obj.bbox.ymax - obj.bbox.ymin;
  
                   float dx = Math.Abs(x1-position.x);
  
                   float dy = Math.Abs(y1-position.y);
  
                   if (dx &lt; ((width+w1) * 0.5f) &amp;&amp; dy &lt; (height + h1) *0.5f )
                   {
                       objectList.Add(obj);
                   }
               }
  
               if (objectList.Count &gt; maxObjs &amp;&amp; width &gt; minSize &amp;&amp; height &gt; minSize)
               {
                   Subdivide();
               }
           } else {
               foreach (QuadTree child in childern)
               {
                   child.AddObject(obj);
               }
           }
           Profiler.EndSample();
       }
   }
  </code></pre>
  
  <p>Here BBox and PPObject are just simple classes containing positions, bounds, velocities, etc. The aforementioned execution time of 4 seconds was performed without the detailed profiler for object sparcities in the range 0.99 to 0.4. If someone could help me understand why this is so slow, that would be awesome. There is probably on the order of 100K function calls, and 20K instantiations totaling 3.4 Mb. Maybe I am just too used to writing in Fortran, but this seems ridiculous for running on a ~10 GFlop core.</p>
  
  <p>Thanks!</p>