Have I found a new more efficient angle-finder?

Game Mechanics
#1

I may have just thought of something big that would get rid of a lot of lag in some projects. I do not know if people use this method a lot for enemy ai:


float dx = x2 - x1;
float dy = y2 - y1;
double h = Math.sqrt(dx * dx + dy * dy);
float dn = (float) (h / 1.41421);

vector2f.set(dx / dn, dy / dn);

Very random, I know, but basically it gives a vector2f to the next point. The sqrt methods take up a lot of memory(Is that what you call it?). So then I remembered in graphs at school, we use y2-y1/x2-x1 to get the slope. I thought about how this could be geometry. The slope formula could be multiplied by the speed, and added to x, and the reverse slope formula (x2-x1/y2-y1) to add to the y. This would get rid of a lot of sqrt methods. So I will test this:


float dx = x2 - x1;
float dy = y2 - y1;

Vector2f.set(dy/dx, dx/dy);

And they just spazz out. Why does this not work?
P.S. I tried dampening all the variables, and still no die.

#2

Not a good method, because slope is a ratio. If you want to move from (0,0) to (50, 50) then no problem, slope of one. However, let’s say you want to move from (0,0) to (37, 24), in which case slope is 37/24. You basically jump 37 x and 24 y pixels, compared to before where it was one each.

#3

Try to name the topic of your thread so that one actually knows what its about D:

#4

I’m not sure I completely understand what you were trying to do, but it sounds like you’re looking for a faster/less memory intensive Math.sqrt(). If that’s the case, you can use a Taylor expansion series to come up with a close approximation that’s much less resource intensive. For example, the Taylor expansion series for Math.sqrt(x) where x is close to 0 is x-x^3/6+x^5/120+O(x^7).

If you’d like to fiddle with this or another Taylor expansion series, take a look at http://www.wolframalpha.com/input/?i=Taylor+expansion+for+f(x)+%3D+sqrt(x)+centered+at+a%3D0

#5

If either dx or dy is equal to zero, which is actually a common case, it results in division by zero. It’s actually only returning the right values when abs(dx)==abs(dy). So, no, you didn’t come up with something useful :slight_smile:

#6

It still wouldn’t always work. If dx or dy was 0, you would get a divide by zero error.

#7

So in your example the slope is 15/10 = 1.5.
Now let’s say speed is 10.
10 * (15/10) = 15
10 * (10/15) = 6.67

sqrt(15^2 + 6.67^2) = 16.41
6.67/15 = 0.44

So you are moving a distance of 16.41 with a slope of 0.44 even though the speed is 10 and the slope was 1.5.

#8

It’s usually bad form to have a check for specific edge cases in what should be a purely mathematical calculation. Also, doing so is not what you want if you are looking for performance.
Here is the formal calculation:

Vector2f dir = new Vector2f(x2 - x1, y2 - y1);
dir.divide(dir.magnitude()) //makes dir into a unit vector(important)
dir.multiply(speed);
//dir is now in the proper direction (dy/dx) and the correct length (speed)
object.moveBy(dir);

Vector2f.magnitude() is the same as Math.sqrt(dir.x * dir.x + dir.y * dir.y), so you’re not going to avoid that.

Ninja edit: Really, sqrts arn’t going to be you’re bottleneck for pretty much anything.

#9

I’m not really seeing why you have to use sqrt in the first place…shouldn’t angle calculation be a simple dx, dy, atan2, rotate vector?

#10

That would be the trig route, which is fine, but then I’m not sure which is more expensive, atans or sqrts?
Benchmark time! Unless it’s already been proven?

#11

Good point there, guess trig route just makes more sense to me.

#12

[quote=“wesley.laferriere”]
Before you go any further, I’d highly suggest that you determine if the code in question is actually a CPU bottleneck using a tool like visualvm (i’m guessing it is not). This will also allow you to see how well any optimizations you make actually improve things.

If it does end up being a bottle neck, then I suggest replacing it with either the shortest possible Taylor expansion, or a lookup table with linear interpolation if you can afford the memory overhead.

#13

Well, it is a nice gesture, but it just doesn’t work. Multiplying the speed by the slope is something I’ve been playing around with a lot when I was designing games for 4K. The problem about multiplying speed by slope is that it does not equate to a “normalized” distance. You can see this if you look closely at this explosion algorithm I used.


...

g.fillOval(ex[i+1], ex[i+2]-ex[i+3], 7, 7);
g.fillOval(ex[i+1]-ex[i+3], ex[i+2]-ex[i+3], 7, 7);
g.fillOval(ex[i+1], ex[i+2]+ex[i+3], 7, 7);
g.fillOval(ex[i+1]-ex[i+3], ex[i+2]+ex[i+3], 7, 7);
g.fillOval(ex[i+1]+ex[i+3], ex[i+2], 7, 7);  
g.fillOval(ex[i+1]+ex[i+3], ex[i+2]-ex[i+3], 7, 7);
g.fillOval(ex[i+1]-ex[i+3], ex[i+2], 7, 7);      			
g.fillOval(ex[i+1]+ex[i+3], ex[i+2]+ex[i+3], 7, 7);

...

[i]I guess I have to explain that…

ex[i+1] and ex[i+2] are the x and y coordinates respectively
ex[i+3] is the speed (a.k.a. slope) created by adding the vectors.

These line create a circular explosion using a method similar to the one described in the first post.[/i]

You can get a value that will be close to the distance, but it won’t be exactly the distance. The distance formula NEEDS trig or sqrt (which is used in the Pythagorean theorem anyway… also trig). To get the exact distance for any movement.

If you try to do it by slope, you have to estimate the speed when moving at angles. You will be off a little bit each step… and that can get really ugly if the distance traveled by bullets is large. How do you check if your distances are correct… Trig.

In other words, it might work for small calculations. My whole system for my 4K game revolved around this concept of using slopes to calculate speeds (and you can be the judge to see if it ruined the game play). However, for that game, I did not have to worry too much about accuracy of the speed or angles. Any game that has to worry about accuracy will need to use trig, no question.

#14

My tests tells me that sqrt() is faster but you’d still need the angles to draw your oriented sprites so I’d go for the trig route.