Java-Gaming.org Hi !
 Featured games (91) games approved by the League of Dukes Games in Showcase (757) Games in Android Showcase (229) games submitted by our members Games in WIP (844) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
Pages: [1]
 ignore  |  Print
 Have I found a new more efficient angle-finder?  (Read 9281 times) 0 Members and 1 Guest are viewing this topic.
wessles
 « Posted 2013-06-18 19:51:22 »

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:
 1  2  3  4  5  6 `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:

 1  2  3  4 `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.
Jimmt
« League of Dukes »

JGO Kernel

Medals: 167
Projects: 5
Exp: 6 years

 « Reply #1 - Posted 2013-06-18 20:17:55 »

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.
Cero
 « Reply #2 - Posted 2013-06-18 20:39:19 »

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

joen

Senior Newbie

Projects: 1

 « Reply #3 - Posted 2013-06-18 21:30:26 »

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%28x%29+%3D+sqrt%28x%29+centered+at+a%3D0

Riven

« JGO Overlord »

Medals: 1340
Projects: 4
Exp: 16 years

 « Reply #4 - Posted 2013-06-18 21:42:06 »

 1  2  3  4 `float dx = x2 - x1;float dy = y2 - y1;Vector2f.set(dy/dx, dx/dy);`

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

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
Longarmx
 « Reply #5 - Posted 2013-06-18 22:01:00 »

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

DrZoidberg

JGO Coder

Medals: 21

 « Reply #6 - Posted 2013-06-18 22:03:14 »

x1 = 10
x2 = 20
y1 = 20
y2 = 35

20-10 = 10
-----------
35 - 20 = 15

X+=speed * (15/10)
Y+=speed * (10/15)

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.
BurntPizza

« JGO Bitwise Duke »

Medals: 485
Exp: 7 years

 « Reply #7 - Posted 2013-06-18 22:14:04 »

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:
 1  2  3  4  5 `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.
Jimmt
« League of Dukes »

JGO Kernel

Medals: 167
Projects: 5
Exp: 6 years

 « Reply #8 - Posted 2013-06-18 22:19:15 »

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?
BurntPizza

« JGO Bitwise Duke »

Medals: 485
Exp: 7 years

 « Reply #9 - Posted 2013-06-18 22:21:25 »

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?

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?
Jimmt
« League of Dukes »

JGO Kernel

Medals: 167
Projects: 5
Exp: 6 years

 « Reply #10 - Posted 2013-06-18 22:35:20 »

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?

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?
Good point there, guess trig route just makes more sense to me.
joen

Senior Newbie

Projects: 1

 « Reply #11 - Posted 2013-06-18 22:45:36 »

Any Ideas on how to optimize my original code?

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.

ctomni231

JGO Wizard

Medals: 99
Projects: 1
Exp: 7 years

Not a glitch. Just have a lil' pixelexia...

 « Reply #12 - Posted 2013-06-18 22:55:03 »

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.

 1  2  3  4  5  6  7  8  9  10  11  12 `...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 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.

---------------------------------------------------------------------------------------------------------------

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.

relminator
 « Reply #13 - Posted 2013-06-19 02:06:34 »

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?

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?

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.
Pages: [1]
 ignore  |  Print

 EgonOlsen (42 views) 2018-06-10 19:43:48 EgonOlsen (22 views) 2018-06-10 19:43:44 EgonOlsen (43 views) 2018-06-10 19:43:20 DesertCoockie (197 views) 2018-05-13 18:23:11 nelsongames (124 views) 2018-04-24 18:15:36 nelsongames (123 views) 2018-04-24 18:14:32 ivj94 (863 views) 2018-03-24 14:47:39 ivj94 (125 views) 2018-03-24 14:46:31 ivj94 (768 views) 2018-03-24 14:43:53 Solater (140 views) 2018-03-17 05:04:08
 Java Gaming Resourcesby philfrei2017-12-05 19:38:37Java Gaming Resourcesby philfrei2017-12-05 19:37:39Java Gaming Resourcesby philfrei2017-12-05 19:36:10Java Gaming Resourcesby philfrei2017-12-05 19:33:10List of Learning Resourcesby elect2017-03-13 14:05:44List of Learning Resourcesby elect2017-03-13 14:04:45SF/X Librariesby philfrei2017-03-02 08:45:19SF/X Librariesby philfrei2017-03-02 08:44:05
 java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org