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; 13 using System.Collections.Generic; 14 using System.Linq; 15 using OpenRA.Activities; 16 using OpenRA.Mods.Common.Pathfinder; 17 using OpenRA.Mods.Common.Traits; 18 using OpenRA.Primitives; 19 using OpenRA.Traits; 20 21 namespace OpenRA.Mods.Common.Activities 22 { 23 public class Move : Activity 24 { 25 static readonly List<CPos> NoPath = new List<CPos>(); 26 27 readonly Mobile mobile; 28 readonly WDist nearEnough; 29 readonly Func<BlockedByActor, List<CPos>> getPath; 30 readonly Actor ignoreActor; 31 readonly Color? targetLineColor; 32 33 static readonly BlockedByActor[] PathSearchOrder = 34 { 35 BlockedByActor.All, 36 BlockedByActor.Immovable, 37 BlockedByActor.Stationary, 38 BlockedByActor.None 39 }; 40 41 List<CPos> path; 42 CPos? destination; 43 44 // For dealing with blockers 45 bool hasWaited; 46 int waitTicksRemaining; 47 48 // To work around queued activity issues while minimizing changes to legacy behaviour 49 bool evaluateNearestMovableCell; 50 51 // Scriptable move order 52 // Ignores lane bias and nearby units Move(Actor self, CPos destination, Color? targetLineColor = null)53 public Move(Actor self, CPos destination, Color? targetLineColor = null) 54 { 55 mobile = self.Trait<Mobile>(); 56 57 getPath = check => 58 { 59 List<CPos> path; 60 using (var search = 61 PathSearch.FromPoint(self.World, mobile.Locomotor, self, mobile.ToCell, destination, check) 62 .WithoutLaneBias()) 63 path = mobile.Pathfinder.FindPath(search); 64 return path; 65 }; 66 67 this.destination = destination; 68 this.targetLineColor = targetLineColor; 69 nearEnough = WDist.Zero; 70 } 71 Move(Actor self, CPos destination, WDist nearEnough, Actor ignoreActor = null, bool evaluateNearestMovableCell = false, Color? targetLineColor = null)72 public Move(Actor self, CPos destination, WDist nearEnough, Actor ignoreActor = null, bool evaluateNearestMovableCell = false, 73 Color? targetLineColor = null) 74 { 75 mobile = self.Trait<Mobile>(); 76 77 getPath = check => 78 { 79 if (!this.destination.HasValue) 80 return NoPath; 81 82 return mobile.Pathfinder.FindUnitPath(mobile.ToCell, this.destination.Value, self, ignoreActor, check); 83 }; 84 85 // Note: Will be recalculated from OnFirstRun if evaluateNearestMovableCell is true 86 this.destination = destination; 87 88 this.nearEnough = nearEnough; 89 this.ignoreActor = ignoreActor; 90 this.evaluateNearestMovableCell = evaluateNearestMovableCell; 91 this.targetLineColor = targetLineColor; 92 } 93 Move(Actor self, CPos destination, SubCell subCell, WDist nearEnough, Color? targetLineColor = null)94 public Move(Actor self, CPos destination, SubCell subCell, WDist nearEnough, Color? targetLineColor = null) 95 { 96 mobile = self.Trait<Mobile>(); 97 98 getPath = check => mobile.Pathfinder.FindUnitPathToRange( 99 mobile.FromCell, subCell, self.World.Map.CenterOfSubCell(destination, subCell), nearEnough, self, check); 100 101 this.destination = destination; 102 this.nearEnough = nearEnough; 103 this.targetLineColor = targetLineColor; 104 } 105 Move(Actor self, Target target, WDist range, Color? targetLineColor = null)106 public Move(Actor self, Target target, WDist range, Color? targetLineColor = null) 107 { 108 mobile = self.Trait<Mobile>(); 109 110 getPath = check => 111 { 112 if (!target.IsValidFor(self)) 113 return NoPath; 114 115 return mobile.Pathfinder.FindUnitPathToRange( 116 mobile.ToCell, mobile.ToSubCell, target.CenterPosition, range, self, check); 117 }; 118 119 destination = null; 120 nearEnough = range; 121 this.targetLineColor = targetLineColor; 122 } 123 Move(Actor self, Func<BlockedByActor, List<CPos>> getPath, Color? targetLineColor = null)124 public Move(Actor self, Func<BlockedByActor, List<CPos>> getPath, Color? targetLineColor = null) 125 { 126 mobile = self.Trait<Mobile>(); 127 128 this.getPath = getPath; 129 130 destination = null; 131 nearEnough = WDist.Zero; 132 this.targetLineColor = targetLineColor; 133 } 134 HashList(List<T> xs)135 static int HashList<T>(List<T> xs) 136 { 137 var hash = 0; 138 var n = 0; 139 foreach (var x in xs) 140 hash += n++ * x.GetHashCode(); 141 142 return hash; 143 } 144 EvalPath(BlockedByActor check)145 List<CPos> EvalPath(BlockedByActor check) 146 { 147 var path = getPath(check).TakeWhile(a => a != mobile.ToCell).ToList(); 148 mobile.PathHash = HashList(path); 149 return path; 150 } 151 OnFirstRun(Actor self)152 protected override void OnFirstRun(Actor self) 153 { 154 if (evaluateNearestMovableCell && destination.HasValue) 155 { 156 var movableDestination = mobile.NearestMoveableCell(destination.Value); 157 destination = mobile.CanEnterCell(movableDestination, check: BlockedByActor.Immovable) ? movableDestination : (CPos?)null; 158 } 159 160 // TODO: Change this to BlockedByActor.Stationary after improving the local avoidance behaviour 161 foreach (var check in PathSearchOrder) 162 { 163 path = EvalPath(check); 164 if (path.Count > 0) 165 return; 166 } 167 } 168 Tick(Actor self)169 public override bool Tick(Actor self) 170 { 171 mobile.TurnToMove = false; 172 173 if (IsCanceling && mobile.CanStayInCell(mobile.ToCell)) 174 { 175 if (path != null) 176 path.Clear(); 177 178 return true; 179 } 180 181 if (mobile.IsTraitDisabled || mobile.IsTraitPaused) 182 return false; 183 184 if (destination == mobile.ToCell) 185 return true; 186 187 if (path.Count == 0) 188 { 189 destination = mobile.ToCell; 190 return false; 191 } 192 193 destination = path[0]; 194 195 var nextCell = PopPath(self); 196 if (nextCell == null) 197 return false; 198 199 var firstFacing = self.World.Map.FacingBetween(mobile.FromCell, nextCell.Value.First, mobile.Facing); 200 if (firstFacing != mobile.Facing) 201 { 202 path.Add(nextCell.Value.First); 203 QueueChild(new Turn(self, firstFacing)); 204 mobile.TurnToMove = true; 205 return false; 206 } 207 208 mobile.SetLocation(mobile.FromCell, mobile.FromSubCell, nextCell.Value.First, nextCell.Value.Second); 209 210 var map = self.World.Map; 211 var from = (mobile.FromCell.Layer == 0 ? map.CenterOfCell(mobile.FromCell) : 212 self.World.GetCustomMovementLayers()[mobile.FromCell.Layer].CenterOfCell(mobile.FromCell)) + 213 map.Grid.OffsetOfSubCell(mobile.FromSubCell); 214 215 var to = Util.BetweenCells(self.World, mobile.FromCell, mobile.ToCell) + 216 (map.Grid.OffsetOfSubCell(mobile.FromSubCell) + map.Grid.OffsetOfSubCell(mobile.ToSubCell)) / 2; 217 218 QueueChild(new MoveFirstHalf(this, from, to, mobile.Facing, mobile.Facing, 0)); 219 return false; 220 } 221 PopPath(Actor self)222 Pair<CPos, SubCell>? PopPath(Actor self) 223 { 224 if (path.Count == 0) 225 return null; 226 227 var nextCell = path[path.Count - 1]; 228 229 // Something else might have moved us, so the path is no longer valid. 230 if (!Util.AreAdjacentCells(mobile.ToCell, nextCell)) 231 { 232 path = EvalPath(BlockedByActor.Immovable); 233 return null; 234 } 235 236 var containsTemporaryBlocker = WorldUtils.ContainsTemporaryBlocker(self.World, nextCell, self); 237 238 // Next cell in the move is blocked by another actor 239 if (containsTemporaryBlocker || !mobile.CanEnterCell(nextCell, ignoreActor)) 240 { 241 // Are we close enough? 242 var cellRange = nearEnough.Length / 1024; 243 if (!containsTemporaryBlocker && (mobile.ToCell - destination.Value).LengthSquared <= cellRange * cellRange && mobile.CanStayInCell(mobile.ToCell)) 244 { 245 // Apply some simple checks to avoid giving up in cases where we can be confident that 246 // nudging/waiting/repathing should produce better results. 247 248 // Avoid fighting over the destination cell 249 if (path.Count < 2) 250 { 251 path.Clear(); 252 return null; 253 } 254 255 // We can reasonably assume that the blocker is friendly and has a similar locomotor type. 256 // If there is a free cell next to the blocker that is a similar or closer distance to the 257 // destination then we can probably nudge or path around it. 258 var blockerDistSq = (nextCell - destination.Value).LengthSquared; 259 var nudgeOrRepath = CVec.Directions 260 .Select(d => nextCell + d) 261 .Any(c => c != self.Location && (c - destination.Value).LengthSquared <= blockerDistSq && mobile.CanEnterCell(c, ignoreActor)); 262 263 if (!nudgeOrRepath) 264 { 265 path.Clear(); 266 return null; 267 } 268 } 269 270 // There is no point in waiting for the other actor to move if it is incapable of moving. 271 if (!mobile.CanEnterCell(nextCell, ignoreActor, BlockedByActor.Immovable)) 272 { 273 path = EvalPath(BlockedByActor.Immovable); 274 return null; 275 } 276 277 // See if they will move 278 self.NotifyBlocker(nextCell); 279 280 // Wait a bit to see if they leave 281 if (!hasWaited) 282 { 283 waitTicksRemaining = mobile.Info.LocomotorInfo.WaitAverage; 284 hasWaited = true; 285 return null; 286 } 287 288 if (--waitTicksRemaining >= 0) 289 return null; 290 291 hasWaited = false; 292 293 // If the blocking actors are already leaving, wait a little longer instead of repathing 294 if (CellIsEvacuating(self, nextCell)) 295 return null; 296 297 // Calculate a new path 298 mobile.RemoveInfluence(); 299 var newPath = EvalPath(BlockedByActor.All); 300 mobile.AddInfluence(); 301 302 if (newPath.Count != 0) 303 { 304 path = newPath; 305 var newCell = path[path.Count - 1]; 306 path.RemoveAt(path.Count - 1); 307 308 return Pair.New(newCell, mobile.GetAvailableSubCell(nextCell, mobile.FromSubCell, ignoreActor)); 309 } 310 else if (mobile.IsBlocking) 311 { 312 // If there is no way around the blocker and blocker will not move and we are blocking others, back up to let others pass. 313 var newCell = mobile.GetAdjacentCell(nextCell); 314 if (newCell != null) 315 { 316 if ((nextCell - newCell).Value.LengthSquared > 2) 317 path.Add(mobile.ToCell); 318 319 return Pair.New(newCell.Value, mobile.GetAvailableSubCell(newCell.Value, mobile.FromSubCell, ignoreActor)); 320 } 321 } 322 323 return null; 324 } 325 326 hasWaited = false; 327 path.RemoveAt(path.Count - 1); 328 329 return Pair.New(nextCell, mobile.GetAvailableSubCell(nextCell, mobile.FromSubCell, ignoreActor)); 330 } 331 OnLastRun(Actor self)332 protected override void OnLastRun(Actor self) 333 { 334 path = null; 335 } 336 CellIsEvacuating(Actor self, CPos cell)337 bool CellIsEvacuating(Actor self, CPos cell) 338 { 339 foreach (var actor in self.World.ActorMap.GetActorsAt(cell)) 340 { 341 var move = actor.TraitOrDefault<Mobile>(); 342 if (move == null || !move.IsTraitEnabled() || !move.IsLeaving()) 343 return false; 344 } 345 346 return true; 347 } 348 Cancel(Actor self, bool keepQueue = false)349 public override void Cancel(Actor self, bool keepQueue = false) 350 { 351 Cancel(self, keepQueue, false); 352 } 353 Cancel(Actor self, bool keepQueue, bool forceClearPath)354 public void Cancel(Actor self, bool keepQueue, bool forceClearPath) 355 { 356 // We need to clear the path here in order to prevent MovePart queueing new instances of itself 357 // when the unit is making a turn. 358 if (path != null && (forceClearPath || mobile.CanStayInCell(mobile.ToCell))) 359 path.Clear(); 360 361 base.Cancel(self, keepQueue); 362 } 363 GetTargets(Actor self)364 public override IEnumerable<Target> GetTargets(Actor self) 365 { 366 if (path != null) 367 return Enumerable.Reverse(path).Select(c => Target.FromCell(self.World, c)); 368 if (destination != null) 369 return new Target[] { Target.FromCell(self.World, destination.Value) }; 370 return Target.None; 371 } 372 TargetLineNodes(Actor self)373 public override IEnumerable<TargetLineNode> TargetLineNodes(Actor self) 374 { 375 if (targetLineColor != null) 376 yield return new TargetLineNode(Target.FromCell(self.World, destination.Value), targetLineColor.Value); 377 } 378 379 abstract class MovePart : Activity 380 { 381 protected readonly Move Move; 382 protected readonly WPos From, To; 383 protected readonly int FromFacing, ToFacing; 384 protected readonly bool EnableArc; 385 protected readonly WPos ArcCenter; 386 protected readonly int ArcFromLength; 387 protected readonly WAngle ArcFromAngle; 388 protected readonly int ArcToLength; 389 protected readonly WAngle ArcToAngle; 390 391 protected readonly int MoveFractionTotal; 392 protected int moveFraction; 393 MovePart(Move move, WPos from, WPos to, int fromFacing, int toFacing, int startingFraction)394 public MovePart(Move move, WPos from, WPos to, int fromFacing, int toFacing, int startingFraction) 395 { 396 Move = move; 397 From = from; 398 To = to; 399 FromFacing = fromFacing; 400 ToFacing = toFacing; 401 moveFraction = startingFraction; 402 MoveFractionTotal = (to - from).Length; 403 IsInterruptible = false; // See comments in Move.Cancel() 404 405 // Calculate an elliptical arc that joins from and to 406 var delta = Util.NormalizeFacing(fromFacing - toFacing); 407 if (delta != 0 && delta != 128) 408 { 409 // The center of rotation is where the normal vectors cross 410 var u = new WVec(1024, 0, 0).Rotate(WRot.FromFacing(fromFacing)); 411 var v = new WVec(1024, 0, 0).Rotate(WRot.FromFacing(toFacing)); 412 var w = from - to; 413 var s = (v.Y * w.X - v.X * w.Y) * 1024 / (v.X * u.Y - v.Y * u.X); 414 var x = from.X + s * u.X / 1024; 415 var y = from.Y + s * u.Y / 1024; 416 417 ArcCenter = new WPos(x, y, 0); 418 ArcFromLength = (ArcCenter - from).HorizontalLength; 419 ArcFromAngle = (ArcCenter - from).Yaw; 420 ArcToLength = (ArcCenter - to).HorizontalLength; 421 ArcToAngle = (ArcCenter - to).Yaw; 422 EnableArc = true; 423 } 424 } 425 Tick(Actor self)426 public override bool Tick(Actor self) 427 { 428 var ret = InnerTick(self, Move.mobile); 429 430 if (moveFraction > MoveFractionTotal) 431 moveFraction = MoveFractionTotal; 432 433 UpdateCenterLocation(self, Move.mobile); 434 435 if (ret == this) 436 return false; 437 438 Queue(ret); 439 return true; 440 } 441 InnerTick(Actor self, Mobile mobile)442 Activity InnerTick(Actor self, Mobile mobile) 443 { 444 moveFraction += mobile.MovementSpeedForCell(self, mobile.ToCell); 445 if (moveFraction <= MoveFractionTotal) 446 return this; 447 448 return OnComplete(self, mobile, Move); 449 } 450 UpdateCenterLocation(Actor self, Mobile mobile)451 void UpdateCenterLocation(Actor self, Mobile mobile) 452 { 453 // Avoid division through zero 454 if (MoveFractionTotal != 0) 455 { 456 WPos pos; 457 if (EnableArc) 458 { 459 var angle = WAngle.Lerp(ArcFromAngle, ArcToAngle, moveFraction, MoveFractionTotal); 460 var length = int2.Lerp(ArcFromLength, ArcToLength, moveFraction, MoveFractionTotal); 461 var height = int2.Lerp(From.Z, To.Z, moveFraction, MoveFractionTotal); 462 pos = ArcCenter + new WVec(0, length, height).Rotate(WRot.FromYaw(angle)); 463 } 464 else 465 pos = WPos.Lerp(From, To, moveFraction, MoveFractionTotal); 466 467 mobile.SetVisualPosition(self, pos); 468 } 469 else 470 mobile.SetVisualPosition(self, To); 471 472 if (moveFraction >= MoveFractionTotal) 473 mobile.Facing = ToFacing & 0xFF; 474 else 475 mobile.Facing = int2.Lerp(FromFacing, ToFacing, moveFraction, MoveFractionTotal) & 0xFF; 476 } 477 OnComplete(Actor self, Mobile mobile, Move parent)478 protected abstract MovePart OnComplete(Actor self, Mobile mobile, Move parent); 479 GetTargets(Actor self)480 public override IEnumerable<Target> GetTargets(Actor self) 481 { 482 return Move.GetTargets(self); 483 } 484 } 485 486 class MoveFirstHalf : MovePart 487 { MoveFirstHalf(Move move, WPos from, WPos to, int fromFacing, int toFacing, int startingFraction)488 public MoveFirstHalf(Move move, WPos from, WPos to, int fromFacing, int toFacing, int startingFraction) 489 : base(move, from, to, fromFacing, toFacing, startingFraction) { } 490 IsTurn(Mobile mobile, CPos nextCell, Map map)491 static bool IsTurn(Mobile mobile, CPos nextCell, Map map) 492 { 493 // Tight U-turns should be done in place instead of making silly looking loops. 494 var nextFacing = map.FacingBetween(nextCell, mobile.ToCell, mobile.Facing); 495 var currentFacing = map.FacingBetween(mobile.ToCell, mobile.FromCell, mobile.Facing); 496 var delta = Util.NormalizeFacing(nextFacing - currentFacing); 497 return delta != 0 && (delta < 96 || delta > 160); 498 } 499 OnComplete(Actor self, Mobile mobile, Move parent)500 protected override MovePart OnComplete(Actor self, Mobile mobile, Move parent) 501 { 502 var map = self.World.Map; 503 var fromSubcellOffset = map.Grid.OffsetOfSubCell(mobile.FromSubCell); 504 var toSubcellOffset = map.Grid.OffsetOfSubCell(mobile.ToSubCell); 505 506 var nextCell = parent.PopPath(self); 507 if (nextCell != null) 508 { 509 if (!mobile.IsTraitPaused && !mobile.IsTraitDisabled && IsTurn(mobile, nextCell.Value.First, map)) 510 { 511 var nextSubcellOffset = map.Grid.OffsetOfSubCell(nextCell.Value.Second); 512 var ret = new MoveFirstHalf( 513 Move, 514 Util.BetweenCells(self.World, mobile.FromCell, mobile.ToCell) + (fromSubcellOffset + toSubcellOffset) / 2, 515 Util.BetweenCells(self.World, mobile.ToCell, nextCell.Value.First) + (toSubcellOffset + nextSubcellOffset) / 2, 516 mobile.Facing, 517 Util.GetNearestFacing(mobile.Facing, map.FacingBetween(mobile.ToCell, nextCell.Value.First, mobile.Facing)), 518 moveFraction - MoveFractionTotal); 519 520 mobile.FinishedMoving(self); 521 mobile.SetLocation(mobile.ToCell, mobile.ToSubCell, nextCell.Value.First, nextCell.Value.Second); 522 return ret; 523 } 524 525 parent.path.Add(nextCell.Value.First); 526 } 527 528 var toPos = mobile.ToCell.Layer == 0 ? map.CenterOfCell(mobile.ToCell) : 529 self.World.GetCustomMovementLayers()[mobile.ToCell.Layer].CenterOfCell(mobile.ToCell); 530 531 var ret2 = new MoveSecondHalf( 532 Move, 533 Util.BetweenCells(self.World, mobile.FromCell, mobile.ToCell) + (fromSubcellOffset + toSubcellOffset) / 2, 534 toPos + toSubcellOffset, 535 mobile.Facing, 536 mobile.Facing, 537 moveFraction - MoveFractionTotal); 538 539 mobile.EnteringCell(self); 540 mobile.SetLocation(mobile.ToCell, mobile.ToSubCell, mobile.ToCell, mobile.ToSubCell); 541 return ret2; 542 } 543 } 544 545 class MoveSecondHalf : MovePart 546 { MoveSecondHalf(Move move, WPos from, WPos to, int fromFacing, int toFacing, int startingFraction)547 public MoveSecondHalf(Move move, WPos from, WPos to, int fromFacing, int toFacing, int startingFraction) 548 : base(move, from, to, fromFacing, toFacing, startingFraction) { } 549 OnComplete(Actor self, Mobile mobile, Move parent)550 protected override MovePart OnComplete(Actor self, Mobile mobile, Move parent) 551 { 552 mobile.SetPosition(self, mobile.ToCell); 553 return null; 554 } 555 } 556 } 557 } 558