using System;

using UnityEngine;

using Framework.Geometry.Lines;
using Framework.Geometry.Lines.Intersection;

namespace Framework.Navigation.Platformer {

  /// <summary>Calculates the jump-off and landing points between two grounds</summary>
  internal static class JumpCalculator {

    #region struct Range

    /// <summary>Stores an index range for an array</summary>
    private struct Range {

      /// <summary>Index where the range begins</summary>
      public int Start;
      /// <summary>Index where the range ends (inclusive)</summary>
      public int End;

    }

    #endregion // struct Range

    /// <summary>Determines the best jump to take from one ground to another</summary>
    /// <param name="from">Ground from which the agent wants to jump</param>
    /// <param name="to">Ground onto which the agent wants to jump</param>
    /// <param name="idealDistanceFactor">
    ///   Factor of the agent's maximum jump distance that controls how far the jump
    ///   should be. Positive values prefer the right side of the ground, negative ones
    ///   prefer the left side.
    /// </param>
    /// <param name="constraints">Limits like maximum jump height and distance</param>
    /// <remarks>
    ///   The <see cref="idealDistanceFactor" /> specifies the jump length the agent would
    ///   prefer (a wide jump, even if not necessary, would be more suitable for
    ///   a fast-moving agent, unless the required jump was opposite to the running direction).
    /// </remarks>
    public static Segment2? GetJumpPath(
      Ground from, Ground to, float idealDistanceFactor, Constraints constraints
    ) {
      if(idealDistanceFactor < 0.0f) {
        Segment2? jumpPath = GetLeftJumpPath(from, to, -idealDistanceFactor, constraints);
        if(jumpPath.HasValue) {
          return jumpPath;
        }

        return GetRightJumpPath(from, to, -idealDistanceFactor, constraints);
      } else {
        Segment2? jumpPath = GetRightJumpPath(from, to, idealDistanceFactor, constraints);
        if(jumpPath.HasValue) {
          return jumpPath;
        }

        return GetLeftJumpPath(from, to, idealDistanceFactor, constraints);
      }
    }

