Saturday, July 30, 2016

mathematics - Why do we use the Pythagorean theorem in game physics?


I've recently learned that we use Pythagorean theorem a lot in our physics calculations and I'm afraid I don't really get the point.


Here's an example from a book to make sure an object doesn't travel faster than a MAXIMUM_VELOCITY constant in the horizontal plane:


MAXIMUM_VELOCITY = ;
SQUARED_MAXIMUM_VELOCITY = MAXIMUM_VELOCITY * MAXIMUM_VELOCITY;

function animate(){

var squared_horizontal_velocity = (x_velocity * x_velocity) + (z_velocity * z_velocity);

if( squared_horizontal_velocity <= SQUARED_MAXIMUM_VELOCITY ){

scalar = squared_horizontal_velocity / SQUARED_MAXIMUM_VELOCITY;

x_velocity = x_velocity / scalar;
z_velocity = x_velocity / scalar;
}
}


Let's try this with some numbers:


An object is attempting to move 5 units in x and 5 units in z. It should only be able to move 5 units horizontally in total!


MAXIMUM_VELOCITY = 5;
SQUARED_MAXIMUM_VELOCITY = 5 * 5;
SQUARED_MAXIMUM_VELOCITY = 25;

function animate(){
var x_velocity = 5;
var z_velocity = 5;


var squared_horizontal_velocity = (x_velocity * x_velocity) + (z_velocity * z_velocity);
var squared_horizontal_velocity = 5 * 5 + 5 * 5;
var squared_horizontal_velocity = 25 + 25;
var squared_horizontal_velocity = 50;

// if( squared_horizontal_velocity <= SQUARED_MAXIMUM_VELOCITY ){
if( 50 <= 25 ){
scalar = squared_horizontal_velocity / SQUARED_MAXIMUM_VELOCITY;
scalar = 50 / 25;

scalar = 2.0;

x_velocity = x_velocity / scalar;
x_velocity = 5 / 2.0;
x_velocity = 2.5;

z_velocity = z_velocity / scalar;
z_velocity = 5 / 2.0;
z_velocity = 2.5;


// new_horizontal_velocity = x_velocity + z_velocity
// new_horizontal_velocity = 2.5 + 2.5
// new_horizontal_velocity = 5
}
}

Now this works well, but we can do the same thing without Pythagoras:


MAXIMUM_VELOCITY = 5;

function animate(){

var x_velocity = 5;
var z_velocity = 5;

var horizontal_velocity = x_velocity + z_velocity;
var horizontal_velocity = 5 + 5;
var horizontal_velocity = 10;

// if( horizontal_velocity >= MAXIMUM_VELOCITY ){
if( 10 >= 5 ){
scalar = horizontal_velocity / MAXIMUM_VELOCITY;

scalar = 10 / 5;
scalar = 2.0;

x_velocity = x_velocity / scalar;
x_velocity = 5 / 2.0;
x_velocity = 2.5;

z_velocity = z_velocity / scalar;
z_velocity = 5 / 2.0;
z_velocity = 2.5;


// new_horizontal_velocity = x_velocity + z_velocity
// new_horizontal_velocity = 2.5 + 2.5
// new_horizontal_velocity = 5
}
}

Benefits of doing it without Pythagoras:



  1. Less lines


  2. Within those lines, it's easier to read what's going on

  3. ...and it takes less time to compute, as there are less multiplications


Seems to me like computers and humans get a better deal without Pythagorean theorem! However, I'm sure I'm wrong as I've seen Pythagoras' theorem in a number of reputable places, so I'd like someone to explain me the benefit of using Pythagorean theorem to a maths newbie.


Does this have anything to do with unit vectors? To me a unit vector is when we normalize a vector and turn it into a fraction. We do this by dividing the vector by a larger constant. I'm not sure what constant it is. The total size of the graph? Anyway, because it's a fraction, I take it, a unit vector is basically a graph that can fit inside a 3D grid with the x-axis running from -1 to 1, z-axis running from -1 to 1, and the y-axis running from -1 to 1. That's literally everything I know about unit vectors... not much :P And I fail to see their usefulness.


Also, we're not really creating a unit vector in the above examples. Should I be determining the scalar like this:


// a mathematical work-around of my own invention. There may be a cleverer way to do this! I've also made up my own terms such as 'divisive_scalar' so don't bother googling
var divisive_scalar = (squared_horizontal_velocity / SQUARED_MAXIMUM_VELOCITY);
var divisive_scalar = ( 50 / 25 );
var divisive_scalar = 2;


var multiplicative_scalar = (divisive_scalar / (2*divisive_scalar));
var multiplicative_scalar = (2 / (2*2));
var multiplicative_scalar = (2 / 4);
var multiplicative_scalar = 0.5;

x_velocity = x_velocity * multiplicative_scalar
x_velocity = 5 * 0.5
x_velocity = 2.5


Again, I can't see why this is better, but it's more "unit-vector-y" because the multiplicative_scalar is a unit_vector? As you can see, I use words such as "unit-vector-y" so I'm really not a maths whiz! Also aware that unit vectors might have nothing to do with Pythagorean theorem so ignore all of this if I'm barking up the wrong tree.


I'm a very visual person (3D modeller and concept artist by trade!) and I find diagrams and graphs really, really helpful so as many as humanely possible please!



Answer



Your Pythagoras-free code doesn't compute a length as we normally think of it.


Normally in 3D games we model the world as a Euclidean space, and we use a Euclidean distance metric (also known as Pythagorean Theorem) to calculate the total length of a vector v with components v.x and v.y. Namely:


EuclideanLength(v) = sqrt(v.x * v.x + v.y * v.y)

(Note that this square root is missing in your sample code above, which is why the two approaches appear to give the same answer. More on that shortly...)


The code you've described uses the Manhattan distance metric:


ManhattanLength(v) = abs(v.x) + abs(v.y)


(Although you didn't include the absolute values, which may make it behave unexpectedly for negative numbers)


It's easy to see that these two distance functions match-up when v.x or v.y is zero, and we're only moving along one axis. How do they compare though when we move diagonally?


Let's say v.x = v.y = 1. How long is this vector (equivalently, how fast is the velocity it describes)?


Euclidean                              Manhattan

sqrt(v.x*v.x + v.y * v.y) abs(v.x) + abs(v.y)
sqrt(1 * 1 + 1 * 1) abs(1) + abs(1)
sqrt(2) 1 + 1
1.414... 2


You can see these metrics don't actually agree for diagonal lines.


Let's plot on a graph the set of points that each metric says are a distance of 1 away from the origin:


Distance metrics


Our familiar Euclidean metric is the red circle. This is the set of all points x,y such that x^2 + y^2 = 1. You can see that it's rotationally-symmetric, and that's why we like it: it neatly represents the idea that distance doesn't change with direction.


The Manhattan metric is the blue diamond. Not a great match for our intuitive idea of distance - but that doesn't make it bad. In many tile-based games where you move in discrete steps in the four cardinal directions, the Manhattan metric gives the correct distance between points (in terms of "how many moves will it take to get there?")


Finally, I threw in the Chebyshev metric for fun - it's the green square:


ChebyshevLength(v) = max(abs(v.x), abs(v.y))

It's also good for tile-based games, where you're allowed to move on diagonals. A King in Chess moves according to the Chebyshev metric.



I hope that clears up what the difference is between typical Pythagorean-style code and the example you provided above.


No comments:

Post a Comment

Simple past, Present perfect Past perfect

Can you tell me which form of the following sentences is the correct one please? Imagine two friends discussing the gym... I was in a good s...