For a while I've been trying to use a polar coordinate system to do movement calculations for a game. Partially because I though it would be more elegant and I also wanted a more difficult control scheme and had an idea for doing so that seemed suited to polar coordinates. Primarily the elegance would come from having immediate access to the vector's magnitude in polar coordinates without the need to do a square root to calculate it as when you use Cartesian coordinates.
Here's a small demo of what the movement will feel like when implemented. The red dot would be the player, you can see the current direction he's accelerating in from the white line in it and the black line is the speed vector. Use the arrow keys. Here's the code.
In older games it was often that when running forwards and strafing the resultant diagonal speed was higher than just running forwards. This is because while it's easy to limit the speed from a single key press, you cannot limit a vector's magnitude without doing a square root which is a relatively expensive operation, especially in ye olden days.
Quake had a novel way of calculating the speed's magnitude by taking the dot product between the speed vector and the "wish" vector that describes where the player wanted to go. As the wish vector was a unit vector this would give a reasonable approximation of the speed's magnitude but only so long as both vectors were pointing in about the same direction. This is what allows for strafe jumping. Whether this was done to avoid doing a square root or if there's some other reason behind it I haven't been able to find out.
So in polar coordinates the vector is described as an angle and a magnitude around a center from which it's pointing instead of x and y coordinates like in a Cartesian system. That's a model that lends itself fairly well to games, a lot of the time it's more natural to express things like the speed of a character and where it's pointing as an angle and so not having to convert this angle back and forth to Cartesian would be beneficial.
Having the magnitude be part of the vector also means that there's no need to do a square root and you also won't have to do some divisions for the components of the vector. Instead you just check what the number is and limit it if it's too large.
fig 2 The red vector can be described by it's angle and magnitude. Here the only two numbers we'd need to know about it is that it has a magnitude of 2.4 and an angle of 47 degrees. In a Cartesian system it would be described using x and y coordinates for its end point.
The problem is how to interpolate between two polar vector. Say you have your current speed vector and then apply an acceleration vector to your character. Then you want the speed vector to shift slightly each frame until it's aligned with the acceleration vector and have the same magnitude as it and you want to do so without having to convert the vectors to Cartesian.
fig 3 The speed is represented by the red line and the current acceleration is the blue one. We want to make the speed change smoothly until it's aligned with the acceleration.
fig 4 Something like this. Each frame would result in a new speed vector that sweeps towards the acceleration vector.
accelerationPercent = 1 - speed / TOP_SPEED
TOP_SPEED is some fixed number we've decided on that we don't want the speed to exceed. Now, if out speed is zero then we're allowed to use 100% of the acceleration available to us. As the speed approaches the top speed the acceleration goes to zero and if for some reason the speed would go beyond the top speed then the acceleration would become negative and so the system would be self regulating.
The simple way of changing the angle would be to just allow for some set amount of change per second but just as with the acceleration I wanted it to be dependent on the speed of the object. The higher the speed to more difficult it should be to change direction.
The angular delta between acceleration vector and speed vector should also factor in. The greater the difference between the speed's angle and the acceleration's the more rapid the change in angle should be. If the player snaps around 180 degrees then the shift in angle per frame should be greater than if he were just doing slight movements.
Also, I wanted the speed vector's angle to actually overshoot its targeted acceleration angle if the player swung around too fast. The idea behind this was to create a wobbly effect that would deliberately make movement slightly more difficult. To do this will require implementing angular velocity so that the rate of change in the speed vector's angle is governed by some changing value.
Taking into account these three things: linear speed, angular delta and angular velocity, means the system for changing the speed's angle was somewhat complex.
When calculating the angle between the acceleration and speed vector we always use the smallest possible value. So if the shortest way to get from the speed's direction to the acceleration is to turn left then the angle difference is between 0° and -180° and if it's quicker to turn right it's between 0° and 180°.
fig 5 The speed vector is the red line and the top and bottom blue lines are acceleration vectors. For the top one it's quicker from the speed's perspective to turn to the left so the relative angle between them is -120° and for the bottom one it's quicker to turn to the right so then the angle is 120°.
As stated I felt the need to add angular velocity to regulate how rapidly the speed vector swings around. If the linear speed is large then the change in position for each frame will consequently be large and if the angular velocity is large then the difference in angle for each frame will similarly be large. It's really just a way of having a memory of how great the difference between the speed and acceleration vector was at the outset of the motion, as a large difference will allow a large buildup of angular velocity.
So how do we calculate the angular velocity? Well, as stated above we want it to be dependent on the linear speed of the player and the difference between the speed and acceleration angle, i.e. how hard the player is trying to turn. Starting with the linear speed we could reuse the same equation as for setting the acceleration:
angularVelocity = 1 - speed / TOP_SPEED
That way, when the speed is at its max the turn rate will be 0 and contrariwise when the speed is zero the turn rate will be 1.
Angular difference between the speed and acceleration was another thing we wanted to influence the turn rate so we could do something like dividing the angle by 180. That would give a turn rate of zero when the angle is zero and a turn rate of one when the angle is at its max of 180. So we'd turn quickly when the difference between our current speed and where we wanted to go (where the acceleration vector is pointing) is large and we'd turn slowly when they're almost the same. The equation, taking into account both speed and angle delta, would then look like this:
angularVelocity = ( angleDelta / 180 ) * ( 1 - speed / TOP_SPEED )
Turn rate would then function like this:
fig 6 The greater the difference between the red speed angle and the blue acceleration angle the greater the turn rate would be. For the right most blue line where the angle is zero the turn rate is also 0. At 90° it's 90 / 180 = 0.5 and at 180° you'd get the max turn rate of 1.
This will work but I found the movement it produced to be unsatisfactory. If the player is trying to completely reverse direction then you don't want the angle to change at all at first, as this would mean the player would start moving sideways. Instead the speed should go to zero, then the angle should change 180° and then the speed can increase again. So when the acceleration is 180° away from the current speed, the speed magnitude should shrink to zero and then the change to the speed's direction should occur. A way of doing this is by using sine:
fig 7 By taking sine( angleDelta ) we get a turn rate of zero both when the angle is zero and when it's 180° and a max turn rate at 90°
This creates a more realistic movement when reversing direction by making the character slow down more before the speed switches direction. Although the angle still swings around when the speed has gotten low and doesn't do a 180 cleanly, due to rounding errors in floats not producing a precise angle of 180°. This slight wobbliness however is something I prefer. Calculating angular velocity would now look like this:
angularVelocity = sine( angleDelta ) * ( 1 - speed / TOP_SPEED )
Oscillations proved to be a problem with this solution. The angle of the speed vector would greatly overshoot it's target and then swing back only to overshoot it again and this would keep going for a long time. To solve this there had to be some way to attenuate the angular velocity if it proved too large as the speed approached it's target angle. For example if the speed had started to swing around from 170° it would have a large angular velocity when closing in on the targeted acceleration vector so we'd need to retard that velocity at some point. However if the speed vector started to move 5° away from the acceleration vector we wouldn't have to brake at all as there'd be very little overshoot.
Braking would then depend on how large of an angular velocity we already had and how close to our goal of aligning the speed to the acceleration vector we were. To start with our braking calculation would then just involve inverting the current angular velocity:
angularVelocityBrake = -angularVelocity
This would remove the entire velocity so we need to multiply it by something. We could do:
angularVelocityBreak = -angularVelocity * ( 1 - angleDelta / 180 )
A large angular velocity and a small angle would result in a large braking force. This does work and creates an increasing braking force as the speed vector narrows in on its target which does alleviate the oscillations but I found a more interesting solution by using cosine.
Cosine varies between -1 when the angle is 180 degrees and 1 when the angle is zero.
fig 8 How cosine varies with angle. 1 at 0°, 0 at 90° and -1 at 180°.
So if we instead multiply the inverted velocity by cosine:
angularVelocityBrake = -angularVelocity * cosine( angleDelta )
The idea behind inverting the angular velocity by putting - in front of it is obviously to counteract the existing velocity. If the velocity is already negative then -velocity will be positive and vice versa, the sign originally depends on whether the speed vector is swinging to the left or right. For angles above 90° however, cosine( angleDelta ) will be negative and so multiplying it to -velocity will bring the sign right back to the same as the original velocity. Meaning that if the angular velocity is positive and the angular delta above 90° then the braking force will also end up positive and so when adding together the velocity and the braking they'll actually end up reinforcing each other and so create an even larger angular velocity, accelerating the swing. This is true also for when the velocity is negative.
All this means is that when the angle between the speed and acceleration vector is greater than 90° the angular velocity braking won't actually slow the swinging motion down but rather increase it. Then as the angle becomes less than 90° the braking will rapidly kick in. This creates a more wobbly movement that I prefer over the solution of taking the angle over 180.
Cosine can also be used to create a more interesting behavior for the linear speed.
Acceleration was calculated as 1 - speed / TOP_SPEED but if we exchange the 1 for cosine and do it like this instead:
accelerationPercent = cosine( angleDelta ) - speed / TOP_SPEED
If for example the player is then trying to completely reverse direction, then the angle between the current speed and the acceleration vector is 180° and cosine will work out to -1. Let's say we're also traveling at the top speed so speed / TOP_SPEED become 1. Now the accelerationPercent will be -1 - 1 = -2 and so the character will brake hard, which is expected if the player is trying to reverse direction.
However if the speed and acceleration vector are pointing in the same direction then cosine( 0 ) = 1 and so we'll still end up with an allowed acceleration of 1 - 1 = 0 which is exactly how we limited the speed before.
Had we just gone with 1 - speed / TOP_SPEED we'd end up with a result of 0 when trying to reverse and so there'd be no braking effect at all and we'd have to somehow detect this and set the acceleration to negative manually.
So we get a more dynamic behavior by using cosine.
We'll just look at the function that sets the speed magnitude and angle:
1. Calculate the difference in angle between the speed and acceleration vectors.
2. Normalize this value to an interval of -180 to 180 but in radians.
3. Calculate sine and cosine for this angle.
4. Calculate how close in percent we are to the top speed.
5. Calculate angular velocity braking as described above. Since it can be used to accelerate as well as brake we now call this angularVelocityMod instead. The only thing new here is the frame time that we have to take into account and TURN_RATE which is a magic number that you can increase to make the character turn faster.
6. Set the magnitude of the speed vector. Also as described above. "acceleration" is a number between -1 and 1 that we set when polling the player input. It will always be positive unless no input is detected in which case it will be -1 and the character will coast to a stop. "ACCELERATION" is another magic number we can increase to make the character go faster.
7. Set the angular velocity as described above.
8. Increase or decrease the angle of the speed vector based on the angular velocity.
9. Do a normalization pass for the angle of the speed vector in order to keep it within 0° and 360° but in radians.
10. If the speed has turned negative we change it to positive and set the speed angle to be whatever the acceleration wants it to be and reset the angular velocity to zero. This is to not end up with weird configurations where the vector is pointing in one direction but the character is moving opposite direction because the speed is negative.
void speed( float *speedMagnitude, float *speedAngle, float *angularVelocity, const float acceleration, const float accelerationAngle, const float frameTime )
{
1. const float angleDelta = accelerationAngle - *speedAngle;
2. const float angleDeltaNorm =
2. angleDelta > RAD180 ? angleDelta - RAD360 :
2. angleDelta < -RAD180 ? angleDelta + RAD360 :
2. angleDelta;
3. const float angleSine = sinf( angleDeltaNorm );
3. const float angleCosine = cosf( angleDeltaNorm );
4. const float speedPrc = *speedMagnitude / MAX_SPEED;
5. const float angularVelocityMod = -*angularVelocity * angleCosine * frameTime * TURN_RATE;
6. *speedMagnitude += ( angleCosine - speedPrc ) * frameTime * acceleration * ACCELERATION;
7. *angularVelocity += ( angleSine * ( 1 - speedPrc ) + angularVelocityMod ) * frameTime * TURN_RATE;
8. *speedAngle += *angularVelocity * frameTime;
9. *speedAngle =
9. *speedAngle < 0 ? *speedAngle + RAD360 :
9. *speedAngle > RAD360 ? *speedAngle - RAD360 :
9. *speedAngle;
10. if( *speedMagnitude < 0 ) {
10. *speedMagnitude *= -1;
10. *speedAngle = accelerationAngle;
10. *angularVelocity = 0;
}
}
How well does this then succeed as far as being a more elegance solution to movement and creating a more challenging control scheme?
As for elegance I do think it's a pretty terse implementation. Especially considering it has angular velocity, something that's not usually part of simple game movement.
Performance was at first one of the primary reason for doing this and particularly getting rid of square roots was one of my goals. Even though I know that it's irrelevant in a modern world with multi GHz computers there's still a warm fuzzy feeling you get when you optimization something out. As it turns out though sine and cosine are both slower than square roots. By how much seems to vary, on my machine sin and cosine both take about 33% longer to calculate than a square root. This is something I should probably have look into at the outset...
Doing a complete comparison with a Cartesian system could possibly be interesting but I'm far too lazy to do it. Performance-wise it would seem to be a bust.
Making the player feel a bit clumsy was another intention, as I want to reproduce what it felt like playing an old FPS with keyboard only, except I don't think you can foist a keyboard only scheme on a modern audience.
This I feel was a success, though it's difficult to tell without having it in an actual FPS game. Maybe it will induce motion sickness when paired with a raycaster engine, which is what I intend to use it for.
You could likely get a very normal control scheme by doing stuff like "angle / 180", removing the angular velocity and just having a fixed turn angle per frame and preventing overshoot of the speed relative to the acceleration but where's fun in that?
Spinning the red circle round and round in the demo above will put it in a state where the speed vector is doing 360s for a while before settling down and again allow for movement. I'm still undecided as to whether this is an intended behavior or not.