context: #region Copyright & License Information
  /*
   * Copyright 2007-2015 The OpenRA Developers (see AUTHORS)
   * This file is part of OpenRA, which is free software. It is made
   * available to you under the terms of the GNU General Public License
   * as published by the Free Software Foundation. For more information,
   * see COPYING.
   */
  #endregion
  
  using System.Collections.Generic;
  using System.Drawing;
  using System.Linq;
  using OpenRA.Effects;
  using OpenRA.GameRules;
  using OpenRA.Graphics;
  using OpenRA.Mods.Common.Graphics;
  using OpenRA.Mods.Common.Traits;
  using OpenRA.Traits;
  
  namespace OpenRA.Mods.Common.Effects
  {
  	public class MissileInfo : IProjectileInfo
  	{
  		[Desc("Name of the image containing the projectile sequence.")]
  		public readonly string Image = null;
  
  		[Desc("Projectile sequence name.")]
  		[SequenceReference("Image")] public readonly string Sequence = "idle";
  
  		[Desc("Palette used to render the projectile sequence.")]
  		[PaletteReference] public readonly string Palette = "effect";
  
  		[Desc("Should the projectile's shadow be rendered?")]
  		public readonly bool Shadow = false;
  
  		[Desc("Minimum vertical launch angle (pitch).")]
  		public readonly WAngle MinimumLaunchAngle = WAngle.Zero;
  
  		[Desc("Maximum vertical launch angle (pitch).")]
  		public readonly WAngle MaximumLaunchAngle = new WAngle(64);
  
  		[Desc("Minimum launch speed in WDist / tick")]
  		public readonly WDist MinimumLaunchSpeed = new WDist(75);
  
  		[Desc("Maximum launch speed in WDist / tick")]
  		public readonly WDist MaximumLaunchSpeed = new WDist(200);
  
  		[Desc("Maximum projectile speed in WDist / tick")]
  		public readonly WDist MaximumSpeed = new WDist(384);
  
  		[Desc("Projectile acceleration when propulsion activated.")]
  		public readonly WDist Acceleration = new WDist(5);
  
  		[Desc("How many ticks before this missile is armed and can explode.")]
  		public readonly int Arm = 0;
  
  		[Desc("Is the missile blocked by actors with BlocksProjectiles: trait.")]
  		public readonly bool Blockable = true;
  
  		[Desc("Maximum offset at the maximum range")]
  		public readonly WDist Inaccuracy = WDist.Zero;
  
  		[Desc("Probability of locking onto and following target.")]
  		public readonly int LockOnProbability = 100;
  
  		[Desc("Horizontal rate of turn.")]
  		public readonly int HorizontalRateOfTurn = 5;
  
  		[Desc("Vertical rate of turn.")]
  		public readonly int VerticalRateOfTurn = 6;
  
  		[Desc("Run out of fuel after being activated this many ticks. Zero for unlimited fuel.")]
  		public readonly int RangeLimit = 0;
  
  		[Desc("Explode when running out of fuel.")]
  		public readonly bool ExplodeWhenEmpty = true;
  
  		[Desc("Altitude above terrain below which to explode. Zero effectively deactivates airburst.")]
  		public readonly WDist AirburstAltitude = WDist.Zero;
  
  		[Desc("Cruise altitude. Zero means no cruise altitude used.")]
  		public readonly WDist CruiseAltitude = new WDist(512);
  
  		[Desc("Activate homing mechanism after this many ticks.")]
  		public readonly int HomingActivationDelay = 0;
  
  		[Desc("Image that contains the trail animation.")]
  		public readonly string TrailImage = null;
  
  		[Desc("Smoke sequence name.")]
  		[SequenceReference("TrailImage")] public readonly string TrailSequence = "idle";
  
  		[Desc("Palette used to render the smoke sequence.")]
  		[PaletteReference("TrailUsePlayerPalette")] public readonly string TrailPalette = "effect";
  
  		[Desc("Use the Player Palette to render the smoke sequence.")]
  		public readonly bool TrailUsePlayerPalette = false;
  
  		[Desc("Interval in ticks between spawning smoke animation.")]
  		public readonly int TrailInterval = 2;
  
  		[Desc("Should smoke animation be spawned when the propulsion is not activated.")]
  		public readonly bool TrailWhenDeactivated = false;
  
  		public readonly int ContrailLength = 0;
  
  		public readonly Color ContrailColor = Color.White;
  
  		public readonly bool ContrailUsePlayerColor = false;
  
  		public readonly int ContrailDelay = 1;
  
  		[Desc("Should missile targeting be thrown off by nearby actors with JamsMissiles.")]
  		public readonly bool Jammable = true;
  
  		[Desc("Range of facings by which jammed missiles can stray from current path.")]
  		public readonly int JammedDiversionRange = 20;
  
  		[Desc("Explodes when leaving the following terrain type, e.g., Water for torpedoes.")]
  		public readonly string BoundToTerrainType = "";
  
  		[Desc("Explodes when inside this proximity radius to target.",
  			"Note: If this value is lower than the missile speed, this check might",
  			"not trigger fast enough, causing the missile to fly past the target.")]
  		public readonly WDist CloseEnough = new WDist(298);
  
  		public IEffect Create(ProjectileArgs args) { return new Missile(this, args); }
  	}
  
  	// TODO: double check square roots!!!
  	public class Missile : IEffect, ISync
  	{
  		enum States
  		{
  			Freefall,
  			Homing,
  			Hitting
  		}
  
  		readonly MissileInfo info;
  		readonly ProjectileArgs args;
  		readonly Animation anim;
  
  		// NOTE: Might be desirable to unhardcode the number -10
  		readonly WVec gravity = new WVec(0, 0, -10);
  
  		int ticks;
  
  		int ticksToNextSmoke;
  		ContrailRenderable contrail;
  		string trailPalette;
  
  		States state;
  		bool targetPassedBy;
  		bool lockOn = false;
  		bool allowPassBy; // TODO: use this also with high minimum launch angle settings
  
  		WPos targetPosition;
  		WVec offset;
  
  		WVec tarVel;
  		WVec predVel;
  
  		[Sync] WPos pos;
  		WVec velocity;
  		int speed;
  		int loopRadius;
  
  		int renderFacing;
  		[Sync] int hFacing;
  		[Sync] int vFacing;
  
  		public Actor SourceActor { get { return args.SourceActor; } }
  		public Target GuidedTarget { get { return args.GuidedTarget; } }
  
  		public Missile(MissileInfo info, ProjectileArgs args)
  		{
  			this.info = info;
  			this.args = args;
  
  			pos = args.Source;
  			hFacing = args.Facing;
  			targetPosition = args.PassiveTarget;
  
  			var world = args.SourceActor.World;
  
  			if (info.Inaccuracy.Length > 0)
  			{
  				var inaccuracy = OpenRA.Traits.Util.ApplyPercentageModifiers(info.Inaccuracy.Length, args.InaccuracyModifiers);
  				offset = WVec.FromPDF(world.SharedRandom, 2) * inaccuracy / 1024;
  			}
  
  			DetermineLaunchSpeedAndAngle(world, out speed, out vFacing);
  
  			velocity = new WVec(0, -speed, 0)
  				.Rotate(new WRot(WAngle.FromFacing(vFacing), WAngle.Zero, WAngle.Zero))
  				.Rotate(new WRot(WAngle.Zero, WAngle.Zero, WAngle.FromFacing(hFacing)));
  
  			if (world.SharedRandom.Next(100) <= info.LockOnProbability)
  				lockOn = true;
  
  			if (!string.IsNullOrEmpty(info.Image))
  			{
  				anim = new Animation(world, info.Image, () => renderFacing);
  				anim.PlayRepeating(info.Sequence);
  			}
  
  			if (info.ContrailLength > 0)
  			{
  				var color = info.ContrailUsePlayerColor ? ContrailRenderable.ChooseColor(args.SourceActor) : info.ContrailColor;
  				contrail = new ContrailRenderable(world, color, info.ContrailLength, info.ContrailDelay, 0);
  			}
  
  			trailPalette = info.TrailPalette;
  			if (info.TrailUsePlayerPalette)
  				trailPalette += args.SourceActor.Owner.InternalName;
  		}
  
  		static int LoopRadius(int speed, int rot)
  		{
  			// loopRadius in w-units = speed in w-units per tick / angular speed in radians per tick
  			// angular speed in radians per tick = rot in facing units per tick * (pi radians / 128 facing units)
  			// pi = 314 / 100
  			// ==> loopRadius = (speed * 128 * 100) / (314 * rot)
  			return (speed * 6400) / (157 * rot);
  		}
  
  		void DetermineLaunchSpeedAndAngleForIncline(int predClfDist, int diffClfMslHgt, int relTarHorDist,
  			out int speed, out int vFacing)
  		{
  			speed = info.MaximumLaunchSpeed.Length;
  
  			// Find smallest vertical facing, for which the missile will be able to climb terrAltDiff w-units
  			// within hHeightChange w-units all the while ending the ascent with vertical facing 0
  			vFacing = info.MaximumLaunchAngle.Angle >> 2;
  
  			// Compute minimum speed necessary to both be able to face directly upwards and have enough space
  			// to hit the target without passing it by (and thus having to do horizontal loops)
  			var minSpeed = ((System.Math.Min(predClfDist * 1024 / (1024 - WAngle.FromFacing(vFacing).Sin()),
  					(relTarHorDist + predClfDist) * 1024 / (2 * (2048 - WAngle.FromFacing(vFacing).Sin())))
  				* info.VerticalRateOfTurn * 157) / 6400).Clamp(info.MinimumLaunchSpeed.Length, info.MaximumLaunchSpeed.Length);
  
  			if ((sbyte)vFacing < 0)
  				speed = minSpeed;
  			else if (!WillClimbWithinDistance(vFacing, loopRadius, predClfDist, diffClfMslHgt)
  				&& !WillClimbAroundInclineTop(vFacing, loopRadius, predClfDist, diffClfMslHgt, speed))
  			{
  				// Find highest speed greater than the above minimum that allows the missile
  				// to surmount the incline
  				var vFac = vFacing;
  				speed = BisectionSearch(minSpeed, info.MaximumLaunchSpeed.Length, spd =>
  				{
  					var lpRds = LoopRadius(spd, info.VerticalRateOfTurn);
  					return WillClimbWithinDistance(vFac, lpRds, predClfDist, diffClfMslHgt)
  						|| WillClimbAroundInclineTop(vFac, lpRds, predClfDist, diffClfMslHgt, spd);
  				});
  			}
  			else
  			{
  				// Find least vertical facing that will allow the missile to climb
  				// terrAltDiff w-units within hHeightChange w-units
  				// all the while ending the ascent with vertical facing 0
  				vFacing = BisectionSearch(System.Math.Max((sbyte)(info.MinimumLaunchAngle.Angle >> 2), (sbyte)0),
  					(sbyte)(info.MaximumLaunchAngle.Angle >> 2),
  					vFac => !WillClimbWithinDistance(vFac, loopRadius, predClfDist, diffClfMslHgt)) + 1;
  			}
  		}
  
  		// TODO: Double check Launch parameter determination
  		void DetermineLaunchSpeedAndAngle(World world, out int speed, out int vFacing)
  		{
  			speed = info.MaximumLaunchSpeed.Length;
  			loopRadius = LoopRadius(speed, info.VerticalRateOfTurn);
  
  			// Compute current distance from target position
  			var tarDistVec = targetPosition + offset - pos;
  			var relTarHorDist = tarDistVec.HorizontalLength;
  
  			int predClfHgt, predClfDist, lastHtChg, lastHt;
  			InclineLookahead(world, relTarHorDist, out predClfHgt, out predClfDist, out lastHtChg, out lastHt);
  
  			// Height difference between the incline height and missile height
  			var diffClfMslHgt = predClfHgt - pos.Z;
  
  			// Incline coming up
  			if (diffClfMslHgt >= 0 && predClfDist > 0)
  				DetermineLaunchSpeedAndAngleForIncline(predClfDist, diffClfMslHgt, relTarHorDist, out speed, out vFacing);
  			else if (lastHt != 0)
  			{
  				vFacing = System.Math.Max((sbyte)(info.MinimumLaunchAngle.Angle >> 2), (sbyte)0);
  				speed = info.MaximumLaunchSpeed.Length;
  			}
  			else
  			{
  				// Set vertical facing so that the missile faces its target
  				var vDist = new WVec(-tarDistVec.Z, -relTarHorDist, 0);
  				vFacing = (sbyte)OpenRA.Traits.Util.GetFacing(vDist, 0);
  
  				// Do not accept -1 as valid vertical facing since it is usually a numerical error
  				// and will lead to premature descent and crashing into the ground
  				if (vFacing == -1)
  					vFacing = 0;
  
  				// Make sure the chosen vertical facing adheres to prescribed bounds
  				vFacing = vFacing.Clamp((sbyte)(info.MinimumLaunchAngle.Angle >> 2),
  					(sbyte)(info.MaximumLaunchAngle.Angle >> 2));
  			}
  		}
  
  		// Will missile be able to climb terrAltDiff w-units within hHeightChange w-units
  		// all the while ending the ascent with vertical facing 0
  		// Calling this function only makes sense when vFacing is nonnegative
  		static bool WillClimbWithinDistance(int vFacing, int loopRadius, int predClfDist, int diffClfMslHgt)
  		{
  			// Missile's horizontal distance from loop's center
  			var missDist = loopRadius * WAngle.FromFacing(vFacing).Sin() / 1024;
  
  			// Missile's height below loop's top
  			var missHgt = loopRadius * (1024 - WAngle.FromFacing(vFacing).Cos()) / 1024;
  
  			// Height that would be climbed without changing vertical facing
  			// for a horizontal distance hHeightChange - missDist
  			var hgtChg = (predClfDist - missDist) * WAngle.FromFacing(vFacing).Tan() / 1024;
  
  			// Check if total manoeuvre height enough to overcome the incline's height
  			return hgtChg + missHgt >= diffClfMslHgt;
  		}
  
  		// This function checks if the missile's vertical facing is
  		// nonnegative, and the incline top's horizontal distance from the missile is
  		// less than loopRadius * (1024 - WAngle.FromFacing(vFacing).Sin()) / 1024
  		static bool IsNearInclineTop(int vFacing, int loopRadius, int predClfDist)
  		{
  			return vFacing >= 0 && predClfDist <= loopRadius * (1024 - WAngle.FromFacing(vFacing).Sin()) / 1024;
  		}
  
  		// Will missile climb around incline top if bringing vertical facing
  		// down to zero on an arc of radius loopRadius
  		// Calling this function only makes sense when IsNearInclineTop returns true
  		static bool WillClimbAroundInclineTop(int vFacing, int loopRadius, int predClfDist, int diffClfMslHgt, int speed)
  		{
  			// Vector from missile's current position pointing to the loop's center
  			var radius = new WVec(loopRadius, 0, 0)
  				.Rotate(new WRot(WAngle.Zero, WAngle.Zero, WAngle.FromFacing(System.Math.Max(0, 64 - vFacing))));
  
  			// Vector from loop's center to incline top + 64 hardcoded in height buffer zone
  			var topVector = new WVec(predClfDist, diffClfMslHgt + 64, 0) - radius;
  
  			// Check if incline top inside of the vertical loop
  			return topVector.Length <= loopRadius;
  		}
  
  		static int BisectionSearch(int lowerBound, int upperBound, System.Func<int, bool> testCriterion)
  		{
  			// Assuming that there exists an integer N between lowerBound and upperBound
  			// for which testCriterion returns true as well as all integers less than N,
  			// and for which testCriterion returns false for all integers greater than N,
  			// this function finds N.
  			while (upperBound - lowerBound > 1)
  			{
  				var middle = (upperBound + lowerBound) / 2;
  
  				if (testCriterion(middle))
  					lowerBound = middle;
  				else
  					upperBound = middle;
  			}
  
  			return lowerBound;
  		}
  
  		bool JammedBy(TraitPair<JamsMissiles> tp)
  		{
  			if ((tp.Actor.CenterPosition - pos).HorizontalLengthSquared > tp.Trait.Range.LengthSquared)
  				return false;
  
  			if (tp.Actor.Owner.Stances[args.SourceActor.Owner] == Stance.Ally && !tp.Trait.AlliedMissiles)
  				return false;
  
  			return tp.Actor.World.SharedRandom.Next(100 / tp.Trait.Chance) == 0;
  		}
  
  		void ChangeSpeed(int sign = 1)
  		{
  			speed = (speed + sign * info.Acceleration.Length).Clamp(0, info.MaximumSpeed.Length);
  
  			// Compute the vertical loop radius
  			loopRadius = LoopRadius(speed, info.VerticalRateOfTurn);
  		}
  
  		WVec FreefallTick()
  		{
  			// Compute the projectile's freefall displacement
  			var move = velocity + gravity / 2;
  			velocity += gravity;
  			var velRatio = info.MaximumSpeed.Length * 1024 / velocity.Length;
  			if (velRatio < 1024)
  				velocity = velocity * velRatio / 1024;
  
  			return move;
  		}
  
  		// NOTE: It might be desirable to make lookahead more intelligent by outputting more information
  		//       than just the highest point in the lookahead distance
  		void InclineLookahead(World world, int distCheck, out int predClfHgt, out int predClfDist, out int lastHtChg, out int lastHt)
  		{
  			predClfHgt = 0; // Highest probed terrain height
  			predClfDist = 0; // Distance from highest point
  			lastHtChg = 0; // Distance from last time the height changes
  			lastHt = 0; // Height just before the last height change
  
  			// NOTE: Might be desired to unhardcode the lookahead step size
  			var stepSize = 32;
  			var step = new WVec(0, -stepSize, 0)
  				.Rotate(new WRot(WAngle.Zero, WAngle.Zero, WAngle.FromFacing(hFacing))); // Step vector of length 128
  
  			// Probe terrain ahead of the missile
  			// NOTE: Might be desired to unhardcode maximum lookahead distance
  			var maxLookaheadDistance = loopRadius * 4;
  			var posProbe = pos;
  			var curDist = 0;
  			var tickLimit = System.Math.Min(maxLookaheadDistance, distCheck) / stepSize;
  			var prevHt = 0;
  
  			// TODO: Make sure cell on map!!!
  			for (var tick = 0; tick <= tickLimit; tick++)
  			{
  
gt: 				posProbe += step;