Comparing Positions

…or even just floats.
[Also on coderwall: https://coderwall.com/p/v3priq]
This one’s got nothing to do with the Derivatives sessions from last weekend.

This may be obvious to some, but I seem to have shared with different people on multiple occasions to, so here goes.

If you’ve got two position vectors you wish to “compare”, you should use distance (in fact, squared distance), instead of a component-wise equality check. As an example – a game character (position) and a specific position in space – “Has the character reached the origin (0, 0, 0) of the world?“.

I often see the naive implementation when someone complains about certain game-play code not working.
Pseudo (Class Vector3 skeleton towards end of article if needed):

  Vector3 position; // player position
  Vector3 destination; // target/destination position
  // ...
  // Naive check
  if(position==destination) {
    onTargetReached();
  }

This is likely to “not work”, since your position is updating based on a speed or velocity vector and taking into account deltaTime (all of them being float or double). The quotes around not work are placed because the computer does exactly what you program it to and nothing else. A reason to use distance is because of the (discrete) time step, position may never actually reach destination (you may skip over it in one frame(or calculation/simulation step) to another). Another reason is that floating point numbers may have accuracy issues.

The distance to use would depend on your scale – if you ever studied mathematics, physics, statistics etc, you may have come across the term standard error or epsilon. Think of the distance as an acceptable measurement error or “close enough”. So if your system scale or the units are 1 float unit = 1 meter and the problem you’re solving (code you’re writing) isn’t affected by anything smaller than a centimeter, you could use 0.01 as your epsilon value.

  // Check using distance
  const float kEpsilon = 0.01f;
  if( (position-destination).magnitude() < kEpsilon ) {
    onTargetReached();
  }

This changes your question to “Has the character reached close enough to the origin (0, 0, 0) of the world?“. Make sure this change is appropriate to your code base – if you’re at NASA or CERN where the accuracy may be more important than speed, walk away from here.

To make this even better, you could use squared distance. “What?! Add more instructions to square both sides of the condition/inequality?

SIDE
For comparing just two floats (rather than vectors), it may be appropriate for you to do so in your application (probably not for you if you code for a bank! But then you should’ve read up about floating point accuracy):

  float a, b;
  // ... (system specific operations assigning values to a and b)
  // Replace:
  // if(a==b)
  // with
  if( (a-b)*(a-b) < kEpsilon*kEpsilon )

This one uses a squares to avoid having to check twice depending on whether the difference is negative or not. The marginally slower operation instead might be to use absolutefabs((a-b)). Another rule of thumb to use: “Math is faster than using a conditional.
END SIDE

The answer to that is – a multiplication requires fewer instructions as compared to a square root which is required in finding the magnitude of a vector. So your check should be:

  // Check using squared distance (helper defined below)
  const float kEpsilonSq = 0.01f*0.01f;
  if( (position-destination).sqMagnitude() < kEpsilonSq ) {
    onTargetReached();
  }

Plus, most Vector classes that you come across probably already have a lenSquared or sqMagnitude equivalent (look for them if you start working with on an existing code base or a project with a new engine etc); if you’re writing your own, you now know what it’s good for. Note that if you do come across some code which doesn’t have a magnitude squared method built in, you should add one. If you can’t (no access to source), just use length if that’s all that’s available – there’s no point squaring the magnitude if you’ve already calculated it.

Finally when it comes to optimization, only optimize something which would benefit the overall performance. Don’t go around changing all places in your (existing) code base to do this unless it’s in a function that gets called a lot – such as an update/step function called every frame. Otherwise it may not be worth the time you spend replacing all usages. Optimization should be balanced with readability. For new code you could use squared distance everywhere from a “good practice” standpoint.

  // Skeleton for Vector3 for those that may need it for better understanding
  class Vector3 {
    float x, y, z;

    // Magnitude (or length) of the vector.
    float magnitude() {
      return sqrtf( this.sqMagnitude() );
    }
    // For more details, see http://en.wikipedia.org/wiki/Magnitude_%28mathematics%29
    float sqMagnitude() {
      return (x*x+y*y+z*z);
    }
    Vector3 operator-(const Vector &other) {
      return Vector3(x-other.x, y-other.y, z-other.z);
    }

    bool operator==(const Vector &other) {
      return (x==other.x && y==other.y && z==other.z);
    }

    // More class details omitted
    // ...
  };
Advertisements
This entry was posted in Computers and Internet and tagged , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s