0
\$\begingroup\$

Feel free to skip to the bottom and see the actual question.

NOTE: Question updated below based on comments

I am trying to make a space game and implement basic movement, unlike most, this is a simulation over time in the likes of Aurora 4x where time can pass by seconds or by days, months, years. I only mention this because my delta and inclusion of ticks would probably raise questions.

Quick Notes:

  • Vector2Wide is just the .NET System.Numerics Vector2 that I copied and made it use double instead of float
  • I am not using a game library. This is actually drawn in WPF taking my "space" location in AU and converting it to pixels on a canvas.
  • Frictionless space
  • Ship can accelerate/decelerate in any 2D direction. There's no ship rotation.
  • X,Y are cartesian coordinates with the sun being at 0,0
  • I am using Kilometers as my distance and acceleration, but I don't think it matters, just mentioning it in case.
  • I also simulated it for every second to make sure it wasn't an issue skipping so much time and the results were basically the same with my acceleration value.

Going from a velocity of 0 is fine as shown here where my path properly shows my ship (center of the sun) moving to where I clicked just past Venus. enter image description here

From here I jump a couple of hours and the ship has velocity from constant acceleration. I then give the ship a new destination and this is where I have thoroughly fried my brain the past couple of days.

The red arrow is the destination the ship is tracking, but my flawed math is sending the crew to their death. enter image description here

var velocity = _velocity;
var position = SystemPosition;
var mid = VectorMath.Midpoint(position, to);
var distanceToMid = Vector2Wide.Distance(position, mid);
var accelerate = true;
var oldDistanceToTarget = distanceToMid;
var acceleration = MaxAccelerationPowerKms;

var alreadyMoving = _velocity != Vector2Wide.Zero;
var oldAcceleration = new Vector2Wide();
var oldDistanceToMid = Vector2Wide.Distance(position, mid);
var headingTowardsDestination = false;

for (var i = 0; i < 72; i++)
{
    var newDirectionToTarget = Vector2Wide.Normalize(Vector2Wide.Subtract(position, to));
    var accelerationDirection = new Vector2Wide(1, 1) * -newDirectionToTarget;
    if (i == 0 && alreadyMoving)
        accelerationDirection = AccelerationDirection;
    
    if (oldAcceleration == Vector2Wide.Zero)
        oldAcceleration = accelerationDirection;

    if (alreadyMoving)
    {
        var angleInRadians = Math.Atan2(position.Y, position.X) - Math.Atan2(to.Y, to.X);

        accelerationDirection = VectorMath.RotateRadians(accelerationDirection, angleInRadians);
        if (i == 0)
            Debug.WriteLine($"{i + 1} | {angleInRadians} | {accelerationDirection} | {oldAcceleration - accelerationDirection}");
    }

    var newPosition = PeekPath(TickConstants.HourTicks, position, ref velocity, accelerationDirection, acceleration);
    var newDistanceToMid = Vector2Wide.Distance(newPosition, mid);
    var newDistanceToTarget = Vector2Wide.Distance(newPosition, to);

    if (newDistanceToMid < oldDistanceToMid)
        headingTowardsDestination = true;
    
    if (accelerate)
    {
        if (headingTowardsDestination && newDistanceToMid > oldDistanceToMid)
        {
            //Debug.WriteLine("Decelerating");
            acceleration = -acceleration;
            oldDistanceToTarget = newDistanceToTarget;
            accelerate = false;
            i--;
            continue;
        }

        oldDistanceToMid = newDistanceToMid;
    }
    else
    {
        if (headingTowardsDestination && oldDistanceToTarget < newDistanceToTarget)
        {
            //PathPoints.Add(position);
            break;
        }
    }

    oldDistanceToTarget = newDistanceToTarget;
    position = newPosition;


    //if (i % (60*60) == 0)
    PathPoints.Add(position);
}

Actual movement code:

