Avoiding Polar Projection

tooltiperror

Super Moderator
Reaction score
231
Normally, I would use a function like this in, say, JASS:

JASS:

function PolarProjectionBJ takes location source, real dist, real angle returns location
    local real x = GetLocationX(source) + dist * Cos(angle * bj_DEGTORAD)
    local real y = GetLocationY(source) + dist * Sin(angle * bj_DEGTORAD)
    return Location(x, y)
endfunction


The problem is, it uses [LJASS]Cos[/LJASS], [LJASS]Sin[/LJASS], and [LJASS]bj_DEGTORAD[/LJASS] which are all comparatively slow in JASS, the reason being natives and operations are pretty slow.

Is there way using vectors to do something better? I know Jesus4Lyf uses vectors for something similar to this, wanted to know how it could be done, and it'd be nice if someone could explain the math of it too.
 

Slapshot136

Divide et impera
Reaction score
471
degtorad shouldn't be any slower then just doing / 57.296 (180/pi), and I guess you could use the Pythagorean theorem for one of the sides to remove either the cos or the sin from the equation, but that probably won't be much faster
 

Darthfett

Aerospace/Cybersecurity Software Engineer
Reaction score
615
My first thoughts are that you're looking at the wrong place to optimize your game. That is the correct way to project. bj_DEGTORAD is a constant, so it can't be "slow". If you're wanting to avoid using it, then always work with Radians. However, I don't know of any way to project an arbitrary angle, without dealing with Cos and Sin. This is how vectors work in Cartesian coordinates, and an equivalent vector version of this would also have to use Cos and Sin.

Also, if you're actually using that BJ, I would recommend never using locations, except for the very rare case that a function requires it. Just use X and Y.
 

tooltiperror

Super Moderator
Reaction score
231
Actually, using [LJASS]bj_DEGTORAD[/LJASS] in place of inlining [LJASS](bj_PI/180)[/LJASS] is quicker, because a variable reference is faster than arithmetic. You're probably not saving much time if you only use bj_DEGTORAD once, but if you're using it in, say, 32 times a second, you're saving some processing power.

>I guess you could use the Pythagorean theorem for one of the sides to remove either the cos or the sin from the equation, but that probably won't be much faster
How would that look in code? You can use on of the C's if you don't know JASS or any other common language, and I can probably implement it in JASS easily.
 

Darthfett

Aerospace/Cybersecurity Software Engineer
Reaction score
615
As far as what Slapshot was saying in regards to the Pythagorean theorem:

Given:
angle theta,
distance d,

Find the X,Y components of the line of length x toward the angle theta.

Given that X and Y are orthogonal, we can use the Pythagorean theorem on the triangle, such that x^2 + y^2 = d^2

Here, you have to know one to get the other. Either way, you have to use a native, whether that's [ljass]Pow[/ljass], [ljass]SquareRoot[/ljass], [ljass]Sin[/ljass], or [ljass]Cos[/ljass].
 

s3rius

Linux is only free if your time is worthless.
Reaction score
130
The problem is, it uses [LJASS]Cos[/LJASS], [LJASS]Sin[/LJASS], and [LJASS]bj_DEGTORAD[/LJASS]

bj_DEGTORAD is a constant and very cheap to use.
But Cos and Sin are always relatively slow operations. There's a faster way of getting it:

Code:
float mag = sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
float sine = (y2 - y1) / mag;
float cosine = (x2 - x1) / mag;

Sin() and Cos() are approximating their values via an expensive loop. A call to sqrt() and a floating-point division are cheaper :3

Alternatively you could also make a lookup table where you store sine/cosine for every degree. Makes it even faster, but eats some memory. If you need to polar-project a lot then it's an option to consider.
 

saw792

Is known to say things. That is all.
Reaction score
280
Sin() and Cos() are approximating their values via an expensive loop. A call to sqrt() and a floating-point division are cheaper :3

Now that's going to need some serious proving.
 

monoVertex

I'm back!
Reaction score
460
I fail to see how the deg2rad bj is slow. As s3rius said, Cos and Sin are slow. If you don't care about memory cost, only about speed, use a lookup table, as already suggested.

I think it is the best method, I used it in a Flash experiment and it considerably cut down the serious lag that I was getting from using Sin and Cos. Of course, the speed of this method also depends on the level of precision you need, as a high one might get you in the same position as using Sin and Cos...
 

Slapshot136

Divide et impera
Reaction score
471
To use the Pythagorean theorem you need an angle of 90 degress which is not always the case.

if you are talking in terms of X from origin and Y from origin, then you have a 90º angle

you have distance (hypotenuse), use sin or cos for one of the legs, then do (dist^2-leg^2)^.5
 

s3rius

Linux is only free if your time is worthless.
Reaction score
130
Now that's going to need some serious proving.

Well, I'm not going to bother proving anything. But I can ramble on a bit.

A computer cannot directly calculate a sine/cosine value. It needs approximation (and does only return an approximate value in most cases). Just like square root needs to be approximated.

