# Distance checking of normalized vectors?

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?

• Hello, and thanks for your detailed question. :) Did you profile your code to see where the time is spent? The issue is surprising, so you might be surprised by the reason too. – Quentin Pradet Feb 22 '13 at 10:08
• Yes, I did profiling. The vast majority of time (90%+) is spent in the DistanceSquared method. This time drops dramatically (30-40%) with normalized vectors. – oiez Feb 23 '13 at 3:10
• What is the maximum visibility/sensibility range of a unit? You could split your world into squares (a dictionary of (X,Y) => set(player), set(enemy)). Now, whenever a player/enemy moves, they will potentially jump from one square to the next. With the right size of the square, you will need to consider only up to 9 squares total and not the whole board for every unit in that square. This way you can do all players and all enemies in that one square. Your dictionary will have as many keys as there are occupied squares. – Leonid Feb 26 '13 at 23:57
• By the way, this type of problem seems to be "map-reducible". Are you looking to employ multithreading? – Leonid Feb 27 '13 at 1:12
• My best guess is that you have code in either or both of the if (distanceToNearestEnemy < 2500f) {} or the if (Vector2.DistanceSquared(human_position, other_human_position) < 100f) {} code blocks that breaks out of the loop. I would recommend what Leonid is recommending. Look up info on space partitioning. – Justin Peel Mar 4 '13 at 16:00

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++)
{
}

double sumOfSquares = 0;

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

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.