Vector2Wide PeekPath(long deltaTicks, Vector2Wide currentPosition, ref Vector2Wide velocity, Vector2Wide accelerationDirection, double acceleration)
{
    var seconds = deltaTicks / TickConstants.SecondTicks;
    var distanceXKm = CalculateDistance(velocity.X, acceleration * accelerationDirection.X, seconds);
    var distanceYKm = CalculateDistance(velocity.Y, acceleration * accelerationDirection.Y, seconds);
    velocity += accelerationDirection * (acceleration * seconds);

    var spaceDistanceX = distanceXKm / CelestialBody.AuKilometer;
    var spaceDistanceY = distanceYKm / CelestialBody.AuKilometer;
    return currentPosition + new Vector2Wide(spaceDistanceX, spaceDistanceY);
}

[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static double CalculateDistance(double velocity, double acceleration, double time)
{
    return (velocity * time) + (0.5 * (acceleration * (time * time)));
}

I know the code is horribly flawed, but I don't know how much.

Actual Question

With a velocity and direction change, how do I apply or find the proper directional force to apply to my velocity to reach the destination? The more I deviate the direction, the more skewed/off the path gets. It will also not allow me to set a destination opposite direction, but I think that's my own issue with trying to figure out when to decelerate.

I do hate to ask this, but if you give an actual formula, can you please explain with an example? I sadly just don't have the math skills to know how to read them correctly =/


Update

Thanks to DMGregory great post, I am much closer. Spaceship acceleration for following waypoints

enter image description here

Red arrow points to the destination. The ship has a positive X velocity and the destination is directly above.

The new problem is that I don't know if I am using the correct vector to use for steering. The other issue is that I now have no idea how I am supposed to properly handle or calculate when/where/angle to decelerate so I can actually get to the destination. The crew are still guinea pigs on a no return mission.

for (var i = 0; i < 72; i++)
{
    var time = TickConstants.HourTicks;
    var seconds = (double) time / TickConstants.SecondTicks;
    
    // A
    var startPosition = position;
    
    // B
    var halfwayPointNoAcceleration = startPosition + ((seconds /2) * velocity) / CelestialBody.AuKilometer;
    
    // D
    var finalPositionNoVelocity = startPosition + (seconds * velocity) / CelestialBody.AuKilometer;
    
    var dRadiusKm = MaxAccelerationPowerKms * (seconds * seconds / 2);
    var dRadius = dRadiusKm / CelestialBody.AuKilometer;

    var radianFromCenterDToTarget = Math.Atan2(target.Y - finalPositionNoVelocity.Y, target.X - finalPositionNoVelocity.X);
    
    // C
    var steeringVector = FindCoordinateOfVectorRadius(finalPositionNoVelocity, dRadius, radianFromCenterDToTarget);

    var directionToSteeringVector = Vector2Wide.Normalize(Vector2Wide.Subtract(steeringVector, finalPositionNoVelocity));
    
    var accelerationDirection = directionToSteeringVector;
    
    position = PeekPath(TickConstants.HourTicks, position, ref velocity, accelerationDirection, acceleration);

    PathPoints.Add(position);
}


public Vector2Wide FindCoordinateOfVectorRadius(Vector2Wide center, double r, double radian)
{
    //x = r cos radian
    //y = r sin radian
    return new Vector2Wide(r * Math.Cos(radian), r * Math.Sin(radian)) + center;
}
\$\endgroup\$
3
  • \$\begingroup\$ I find it's useful to conceive of your planned trajectory as a Bezier curve. A quadratic Bezier corresponds to a trajectory with constant acceleration. A cubic Bezier corresponds to a trajectory with linearly-varying acceleration, and makes it easier to control the velocity you have as you arrive at the destination. I develop this technique in Spaceship acceleration for following waypoints and How can I maneuver an AI pirate ship for a sea battle. \$\endgroup\$
    – DMGregory
    Mar 9, 2021 at 0:48
  • \$\begingroup\$ @DMGregory Thank you. I will start reading these. They look very helpful. Hopefully my brain can actually comprehend them lol \$\endgroup\$
    – TyCobb
    Mar 9, 2021 at 1:00
  • \$\begingroup\$ @DMGregory Thanks a lot for the spaceship article. I think I've implemented properly and have updated my question. Any feedback would be most helpful. \$\endgroup\$
    – TyCobb
    Mar 10, 2021 at 0:36

2 Answers 2

1
+50
\$\begingroup\$

You're fixing your time horizon as always taking 1 hour to get to your destination.

var time = TickConstants.HourTicks;
var seconds = (double) time / TickConstants.SecondTicks;

Even if you've already spent 59 minutes flying, you continue re-plotting a new trajectory designed to bring you to the destination after 1 hour of additional flight from here - guaranteeing mathematically that you will never reach your goal.

You've also decided to always steer for a point at the outer limit of what you can accelerate to reach, even if your actual target point is closer/further. (In the general case, our target will not sit exactly on this circle, if it does not take exactly one hour to reach from here at max acceleration)

var steeringVector = FindCoordinateOfVectorRadius(finalPositionNoVelocity, dRadius, radianFromCenterDToTarget);

What we want to do instead (if you choose to go with the quadratic approach from the first link) is plan what time horizon we need to reach this point with a single constant acceleration burn. ie. at what time \$T^*\$ does point \$C\$ lie exactly on the circle of radius \$\frac {T^{*2}} 2 a_\text{max}\$?

This involves solving the quartic equation:

$$||\vec C - \vec D|| = \frac {T^{*2}} 2 a_\text{max}\\ T^{*4} \left(\frac {a_\text{max}^2}2 \right) - T^{*2}v^2 - T^* \left(2 \vec v \cdot (\vec C - \vec A)\right) - \left(\vec C - \vec A\right)^2 = 0$$

I won't go into that here, but you can plug that into the math package of your choice and take the smallest positive real solution as your \$T^*\$.

Once you've done that, you can calculate your point \$\vec D = \vec A + T^* \vec v\$,

And your acceleration vector is then \$\vec a = \frac {2 (\vec C - \vec D)} {T^{*2}}\$

And you can compute points along this path as...

for (int i = 0; i <= 100; i++) {
    double time = T * i/100.0;
    var positionAtTime = startPosition 
                       + initialVelocity * time
                       + acceleration    * time * time / 2.0;
    PathPoints.Add(positionAtTime);
}

Note that we calculate our trajectory just once, then loop over its points to plot it. We don't plan a new trajectory at every iteration of the loop.

This will give you a trajectory travelling through your target point, but you might build up quite a lot of velocity on your way there. If you want to allow for braking or otherwise controlling your velocity at the destination point, you should use the cubic approach from my second link instead.

\$\endgroup\$
1
  • \$\begingroup\$ Thank you for the information. I will play around with this after work. In regards to the 1 hour time span, I just did that to test the path. If ran what I had coded for every second, the path was almost identical at render scale. So my logic was definitely flawed. I'll look at this and look at the 2nd link again. Thank you \$\endgroup\$
    – TyCobb
    Mar 11, 2021 at 21:37
0
\$\begingroup\$

I fail to understand your code because it's early morning here and the code looks quite messy on mobile, but I have one thing that I think might be useful to you to determine where to start to decelerate.
You can find the distance threshold where the ship should start to decelerate to stop at the target position with velocity = 0.

The formula is:

float t = velocity / accel;
float d = velocity * t + accel * (t * t) / 2f;

In the case of linear deceleration when you decrease the velocity over time by simple subtraction: velocity -= accel, the d will be the distance from the target where you should start to do that.
So, you find the distance from current position to target position, and then check if the distance is less than d, and if it is, you decrease the velocity by the acceleration value.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .