1 #region Copyright & License Information 2 /* 3 * Copyright 2007-2020 The OpenRA Developers (see AUTHORS) 4 * This file is part of OpenRA, which is free software. It is made 5 * available to you under the terms of the GNU General Public License 6 * as published by the Free Software Foundation, either version 3 of 7 * the License, or (at your option) any later version. For more 8 * information, see COPYING. 9 */ 10 #endregion 11 12 using System.Collections.Generic; 13 using System.Linq; 14 using OpenRA.Mods.Common.Traits; 15 16 namespace OpenRA.Mods.Common 17 { 18 public static class WorldExtensions 19 { 20 /// <summary> 21 /// Finds all the actors of which their health radius is intersected by a line (with a definable width) between two points. 22 /// </summary> 23 /// <param name="world">The engine world the line intersection is to be done in.</param> 24 /// <param name="lineStart">The position the line should start at</param> 25 /// <param name="lineEnd">The position the line should end at</param> 26 /// <param name="lineWidth">How close an actor's health radius needs to be to the line to be considered 'intersected' by the line</param> 27 /// <returns>A list of all the actors intersected by the line</returns> FindActorsOnLine(this World world, WPos lineStart, WPos lineEnd, WDist lineWidth, bool onlyBlockers = false)28 public static IEnumerable<Actor> FindActorsOnLine(this World world, WPos lineStart, WPos lineEnd, WDist lineWidth, bool onlyBlockers = false) 29 { 30 // This line intersection check is done by first just finding all actors within a square that starts at the source, and ends at the target. 31 // Then we iterate over this list, and find all actors for which their health radius is at least within lineWidth of the line. 32 // For actors without a health radius, we simply check their center point. 33 // The square in which we select all actors must be large enough to encompass the entire line's width. 34 // xDir and yDir must never be 0, otherwise the overscan will be 0 in the respective direction. 35 var xDiff = lineEnd.X - lineStart.X; 36 var yDiff = lineEnd.Y - lineStart.Y; 37 var xDir = xDiff < 0 ? -1 : 1; 38 var yDir = yDiff < 0 ? -1 : 1; 39 40 var dir = new WVec(xDir, yDir, 0); 41 var largestValidActorRadius = onlyBlockers ? world.ActorMap.LargestBlockingActorRadius.Length : world.ActorMap.LargestActorRadius.Length; 42 var overselect = dir * (1024 + lineWidth.Length + largestValidActorRadius); 43 var finalTarget = lineEnd + overselect; 44 var finalSource = lineStart - overselect; 45 46 var actorsInSquare = world.ActorMap.ActorsInBox(finalTarget, finalSource); 47 var intersectedActors = new List<Actor>(); 48 49 foreach (var currActor in actorsInSquare) 50 { 51 var actorWidth = 0; 52 var shapes = currActor.TraitsImplementing<HitShape>().Where(Exts.IsTraitEnabled); 53 if (shapes.Any()) 54 actorWidth = shapes.Max(h => h.Info.Type.OuterRadius.Length); 55 56 var projection = MinimumPointLineProjection(lineStart, lineEnd, currActor.CenterPosition); 57 var distance = (currActor.CenterPosition - projection).HorizontalLength; 58 var maxReach = actorWidth + lineWidth.Length; 59 60 if (distance <= maxReach) 61 intersectedActors.Add(currActor); 62 } 63 64 return intersectedActors; 65 } 66 FindBlockingActorsOnLine(this World world, WPos lineStart, WPos lineEnd, WDist lineWidth)67 public static IEnumerable<Actor> FindBlockingActorsOnLine(this World world, WPos lineStart, WPos lineEnd, WDist lineWidth) 68 { 69 return world.FindActorsOnLine(lineStart, lineEnd, lineWidth, true); 70 } 71 72 /// <summary> 73 /// Finds all the actors of which their health radius might be intersected by a specified circle. 74 /// </summary> FindActorsOnCircle(this World world, WPos origin, WDist r)75 public static IEnumerable<Actor> FindActorsOnCircle(this World world, WPos origin, WDist r) 76 { 77 return world.FindActorsInCircle(origin, r + world.ActorMap.LargestActorRadius); 78 } 79 80 /// <summary> 81 /// Find the point (D) on a line (A-B) that is closest to the target point (C). 82 /// </summary> 83 /// <param name="lineStart">The source point (tail) of the line</param> 84 /// <param name="lineEnd">The target point (head) of the line</param> 85 /// <param name="point">The target point that the minimum distance should be found to</param> 86 /// <returns>The WPos that is the point on the line that is closest to the target point</returns> MinimumPointLineProjection(WPos lineStart, WPos lineEnd, WPos point)87 public static WPos MinimumPointLineProjection(WPos lineStart, WPos lineEnd, WPos point) 88 { 89 var squaredLength = (lineEnd - lineStart).HorizontalLengthSquared; 90 91 // Line has zero length, so just use the lineEnd position as the closest position. 92 if (squaredLength == 0) 93 return lineEnd; 94 95 // Consider the line extending the segment, parameterized as target + t (source - target). 96 // We find projection of point onto the line. 97 // It falls where t = [(point - target) . (source - target)] / |source - target|^2 98 // The normal DotProduct math would be (xDiff + yDiff) / dist, where dist = (target - source).LengthSquared; 99 // But in order to avoid floating points, we do not divide here, but rather work with the large numbers as far as possible. 100 // We then later divide by dist, only AFTER we have multiplied by the dotproduct. 101 var xDiff = ((long)point.X - lineEnd.X) * (lineStart.X - lineEnd.X); 102 var yDiff = ((long)point.Y - lineEnd.Y) * (lineStart.Y - lineEnd.Y); 103 var t = xDiff + yDiff; 104 105 // Beyond the 'target' end of the segment 106 if (t < 0) 107 return lineEnd; 108 109 // Beyond the 'source' end of the segment 110 if (t > squaredLength) 111 return lineStart; 112 113 // Projection falls on the segment 114 return WPos.Lerp(lineEnd, lineStart, t, squaredLength); 115 } 116 } 117 } 118