Java-Gaming.org Hi !
 Featured games (84) games approved by the League of Dukes Games in Showcase (570) Games in Android Showcase (154) games submitted by our members Games in WIP (619) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
 Home Help Search Login Register
Pages: [1]
 ignore  |  Print
 Have I found a new more efficient angle-finder?  (Read 2628 times) 0 Members and 1 Guest are viewing this topic.
wessles

JGO Kernel

Medals: 114
Projects: 4
Exp: 3 years

Enthusiast of amusement. Lover of code.

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

Check out my twitter to hear more about RFLEX. My Twitter
Jimmt
« League of Dukes »

JGO Kernel

Medals: 159
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 Kernel

Medals: 114
Projects: 4
Exp: 3 years

Enthusiast of amusement. Lover of code.

 « 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)

Check out my twitter to hear more about RFLEX. My Twitter
 Games published by our own members! Check 'em out!
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 Kernel

Medals: 114
Projects: 4
Exp: 3 years

Enthusiast of amusement. Lover of code.

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

K, I'll do it.

Check out my twitter to hear more about RFLEX. My Twitter
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 Kernel

Medals: 114
Projects: 4
Exp: 3 years

Enthusiast of amusement. Lover of code.

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

Check out my twitter to hear more about RFLEX. My Twitter
Riven
« League of Dukes »

« JGO Overlord »

Medals: 953
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 Kernel

Medals: 114
Projects: 4
Exp: 3 years

Enthusiast of amusement. Lover of code.

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

Check out my twitter to hear more about RFLEX. My Twitter
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.

 Games published by our own members! Check 'em out!
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 Kernel

Medals: 114
Projects: 4
Exp: 3 years

Enthusiast of amusement. Lover of code.

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

Check out my twitter to hear more about RFLEX. My Twitter
wessles

JGO Kernel

Medals: 114
Projects: 4
Exp: 3 years

Enthusiast of amusement. Lover of code.

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

Check out my twitter to hear more about RFLEX. My Twitter
BurntPizza

« JGO Bitwise Duke »

Medals: 370
Exp: 6 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: 159
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: 370
Exp: 6 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 Kernel

Medals: 114
Projects: 4
Exp: 3 years

Enthusiast of amusement. Lover of code.

 « 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);`

Check out my twitter to hear more about RFLEX. My Twitter
Jimmt
« League of Dukes »

JGO Kernel

Medals: 159
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 Kernel

Medals: 114
Projects: 4
Exp: 3 years

Enthusiast of amusement. Lover of code.

 « 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

Check out my twitter to hear more about RFLEX. My Twitter
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 Kernel

Medals: 114
Projects: 4
Exp: 3 years

Enthusiast of amusement. Lover of code.

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

Check out my twitter to hear more about RFLEX. My Twitter
Pages: [1]
 ignore  |  Print

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

 Riven (23 views) 2015-04-16 10:48:47 Duke0200 (36 views) 2015-04-16 01:59:01 Fairy Tailz (27 views) 2015-04-14 20:13:12 Riven (29 views) 2015-04-12 21:36:37 bus hotdog (46 views) 2015-04-10 02:39:32 CopyableCougar4 (48 views) 2015-04-10 00:51:04 BurntPizza (48 views) 2015-04-06 22:06:58 ags1 (51 views) 2015-04-02 10:58:48 Riven (49 views) 2015-04-01 18:27:05 ags1 (67 views) 2015-03-31 10:55:12
 BurntPizza 24x theagentd 21x wessles 15x Rayvolution 12x 65K 11x kingroka123 11x alwex 10x KevinWorkman 9x kevglass 8x ra4king 8x phu004 8x SHC 7x Olo 7x Ecumene 7x chrislo27 7x Roquen 7x
 How to: JGO Wikiby Mac702015-02-17 20:56:162D Dynamic Lighting2015-01-01 20:25:42How do I start Java Game Development?by gouessej2014-12-27 19:41:21Resources for WIP gamesby kpars2014-12-18 10:26:14Understanding 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:27
 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