Distance checking of normalized vectors?

Question

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:

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.

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.

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):

List<Human> humans;
List<Enemy> enemies;

public void Update(City city, float gameTime)
{
    humans = city.GetHumans();
    enemies = city.GetEnemies();

    for (int h = 0; h < humans.Count; h++)
    {
        Vector2 human_position = humans[h].position;

        Vector2 nearestEnemyPosition = Vector2.Zero;

        for (int e = 0; e < enemies.Count; e++)
            {
                Vector2 enemy_position = enemies[e].position;
                float distanceToEnemy = Vector2.DistanceSquared(human_position, enemy_position);

                if (distanceToEnemy < distanceToNearestEnemy)
                {
                    distanceToNearestEnemy = distanceToEnemy;
                    nearestEnemyPosition = enemy_position;
                }

                if (distanceToNearestEnemy < 2500f)
                {
                     logic code here (very little performance impact)
                }
            }

        for (int hh = 0; hh < 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) < 100f)
                {
                   do more stuff here (movement code, no performance impact)
                }

I also have almost identical loops for the enemy list.

The code to make them is here:

foreach (Human human in this.humans)
        {
            Vector2 position = new Vector2(random.Next(800), random.Next(480));
            human.Spawn(position);
        }

This works fine. I get 60FPS and it's totally smooth & everything runs perfectly. However, if I do this:

foreach (Human human in this.humans)
        {
            Vector2 position = new Vector2(random.Next(8000), random.Next(4800));
            human.Spawn(position);
        }

Everything tanks and I get 1FPS. I tried normalizing the vectors, which solved the performance issue, but whenever I checked to find the closest object it gave me inaccurate results.

Is there any way to accurately check for the distance of two objects that have been normalized with Vector2.Normalize()? Am I even asking the right question?

Answer 1

Let me start by agreeing with the comments that have been posted. It is really strange that you're getting this behavior. In fact, it seems like it should be the opposite.

I Could Not Reproduce the Performance Delay

I started off by trying to recreate the problem you're describing. I first attempted by starting from the code you've given. I could measure no performance difference (using the Stopwatch class) when selecting between the small 800x480 size and the larger 8000x4800 size.

The next thing I tried was to strip the example down to just simply Vector2 objects, leaving out all of your Human, Enemy, and City types. I used the following code:

private static Random random = new Random();

protected override void Update(GameTime gameTime)
{
    // Generate initial list of vectors.
    List<Vector2> vectors = new List<Vector2>();
    for (int index = 0; index < 1000; index++)
    {
        vectors.Add(new Vector2(random.Next(800), random.Next(480)));
    }

    double sumOfSquares = 0;

    // Start timing.
    Stopwatch stopwatch = new Stopwatch();
    stopwatch.Start();

    // Add up the 
    foreach(Vector2 a in vectors)
    {
        foreach(Vector2 b in vectors)
        {
            sumOfSquares += Vector2.DistanceSquared(a, b);
        }
    }

    // End timing and print results.
    stopwatch.Stop();
    Console.WriteLine(stopwatch.ElapsedMilliseconds);
}

In both cases, there were no measurable differences. The size of the vectors does not have an impact on the performance.

I think this jives with what people would usually expect, hence the comments indicating it was a surprise. Regardless of the size of the values contained in the variables, the code should produce the same IL code, and ultimately the same machine instructions. It should be running the exact same code.

Looking for Other Problems

I think at this point, you should turn your attention elsewhere in your code. (You probably already did. This question is six months old now.)

One thing that strikes me as a possibility is if all you do is essentially change the size of your world (800x480 to 8000x4800), you potentially need to change a number of other variables as well, if you're making the change to create a higher resolution world, instead of just simply a larger world. In particular, the number you're using as the minimum distance between a human and an enemy, and a human and another human. Without changing these appropriately, you'll get different percentages of breakdowns in how often it gets into each of these if-statements.

What's still odd to me is that it seems backwards. If you increase the size of the world without increasing the number of objects in it, they'll be less dense. You should be hitting the inside of those if-statements less frequently. In theory, it should increase the performance to use a bigger world.

So in the end, you'll probably want to reconsider what the code inside of those if-statements actually do. There's a much better chance that that is causing the lag, not the actual size of the world. If you've got break or continue, you'll want to take an especially close look at how these behave, because these could be short circuiting your loop.

The Difference in Performance is Not Caused by Not Having Space Partitioning

One thing I don't agree with, as far as the comments go, is that this case warrants looking into space partitioning. It's possible that you'll want it in the end, but your underlying performance problem isn't necessarily tied to the spatial arrangement of your objects. There is something else strange going on here, and you'll want to figure that out first.

If both of your cases had the same performance, you felt like it was too slow, and the performance delay was clearly and measurably caused by the distance comparisons (i.e., profiling) that's when you'd look into some form of partitioning.

Vector Normalization

You mentioned that you normalized the vectors, and that solved your issue. Vector normalization takes a vector and turns it into one that points in the same direction, but has a length of 1. If a Vector2 object represents a velocity, an acceleration, or a vector from one point to another, vector normalization can be used to tell you the direction of that vector.

But if your vector is being used to represent a point in 2D space (or 3D space) normalizing it will just tell you the direction that the point lies from the origin of your world. It loses its meaning, as far as determining how far away two points are from each other. So that's why you're no longer getting correct results when you do this.