What I can tell you is that those functions are highly implementation-dependent. For some it could be calculated via the FPU(where, again, it could be calculated or stored as a lookup table. A lookup table could be enhanced with linear interpolation to make it smaller, but it not always is.
For others it'll be a software-only implementation.
And then there's a bunch of different methods to get the right numbers, but as far as I know CORDIC is one of the more popular.
But since there's no standard and no specification it could very well be that your software implementation uses the Tyler approximation or yet another lookup table.

Long story short - you never really know unless you look it up on your system. But on another person's system it can be something completely different.
So you don't really need test results. You have to prepare for worst-case scenario, which would be that your client machine uses the most slow-poke algorithm you've ever seen :)
 

SerraAvenger

Cuz I can
Reaction score
234
So you don't really need test results. You have to prepare for worst-case scenario, which would be that your client machine uses the most slow-poke algorithm you've ever seen :)

Given two options A and B, the worst case is that you're choosing the wrong one.
So you should actually look at the options before making any claims. And since you say you can't, don't make any claims.
 

s3rius

Linux is only free if your time is worthless.
Reaction score
130
Given two options A and B, the worst case is that you're choosing the wrong one.
So you should actually look at the options before making any claims. And since you say you can't, don't make any claims.

There are two cases and two choices. So 4 options:

Fast implementation and you depend on it = Good result
Slow implementation and you depend on it = Bad result
Fast implementation but you use your own = Good result, a few kb wasted memory
Slow implementation but you use your own = Good results.

(By using your own I mean not calculating tons and tons of sin/cos, but for example using a table)

As you can see, using your own will always yield positive results while depending on system implementation can put you in a bad spot.

I can't make a claim whether the implementation is slow or not, but I can claim that being on the save side is a good thing :)
(I can also claim that the implementation will hardly be faster than a lookup table)
 

saw792

Is known to say things. That is all.
Reaction score
280
I'm glad you understand, it just becomes misleading for people if you say things that can be interpreted as "sin and cos implementations are always slow". I also think that the results achieved from a GOOD hardware/efficient table/algorithm/whatever implementation are going to be significantly better than your own implementation. So while I support people trying their own implementation and seeing if it has an effect on their computer, in the vast majority of cases the native implementation is going to be superior to your implementation, resulting in a less-than-ideal result for the vast majority of users.
 

tooltiperror

Super Moderator
Reaction score
231
So ... would this be faster?

JASS:
//! zinc

library CoSlashSine {
	public real Sine[360];
	public real Cosine[360];

	function onInit() {
		i = 0;
		while (i<=360) {
			Sine<i> = Sin(i);
			Cosine<i> = Cos(i);
			i += 1;
		}
	}
}

//! endzinc
</i></i>
 

s3rius

Linux is only free if your time is worthless.
Reaction score
130
Of course it'll be faster since you're pre-calculating all values and you can re-use them.

On the other hand you'll lose a little bit of accuracy, because you'll not have the Sin of 33.5, but only of 33 and 34. But one degree of inaccuracy is hardly important for general purposes.
 

Romek

Super Moderator
Reaction score
963
Can anyone actually prove that Sin and Cos are 'slow' natives?
I've heard that they're almost as fast as an array read because internally, they do exactly what post #15 does, but with slightly higher accuracy.
 

s3rius

Linux is only free if your time is worthless.
Reaction score
130
Well, someone would have to speed-test them.

I can't - I don't have Warcraft installed anymore.
 

Bribe

vJass errors are legion
Reaction score
67
Cos and Sin would logically be at least a few times slower than a JASS array read because JASS constantly has to be interpreted before it can be executed, meaning lots and lots of string operations. We can assume JASS is never compiled beyond strings because otherwise ExecuteFunc or TriggerRegisterVariableEvent would do nothing, and why else would long variable names execute more slowly than short ones.
 

s3rius

Linux is only free if your time is worthless.
Reaction score
130
Cos and Sin would logically be at least a few times slower than a JASS array read because JASS constantly has to be interpreted before it can be executed, meaning lots and lots of string operations. We can assume JASS is never compiled beyond strings because otherwise ExecuteFunc or TriggerRegisterVariableEvent would do nothing, and why else would long variable names execute more slowly than short ones.

If I had to guess I'd say the functions are converted to internal "action-lists" that are stored by their function name or hash inside a map. It's way faster and less memory consuming than interpreting strings on-the-fly.
Long variable name r/w access being slower could be a cause of how the data is stored. If the var names are unhashed it can very well be.

Then again I'm not updated on the newest Jass discoveries. I'm out of business.
 
General chit-chat
Help Users
  • No one is chatting at the moment.

      The Helper Discord

      Members online

      No members online now.

      Affiliates

      Hive Workshop NUON Dome World Editor Tutorials

      Network Sponsors

      Apex Steel Pipe - Buys and sells Steel Pipe.
      Top