0
\$\begingroup\$

Edit: Having to edit this question extensively because DMGregory was right and there were unexpected consequences.

I am working on local avoidance and pathfinding code for a 3D strategy game. It has to be deterministic, so I'm editing a pathfinding library which uses floating point based classes (this is with Unity) like Vector2, Vector3, Quaternion.

There are custom vector classes I have picked up elsewhere which use longs instead of floats to store position data deterministicly. I'm just in the process of replacing the data types with deterministic vector classes.

The problem is that there are some operations which use quaternion times vector calculations. I do not have a deterministic quaternion class, and the deterministic code I have found elsewhere uses a deterministic Vector2 to store rotation data instead of a Quaternion.

    public static Vector2d CreateRotation(long angle)
    {
        return new Vector2d(FixedMath.Trig.Cos(angle), FixedMath.Trig.Sin(angle));
    }

    public Vector2d ToDirection()
    {
        return new Vector2d(y, x);
    }

    public Vector2d ToRotation()
    {
        return new Vector2d(y, x);
    }

This is fine, because the pathfinding and avoidance library converts Vector3 to Vector2, to calculate avoidance on a 2D plane. I suppose there's no reason to calculate it in 3D, as that's just added complexity, elevation gets tagged on later.

The Libraries used are:

There are two functions which use Quaternion * Vector calculations which need replaced. I extracted this into the function CalculateVector2Forward, which is invoked inside TraverseFunnel and FinalMovement. This all exists as part of a complex solution. These are both invoked from MovementUpdateInterval function.

Quaternion simulatedRotation updates the gameObject's transform.rotation, and is updated indirectly via the "nextRotation" out variables of the functions mentioned, in which the class SimulateRotationTowards is invoked.

CalculateVector2Forward

    private Vector2 CalculateVector2Forward()
    {
        return movementPlane.ToPlane(simulatedRotation * Vector3.forward);
    }

MovementUpdateInterval

    protected override void MovementUpdateInternal(float deltaTime, out Vector3 nextPosition, out Quaternion nextRotation)
    {
        NornRichPathPart currentPart = richPath.GetCurrentPart();

        if (currentPart is NornRichSpecial)
        {
            if (!traversingOffMeshLink)
            {
                StartCoroutine(TraverseSpecial(currentPart as NornRichSpecial));
            }

            nextPosition = steeringTarget = simulatedPosition;
            nextRotation = rotation;
        }
        else
        {
            NornRichFunnel funnel = currentPart as NornRichFunnel;

            if (funnel != null && !isStopped)
            {
                TraverseFunnel(funnel, deltaTime, out nextPosition, out nextRotation);
            }
            else
            {
                // Unknown, null path part, or the character is stopped.  Slow down as quickly as possible.  
                velocity2D -= Vector2.ClampMagnitude(velocity2D, acceleration * deltaTime);
                FinalMovement(simulatedPosition, deltaTime, float.PositiveInfinity, 1f, out nextPosition, out nextRotation);
                steeringTarget = simulatedPosition;
            }
        }
    }

Finalize Movement

    public virtual void FinalizeMovement(Vector3 nextPosition, Quaternion nextRotation, Vector2d nextDirection)
    {
        if (enableRotation)
        {
            FinalizeRotation(nextRotation, nextDirection);
        }

        FinalizePosition(nextPosition);
    }

Finalize Rotation

    void FinalizeRotation(Quaternion nextRotation, Vector2d nextDirection)
    {
        simulatedRotation = nextRotation;
        simulatedDirection = nextDirection;

        if (updateRotation)
        {
            tr.rotation = nextRotation;
        }
    }

Finalize Position

    void FinalizePosition(Vector3 nextPosition)
    {
        // Use a local variable, it is significantly faster.  
        Vector3 currentPosition = simulatedPosition;
        bool positionDirty1 = false;

        if (controller != null && controller.enabled && updatePosition)
        {
            // Use CharacterController.  The Transform may not be at #position if it was outside the navmesh and had to be moved to the closest valid position.  
            tr.position = currentPosition;
            controller.Move((nextPosition - currentPosition) + accumulatedMovementDelta);
            // Grab the position after the movement to be able to take physics into account.  
            // TODO: Add this into the clampedPosition calculation below to make RVO better respond to physics.  
            //currentPosition = tr.position; // MUST NOT UPDATE FROM TRANSFORM!  WILL BREAK DETERMINISM!  

            if (controller.isGrounded)
            {
                verticalVelocity = 0;
            }
        }
        else
        {
            // Use Transform, Rigidbody, Rigidbody2D or nothing at all (if updatePosition = false).  
            float lastElevation;
            movementPlane.ToPlane(currentPosition, out lastElevation);
            currentPosition = nextPosition + accumulatedMovementDelta;

            // Position the character on the ground.  
            if (usingGravity)
            {
                currentPosition = RaycastPosition(currentPosition, lastElevation);
            }

            positionDirty1 = true;
        }

        // Clamp the position to the navmesh after movement is done.  
        bool positionDirty2 = false;
        currentPosition = ClampToNavmesh(currentPosition, out positionDirty2);

        // Assign the final position to the character if we haven't already set it (mostly for performance, setting the position can be slow).  
        if ((positionDirty1 || positionDirty2) && updatePosition)
        {
            tr.position = currentPosition;
        }

        accumulatedMovementDelta = Vector3.zero;
        simulatedPosition = currentPosition;
        UpdateVelocity();
    }

