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.Graphics; 16 using OpenRA.Primitives; 17 using OpenRA.Support; 18 using OpenRA.Traits; 19 20 namespace OpenRA.Mods.Common.Traits 21 { 22 [Flags] 23 public enum CellFlag : byte 24 { 25 HasFreeSpace = 0, 26 HasMovingActor = 1, 27 HasStationaryActor = 2, 28 HasMovableActor = 4, 29 HasCrushableActor = 8, 30 HasTemporaryBlocker = 16, 31 HasTransitOnlyActor = 32, 32 } 33 34 public static class LocomoterExts 35 { HasCellFlag(this CellFlag c, CellFlag cellFlag)36 public static bool HasCellFlag(this CellFlag c, CellFlag cellFlag) 37 { 38 // PERF: Enum.HasFlag is slower and requires allocations. 39 return (c & cellFlag) == cellFlag; 40 } 41 HasMovementType(this MovementType m, MovementType movementType)42 public static bool HasMovementType(this MovementType m, MovementType movementType) 43 { 44 // PERF: Enum.HasFlag is slower and requires allocations. 45 return (m & movementType) == movementType; 46 } 47 } 48 49 public static class CustomMovementLayerType 50 { 51 public const byte Tunnel = 1; 52 public const byte Subterranean = 2; 53 public const byte Jumpjet = 3; 54 public const byte ElevatedBridge = 4; 55 } 56 57 [Desc("Used by Mobile. Attach these to the world actor. You can have multiple variants by adding @suffixes.")] 58 public class LocomotorInfo : ITraitInfo 59 { 60 [Desc("Locomotor ID.")] 61 public readonly string Name = "default"; 62 63 public readonly int WaitAverage = 40; 64 65 public readonly int WaitSpread = 10; 66 67 [Desc("Allow multiple (infantry) units in one cell.")] 68 public readonly bool SharesCell = false; 69 70 [Desc("Can the actor be ordered to move in to shroud?")] 71 public readonly bool MoveIntoShroud = true; 72 73 [Desc("e.g. crate, wall, infantry")] 74 public readonly BitSet<CrushClass> Crushes = default(BitSet<CrushClass>); 75 76 [Desc("Types of damage that are caused while crushing. Leave empty for no damage types.")] 77 public readonly BitSet<DamageType> CrushDamageTypes = default(BitSet<DamageType>); 78 79 [FieldLoader.LoadUsing("LoadSpeeds", true)] 80 [Desc("Lower the value on rough terrain. Leave out entries for impassable terrain.")] 81 public readonly Dictionary<string, TerrainInfo> TerrainSpeeds; 82 LoadSpeeds(MiniYaml y)83 protected static object LoadSpeeds(MiniYaml y) 84 { 85 var ret = new Dictionary<string, TerrainInfo>(); 86 foreach (var t in y.ToDictionary()["TerrainSpeeds"].Nodes) 87 { 88 var speed = FieldLoader.GetValue<int>("speed", t.Value.Value); 89 if (speed > 0) 90 { 91 var nodesDict = t.Value.ToDictionary(); 92 var cost = (nodesDict.ContainsKey("PathingCost") 93 ? FieldLoader.GetValue<short>("cost", nodesDict["PathingCost"].Value) 94 : 10000 / speed); 95 ret.Add(t.Key, new TerrainInfo(speed, (short)cost)); 96 } 97 } 98 99 return ret; 100 } 101 LoadTilesetSpeeds(TileSet tileSet)102 TerrainInfo[] LoadTilesetSpeeds(TileSet tileSet) 103 { 104 var info = new TerrainInfo[tileSet.TerrainInfo.Length]; 105 for (var i = 0; i < info.Length; i++) 106 info[i] = TerrainInfo.Impassable; 107 108 foreach (var kvp in TerrainSpeeds) 109 { 110 byte index; 111 if (tileSet.TryGetTerrainIndex(kvp.Key, out index)) 112 info[index] = kvp.Value; 113 } 114 115 return info; 116 } 117 118 public class TerrainInfo 119 { 120 public static readonly TerrainInfo Impassable = new TerrainInfo(); 121 122 public readonly short Cost; 123 public readonly int Speed; 124 TerrainInfo()125 public TerrainInfo() 126 { 127 Cost = short.MaxValue; 128 Speed = 0; 129 } 130 TerrainInfo(int speed, short cost)131 public TerrainInfo(int speed, short cost) 132 { 133 Speed = speed; 134 Cost = cost; 135 } 136 } 137 138 public struct WorldMovementInfo 139 { 140 internal readonly World World; 141 internal readonly TerrainInfo[] TerrainInfos; WorldMovementInfoOpenRA.Mods.Common.Traits.LocomotorInfo.WorldMovementInfo142 internal WorldMovementInfo(World world, LocomotorInfo info) 143 { 144 // PERF: This struct allows us to cache the terrain info for the tileset used by the world. 145 // This allows us to speed up some performance-sensitive pathfinding calculations. 146 World = world; 147 TerrainInfos = info.TilesetTerrainInfo[world.Map.Rules.TileSet]; 148 } 149 } 150 151 public readonly Cache<TileSet, TerrainInfo[]> TilesetTerrainInfo; 152 public readonly Cache<TileSet, int> TilesetMovementClass; 153 LocomotorInfo()154 public LocomotorInfo() 155 { 156 TilesetTerrainInfo = new Cache<TileSet, TerrainInfo[]>(LoadTilesetSpeeds); 157 TilesetMovementClass = new Cache<TileSet, int>(CalculateTilesetMovementClass); 158 } 159 CalculateTilesetMovementClass(TileSet tileset)160 public int CalculateTilesetMovementClass(TileSet tileset) 161 { 162 // collect our ability to cross *all* terraintypes, in a bitvector 163 return TilesetTerrainInfo[tileset].Select(ti => ti.Cost < short.MaxValue).ToBits(); 164 } 165 GetMovementClass(TileSet tileset)166 public uint GetMovementClass(TileSet tileset) 167 { 168 return (uint)TilesetMovementClass[tileset]; 169 } 170 TileSetMovementHash(TileSet tileSet)171 public int TileSetMovementHash(TileSet tileSet) 172 { 173 var terrainInfos = TilesetTerrainInfo[tileSet]; 174 175 // Compute and return the hash using aggregate 176 return terrainInfos.Aggregate(terrainInfos.Length, 177 (current, terrainInfo) => unchecked(current * 31 + terrainInfo.Cost)); 178 } 179 GetWorldMovementInfo(World world)180 public WorldMovementInfo GetWorldMovementInfo(World world) 181 { 182 return new WorldMovementInfo(world, this); 183 } 184 185 public virtual bool DisableDomainPassabilityCheck { get { return false; } } 186 Create(ActorInitializer init)187 public virtual object Create(ActorInitializer init) { return new Locomotor(init.Self, this); } 188 } 189 190 public class Locomotor : IWorldLoaded 191 { 192 struct CellCache 193 { 194 public readonly LongBitSet<PlayerBitMask> Immovable; 195 public readonly LongBitSet<PlayerBitMask> Crushable; 196 public readonly CellFlag CellFlag; 197 CellCacheOpenRA.Mods.Common.Traits.Locomotor.CellCache198 public CellCache(LongBitSet<PlayerBitMask> immovable, CellFlag cellFlag, LongBitSet<PlayerBitMask> crushable = default(LongBitSet<PlayerBitMask>)) 199 { 200 Immovable = immovable; 201 Crushable = crushable; 202 CellFlag = cellFlag; 203 } 204 } 205 206 public readonly LocomotorInfo Info; 207 CellLayer<short> cellsCost; 208 CellLayer<CellCache> blockingCache; 209 210 readonly Dictionary<byte, CellLayer<short>> customLayerCellsCost = new Dictionary<byte, CellLayer<short>>(); 211 readonly Dictionary<byte, CellLayer<CellCache>> customLayerBlockingCache = new Dictionary<byte, CellLayer<CellCache>>(); 212 213 LocomotorInfo.TerrainInfo[] terrainInfos; 214 World world; 215 readonly HashSet<CPos> dirtyCells = new HashSet<CPos>(); 216 217 IActorMap actorMap; 218 bool sharesCell; 219 Locomotor(Actor self, LocomotorInfo info)220 public Locomotor(Actor self, LocomotorInfo info) 221 { 222 Info = info; 223 sharesCell = info.SharesCell; 224 } 225 MovementCostForCell(CPos cell)226 public short MovementCostForCell(CPos cell) 227 { 228 if (!world.Map.Contains(cell)) 229 return short.MaxValue; 230 231 return cell.Layer == 0 ? cellsCost[cell] : customLayerCellsCost[cell.Layer][cell]; 232 } 233 MovementCostToEnterCell(Actor actor, CPos destNode, BlockedByActor check, Actor ignoreActor)234 public short MovementCostToEnterCell(Actor actor, CPos destNode, BlockedByActor check, Actor ignoreActor) 235 { 236 if (!world.Map.Contains(destNode)) 237 return short.MaxValue; 238 239 var cellCost = destNode.Layer == 0 ? cellsCost[destNode] : customLayerCellsCost[destNode.Layer][destNode]; 240 241 if (cellCost == short.MaxValue || 242 !CanMoveFreelyInto(actor, destNode, check, ignoreActor)) 243 return short.MaxValue; 244 245 return cellCost; 246 } 247 248 // Determines whether the actor is blocked by other Actors CanMoveFreelyInto(Actor actor, CPos cell, BlockedByActor check, Actor ignoreActor)249 public bool CanMoveFreelyInto(Actor actor, CPos cell, BlockedByActor check, Actor ignoreActor) 250 { 251 return CanMoveFreelyInto(actor, cell, SubCell.FullCell, check, ignoreActor); 252 } 253 CanMoveFreelyInto(Actor actor, CPos cell, SubCell subCell, BlockedByActor check, Actor ignoreActor)254 public bool CanMoveFreelyInto(Actor actor, CPos cell, SubCell subCell, BlockedByActor check, Actor ignoreActor) 255 { 256 var cellCache = GetCache(cell); 257 var cellFlag = cellCache.CellFlag; 258 259 // If the check allows: We are not blocked by transient actors. 260 if (check == BlockedByActor.None) 261 return true; 262 263 // No actor in the cell or free SubCell. 264 if (cellFlag == CellFlag.HasFreeSpace) 265 return true; 266 267 // If actor is null we're just checking what would happen theoretically. 268 // In such a scenario - we'll just assume any other actor in the cell will block us by default. 269 // If we have a real actor, we can then perform the extra checks that allow us to avoid being blocked. 270 if (actor == null) 271 return false; 272 273 // All actors that may be in the cell can be crushed. 274 if (cellCache.Crushable.Overlaps(actor.Owner.PlayerMask)) 275 return true; 276 277 // If the check allows: We are not blocked by moving units. 278 if (check <= BlockedByActor.Stationary && !cellFlag.HasCellFlag(CellFlag.HasStationaryActor)) 279 return true; 280 281 // If the check allows: We are not blocked by units that we can force to move out of the way. 282 if (check <= BlockedByActor.Immovable && !cellCache.Immovable.Overlaps(actor.Owner.PlayerMask)) 283 return true; 284 285 // Cache doesn't account for ignored actors, temporary blockers, or subcells - these must use the slow path. 286 if (ignoreActor == null && !cellFlag.HasCellFlag(CellFlag.HasTemporaryBlocker) && subCell == SubCell.FullCell) 287 { 288 // We already know there are uncrushable actors in the cell so we are always blocked. 289 if (check == BlockedByActor.All) 290 return false; 291 292 // We already know there are either immovable or stationary actors which the check does not allow. 293 if (!cellFlag.HasCellFlag(CellFlag.HasCrushableActor)) 294 return false; 295 296 // All actors in the cell are immovable and some cannot be crushed. 297 if (!cellFlag.HasCellFlag(CellFlag.HasMovableActor)) 298 return false; 299 300 // All actors in the cell are stationary and some cannot be crushed. 301 if (check == BlockedByActor.Stationary && !cellFlag.HasCellFlag(CellFlag.HasMovingActor)) 302 return false; 303 } 304 305 var otherActors = subCell == SubCell.FullCell ? world.ActorMap.GetActorsAt(cell) : world.ActorMap.GetActorsAt(cell, subCell); 306 foreach (var otherActor in otherActors) 307 if (IsBlockedBy(actor, otherActor, ignoreActor, cell, check, cellFlag)) 308 return false; 309 310 return true; 311 } 312 CanStayInCell(CPos cell)313 public bool CanStayInCell(CPos cell) 314 { 315 return !GetCache(cell).CellFlag.HasCellFlag(CellFlag.HasTransitOnlyActor); 316 } 317 GetAvailableSubCell(Actor self, CPos cell, BlockedByActor check, SubCell preferredSubCell = SubCell.Any, Actor ignoreActor = null)318 public SubCell GetAvailableSubCell(Actor self, CPos cell, BlockedByActor check, SubCell preferredSubCell = SubCell.Any, Actor ignoreActor = null) 319 { 320 if (MovementCostForCell(cell) == short.MaxValue) 321 return SubCell.Invalid; 322 323 if (check > BlockedByActor.None) 324 { 325 Func<Actor, bool> checkTransient = otherActor => IsBlockedBy(self, otherActor, ignoreActor, cell, check, GetCache(cell).CellFlag); 326 327 if (!sharesCell) 328 return world.ActorMap.AnyActorsAt(cell, SubCell.FullCell, checkTransient) ? SubCell.Invalid : SubCell.FullCell; 329 330 return world.ActorMap.FreeSubCell(cell, preferredSubCell, checkTransient); 331 } 332 333 if (!sharesCell) 334 return world.ActorMap.AnyActorsAt(cell, SubCell.FullCell) ? SubCell.Invalid : SubCell.FullCell; 335 336 return world.ActorMap.FreeSubCell(cell, preferredSubCell); 337 } 338 IsBlockedBy(Actor actor, Actor otherActor, Actor ignoreActor, CPos cell, BlockedByActor check, CellFlag cellFlag)339 bool IsBlockedBy(Actor actor, Actor otherActor, Actor ignoreActor, CPos cell, BlockedByActor check, CellFlag cellFlag) 340 { 341 if (otherActor == ignoreActor) 342 return false; 343 344 // If the check allows: We are not blocked by units that we can force to move out of the way. 345 if (check <= BlockedByActor.Immovable && cellFlag.HasCellFlag(CellFlag.HasMovableActor) && 346 actor.Owner.Stances[otherActor.Owner] == Stance.Ally) 347 { 348 var mobile = otherActor.TraitOrDefault<Mobile>(); 349 if (mobile != null && !mobile.IsTraitDisabled && !mobile.IsTraitPaused && !mobile.IsImmovable) 350 return false; 351 } 352 353 // If the check allows: we are not blocked by moving units. 354 if (check <= BlockedByActor.Stationary && cellFlag.HasCellFlag(CellFlag.HasMovingActor) && 355 IsMoving(actor, otherActor)) 356 return false; 357 358 if (cellFlag.HasCellFlag(CellFlag.HasTemporaryBlocker)) 359 { 360 // If there is a temporary blocker in our path, but we can remove it, we are not blocked. 361 var temporaryBlocker = otherActor.TraitOrDefault<ITemporaryBlocker>(); 362 if (temporaryBlocker != null && temporaryBlocker.CanRemoveBlockage(otherActor, actor)) 363 return false; 364 } 365 366 if (cellFlag.HasCellFlag(CellFlag.HasTransitOnlyActor)) 367 { 368 // Transit only tiles should not block movement 369 var building = otherActor.TraitOrDefault<Building>(); 370 if (building != null && building.TransitOnlyCells().Contains(cell)) 371 return false; 372 } 373 374 // If we cannot crush the other actor in our way, we are blocked. 375 if (!cellFlag.HasCellFlag(CellFlag.HasCrushableActor) || Info.Crushes.IsEmpty) 376 return true; 377 378 // If the other actor in our way cannot be crushed, we are blocked. 379 // PERF: Avoid LINQ. 380 var crushables = otherActor.TraitsImplementing<ICrushable>(); 381 foreach (var crushable in crushables) 382 if (crushable.CrushableBy(otherActor, actor, Info.Crushes)) 383 return false; 384 385 return true; 386 } 387 IsMoving(Actor self, Actor other)388 static bool IsMoving(Actor self, Actor other) 389 { 390 // PERF: Because we can be sure that OccupiesSpace is Mobile here we can save some performance by avoiding querying for the trait. 391 var otherMobile = other.OccupiesSpace as Mobile; 392 if (otherMobile == null || !otherMobile.CurrentMovementTypes.HasMovementType(MovementType.Horizontal)) 393 return false; 394 395 // PERF: Same here. 396 var selfMobile = self.OccupiesSpace as Mobile; 397 if (selfMobile == null) 398 return false; 399 400 return true; 401 } 402 WorldLoaded(World w, WorldRenderer wr)403 public void WorldLoaded(World w, WorldRenderer wr) 404 { 405 world = w; 406 var map = w.Map; 407 actorMap = w.ActorMap; 408 actorMap.CellUpdated += CellUpdated; 409 terrainInfos = Info.TilesetTerrainInfo[map.Rules.TileSet]; 410 411 blockingCache = new CellLayer<CellCache>(map); 412 cellsCost = new CellLayer<short>(map); 413 414 foreach (var cell in map.AllCells) 415 UpdateCellCost(cell); 416 417 map.CustomTerrain.CellEntryChanged += UpdateCellCost; 418 map.Tiles.CellEntryChanged += UpdateCellCost; 419 420 // This section needs to run after WorldLoaded() because we need to be sure that all types of ICustomMovementLayer have been initialized. 421 w.AddFrameEndTask(_ => 422 { 423 var customMovementLayers = w.WorldActor.TraitsImplementing<ICustomMovementLayer>(); 424 foreach (var cml in customMovementLayers) 425 { 426 var cellLayer = new CellLayer<short>(map); 427 customLayerCellsCost[cml.Index] = cellLayer; 428 customLayerBlockingCache[cml.Index] = new CellLayer<CellCache>(map); 429 430 foreach (var cell in map.AllCells) 431 { 432 var index = cml.GetTerrainIndex(cell); 433 434 var cost = short.MaxValue; 435 436 if (index != byte.MaxValue) 437 cost = terrainInfos[index].Cost; 438 439 cellLayer[cell] = cost; 440 } 441 } 442 }); 443 } 444 GetCache(CPos cell)445 CellCache GetCache(CPos cell) 446 { 447 if (dirtyCells.Contains(cell)) 448 { 449 UpdateCellBlocking(cell); 450 dirtyCells.Remove(cell); 451 } 452 453 var cache = cell.Layer == 0 ? blockingCache : customLayerBlockingCache[cell.Layer]; 454 455 return cache[cell]; 456 } 457 CellUpdated(CPos cell)458 void CellUpdated(CPos cell) 459 { 460 dirtyCells.Add(cell); 461 } 462 UpdateCellCost(CPos cell)463 void UpdateCellCost(CPos cell) 464 { 465 var index = cell.Layer == 0 466 ? world.Map.GetTerrainIndex(cell) 467 : world.GetCustomMovementLayers()[cell.Layer].GetTerrainIndex(cell); 468 469 var cost = short.MaxValue; 470 471 if (index != byte.MaxValue) 472 cost = terrainInfos[index].Cost; 473 474 var cache = cell.Layer == 0 ? cellsCost : customLayerCellsCost[cell.Layer]; 475 476 cache[cell] = cost; 477 } 478 UpdateCellBlocking(CPos cell)479 void UpdateCellBlocking(CPos cell) 480 { 481 using (new PerfSample("locomotor_cache")) 482 { 483 var cache = cell.Layer == 0 ? blockingCache : customLayerBlockingCache[cell.Layer]; 484 485 var actors = actorMap.GetActorsAt(cell); 486 var cellFlag = CellFlag.HasFreeSpace; 487 488 if (!actors.Any()) 489 { 490 cache[cell] = new CellCache(default(LongBitSet<PlayerBitMask>), cellFlag); 491 return; 492 } 493 494 if (sharesCell && actorMap.HasFreeSubCell(cell)) 495 { 496 cache[cell] = new CellCache(default(LongBitSet<PlayerBitMask>), cellFlag); 497 return; 498 } 499 500 var cellImmovablePlayers = default(LongBitSet<PlayerBitMask>); 501 var cellCrushablePlayers = world.AllPlayersMask; 502 503 foreach (var actor in actors) 504 { 505 var actorImmovablePlayers = world.AllPlayersMask; 506 var actorCrushablePlayers = world.NoPlayersMask; 507 508 var crushables = actor.TraitsImplementing<ICrushable>(); 509 var mobile = actor.OccupiesSpace as Mobile; 510 var isMovable = mobile != null && !mobile.IsTraitDisabled && !mobile.IsTraitPaused && !mobile.IsImmovable; 511 var isMoving = isMovable && mobile.CurrentMovementTypes.HasMovementType(MovementType.Horizontal); 512 513 var building = actor.OccupiesSpace as Building; 514 var isTransitOnly = building != null && building.TransitOnlyCells().Contains(cell); 515 516 if (isTransitOnly) 517 { 518 cellFlag |= CellFlag.HasTransitOnlyActor; 519 continue; 520 } 521 522 if (crushables.Any()) 523 { 524 cellFlag |= CellFlag.HasCrushableActor; 525 foreach (var crushable in crushables) 526 actorCrushablePlayers = actorCrushablePlayers.Union(crushable.CrushableBy(actor, Info.Crushes)); 527 } 528 529 if (isMoving) 530 cellFlag |= CellFlag.HasMovingActor; 531 else 532 cellFlag |= CellFlag.HasStationaryActor; 533 534 if (isMovable) 535 { 536 cellFlag |= CellFlag.HasMovableActor; 537 actorImmovablePlayers = actorImmovablePlayers.Except(actor.Owner.AlliedPlayersMask); 538 } 539 540 // PERF: Only perform ITemporaryBlocker trait look-up if mod/map rules contain any actors that are temporary blockers 541 if (world.RulesContainTemporaryBlocker) 542 { 543 // If there is a temporary blocker in this cell. 544 if (actor.TraitOrDefault<ITemporaryBlocker>() != null) 545 cellFlag |= CellFlag.HasTemporaryBlocker; 546 } 547 548 cellCrushablePlayers = cellCrushablePlayers.Intersect(actorCrushablePlayers); 549 cellImmovablePlayers = cellImmovablePlayers.Union(actorImmovablePlayers); 550 } 551 552 cache[cell] = new CellCache(cellImmovablePlayers, cellFlag, cellCrushablePlayers); 553 } 554 } 555 } 556 } 557