| | | 1 | | using System; |
| | | 2 | | using System.Collections.Generic; |
| | | 3 | | using System.Linq; |
| | | 4 | | using UnityEngine; |
| | | 5 | | |
| | | 6 | | // Base implementation of a hierarchical object. |
| | | 7 | | // |
| | | 8 | | // The position and velocity of a hierarchical object is defined as the mean of the positions and |
| | | 9 | | // velocities of the sub-hierarchical objects. |
| | | 10 | | [Serializable] |
| | | 11 | | public class HierarchicalBase : IHierarchical { |
| | | 12 | | // Soft maximum number of sub-hierarchical objects. This is used for recursive clustering. |
| | | 13 | | private const int _maxNumSubHierarchicals = 10; |
| | | 14 | | |
| | | 15 | | // Maximum cluster radius in meters. |
| | | 16 | | private const float _clusterMaxRadius = 1000f; |
| | | 17 | | |
| | | 18 | | // List of hierarchical objects in the hierarchy level below. |
| | | 19 | | [SerializeReference] |
| | 969 | 20 | | protected List<IHierarchical> _subHierarchicals = new List<IHierarchical>(); |
| | | 21 | | |
| | | 22 | | // List of hierarchical objects pursuing this hierarchical object. |
| | | 23 | | [SerializeReference] |
| | 969 | 24 | | private List<IHierarchical> _pursuers = new List<IHierarchical>(); |
| | | 25 | | |
| | | 26 | | // Target hierarchical object. |
| | | 27 | | [SerializeReference] |
| | | 28 | | private IHierarchical _target; |
| | | 29 | | |
| | | 30 | | // List of launched hierarchical objects. |
| | | 31 | | [SerializeReference] |
| | 969 | 32 | | private List<IHierarchical> _launchedHierarchicals = new List<IHierarchical>(); |
| | | 33 | | |
| | 146 | 34 | | public IReadOnlyList<IHierarchical> SubHierarchicals => _subHierarchicals.AsReadOnly(); |
| | | 35 | | |
| | | 36 | | // Return a list of active sub-hierarchical objects. |
| | | 37 | | public IEnumerable<IHierarchical> ActiveSubHierarchicals => |
| | 0 | 38 | | _subHierarchicals.Where(s => !s.IsTerminated); |
| | | 39 | | |
| | | 40 | | public virtual IHierarchical Target { |
| | 20069 | 41 | | get => _target; |
| | 2865 | 42 | | set { _target = value; } |
| | | 43 | | } |
| | | 44 | | |
| | 6995 | 45 | | public IReadOnlyList<IHierarchical> Pursuers => _pursuers.AsReadOnly(); |
| | | 46 | | public IEnumerable<IHierarchical> ActivePursuers => |
| | 6995 | 47 | | Pursuers.Where(pursuer => !pursuer.IsTerminated); |
| | | 48 | | |
| | 0 | 49 | | public IReadOnlyList<IHierarchical> LaunchedHierarchicals => _launchedHierarchicals.AsReadOnly(); |
| | | 50 | | |
| | 0 | 51 | | public virtual Vector3 Position => GetMean(s => s.Position); |
| | 0 | 52 | | public virtual Vector3 Velocity => GetMean(s => s.Velocity); |
| | 0 | 53 | | public float Speed => Velocity.magnitude; |
| | 0 | 54 | | public virtual Vector3 Acceleration => GetMean(s => s.Acceleration); |
| | 0 | 55 | | public virtual bool IsTerminated => !ActiveSubHierarchicals.Any(); |
| | | 56 | | |
| | 0 | 57 | | public void AddSubHierarchical(IHierarchical subHierarchical) { |
| | 0 | 58 | | if (!_subHierarchicals.Contains(subHierarchical)) { |
| | 0 | 59 | | _subHierarchicals.Add(subHierarchical); |
| | 0 | 60 | | } |
| | 0 | 61 | | } |
| | | 62 | | |
| | 0 | 63 | | public void RemoveSubHierarchical(IHierarchical subHierarchical) { |
| | 0 | 64 | | _subHierarchicals.Remove(subHierarchical); |
| | 0 | 65 | | } |
| | | 66 | | |
| | 0 | 67 | | public void ClearSubHierarchicals() { |
| | 0 | 68 | | _subHierarchicals.Clear(); |
| | 0 | 69 | | } |
| | | 70 | | |
| | 146 | 71 | | public List<IHierarchical> LeafHierarchicals(bool activeOnly, bool withTargetOnly) { |
| | 146 | 72 | | var subHierarchicals = (activeOnly ? ActiveSubHierarchicals : SubHierarchicals).ToList(); |
| | 146 | 73 | | if (subHierarchicals.Count > 0) { |
| | 0 | 74 | | var leafHierarchicals = new List<IHierarchical>(); |
| | 0 | 75 | | foreach (var subHierarchical in subHierarchicals) { |
| | 0 | 76 | | leafHierarchicals.AddRange(subHierarchical.LeafHierarchicals(activeOnly, withTargetOnly)); |
| | 0 | 77 | | } |
| | 0 | 78 | | return leafHierarchicals; |
| | | 79 | | } |
| | | 80 | | |
| | 160 | 81 | | if (withTargetOnly && (Target == null || Target.IsTerminated)) { |
| | 14 | 82 | | return new List<IHierarchical>(); |
| | | 83 | | } |
| | 132 | 84 | | return new List<IHierarchical> { this }; |
| | 146 | 85 | | } |
| | | 86 | | |
| | 955 | 87 | | public void AddPursuer(IHierarchical pursuer) { |
| | 1910 | 88 | | if (!_pursuers.Contains(pursuer)) { |
| | 955 | 89 | | _pursuers.Add(pursuer); |
| | 955 | 90 | | } |
| | 955 | 91 | | } |
| | | 92 | | |
| | 0 | 93 | | public void RemovePursuer(IHierarchical pursuer) { |
| | 0 | 94 | | _pursuers.Remove(pursuer); |
| | 0 | 95 | | } |
| | | 96 | | |
| | 0 | 97 | | public void AddLaunchedHierarchical(IHierarchical hierarchical) { |
| | 0 | 98 | | if (!_launchedHierarchicals.Contains(hierarchical)) { |
| | 0 | 99 | | _launchedHierarchicals.Add(hierarchical); |
| | 0 | 100 | | } |
| | 0 | 101 | | } |
| | | 102 | | |
| | 0 | 103 | | public void RemoveTargetHierarchical(IHierarchical target) { |
| | 0 | 104 | | Target?.RemoveSubHierarchical(target); |
| | 0 | 105 | | foreach (var subHierarchical in SubHierarchicals) { |
| | 0 | 106 | | subHierarchical.RemoveTargetHierarchical(target); |
| | 0 | 107 | | } |
| | 0 | 108 | | } |
| | | 109 | | |
| | 0 | 110 | | public void RecursiveCluster(int maxClusterSize) { |
| | 0 | 111 | | if (SubHierarchicals.Count > 0) { |
| | 0 | 112 | | foreach (var subHierarchical in SubHierarchicals) { |
| | 0 | 113 | | subHierarchical.RecursiveCluster(maxClusterSize); |
| | 0 | 114 | | } |
| | 0 | 115 | | return; |
| | | 116 | | } |
| | 0 | 117 | | if (Target == null) { |
| | 0 | 118 | | return; |
| | | 119 | | } |
| | 0 | 120 | | int numActiveSubHierarchicals = Target.ActiveSubHierarchicals.Count(); |
| | 0 | 121 | | if (numActiveSubHierarchicals <= maxClusterSize) { |
| | 0 | 122 | | return; |
| | | 123 | | } |
| | | 124 | | |
| | | 125 | | // Perform clustering on the assigned targets. |
| | | 126 | | // TODO(titan): Define a better heuristic for choosing the clustering algorithm to minimize the |
| | | 127 | | // size and radius of each cluster without generating too many clusters. |
| | 0 | 128 | | IClusterer clusterer = null; |
| | 0 | 129 | | if (numActiveSubHierarchicals >= _maxNumSubHierarchicals * Mathf.Max(maxClusterSize / 2, 1)) { |
| | 0 | 130 | | clusterer = new KMeansClusterer(_maxNumSubHierarchicals); |
| | 0 | 131 | | } else { |
| | 0 | 132 | | clusterer = new AgglomerativeClusterer(maxClusterSize, _clusterMaxRadius); |
| | 0 | 133 | | } |
| | 0 | 134 | | List<Cluster> clusters = clusterer.Cluster(Target.ActiveSubHierarchicals); |
| | | 135 | | |
| | | 136 | | // Generate sub-hierarchical objects to manage the target clusters. |
| | 0 | 137 | | foreach (var cluster in clusters) { |
| | 0 | 138 | | var subHierarchical = new HierarchicalBase { Target = cluster }; |
| | 0 | 139 | | AddSubHierarchical(subHierarchical); |
| | 0 | 140 | | subHierarchical.RecursiveCluster(maxClusterSize); |
| | 0 | 141 | | } |
| | 0 | 142 | | } |
| | | 143 | | |
| | 0 | 144 | | public bool AssignNewTarget(IHierarchical hierarchical, int capacity) { |
| | | 145 | | // TODO(titan): Abstract the target picking strategy to its own interface and class. |
| | | 146 | | // TODO(titan): Consider whether the OnAssignSubInterceptor and OnReassignTarget events should |
| | | 147 | | // be modified to refer to the new parent interceptor. |
| | 0 | 148 | | hierarchical.Target = FindBestHierarchicalTarget(hierarchical, capacity) ?? |
| | | 149 | | FindBestLeafHierarchicalTarget(hierarchical, capacity); |
| | 0 | 150 | | return hierarchical.Target != null; |
| | 0 | 151 | | } |
| | | 152 | | |
| | 0 | 153 | | private Vector3 GetMean(System.Func<IHierarchical, Vector3> selector) { |
| | 0 | 154 | | Vector3 sum = Vector3.zero; |
| | 0 | 155 | | int count = 0; |
| | 0 | 156 | | foreach (var subHierarchical in ActiveSubHierarchicals) { |
| | 0 | 157 | | sum += selector(subHierarchical); |
| | 0 | 158 | | ++count; |
| | 0 | 159 | | } |
| | 0 | 160 | | if (count == 0) { |
| | 0 | 161 | | return Vector3.zero; |
| | | 162 | | } |
| | 0 | 163 | | return sum / count; |
| | 0 | 164 | | } |
| | | 165 | | |
| | 0 | 166 | | private IHierarchical FindBestHierarchicalTarget(IHierarchical hierarchical, int capacity) { |
| | | 167 | | // Find all sub-hierarchical objects that have at least one active target but no more than the |
| | | 168 | | // interceptor capacity. |
| | 0 | 169 | | List<IHierarchical> FindPossibleHierarchicalTargets(IHierarchical hierarchical) { |
| | 0 | 170 | | if (hierarchical.Target == null) { |
| | 0 | 171 | | return new List<IHierarchical>(); |
| | | 172 | | } |
| | 0 | 173 | | int numActiveTargets = hierarchical.Target.ActiveSubHierarchicals.Count(); |
| | 0 | 174 | | if (numActiveTargets > 0 && numActiveTargets <= capacity) { |
| | 0 | 175 | | return new List<IHierarchical> { hierarchical.Target }; |
| | | 176 | | } |
| | | 177 | | |
| | 0 | 178 | | var possibleTargets = new List<IHierarchical>(); |
| | 0 | 179 | | foreach (var subHierarchical in hierarchical.SubHierarchicals) { |
| | 0 | 180 | | possibleTargets.AddRange(FindPossibleHierarchicalTargets(subHierarchical)); |
| | 0 | 181 | | } |
| | 0 | 182 | | return possibleTargets; |
| | 0 | 183 | | } |
| | 0 | 184 | | List<IHierarchical> possibleTargets = FindPossibleHierarchicalTargets(this); |
| | 0 | 185 | | if (possibleTargets.Count == 0) { |
| | 0 | 186 | | return null; |
| | | 187 | | } |
| | | 188 | | |
| | | 189 | | // Use a maximum speed assignment to select the target resulting in the maximum intercept speed. |
| | 0 | 190 | | IAssignment targetAssignment = |
| | | 191 | | new MaxSpeedAssignment(Assignment.Assignment_EvenAssignment_Assign); |
| | 0 | 192 | | List<AssignmentItem> assignments = |
| | | 193 | | targetAssignment.Assign(new List<IHierarchical> { hierarchical }, possibleTargets); |
| | 0 | 194 | | if (assignments.Count != 1) { |
| | 0 | 195 | | return null; |
| | | 196 | | } |
| | 0 | 197 | | return assignments[0].Second; |
| | 0 | 198 | | } |
| | | 199 | | |
| | 0 | 200 | | private IHierarchical FindBestLeafHierarchicalTarget(IHierarchical hierarchical, int capacity) { |
| | 0 | 201 | | List<IHierarchical> leafHierarchicalTargets = |
| | | 202 | | LeafHierarchicals(activeOnly: true, withTargetOnly: true) |
| | 0 | 203 | | .Select(hierarchical => hierarchical.Target) |
| | | 204 | | .ToList(); |
| | 0 | 205 | | if (leafHierarchicalTargets.Count == 0) { |
| | 0 | 206 | | return null; |
| | | 207 | | } |
| | | 208 | | |
| | | 209 | | // Use a maximum speed assignment to select the target resulting in the maximum intercept speed. |
| | 0 | 210 | | IAssignment targetAssignment = |
| | | 211 | | new MaxSpeedAssignment(Assignment.Assignment_EvenAssignment_Assign); |
| | 0 | 212 | | List<AssignmentItem> assignments = |
| | | 213 | | targetAssignment.Assign(new List<IHierarchical> { hierarchical }, leafHierarchicalTargets); |
| | 0 | 214 | | if (assignments.Count != 1) { |
| | 0 | 215 | | return null; |
| | | 216 | | } |
| | | 217 | | |
| | | 218 | | // Remove as many target sub-hierarchical objects until the interceptor capacity. |
| | 0 | 219 | | var targetSubHierarchicals = assignments[0].Second.ActiveSubHierarchicals.ToList(); |
| | 0 | 220 | | var filteredSubHierarchicals = |
| | | 221 | | targetSubHierarchicals |
| | | 222 | | .OrderBy(subHierarchical => |
| | 0 | 223 | | Vector3.Distance(subHierarchical.Position, assignments[0].Second.Position)) |
| | | 224 | | .Take(capacity); |
| | 0 | 225 | | var targetHierarchical = new HierarchicalBase(); |
| | 0 | 226 | | foreach (var subHierarchical in filteredSubHierarchicals) { |
| | 0 | 227 | | targetHierarchical.AddSubHierarchical(subHierarchical); |
| | 0 | 228 | | } |
| | 0 | 229 | | return targetHierarchical; |
| | 0 | 230 | | } |
| | | 231 | | } |