It is currently Wed Dec 04, 2013 10:39 pm

 All times are UTC

 Page 1 of 1 [ 15 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: Shortest path between two rotationsPosted: Wed Nov 10, 2010 11:58 pm
 Harmlessness does no harm

Joined: Tue Sep 14, 2004 8:37 pm
Posts: 3913
Location: Ferriday, LA, US
Howdy!

I'm working on my game and am having problems figuring out how to determine which direction to turn an enemy ship so that it moves toward the player. Basically, I get the angle between the player and the enemy ship with atan2(). Then I want to take that, factor in the current angle of the ship, and determine whether the path is shorter between the two angles is clockwise or counter-clockwise. Positive turnSpeed turns the ship clockwise; negative values turn the ship counter-clockwise.

Here's what I have:

Code:
//Initialize enemy ship's turning speed
enemy_ship.turnSpeed = 0;

//Find the angle between the player and the enemy ship in radians
targetAngle = Math.atan2(player.y - enemy_ship.y, player.x - enemy_ship.x);

//If it's faster to meet the target angle by turning CW, set turnSpeed to positive value
//If it's faster to go CCW, set turnspeed to negative value

// <---Magical algorithm goes here!

enemy_ship.angle += turnSpeed;

That magical algorithm is really stumping me. Any help sorting this out is welcome.

_________________
What most people don't understand about "enlightenment" is that it is not an end-goal; but where you find yourself just before taking a new "first step."

Top

 Post subject: Posted: Thu Nov 11, 2010 1:08 am
 Elder Statesperson

Joined: Thu Mar 09, 2006 5:15 pm
Posts: 217
Location: Wellington, New Zealand
I think this snippet (pulled out of a quick java test) should do the trick.
Code:
//shift angles to be in range 0 - 360
currentAngle = currentAngle % 360;
targetAngle = targetAngle % 360;

//Get difference between angles
float angle = Math.abs(currentAngle - targetAngle) % 360;

//If its more than halfway round go backward
//----------------------------------------
// Set turnspeed
if (angle > 180) {
//turn forwards
} else {
//turn backwards
}
//---------------OR----------------------
// Adjust angle to get the amount to turn

if (angle > 180) angle = -360 + angle;

Assuming degrees in the range 0-360 (unlike stupid Flash's -180 to 180).

Hope it works!

_________________
www.littlemonkey.co.nz

Top

 Post subject: Posted: Thu Nov 11, 2010 11:07 am
 Corpse Bride

Joined: Tue Jul 01, 2008 11:44 pm
Posts: 2221
Location: England
If you want some theory, I'll give you that.

The basic idea is to measure the distance to turn each way, and choose whichever is the shortest.

(Assuming +ve is clockwise)

Let D = targetangle - angle
clockwise turning distance C = (D) modulo 360 = D%360
anticlockwise turning distance A = (-D) modulo 360 = (-D)%360

And whichever is smallest we go that way.

Code:
D = targetangle - angle
Direction = SGN( (-D)%360 - D%360 )

(where 1=clockwise, -1=anticlockwise.)

Another way of looking at it is like this:

If D is between -180 and 0, then C=D+360 which is between 180 and 360.
Meanwhile A= -D which is between 0 and 180. Therefore A<C and we go anticlockwise.

If D is between -360 and -180, then C=D+360 which is between 0 and 180.
Meanwhile A= -D which is between 180 and 360. Therefore C<A and we go clockwise.

If D is between 0 and 180 then C=D, while A=360-D which is between 180 and 360. Therefore C<A and we go clockwise.

If D is between 180 and 360 then C=D, while A=360-D which is between 0 and 180. Therefore A<C and we go anticlockwise.

That logic can be written like this:

Code:
D = targetangle - angle
Direction = (D>0) XOR (ABS(D)>180)

(where 1=clockwise, 0=anticlockwise.)

_________________
I ain't pushing no moon buttons.

Top

 Post subject: Re: Shortest path between two rotationsPosted: Thu Nov 11, 2010 11:22 am
 Corpse Bride

Joined: Tue Jul 01, 2008 11:44 pm
Posts: 2221
Location: England
Also, you don't need to calculate any angles.

You can use the vector cross product to determine which way to move.

Suppose ship is at position (x, y)
Suppose target point is at position (tx, ty)
Suppose the ship is currently pointing along vector (rx, ry)

Calculate displacement:
dx = tx - x
dy = ty - y

Do cross product:
CP = dx * ry - dy * rx

If CP>0, you go one way, if CP<0 you go the other way...

Direction = SGN(dx*ry - dy*rx)

Hope that helps.

_________________
I ain't pushing no moon buttons.

Top

 Post subject: Re: Shortest path between two rotationsPosted: Thu Nov 11, 2010 11:58 am
 Harmlessness does no harm

Joined: Tue Sep 14, 2004 8:37 pm
Posts: 3913
Location: Ferriday, LA, US
Jasmine wrote:
Also, you don't need to calculate any angles.

You can use the vector cross product to determine which way to move.

Suppose ship is at position (x, y)
Suppose target point is at position (tx, ty)
Suppose the ship is currently pointing along vector (rx, ry)

Calculate displacement:
dx = tx - x
dy = ty - y

Do cross product:
CP = dx * ry - dy * rx

If CP>0, you go one way, if CP<0 you go the other way...

Direction = SGN(dx*ry - dy*rx)

Hope that helps.

I'm not using vectors, just an X, Y coordinate and an angle. How do I get rx/ry without resorting to vectors?

Also, what does the function SGN() represent?

_________________
What most people don't understand about "enlightenment" is that it is not an end-goal; but where you find yourself just before taking a new "first step."

Top

 Post subject: Posted: Thu Nov 11, 2010 12:02 pm
 Corpse Bride

Joined: Tue Jul 01, 2008 11:44 pm
Posts: 2221
Location: England
Well you would use cos and sin

But it depends on where you're measuring angles from

If angle = 0 corresponds with the +y axis, then this would work:

Code:
rx = sin(angle)
ry = cos(angle)

dx = tx - x
dy = ty - y

TurnDirection = SGN(dx * ry - dy * rx)

You are probably calculating sin and cos already to get components of velocity/acceleration.

SGN is the sign function.

_________________
I ain't pushing no moon buttons.

Top

 Post subject: Posted: Thu Nov 11, 2010 12:20 pm
 Harmlessness does no harm

Joined: Tue Sep 14, 2004 8:37 pm
Posts: 3913
Location: Ferriday, LA, US
Jasmine wrote:
Code:
rx = sin(angle)
ry = cos(angle)

dx = tx - x
dy = ty - y

TurnDirection = SGN(dx * ry - dy * rx)

Doing this:

Code:
rx = cos(angle)
ry = sin(angle)

Instead. It works now (finally!!!). Thanks so much!

Is SGN a common function in programming languages? I'd never heard of it before. If it's a general function in math, well, you have to remember that my math IQ is below zero.

_________________
What most people don't understand about "enlightenment" is that it is not an end-goal; but where you find yourself just before taking a new "first step."

Top

 Post subject: Posted: Thu Nov 11, 2010 1:00 pm
 Corpse Bride

Joined: Tue Jul 01, 2008 11:44 pm
Posts: 2221
Location: England
theraje wrote:
Code:
rx = cos(angle)
ry = sin(angle)

Instead. It works now (finally!!!). Thanks so much!

okay, but you know that measures angles anticlockwise?

Quote:
Is SGN a common function in programming languages? I'd never heard of it before.

Yes it's a common math function. But Java likes latin, and calls it 'signum'.

Java signum dolor sit.

_________________
I ain't pushing no moon buttons.

Top

 Post subject: Posted: Thu Nov 11, 2010 1:06 pm
 Harmlessness does no harm

Joined: Tue Sep 14, 2004 8:37 pm
Posts: 3913
Location: Ferriday, LA, US
Anti-clockwise? Hmm... strange. Maybe that's the HTML5 canvas or JavaScript doing that, but it could just as easily be something I'm doing somewhere else. Weird.

JavaScript doesn't have a function similar to signum or sgn, as far as I know. I might have just missed it (I have a book that references all the methods and properties in the Math library, but it is a bit old).

_________________
What most people don't understand about "enlightenment" is that it is not an end-goal; but where you find yourself just before taking a new "first step."

Top

 Post subject: Posted: Thu Nov 11, 2010 1:27 pm
 Corpse Bride

Joined: Tue Jul 01, 2008 11:44 pm
Posts: 2221
Location: England
Oh I know now... it's because the axes of the screen are left handed (+y is downward), so clockwise and anticlockwise appear to be switched.

You could write your own SGN function.
Code:
function sgn(x){
if(x>0)return 1;
else if(x<0)return -1;
else return 0;
}

_________________
I ain't pushing no moon buttons.

Top

 Post subject: Posted: Thu Nov 11, 2010 2:56 pm
 Harmlessness does no harm

Joined: Tue Sep 14, 2004 8:37 pm
Posts: 3913
Location: Ferriday, LA, US
Jasmine wrote:
Oh I know now... it's because the axes of the screen are left handed (+y is downward), so clockwise and anticlockwise appear to be switched.

Oh yeah! That makes perfect sense. Not sure why none of us had thought about that sooner.

_________________
What most people don't understand about "enlightenment" is that it is not an end-goal; but where you find yourself just before taking a new "first step."

Top

 Post subject: Posted: Thu Nov 11, 2010 11:19 pm
 Corpse Bride

Joined: Tue Jul 01, 2008 11:44 pm
Posts: 2221
Location: England
Jasmine wrote:
Java likes latin

Now this got me thinking, what would a programming language be like if all of it's keywords were in Latin?

Code:
Usura Systematis;
Usura Systematis.Callatim.Imperator

nomen GPWiki
{
publica genus Factory<TKey, TBase>
{
secreto delegato TBase CreoTractandi();

Lexicon<TKey, CreoTractandi> _Proventus = novum Lexicon<TKey, CreoTractandi>();

publica vacuum Registri<T>(TKey key) ubi T : TBase, novum()
{
}
publica TBase Creat(TKey key)
{
reditum _Creat[key]();
}

secreto TBase Molitor<T>() ubi T : TBase, novum()
{
reditum novum T();
}
}
}

_________________
I ain't pushing no moon buttons.

Top

 Post subject: Posted: Fri Nov 12, 2010 2:32 am
 Elder Statesperson

Joined: Thu Mar 09, 2006 5:15 pm
Posts: 217
Location: Wellington, New Zealand
Quote:
Now this got me thinking, what would a programming language be like if all of it's keywords were in Latin?

You do think of the strangest things Jasmine, though I admire your dedication to following through.

_________________
www.littlemonkey.co.nz

Top

 Post subject: Posted: Fri Nov 12, 2010 12:24 pm
 Corpse Bride

Joined: Tue Jul 01, 2008 11:44 pm
Posts: 2221
Location: England
I feel that new ways of looking at things or combining things is good. Exploring possibilities is the force behind creativity, the imagination, invention, and the intellect. "what if" makes life interesting.

_________________
I ain't pushing no moon buttons.

Top

 Post subject: Posted: Mon Nov 15, 2010 5:41 pm
 Level 22 Norse Warrior-Librarian

Joined: Mon Sep 04, 2006 5:25 pm
Posts: 517
Location: U.S.
Hahaha, that's awesome, Jasmine!

_________________
Worlds at War (Current Project) - http://www.awkward-games.com
Ganadu'r, The Eternal Sage (Other Current Project) - http://rpg.naget.com
Programming tutorials and web-design services: http://www.wyrmmage.com

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 15 posts ]

 All times are UTC

#### Who is online

Users browsing this forum: No registered users and 1 guest

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forum

Search for:
 Jump to:  Select a forum ------------------ Forums    Forum Rules and Posting Guidelines Wiki Discussion    Help    Content Issues Game Programming Discussion    C and C++ Game Programming    Java Game Programming    Language Agnostic Programming    .NET Game Programming    VB Game Programming    Mobile Game Programming    Web-Based Game Programming    Other Languages    OpenGL Development    Direct X Development Game Development Discussion    Game Design    Game Media Off-Topic Discussion    Announcements    Off-Topic    Community Projects    News