Computing Distance

Learning Objectives

Create code that will compute the distance between two points in a 3D space.

Introduction

The shortest distance between two points is a straight line. Often, one will need the distance between two objects for various reasons in a game, whether it's to know the distance between the player's vehicle and a waypoint, or as a proximity check to see if an event should be triggered. Computing this distance is simple enough if you know the coordinates for the two points in question.

Distance in 3 Dimensions

From algebra, you may remember that the distance between any two points can be determined by using the Pythagorean Theorem, $a^2 + b^2 = c^2$. By applying this relationship a couple of times, our formula from 2D can be extended 3D. One may wish to have separate 2D and 3D tools for calculating distance, but for our purposes here, we can simply apply the 3D formula in either case by simply setting $z = 0$ for the 2D case.

(1)
\begin{align} d=\sqrt{(x_2-x_1)^2+(y_2-y_1)^2+(z_2-z_1)^2} \end{align}
Distance3d.jpg

As we will see often throughout this course, the fastest way to code up a process isn't always the fastest way for the code to execute. Since our objective is to produce smooth motion in a gaming environment where new data and a new frame must be generated every 1/120th of a second, we will need to think carefully about what computational steps we are asking the CPU to perform. For example, let's take a look at a very straightforward way in which we can encode the above distance formula,

double Distance = sqrt(pow(((x2-x1),2) + pow((y2-y1),2) + pow((z2-z1),2));

It's a single line that does the job simply and elegantly, right? Well, let's take a look at exactly what is happening when we call the pow(argument, exponent) function. Take a look at the source code of the actual pow.c function here: http://www.open64.net/doc/db/d6e/pow_8c-source.html. Seems mightily complex for the simple task of taking a number times itself, doesn't it! If you need to raise a number to an arbitrary fractional power, this function is quite useful, but it's definitely overkill for simply squaring a value. Why use pow(x,2) when simply using x*x will work just as well and work significantly faster? So let's take another stab at our distance formula.

double Distance = sqrt((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1) + (z2-z1)*(z2-z1));

This takes a bit longer to write, but it executes a lot faster! There's still some more efficiency we can find, though, if we look carefully. Notice that we're repeating the same calculation of (x2-x1) twice, and the same for the y and z coordinates. It will take just a little bit more memory, but it will eliminate a lot of computational repetition if we define the differences as a new variable and use that in our distance calculataion.

double dx = x2 - x1;
double dy = y2 - y1;
double dz = z2 - z1;
double Distance = sqrt(dx*dx + dy*dy + dz*dz);

Lastly, we can think about how much memory we're using. By default, most people define floating-point numbers as double-precision, and where this is fine if you actually need fifteen significant figures, but in a game environment this is rarely the case. The seven digits of precision in a single-precision float is good enough and uses half the memory, four bytes instead of eight, to store the data. Since the sqrt function takes double-precision values by default, we can force a single-precision implementation by using the sqrtf function.

float dx = x2 - x1;
float dy = y2 - y1;
float dz = z2 - z1;
float Distance = sqrtf(dx*dx + dy*dy + dz*dz);

Now we have a nice bit of code that is miserly in both it's use of memory and of CPU time. There are additional savings that can be found in writing a custom sqrtf, but those methods are beyond what we will be doing in this class. For now, this is good enough. If you're interested in these faster, but less precise, methods of calculating roots, you can find a nice discussion here, http://www.codeproject.com/

Laboratory Procedures

Write code that will calculate the distance between two user-supplied points in a three dimensional space.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License