Fast Semi-Accurate Vector Calculation for 2D Games
Posted November 17, 2010 by Nick Vogt in Programming
See this post for a much-improved version
----------------------------
I am working on a simple platformer in Actionscript 3. The player aims with the mouse cursor and when he shoots it calculates the vector using trigonometry and a speed multiplier. This works well as it is very accurate, but I started to wonder if I might not be able to make a more efficient formula, since it doesn't really need to be absolutely accurate.
Here is the trigonometry I used originally (the syntax is Actionscript 3 but it should be pretty self-explanatory for C++, Python, etc programmers):
I am looking to use something that doesn't use any trigonometry functions, just multiplication and division. I came up with this:
Unfortunately it requires more variables and several more lines of code, but in my testing it is much faster than the trigonometry method. What this formula does is first calculate the absolute values of the X and Y parts of the vector (avX and avY) using a much faster method than the absolute value function. Then it uses a ratio (sRatio) to normalize the vector to the desired speed, then another ratio (cRatio) to adjust the vector based on how close the X and Y parts of the vectors are (signifying how diagonally the player is aiming). The reason I need the absolute values is to find the ratios (negative signs would mess that up). If you're wondering what the 0.43 is, it happens to be the ratio to get the points to line up with a circle. The result is a firing pattern that is an octagon. It looks something like this:
The outer line represents the firing pattern using trigonometry, while the inner line represents the firing pattern using the basic math formula. As you can see, the inner line (using basic math) is not perfect, but for a simple platformer it will more than suffice.
Now to see the performance difference using loop iterations. I use my performance tester, which uses 5,000,000 iterations and records the time it takes. Notice that I keep the variable initialization outside of the timed loop, to eliminate initialization time from the test.
First the original trig function:
This took 2231 milliseconds to process.
Now the basic math function:
This only took 227 milliseconds to process, or about 10% of the time.
Depending on your game, the performance difference may not be noticeable. But if you're creating lots of new vectors every frame the less accurate function may result in some performance improvements. As with most things, there is a trade-off between accuracy and speed. I hope this will help someone.
Update:
I decided to try a more realistic comparison between these two methods, as I wasn't seeing much change in my game despite hundreds of new vectors being created per frame at times. Here are the results of my new test, which uses fewer iterations but does more per iteration:
The trig method returned 667 milliseconds in this test:
And the basic math method returned 448 milliseconds:
The basic math method is still faster, but it isn't as stark of a difference as illustrated before. This is because there is now more going on, including some additional variable initialization, which narrows the gap. The test is more real-world now than before, and it shows that the difference between these two methods isn't as big when you factor in initialization and other things that have a greater impact on performance.
----------------------------
I am working on a simple platformer in Actionscript 3. The player aims with the mouse cursor and when he shoots it calculates the vector using trigonometry and a speed multiplier. This works well as it is very accurate, but I started to wonder if I might not be able to make a more efficient formula, since it doesn't really need to be absolutely accurate.
Here is the trigonometry I used originally (the syntax is Actionscript 3 but it should be pretty self-explanatory for C++, Python, etc programmers):
radians = Math.atan2(eX - sX, eY - sY);
vX = Math.sin(radians) * speed;
vY = Math.cos(radians) * speed;
vX = Math.sin(radians) * speed;
vY = Math.cos(radians) * speed;
I am looking to use something that doesn't use any trigonometry functions, just multiplication and division. I came up with this:
vX = eX - sX;
vY = eY - sY;
if(vX < 0) avX = vX * -1;
else avX = vX;
if(vY < 0) avY = vY * -1;
else avY = vY;
if(avX > avY)
{
sRatio = speed / avX;
cRatio = avY / avX * 0.43 + 1;
}
else
{
sRatio = speed / avY;
cRatio = avX / avY * 0.43 + 1;
}
vX = vX * sRatio / cRatio;
vY = vY * sRatio / cRatio;
vY = eY - sY;
if(vX < 0) avX = vX * -1;
else avX = vX;
if(vY < 0) avY = vY * -1;
else avY = vY;
if(avX > avY)
{
sRatio = speed / avX;
cRatio = avY / avX * 0.43 + 1;
}
else
{
sRatio = speed / avY;
cRatio = avX / avY * 0.43 + 1;
}
vX = vX * sRatio / cRatio;
vY = vY * sRatio / cRatio;
Unfortunately it requires more variables and several more lines of code, but in my testing it is much faster than the trigonometry method. What this formula does is first calculate the absolute values of the X and Y parts of the vector (avX and avY) using a much faster method than the absolute value function. Then it uses a ratio (sRatio) to normalize the vector to the desired speed, then another ratio (cRatio) to adjust the vector based on how close the X and Y parts of the vectors are (signifying how diagonally the player is aiming). The reason I need the absolute values is to find the ratios (negative signs would mess that up). If you're wondering what the 0.43 is, it happens to be the ratio to get the points to line up with a circle. The result is a firing pattern that is an octagon. It looks something like this:
The outer line represents the firing pattern using trigonometry, while the inner line represents the firing pattern using the basic math formula. As you can see, the inner line (using basic math) is not perfect, but for a simple platformer it will more than suffice.
Now to see the performance difference using loop iterations. I use my performance tester, which uses 5,000,000 iterations and records the time it takes. Notice that I keep the variable initialization outside of the timed loop, to eliminate initialization time from the test.
First the original trig function:
var i:int = 0;
var sX:Number = 24.2, sY:Number = 18.1, eX:Number = 158.9, eY:Number = -29.8;
var radians:Number;
var vX:Number;
var vY:Number;
var speed:Number = 10;
var time1 = new Date();
for(i = 0; i < 5000000; i ++)
{
radians = Math.atan2(eX - sX, eY - sY);
vX = Math.sin(radians) * speed;
vY = Math.cos(radians) * speed;
}
var time2 = new Date();
trace(time2 - time1);
var sX:Number = 24.2, sY:Number = 18.1, eX:Number = 158.9, eY:Number = -29.8;
var radians:Number;
var vX:Number;
var vY:Number;
var speed:Number = 10;
var time1 = new Date();
for(i = 0; i < 5000000; i ++)
{
radians = Math.atan2(eX - sX, eY - sY);
vX = Math.sin(radians) * speed;
vY = Math.cos(radians) * speed;
}
var time2 = new Date();
trace(time2 - time1);
This took 2231 milliseconds to process.
Now the basic math function:
var i:int = 0;
var sX:Number = 24.2, sY:Number = 18.1, eX:Number = 158.9, eY:Number = -29.8;
var sRatio:Number;
var cRatio:Number;
var vX:Number;
var vY:Number;
var avX:Number;
var avY:Number;
var speed:Number = 10;
var time1 = new Date();
for(i = 0; i < 5000000; i ++)
{
vX = eX - sX;
vY = eY - sY;
if(vX < 0) avX = vX * -1;
else avX = vX;
if(vY < 0) avY = vY * -1;
else avY = vY;
if(avX > avY)
{
sRatio = speed / avX;
cRatio = avY / avX * 0.43 + 1;
}
else
{
sRatio = speed / avY;
cRatio = avX / avY * 0.43 + 1;
}
vX = vX * sRatio / cRatio;
vY = vY * sRatio / cRatio;
}
var time2 = new Date();
trace(time2 - time1);
var sX:Number = 24.2, sY:Number = 18.1, eX:Number = 158.9, eY:Number = -29.8;
var sRatio:Number;
var cRatio:Number;
var vX:Number;
var vY:Number;
var avX:Number;
var avY:Number;
var speed:Number = 10;
var time1 = new Date();
for(i = 0; i < 5000000; i ++)
{
vX = eX - sX;
vY = eY - sY;
if(vX < 0) avX = vX * -1;
else avX = vX;
if(vY < 0) avY = vY * -1;
else avY = vY;
if(avX > avY)
{
sRatio = speed / avX;
cRatio = avY / avX * 0.43 + 1;
}
else
{
sRatio = speed / avY;
cRatio = avX / avY * 0.43 + 1;
}
vX = vX * sRatio / cRatio;
vY = vY * sRatio / cRatio;
}
var time2 = new Date();
trace(time2 - time1);
This only took 227 milliseconds to process, or about 10% of the time.
Depending on your game, the performance difference may not be noticeable. But if you're creating lots of new vectors every frame the less accurate function may result in some performance improvements. As with most things, there is a trade-off between accuracy and speed. I hope this will help someone.
Update:
I decided to try a more realistic comparison between these two methods, as I wasn't seeing much change in my game despite hundreds of new vectors being created per frame at times. Here are the results of my new test, which uses fewer iterations but does more per iteration:
The trig method returned 667 milliseconds in this test:
var i:int = 0;
var radians:Number;
var myVector:Array;
var time1 = new Date();
for(i = 0; i < 500000; i ++)
{
myVector = vector(58.11, 38.29, -29.1, -9.88, 200);
}
var time2 = new Date();
trace(time2 - time1);
function vector(sX:Number, sY:Number, eX:Number, eY:Number, speed:Number):Array
{
radians = Math.atan2(eX - sX, eY - sY);
return [Math.sin(radians) * speed, Math.cos(radians) * speed];
}
var radians:Number;
var myVector:Array;
var time1 = new Date();
for(i = 0; i < 500000; i ++)
{
myVector = vector(58.11, 38.29, -29.1, -9.88, 200);
}
var time2 = new Date();
trace(time2 - time1);
function vector(sX:Number, sY:Number, eX:Number, eY:Number, speed:Number):Array
{
radians = Math.atan2(eX - sX, eY - sY);
return [Math.sin(radians) * speed, Math.cos(radians) * speed];
}
And the basic math method returned 448 milliseconds:
var i:int = 0;
var sRatio:Number, cRatio:Number, vX:Number, vY:Number, avX:Number, avY:Number;
var myVector:Array;
var time1 = new Date();
for(i = 0; i < 500000; i ++)
{
myVector = vector(58.11, 38.29, -29.1, -9.88, 200);
}
var time2 = new Date();
trace(time2 - time1);
function vector(sX:Number, sY:Number, eX:Number, eY:Number, speed:Number):Array
{
vX = eX - sX;
vY = eY - sY;
if(vX < 0) avX = vX * -1;
else avX = vX;
if(vY < 0) avY = vY * -1;
else avY = vY;
if(avX > avY)
{
sRatio = speed / avX;
cRatio = avY / avX * 0.43 + 1;
}
else
{
sRatio = speed / avY;
cRatio = avX / avY * 0.43 + 1;
}
return [vX * sRatio / cRatio, vY * sRatio / cRatio];
}
var sRatio:Number, cRatio:Number, vX:Number, vY:Number, avX:Number, avY:Number;
var myVector:Array;
var time1 = new Date();
for(i = 0; i < 500000; i ++)
{
myVector = vector(58.11, 38.29, -29.1, -9.88, 200);
}
var time2 = new Date();
trace(time2 - time1);
function vector(sX:Number, sY:Number, eX:Number, eY:Number, speed:Number):Array
{
vX = eX - sX;
vY = eY - sY;
if(vX < 0) avX = vX * -1;
else avX = vX;
if(vY < 0) avY = vY * -1;
else avY = vY;
if(avX > avY)
{
sRatio = speed / avX;
cRatio = avY / avX * 0.43 + 1;
}
else
{
sRatio = speed / avY;
cRatio = avX / avY * 0.43 + 1;
}
return [vX * sRatio / cRatio, vY * sRatio / cRatio];
}
The basic math method is still faster, but it isn't as stark of a difference as illustrated before. This is because there is now more going on, including some additional variable initialization, which narrows the gap. The test is more real-world now than before, and it shows that the difference between these two methods isn't as big when you factor in initialization and other things that have a greater impact on performance.
| Series | ActionScript 3 Tutorials |
|---|---|
| Tags | actionscript 3 tutorial |