TraverseFunnel

    void TraverseFunnel(NornRichFunnel fn, float deltaTime, out Vector3 nextPosition, out Quaternion nextRotation)
    {
        // Clamp the current position to the navmesh and update the list of upcoming corners in the path and store that in the 'nextCorners' field.  
        Vector3 position3D = UpdateTarget(fn);
        Vector2 position = movementPlane.ToPlane(position3D, out float elevation);

        // Only find nearby walls every 5th frame to improve performance.  
        if (Time.frameCount % 5 == 0 && wallForce > 0 && wallDist > 0)
        {
            wallBuffer.Clear();
            fn.FindWalls(wallBuffer, wallDist);
        }

        steeringTarget = nextCorners[0];
        Vector2 targetPoint = movementPlane.ToPlane(steeringTarget);
        Vector2 directionToTarget = targetPoint - position;  
        Vector2 normalizedDirectionToTarget = NornVectorMath.Normalize(directionToTarget, out distanceToSteeringTarget);
        // Calculate force from walls.  
        Vector2 wallForceVector = CalculateWallForce(position, elevation, normalizedDirectionToTarget);
        Vector2 targetVelocity;

        if (approachingPartEndpoint)
        {
            targetVelocity = slowdownTime > 0 ? Vector2.zero : normalizedDirectionToTarget * maxSpeed;
            // Reduce the wall avoidance force as we get closer to our target.  
            wallForceVector *= System.Math.Min(distanceToSteeringTarget / 0.5f, 1);

            if (distanceToSteeringTarget <= endReachedDistance)
            {
                // Reached the end of the path or an off mesh link.  
                NextPart();
            }
        }
        else
        {
            Vector2 nextNextCorner = nextCorners.Count > 1 ? movementPlane.ToPlane(nextCorners[1]) : position + 2 * directionToTarget;
            targetVelocity = (nextNextCorner - targetPoint).normalized * maxSpeed;
        }

        Vector2 forwards = CalculateVector2Forward();
        Vector2 accel = NornMovementUtilities.CalculateAccelerationToReachPoint(targetPoint - position, targetVelocity, velocity2D, acceleration, rotationSpeed, maxSpeed, forwards);
        // Update the velocity using the acceleration.  
        velocity2D += (accel + wallForceVector * wallForce) * deltaTime;
        // Distance to the end of the path (almost as the crow flies).  
        float distanceToEndOfPath = distanceToSteeringTarget + Vector3.Distance(steeringTarget, fn.exactEnd);
        float slowdownFactor = distanceToEndOfPath < maxSpeed * slowdownTime ? Mathf.Sqrt(distanceToEndOfPath / (maxSpeed * slowdownTime)) : 1;

        FinalMovement(position3D, deltaTime, distanceToEndOfPath, slowdownFactor, out nextPosition, out nextRotation);
    }

FinalMovement

    void FinalMovement(Vector3 position3D, float deltaTime, float distanceToEndOfPath, float slowdownFactor, out Vector3 nextPosition, out Quaternion nextRotation)
    {
        Vector2 forwards = CalculateVector2Forward();
        velocity2D = NornMovementUtilities.ClampVelocity(velocity2D, maxSpeed, slowdownFactor, slowWhenNotFacingTarget && enableRotation, forwards);
        ApplyGravity(deltaTime);

        // Direction and distance to move during this frame.  
        Vector2 deltaPosition = lastDeltaPosition = CalculateDeltaToMoveThisFrame(movementPlane.ToPlane(position3D), distanceToEndOfPath, deltaTime);
        // Rotate towards the direction we are moving in.  Slow down the rotation of the character very close to the endpoint of the path to prevent oscillations.  
        float rotationSpeedFactor = approachingPartEndpoint ? Mathf.Clamp01(1.1f * slowdownFactor - 0.1f) : 1f;
        nextRotation = enableRotation ? SimulateRotationTowards(deltaPosition, rotationSpeed * rotationSpeedFactor * deltaTime) : simulatedRotation;
        nextPosition = position3D + movementPlane.ToWorld(deltaPosition, verticalVelocity * deltaTime);
    }

SimulateTowardsRotation

    protected Quaternion SimulateRotationTowards(Vector2 direction, float maxDegrees)
    {
        if (direction != Vector2.zero)
        {
            Quaternion targetRotation = Quaternion.LookRotation(movementPlane.ToWorld(direction, 0), movementPlane.ToWorld(Vector2.zero, 1));

            return Quaternion.RotateTowards(simulatedRotation, targetRotation, maxDegrees);
        }

        return simulatedRotation;
    }