    /// <summary>Calculates a jump path for an agent on the left side of the ground</summary>
    /// <param name="from">Ground the agent wants to jump off from</param>
    /// <param name="to">Ground the agent wants to reach</param>
    /// <param name="idealDistanceFactor">Jump distance the agent would prefer</param>
    /// <param name="constraints">Limits like maximum jump height and distance</param>
    /// <returns>The jump path to the other ground, if one exists</returns>
    public static Segment2? GetLeftJumpPath(
      Ground from, Ground to, float idealDistanceFactor, Constraints constraints
    ) {
      Vector2 fromLeft = from.Heights[0] + xyOnly(from.transform.position);
      Vector2 toLeft = to.Heights[0] + xyOnly(to.transform.position);

      // Is the origin ground further to the left?
      if(fromLeft.x < toLeft.x) {
        float y = from.GetGroundHeightAt(toLeft.x);
        if(y > toLeft.y) { // Destination ground starts under origin ground
          return null; // No path on this side, let getRightJumpPath() handle it
        }

        // See which jump off points can reach the edge of the target ground
        Range reachableSegments = getReachableSegments(
          from, toLeft.x - constraints.MaximumJumpDistance, toLeft.x
        );

        float idealX = toLeft.x - (constraints.MaximumJumpDistance * idealDistanceFactor);

        // Now go over the segments and look the point closest to
        Vector2? jumpOffPoint = null;
        Vector2 fromOffset = xyOnly(from.transform.position);
        float jumpOffPointDistance = float.PositiveInfinity;
        for(int index = reachableSegments.Start; index < reachableSegments.End; ++index) {
          Segment2? union = constraints.GetLineSegmentInverseArchUnion(
            toLeft,
            new Segment2(
              from.Heights[index] + fromOffset, from.Heights[index + 1] + fromOffset
            )
          );
          if(union.HasValue) {
            if(union.Value.From.x < toLeft.x) {
              float closestX = Mathf.Clamp(idealX, union.Value.From.x, union.Value.To.x);
              float closestDistance = Mathf.Abs(idealX - closestX);
              if(closestDistance < jumpOffPointDistance) {
                jumpOffPoint = new Vector2(
                  closestX, Intersector.GetLineSegmentYfromX(union.Value, closestX)
                );
                jumpOffPointDistance = closestDistance;
              }
            }
          }
        }

        if(jumpOffPoint.HasValue) {
          return new Segment2(jumpOffPoint.Value, toLeft);
        }
      } else { // No, the destination ground is further to the left
        float y = to.GetGroundHeightAt(fromLeft.x);
        if(y > fromLeft.y) { // Jump to higher ground
          return null; // Could extend over this ground, let getRightJumpPath() handle it
        }

        // See which segments of the target ground we can reach from out jump off point
        Range reachableSegments = getReachableSegments(
          to, fromLeft.x - constraints.MaximumJumpDistance, fromLeft.x
        );

        float idealX = fromLeft.x - (constraints.MaximumJumpDistance * idealDistanceFactor);

        // Now go over the segments and look the point closest to
        Vector2? landingPoint = null;
        Vector2 toOffset = xyOnly(to.transform.position);
        float landingPointDistance = float.PositiveInfinity;
        for(int index = reachableSegments.Start; index < reachableSegments.End; ++index) {
          Segment2? union = constraints.GetLineSegmentArchUnion(
            fromLeft,
            new Segment2(to.Heights[index] + toOffset, to.Heights[index + 1] + toOffset)
          );
          if(union.HasValue) {
            if(union.Value.From.x < fromLeft.x) {
              float closestX = Mathf.Clamp(idealX, union.Value.From.x, union.Value.To.x);
              float closestDistance = Mathf.Abs(idealX - closestX);
              if(closestDistance < landingPointDistance) {
                landingPoint = new Vector2(
                  closestX, Intersector.GetLineSegmentYfromX(union.Value, closestX)
                );
                landingPointDistance = closestDistance;
              }
            }
          }
        }

        if(landingPoint.HasValue) {
          return new Segment2(fromLeft, landingPoint.Value);
        }
      }

      return null;
    }

