Java-Gaming.org Hi !
 Featured games (83) games approved by the League of Dukes Games in Showcase (521) Games in Android Showcase (127) games submitted by our members Games in WIP (589) 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 2099 times) 0 Members and 1 Guest are viewing this topic.
wessles

JGO Wizard

Medals: 74
Projects: 4
Exp: 4 years

 « 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: 138
Projects: 4
Exp: 3 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.
wessles

JGO Wizard

Medals: 74
Projects: 4
Exp: 4 years

 « Reply #2 - Posted 2013-06-18 20:28:42 »

Ah, but you miss that a ratio, say, of 1:2 is really 1 over 2, which is also 1/2, which is equal to .5. So If I multiply it, it should work. Say my speed per step is 2. The ratio is 1:3, which is really .3 repeating. so I multiply the ratio by 2, and I get approximately .6 repeating. Just look at it that way.
I.E.
x1 = 10
x2 = 20
y1 = 20
y2 = 35

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

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

Cero
 « Reply #3 - Posted 2013-06-18 20:39:19 »

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

wessles

JGO Wizard

Medals: 74
Projects: 4
Exp: 4 years

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

K, I'll do it.

joen

Senior Newbie

Projects: 1

 « Reply #5 - 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

wessles

JGO Wizard

Medals: 74
Projects: 4
Exp: 4 years

 « Reply #6 - Posted 2013-06-18 21:41:28 »

All those ^(means exponent, right?) would take up just as much memory as 2 divide and 2 multiplies, right?

Riven
« League of Dukes »

« JGO Overlord »

Medals: 829
Projects: 4
Exp: 16 years

 « Reply #7 - 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
wessles

JGO Wizard

Medals: 74
Projects: 4
Exp: 4 years

 « Reply #8 - Posted 2013-06-18 21:53:28 »

What if I don't use vectors? Just
 1  2 `x += speed * (dy / dx);y += speed * (dx / dy);`

And if it is zero, default to
 1  2 `x += speed * 1;y += speed * 1;`

Would that work?

Longarmx
 « Reply #9 - 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

Senior Devvie

Medals: 17

 « Reply #10 - 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.
wessles

JGO Wizard

Medals: 74
Projects: 4
Exp: 4 years

 « Reply #11 - Posted 2013-06-18 22:04:00 »

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

Ahem, you seem to have missed the following:
And if it is zero, default to...

wessles

JGO Wizard

Medals: 74
Projects: 4
Exp: 4 years

 « Reply #12 - Posted 2013-06-18 22:13:51 »

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.
Where did I say I am using the sqrt method? The whole point of this method(as in a way of working) was to get rid of all the sqrt methods. They are sucking up resources.

BurntPizza

« JGO Bitwise Duke »

Medals: 271
Exp: 5 years

 « Reply #13 - 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: 138
Projects: 4
Exp: 3 years

 « Reply #14 - 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: 271
Exp: 5 years

 « Reply #15 - 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?
wessles

JGO Wizard

Medals: 74
Projects: 4
Exp: 4 years

 « Reply #16 - Posted 2013-06-18 22:33:48 »

Well, this is getting big. Perhaps by popular demand, I should use sqrt after all. Any Ideas on how to optimize my original code?
Quote
 1  2  3  4 `float dx = x2 - x1;float dy = y2 - y1;double h = Math.sqrt(dx * dx + dy * dy);float dn = (float) (h / 1.41421);`

Jimmt
« League of Dukes »

JGO Kernel

Medals: 138
Projects: 4
Exp: 3 years

 « Reply #17 - 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 #18 - 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 #19 - 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.

wessles

JGO Wizard

Medals: 74
Projects: 4
Exp: 4 years

 « Reply #20 - Posted 2013-06-19 00:47:54 »

Thank you. For the lazies that skipped to the end:
Darn you.
And here is my analysis. Enemy AI is a precise thing, and as stated here,
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.
So, enemy AI + slope formulas = Bad Idea. Just use trig, or sqrt. Whatever anyone decides. CASE CLOSED

relminator
 « Reply #21 - 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.
wessles

JGO Wizard

Medals: 74
Projects: 4
Exp: 4 years

 « Reply #22 - Posted 2013-06-19 02:14:18 »

Thank you! You must have put a lot of time into it. Definetly will go trig.

Pages: [1]
 ignore  |  Print

You cannot reply to this message, because it is very, very old.

 Add your game by posting it in the WIP section, or publish it in Showcase. The first screenshot will be displayed as a thumbnail.
 xFryIx (55 views) 2014-11-13 12:34:49 digdugdiggy (34 views) 2014-11-12 21:11:50 digdugdiggy (29 views) 2014-11-12 21:10:15 digdugdiggy (23 views) 2014-11-12 21:09:33 kovacsa (46 views) 2014-11-07 19:57:14 TehJavaDev (50 views) 2014-11-03 22:04:50 BurntPizza (49 views) 2014-11-03 18:54:52 moogie (65 views) 2014-11-03 06:22:04 CopyableCougar4 (63 views) 2014-11-01 23:36:41 DarkCart (148 views) 2014-11-01 14:51:03
 theagentd 29x basil_ 27x BurntPizza 23x princec 17x Spasi 17x pitbuller 15x kpars 14x HeroesGraveDev 14x Riven 13x KevinWorkman 13x Grunnt 12x SHC 11x gouessej 11x kevglass 9x Longarmx 9x Nate 9x
 Understanding relations between setOrigin, setScale and setPosition in libGdx2014-10-09 22:35:00Definite guide to supporting multiple device resolutions on Android (2014)2014-10-02 22:36:02List of Learning Resources2014-08-16 10:40:00List of Learning Resources2014-08-05 19:33:27Resources for WIP games2014-08-01 16:20:17Resources for WIP games2014-08-01 16:19:50List of Learning Resources2014-07-31 16:29:50List of Learning Resources2014-07-31 16:26:06
 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