I apologise for how many edits it has taken to make this question any good.

\$\endgroup\$
  • 1
    \$\begingroup\$ We need to see more context around this code to know how quarternionY is formed and what vector3X is used for. Or, if you'd like to share the determinism issues you're experiencing instead, we can try to help you solve that problem at its source. \$\endgroup\$ – DMGregory Apr 10 at 18:11
  • \$\begingroup\$ @DMGregory Fine point, I have updated it now. Is this better, or is there anything more specific to add? \$\endgroup\$ – inappropriateCode Apr 10 at 18:29
  • 1
    \$\begingroup\$ Are you just looking for how to convert an angle to a direction in the plane? You still haven't shown us how that quarternion is computed, or an example of how your library uses a vector 2 to store rotation data (I can think of a few mutually-incompatible ways, so to make sure we work with the one you're using, we really need to see the one you're using!) The more you keep us in the dark, the more likely you are to get answers that don't work for your complete context. \$\endgroup\$ – DMGregory Apr 10 at 18:34
  • 1
    \$\begingroup\$ We still can't see a line of code where simulatedRotation is written to, and we still don't know what library you're using for your Vector2 rotation. The three functions you've chosen to snip out are not informative of how they're using these values to perform a rotation (there are two different rotation conventions they might be following, but you haven't shown us the parts of the library that do this work, or named the library so we can look it up for clarification). \$\endgroup\$ – DMGregory Apr 10 at 19:27
  • 1
    \$\begingroup\$ Please edit your question to ensure this relevant information is all in one place. \$\endgroup\$ – DMGregory Apr 10 at 20:18
1
\$\begingroup\$

We can replace your simulatedRotation quaterion with a Vector2d facingDirection, representing your forward direction.

Now you don't need CalculateVector2Forward() at all: you can use your facingDirection directly.

You can replace your SimulateRotationTowards(Vector2 direction, float maxDegrees) method like so:

Vector2d RotateFacing(Vector2d targetDirection, long maxRadians) {

    // If we're given a zero vector, just keep our current direction.
    if(targetDirection == Vector2d.zero)
        return facingDirection;

    // Ensure we're working with a unit vector. Skip this if you can guarantee it.
    targetDirection.Normalize();

    // Compute the projection of our target onto our current direction.
    // Note that this is equal to the cosine of the angle between them.
    var cosine = targetDirection.Dot(facingDirection);

    // Clamp the projection within our allowed rotation range.
    cosine = Max(cosine, FixedMath.Trig.Cos(maxRadians));

    // Compute a vector perpendicular to our facing direction.
    var perpendicular = facingDirection.rotatedLeft;

    // Compute how much of the perpendicular to add to our result,
    // rotating in the direction of our target (that's the sign part)
    // and ensuring our parallel and perpendicular components add to a length of one
    // by using the Pythagorean identity: (sin^2 + cos^2) = 1
    var sine = FixedMath.Sign(targetDirection.Dot(perpendicular)) 
             * FixedMath.Sqrt(FixedMath.One - (cosine.Mul(cosine)));

    // Build our new vector, with a component parallel to our current direction,
    // and a component perpendicular to it.
    var newDirection = cosine * facingDirection +  sine * perpendicular;

    // Correct for any accumulated error - you might not need this, 
    // or might need to re-normalize only periodically.
    newDirection.Normalize(); 

    return newDirection;
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thank you very much for this answer! I've upvoted, it's just taking a while to edit everything before I can run and verify. \$\endgroup\$ – inappropriateCode Apr 10 at 21:03
  • \$\begingroup\$ Sorry, stupid question to finish. How do I apply the Vector2 direction into a Quaternion to apply the rotation to the transform? \$\endgroup\$ – inappropriateCode Apr 10 at 21:34
  • 1
    \$\begingroup\$ First change your Vector2d into a Unity Vector3 in the appropriate plane (I assume xz?), then either Quaternion.LookRotation(facingDirectionVector3) or Quarternion.FromToRotation(Vector3.forward, facingDirectionVector3) if your "forward" direction is z+. Change the second version's first argument accordingly if you use a different forward direction. \$\endgroup\$ – DMGregory Apr 10 at 21:36
  • \$\begingroup\$ You were right, there was unforseen complexity owing to my question not containing enough information. It's not that your answer is wrong, it's that it's not working. I've edited the question yet again. Not sure if that helps. I do not like vector maths at this point. \$\endgroup\$ – inappropriateCode Apr 11 at 13:53
  • 1
    \$\begingroup\$ @inappropriateCode What specific aspect is "not working"? The more concretely you can identify the problem, the better we can target fixes. \$\endgroup\$ – DMGregory Apr 11 at 13:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.