    /// <summary>Calculates a jump path for an agent on the right side of the ground</summary>
    /// <param name="from">Ground the agent wants to jump off from</param>
    /// <param name="to">Ground the agent wants to reach</param>
    /// <param name="idealDistanceFactor">Jump distance the agent would prefer</param>
    /// <param name="constraints">Limits like maximum jump height and distance</param>
    /// <returns>The jump path to the other ground, if one exists</returns>
    public static Segment2? GetRightJumpPath(
      Ground from, Ground to, float idealDistanceFactor, Constraints constraints
    ) {
      Vector2 fromRight = from.Heights[from.Heights.Length - 1] + xyOnly(from.transform.position);
      Vector2 toRight = to.Heights[to.Heights.Length - 1] + xyOnly(to.transform.position);

      // Is the origin ground further to the left?
      if(fromRight.x > toRight.x) {
        float y = from.GetGroundHeightAt(toRight.x);
        if(y > toRight.y) { // Destination ground starts under origin ground
          return null; // No path on this side, let getRightJumpPath() handle it
        }

        // See which jump off points can reach the edge of the target ground
        Range reachableSegments = getReachableSegments(
          from, toRight.x, toRight.x + constraints.MaximumJumpDistance
        );

        float idealX = toRight.x + (constraints.MaximumJumpDistance * idealDistanceFactor);

        // Now go over the segments and look the point closest to
        Vector2? jumpOffPoint = null;
        Vector2 fromOffset = xyOnly(from.transform.position);
        float jumpOffPointDistance = float.PositiveInfinity;
        for(int index = reachableSegments.Start; index < reachableSegments.End; ++index) {
          Segment2? union = constraints.GetLineSegmentInverseArchUnion(
            toRight,
            new Segment2(
              from.Heights[index] + fromOffset, from.Heights[index + 1] + fromOffset
            )
          );
          if(union.HasValue) {
            if(union.Value.To.x > toRight.x) {
              float closestX = Mathf.Clamp(idealX, union.Value.From.x, union.Value.To.x);
              float closestDistance = Mathf.Abs(idealX - closestX);
              if(closestDistance < jumpOffPointDistance) {
                jumpOffPoint = new Vector2(
                  closestX, Intersector.GetLineSegmentYfromX(union.Value, closestX)
                );
                jumpOffPointDistance = closestDistance;
              }
            }
          }
        }

        if(jumpOffPoint.HasValue) {
          return new Segment2(jumpOffPoint.Value, toRight);
        }
      } else { // No, the destination ground is further to the right
        float y = to.GetGroundHeightAt(fromRight.x);
        if(y > fromRight.y) { // Jump to higher ground
          return null; // Could extend over this ground, let getLeftJumpPath() handle it
        }

        // See which segments of the target ground we can reach from out jump off point
        Range reachableSegments = getReachableSegments(
          to, fromRight.x, fromRight.x + constraints.MaximumJumpDistance
        );

        float idealX = fromRight.x + (constraints.MaximumJumpDistance * idealDistanceFactor);

        // Now go over the segments and look the point closest to
        Vector2? landingPoint = null;
        Vector2 toOffset = xyOnly(to.transform.position);
        float landingPointDistance = float.PositiveInfinity;
        for(int index = reachableSegments.Start; index < reachableSegments.End; ++index) {
          Segment2? union = constraints.GetLineSegmentArchUnion(
            fromRight,
            new Segment2(to.Heights[index] + toOffset, to.Heights[index + 1] + toOffset)
          );
          if(union.HasValue) {
            if(union.Value.To.x > fromRight.x) {
              float closestX = Mathf.Clamp(idealX, union.Value.From.x, union.Value.To.x);
              float closestDistance = Mathf.Abs(idealX - closestX);
              if(closestDistance < landingPointDistance) {
                landingPoint = new Vector2(
                  closestX, Intersector.GetLineSegmentYfromX(union.Value, closestX)
                );
                landingPointDistance = closestDistance;
              }
            }
          }
        }

        if(landingPoint.HasValue) {
          return new Segment2(fromRight, landingPoint.Value);
        }
      }

      return null;
    }

    /// <summary>
    ///   Determines the range of line segments within a specified coordinate range
    /// </summary>
    /// <param name="ground">Ground that will be searched for reachable line segments</param>
    /// <param name="minX">Minimum reachable X coordinate</param>
    /// <param name="maxX">Maximum reachable X coordinate</param>
    /// <returns>The range of line segments within the specified coordinate range</returns>
    private static Range getReachableSegments(Ground ground, float minX, float maxX) {
      Vector3 position = ground.transform.position;
      var range = new Range();

      // Look for the first index that is still outside of the coordinate range or,
      // if the ground begins within the coordinate range, just use index 0
      while(range.Start < ground.Heights.Length - 1) {
        if(ground.Heights[range.Start + 1].x + position.x > minX) {
          break;
        } else {
          ++range.Start;
        }
      }

      // Now look for the first index where the ground leaves the coordinate range.
      range.End = range.Start + 1;
      while(range.End < ground.Heights.Length) {
        if(ground.Heights[range.End].x + position.x > maxX) {
          break;
        } else {
          ++range.End;
        }
      }

      // To simplify the previous search, we allowed it to potentially increment
      // the index one past the height array size. If this happened, go back by
      // one index.
      if(range.End >= ground.Heights.Length) {
        range.End = ground.Heights.Length - 1;
      }

      return range;
    }

    /// <summary>Returns only the X and Y coordinates of a 3D position</summary>
    /// <param name="position">Position from which the Z coordinate will be cut</param>
    /// <returns>A 2D vector containing the input's X and Y coordinates</returns>
    private static Vector2 xyOnly(Vector3 position) {
      return new Vector2(position.x, position.y);
    }

  }

} // namespace Framework.Navigation.Platformer