title: Distance checking performance
body: <p>I've been learning C#/XNA in an attempt to make a game for the past few weeks so maybe this is an obvious newbie thing, but here goes:</p>
  
  <p>I've been making a fairly simple 2D game, so I have a list of ~1000 objects (NPC's), and I'm iterating through them extremely frequently to do distance checking on each one. The problem is when I increase the distances, everything slows down considerably to the point where the game is unplayable, and I don't really understand why. </p>
  
  <p>It works fine when the distances are short (if all objects are within one 800x480 world size), but when they are increased (say, an 8000x4800 world size), my performance tanks.</p>
  
  <p>Here is some relevant code (not all of it, obviously, since that would be too much stuff, but this is the gist of what's happening):</p>
  
  <pre><code>List&lt;Human&gt; humans;
  List&lt;Enemy&gt; enemies;
  
  public void Update(City city, float gameTime)
  {
      humans = city.GetHumans();
      enemies = city.GetEnemies();
  
      for (int h = 0; h &lt; humans.Count; h++)
      {
          Vector2 human_position = humans[h].position;
  
          Vector2 nearestEnemyPosition = Vector2.Zero;
  
          for (int e = 0; e &lt; enemies.Count; e++)
              {
                  Vector2 enemy_position = enemies[e].position;
                  float distanceToEnemy = Vector2.DistanceSquared(human_position, enemy_position);
  
                  if (distanceToEnemy &lt; distanceToNearestEnemy)
                  {
                      distanceToNearestEnemy = distanceToEnemy;
                      nearestEnemyPosition = enemy_position;
                  }
  
                  if (distanceToNearestEnemy &lt; 2500f)
                  {
                       logic code here (very little performance impact)
                  }
              }
  
          for (int hh = 0; hh &lt; humans.Count; hh++)
              {
                  if (h == hh)
                  {
                      continue;
                  }
  
                  if (humanMoved == true)
                  {
                      continue;
                  }
  
                  Vector2 other_human_position = humans[hh].position;
  
                  if (Vector2.DistanceSquared(human_position, other_human_position) &lt; 100f)
                  {
                     do more stuff here (movement code, no performance impact)
                  }
  </code></pre>
  
  <p>I also have almost identical loops for the enemy list.</p>
  
  <p>The code to make them is here:</p>
  
  <pre><code>foreach (Human human in this.humans)
          {
              Vector2 position = new Vector2(random.Next(800), random.Next(480));
              human.Spawn(position);
          }
  </code></pre>
  
  <p>This works fine. I get 60fps and it's totally smooth &amp; everything runs perfectly. However, if I do this:</p>
  
  <pre><code>foreach (Human human in this.humans)
          {
              Vector2 position = new Vector2(random.Next(8000), random.Next(4800));
              human.Spawn(position);
          }
  </code></pre>
  
  <p>Everything tanks and I get 1fps. This seems very strange, do bigger numbers really make the DistanceSquared function take longer to compute? Why? Or is there something else that could be causing this that I am missing?</p>
  
  <p>I've already run a couple performance profilers and they told me nothing useful, just that DistanceSquared is taking up the vast majority of my CPU cycles. If it's at the normal value of 800x480, only 38% of my game time is spent in that loop. When I change the numbers from 800->8000/480->4800, 90% of my time is spent in the loop. It's not like there are more objects to call, or more math to do, it's the same math, just with bigger numbers, so why is there such a dramatic difference?</p>