title: XNA performance
body: <p>I'm writing some sort of Geometry Wars inspired game except with added 2d rigid body physics Ai pathfinding some waypoint analysis line of sight checks load balancing etc. It seems that even though with around 80-100 enemies on screen it can work reasonably fast with all  that stuff enabled the performance completely breaks down once you get to a total of 250 (150 enemies) objects or so. I've searched for any O(n^2) parts in the code but there don't seem to be any left. I'm also using spatial grids.</p>
  
  <p>Even if I disable pretty much everything from the supposedly expensive Ai related processing it doesn't seem to matter, it like still breaks down at 150 enemies.</p>
  
  <p>Now I implemened all the code from scratch, currently even the matrix multiplication code, and I'm almost completely relying on the GC as well as using C# closures for some things, so I expect this to be seriously far from being optimized, but still it doesn't make sense to me that with like 1/15 of the processing work but double the objects the game suddenly starts to slow down to crawl? Is this normal, how is the XNA platform normally supposed to scale as far as the amount of objects being processed is concerned? </p>
  
  <p>I remember Some slerp spinning cube thing I did at first could handle more than 1000 at once so I think I'm doing something wrong?</p>
  
  <p>edit:
  Here's the grid structure's class</p>
  
  <p>public abstract class GridBase{</p>
  
  <pre><code>    public const int WORLDHEIGHT = (int)AIGridInfo.height;
      public const int WORLDWIDTH = (int)AIGridInfo.width;
      protected float cellwidth;
      protected float cellheight;
  
  
      int no_of_col_types;
  
      // a dictionary of lists that gets cleared every frame
      // 3 (=no_of_col_types) groups of objects (enemy side, players side, neutral)
      // 4000 initial Dictionary hash positions for each group
      // I have also tried using an array of lists of 100*100 cells
      //with pretty much identical results
      protected Dictionary&lt;CoordsInt, List&lt;Collidable&gt;&gt;[] grid;
  
  
      public GridBase(float cellwidth, float cellheight, int no_of_col_types)
      {
          this.no_of_col_types = no_of_col_types;
          this.cellheight=cellheight;
          this.cellwidth=cellwidth;
  
          grid = new Dictionary&lt;CoordsInt, List&lt;Collidable&gt;&gt;[no_of_col_types];
          for (int u = 0; u &lt; no_of_col_types; u++)
             grid[u] = new Dictionary&lt;CoordsInt, List&lt;Collidable&gt;&gt;(4000);
  
      }
  
      public abstract void InsertCollidable(Collidable c);
      public abstract void InsertCollidable(Grid_AI_Placeable aic);
  
      //gets called in the update loop
      public void Clear()
      {
          for (int u = 0; u &lt; no_of_col_types; u++)
              grid[u].Clear();
      }
  
      //gets the grid cell of the left down corner
      protected void BaseCell(Vector3 v, out int gx, out int gy)
      {
          gx = (int)((v.X + (WORLDWIDTH / 2)) / cellwidth);
          gy = (int)((v.Y + (WORLDHEIGHT / 2)) / cellheight);
  
      }
  
      //gets all cells covered by the AABB
      protected void Extent(Vector3 pos, float aabb_width, float aabb_height, out int totalx, out int totaly)
      {
          var xpos = pos.X + (WORLDWIDTH / 2);
          var ypos = pos.Y + (WORLDHEIGHT / 2);
          totalx = -(int)((xpos / cellwidth)) + (int)((xpos + aabb_width) / cellwidth) + 1;
          totaly = -(int)((ypos / cellheight)) + (int)((ypos + aabb_height) / cellheight) + 1;
  
      }
  
  
  }
  </code></pre>
  
  <p>public class GridBaseImpl1 : GridBase{</p>
  
  <pre><code>    public GridBaseImpl1(float widthx, float widthy)
          : base(widthx, widthy, 3)
      {
  
      }
  
  
      //adds a collidable to the grid /
      //caches for intersection test
      //checks if it should be tested to prevent penetration /
      //tests penetration
      //updates close, intersecting, touching lists
      //Collidable is an interface for all objects that can be tested geometrically
      //the dictionary is indexed by some simple struct that wraps the row and column number in the grid
      public override void InsertCollidable(Collidable c)
      {
  
          //some tag so that objects don't get checked more than once
          Grid_Query_Counter.current++;
  
          //the AABB is allocated in the heap
          var aabb = c.CollisionAABB;
          if (aabb == null) return;
          int gx, gy, totalxcells, totalycells;
          BaseCell(aabb.Position, out gx, out gy);
  
          Extent(aabb.Position, aabb.widthx, aabb.widthy, out totalxcells, out totalycells);
  
          //gets which groups to test this object with in an IEnumerable (from a statically created array)
          var groupstestedagainst = CollidableCalls.GetListPrevent(c.CollisionType).Select(u =&gt;   CollidableCalls.group[u]);
          var groups_tested_against = groupstestedagainst.Distinct();
          var own_group = CollidableCalls.group[c.CollisionType];
  
  
          foreach (var list in groups_tested_against)
              for (int i = -1; i &lt; totalxcells + 1; i++)
                  for (int j = -1; j &lt; totalycells + 1; j++)
                  {
  
                      var index = new CoordsInt((short)(gx + i), (short)(gy + j));
  
                      if (grid[list].ContainsKey(index))
  
                          foreach (var other in grid[list][index])
                          {
  
                              if (Grid_Query_Counter.Check(other.Tag))
                              {
  
                                  //marks the pair as close, I've tried only keeping the 20 closest but it's still slow
                                  other.Close.Add(c);
                                  c.Close.Add(other);
  
                                  //caches the pair it so that checking if the pair intersects doesn't go through the grid        //structure loop again
                                  c.CachedIntersections.Add(other);
  
                                  var collision_function_table_id = c.CollisionType * CollidableCalls.size +      other.CollisionType;
  
  
                                  //gets the function to use on the pair for testing penetration
                                  //the function is in a delegate array statically created to simulate multiple dispatch
                                  //the function decides what coarse test to use until descending to some complete        //geometric query
                                  var prevent_delegate = CollidableCalls.preventfunctions[collision_function_table_id];
  
                                  if (prevent_delegate == null) { Grid_Query_Counter.Put(other.Tag); continue; }
  
                                  var a = CollidableCalls.preventfunctions[collision_function_table_id](c, other);
  
                                  //if the query returns true mark as touching
                                  if (a) { c.Contacted.Add(other); other.Contacted.Add(c); }
  
  
  
  
  
  
                                  //marks it as tested in this query
                                  Grid_Query_Counter.Put(other.Tag);
                              }
  
  
  
  
                          }
  
  
                  }
  
          //adds it to the grid if the key doesn't exist it creates the list first
          for (int i = -1; i &lt; totalxcells + 1; i++)
              for (int j = -1; j &lt; totalycells + 1; j++)
              {
                  var index = new CoordsInt((short)(gx + i), (short)(gy + j));
  
                  if (!grid[own_group].ContainsKey(index)) grid[own_group][index] = new List&lt;Collidable&gt;();
  
                  grid[own_group][index].Add(c);
              }
      }
  
  
      [...]
  }
  </code></pre>