Java-Gaming.org    
Featured games (91)
games approved by the League of Dukes
Games in Showcase (581)
games submitted by our members
Games in WIP (500)
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 1560 times)
0 Members and 1 Guest are viewing this topic.
Offline wessles

JGO Ninja


Medals: 49
Projects: 4
Exp: 3 years


Coding with bad posture since 2011... Nonstop.


« Posted 2013-06-18 21: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.

You don't know nerdiness yet; you haven't even met me!
www.wessles.com
Offline Jimmt
« League of Dukes »

JGO Kernel


Medals: 114
Projects: 4
Exp: 3 years



« Reply #1 - Posted 2013-06-18 22: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.
Offline wessles

JGO Ninja


Medals: 49
Projects: 4
Exp: 3 years


Coding with bad posture since 2011... Nonstop.


« Reply #2 - Posted 2013-06-18 22: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)

You don't know nerdiness yet; you haven't even met me!
www.wessles.com
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Cero
« Reply #3 - Posted 2013-06-18 22:39:19 »

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

Offline wessles

JGO Ninja


Medals: 49
Projects: 4
Exp: 3 years


Coding with bad posture since 2011... Nonstop.


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

K, I'll do it.

You don't know nerdiness yet; you haven't even met me!
www.wessles.com
Offline joen

Senior Newbie


Projects: 1



« Reply #5 - Posted 2013-06-18 23: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

Offline wessles

JGO Ninja


Medals: 49
Projects: 4
Exp: 3 years


Coding with bad posture since 2011... Nonstop.


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

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

You don't know nerdiness yet; you haven't even met me!
www.wessles.com
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 605
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #7 - Posted 2013-06-18 23: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 Smiley

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline wessles

JGO Ninja


Medals: 49
Projects: 4
Exp: 3 years


Coding with bad posture since 2011... Nonstop.


« Reply #8 - Posted 2013-06-18 23: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?

You don't know nerdiness yet; you haven't even met me!
www.wessles.com
Offline Longarmx
« Reply #9 - Posted 2013-06-19 00: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!
Legends of Yore - The Casual Retro Roguelike
Offline DrZoidberg

Senior Member


Medals: 10



« Reply #10 - Posted 2013-06-19 00: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.
Offline wessles

JGO Ninja


Medals: 49
Projects: 4
Exp: 3 years


Coding with bad posture since 2011... Nonstop.


« Reply #11 - Posted 2013-06-19 00: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...

You don't know nerdiness yet; you haven't even met me!
www.wessles.com
Offline wessles

JGO Ninja


Medals: 49
Projects: 4
Exp: 3 years


Coding with bad posture since 2011... Nonstop.


« Reply #12 - Posted 2013-06-19 00: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.

You don't know nerdiness yet; you haven't even met me!
www.wessles.com
Offline BurntPizza
« Reply #13 - Posted 2013-06-19 00: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.
Offline Jimmt
« League of Dukes »

JGO Kernel


Medals: 114
Projects: 4
Exp: 3 years



« Reply #14 - Posted 2013-06-19 00: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?
Offline BurntPizza
« Reply #15 - Posted 2013-06-19 00: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?
Offline wessles

JGO Ninja


Medals: 49
Projects: 4
Exp: 3 years


Coding with bad posture since 2011... Nonstop.


« Reply #16 - Posted 2013-06-19 00: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);


You don't know nerdiness yet; you haven't even met me!
www.wessles.com
Offline Jimmt
« League of Dukes »

JGO Kernel


Medals: 114
Projects: 4
Exp: 3 years



« Reply #17 - Posted 2013-06-19 00: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.
Offline joen

Senior Newbie


Projects: 1



« Reply #18 - Posted 2013-06-19 00: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.

Offline ctomni231

JGO Ninja


Medals: 71
Projects: 1
Exp: 7 years


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


« Reply #19 - Posted 2013-06-19 00: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.

Offline wessles

JGO Ninja


Medals: 49
Projects: 4
Exp: 3 years


Coding with bad posture since 2011... Nonstop.


« Reply #20 - Posted 2013-06-19 02: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

You don't know nerdiness yet; you haven't even met me!
www.wessles.com
Offline relminator
« Reply #21 - Posted 2013-06-19 04: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.
Offline wessles

JGO Ninja


Medals: 49
Projects: 4
Exp: 3 years


Coding with bad posture since 2011... Nonstop.


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

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

You don't know nerdiness yet; you haven't even met me!
www.wessles.com
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.

xsi3rr4x (53 views)
2014-04-15 18:08:23

BurntPizza (51 views)
2014-04-15 03:46:01

UprightPath (65 views)
2014-04-14 17:39:50

UprightPath (48 views)
2014-04-14 17:35:47

Porlus (65 views)
2014-04-14 15:48:38

tom_mai78101 (89 views)
2014-04-10 04:04:31

BurntPizza (149 views)
2014-04-08 23:06:04

tom_mai78101 (245 views)
2014-04-05 13:34:39

trollwarrior1 (203 views)
2014-04-04 12:06:45

CJLetsGame (210 views)
2014-04-01 02:16:10
List of Learning Resources
by SHC
2014-04-18 03:17:39

List of Learning Resources
by Longarmx
2014-04-08 03:14:44

Good Examples
by matheus23
2014-04-05 13:51:37

Good Examples
by Grunnt
2014-04-03 15:48:46

Good Examples
by Grunnt
2014-04-03 15:48:37

Good Examples
by matheus23
2014-04-01 18:40:51

Good Examples
by matheus23
2014-04-01 18:40:34

Anonymous/Local/Inner class gotchas
by Roquen
2014-03-11 15:22:30
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
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!