Index: binaries/data/mods/public/maps/scenarios/unit_pushing_test.js =================================================================== --- /dev/null +++ binaries/data/mods/public/maps/scenarios/unit_pushing_test.js @@ -0,0 +1,380 @@ +const REG_UNIT_TEMPLATE = "units/athen/infantry_spearman_b"; +const FAST_UNIT_TEMPLATE = "units/athen/cavalry_swordsman_b"; +const LARGE_UNIT_TEMPLATE = "units/brit/siege_ram"; +const ELE_TEMPLATE = "units/cart/champion_elephant"; + +const ATTACKER = 2; + +var QuickSpawn = function(x, z, template, owner = 1) +{ + let ent = Engine.AddEntity(template); + + let cmpEntOwnership = Engine.QueryInterface(ent, IID_Ownership); + if (cmpEntOwnership) + cmpEntOwnership.SetOwner(owner); + + let cmpEntPosition = Engine.QueryInterface(ent, IID_Position); + cmpEntPosition.JumpTo(x, z); + return ent; +}; + +var Rotate = function(angle, ent) +{ + let cmpEntPosition = Engine.QueryInterface(ent, IID_Position); + cmpEntPosition.SetYRotation(angle); + return ent; +}; + +var WalkTo = function(x, z, queued, ent, owner=1) +{ + ProcessCommand(owner, { + "type": "walk", + "entities": Array.isArray(ent) ? ent : [ent], + "x": x, + "z": z, + "queued": queued, + "force": true, + }); + return ent; +}; + +var FormationWalkTo = function(x, z, queued, ent, owner=1) +{ + ProcessCommand(owner, { + "type": "walk", + "entities": Array.isArray(ent) ? ent : [ent], + "x": x, + "z": z, + "queued": queued, + "force": true, + "formation": "special/formations/box" + }); + return ent; +}; + +var Attack = function(target, ent) +{ + let comm = { + "type": "attack", + "entities": Array.isArray(ent) ? ent : [ent], + "target": target, + "queued": true, + "force": true, + }; + ProcessCommand(ATTACKER, comm); + return ent; +}; + +var Do = function(name, data, ent, owner = 1) +{ + let comm = { + "type": name, + "entities": Array.isArray(ent) ? ent : [ent], + "queued": false + }; + for (let k in data) + comm[k] = data[k]; + ProcessCommand(owner, comm); +}; + + +var experiments = {}; + +experiments.units_sparse_forest_of_units = { + "spawn": (gx, gy) => { + for (let i = -16; i <= 16; i += 8) + for (let j = -16; j <= 16; j += 8) + QuickSpawn(gx + i, gy + 50 + j, REG_UNIT_TEMPLATE); + WalkTo(gx, gy + 100, true, QuickSpawn(gx, gy, REG_UNIT_TEMPLATE)); + WalkTo(gx, gy + 100, true, QuickSpawn(gx, gy-10, LARGE_UNIT_TEMPLATE)); + } +}; + +experiments.units_dense_forest_of_units = { + "spawn": (gx, gy) => { + for (let i = -16; i <= 16; i += 4) + for (let j = -16; j <= 16; j += 4) + QuickSpawn(gx + i, gy + 50 + j, REG_UNIT_TEMPLATE); + WalkTo(gx, gy + 100, true, QuickSpawn(gx, gy, REG_UNIT_TEMPLATE)); + WalkTo(gx, gy + 100, true, QuickSpawn(gx, gy-10, LARGE_UNIT_TEMPLATE)); + } +}; + +experiments.units_superdense_forest_of_units = { + "spawn": (gx, gy) => { + for (let i = -6; i <= 6; i += 2) + for (let j = -6; j <= 6; j += 2) + QuickSpawn(gx + i, gy + 50 + j, REG_UNIT_TEMPLATE); + WalkTo(gx, gy + 100, true, QuickSpawn(gx, gy, REG_UNIT_TEMPLATE)); + WalkTo(gx, gy + 100, true, QuickSpawn(gx, gy-10, LARGE_UNIT_TEMPLATE)); + } +}; + +experiments.building = { + "spawn": (gx, gy) => { + let target = QuickSpawn(gx + 20, gy + 20, "foundation|structures/athen/storehouse"); + for (let i = 0; i < 8; ++i) + Do("repair", { "target": target }, QuickSpawn(gx + i, gy, REG_UNIT_TEMPLATE)); + + let cmpFoundation = Engine.QueryInterface(target, IID_Foundation); + cmpFoundation.InitialiseConstruction(1, "structures/athen/storehouse"); + } +}; + +experiments.collecting_tree = { + "spawn": (gx, gy) => { + let target = QuickSpawn(gx + 10, gy + 10, "gaia/tree/acacia"); + let storehouse = QuickSpawn(gx - 10, gy - 10, "structures/athen/storehouse"); + for (let i = 0; i < 8; ++i) + Do("gather", { "target": target }, QuickSpawn(gx + i, gy, REG_UNIT_TEMPLATE)); + + let cmpModifiersManager = Engine.QueryInterface(SYSTEM_ENTITY, IID_ModifiersManager); + // Make that tree essentially infinite. + cmpModifiersManager.AddModifiers("inf_tree", { + "ResourceSupply/Max": [{ "affects": ["Tree"], "replace": 50000 }], + }, target); + let cmpSupply = Engine.QueryInterface(target, IID_ResourceSupply); + cmpSupply.SetAmount(50000); + // Make the storehouse a territory root + cmpModifiersManager.AddModifiers("root", { + "TerritoryInfluence/Root": [{ "affects": ["Structure"], "replace": true }], + }, storehouse); + // Make units gather instantly + cmpModifiersManager.AddModifiers("gatherrate", { + "ResourceGatherer/BaseSpeed": [{ "affects": ["Unit"], "replace": 100 }], + }, 3); // Player 1 is ent 3 + } +}; + +experiments.sep1 = { + "spawn": (gx, gy) => {} +}; + +experiments.battle = { + "spawn": (gx, gy) => { + for (let i = 0; i < 4; ++i) + for (let j = 0; j < 8; ++j) + { + QuickSpawn(gx + i, gy + j, REG_UNIT_TEMPLATE); + QuickSpawn(gx + i, gy + 50 + j, REG_UNIT_TEMPLATE, ATTACKER); + } + } +}; + +experiments.sep2 = { + "spawn": (gx, gy) => {} +}; + + +experiments.overlapping = { + "spawn": (gx, gy) => { + for (let i = 0; i < 20; ++i) + QuickSpawn(gx, gy, REG_UNIT_TEMPLATE); + } +}; + +experiments.multicrossing = { + "spawn": (gx, gy) => { + for (let i = 0; i < 20; i += 2) + for (let j = 0; j < 20; j += 2) + WalkTo(gx+10, gy+70, false, QuickSpawn(gx + i, gy + j, REG_UNIT_TEMPLATE)); + for (let i = 0; i < 20; i += 2) + for (let j = 0; j < 20; j += 2) + WalkTo(gx+10, gy, false, QuickSpawn(gx + i, gy + j + 70, REG_UNIT_TEMPLATE)); + } +}; + +experiments.elephant_formation = { + "spawn": (gx, gy) => { + let ents = []; + for (let i = 0; i < 20; i += 4) + for (let j = 0; j < 20; j += 4) + ents.push(QuickSpawn(gx + i, gy + j, ELE_TEMPLATE)); + FormationWalkTo(gx, gy+10, false, ents); + } +}; + +var perf_experiments = {}; + +// Perf check: put units everywhere, not moving. +perf_experiments.Idle = { + "spawn": () => { + const spacing = 12; + for (let x = 0; x < 20*16*4 - 20; x += spacing) + for (let z = 0; z < 20*16*4 - 20; z += spacing) + QuickSpawn(x, z, REG_UNIT_TEMPLATE); + } +}; + +// Perf check: put units everywhere, moving. +perf_experiments.MovingAround = { + "spawn": () => { + const spacing = 24; + for (let x = 0; x < 20*16*4 - 20; x += spacing) + for (let z = 0; z < 20*16*4 - 20; z += spacing) + { + let ent = QuickSpawn(x, z, REG_UNIT_TEMPLATE); + for (let i = 0; i < 5; ++i) + { + WalkTo(x + 4, z, true, ent); + WalkTo(x + 4, z + 4, true, ent); + WalkTo(x, z + 4, true, ent); + WalkTo(x, z, true, ent); + } + } + } +}; +// Perf check: fewer units moving more. +perf_experiments.LighterMovingAround = { + "spawn": () => { + const spacing = 48; + for (let x = 0; x < 20*16*4 - 20; x += spacing) + for (let z = 0; z < 20*16*4 - 20; z += spacing) + { + let ent = QuickSpawn(x, z, REG_UNIT_TEMPLATE); + for (let i = 0; i < 5; ++i) + { + WalkTo(x + 20, z, true, ent); + WalkTo(x + 20, z + 20, true, ent); + WalkTo(x, z + 20, true, ent); + WalkTo(x, z, true, ent); + } + } + } +}; + +// Perf check: rows of units crossing each other. +perf_experiments.BunchaCollisions = { + "spawn": () => { + const spacing = 64; + for (let x = 0; x < 20*16*4 - 20; x += spacing) + for (let z = 0; z < 20*16*4 - 20; z += spacing) + { + for (let i = 0; i < 10; ++i) + { + // Add a little variation to the spawning, or all clusters end up identical. + let ent = QuickSpawn(x + i + randFloat(-0.5, 0.5), z + 20 * (i%2) + randFloat(-0.5, 0.5), REG_UNIT_TEMPLATE); + for (let ii = 0; ii < 5; ++ii) + { + WalkTo(x + i, z + 20, true, ent); + WalkTo(x + i, z, true, ent); + } + } + } + } +}; + +// Massive moshpit of pushing. +perf_experiments.LotsaLocalCollisions = { + "spawn": () => { + const spacing = 3; + for (let x = 100; x < 200; x += spacing) + for (let z = 100; z < 200; z += spacing) + { + let ent = QuickSpawn(x, z, REG_UNIT_TEMPLATE); + for (let ii = 0; ii < 20; ++ii) + WalkTo(randFloat(100, 200), randFloat(100, 200), true, ent); + } + } +}; + +var woodcutting = (gx, gy) => { + let dropsite = QuickSpawn(gx + 50, gy, "structures/athen/storehouse"); + let cmpModifiersManager = Engine.QueryInterface(SYSTEM_ENTITY, IID_ModifiersManager); + cmpModifiersManager.AddModifiers("root", { + "TerritoryInfluence/Root": [{ "affects": ["Structure"], "replace": true }], + }, dropsite); + // Make units gather faster + cmpModifiersManager.AddModifiers("gatherrate", { + "ResourceGatherer/BaseSpeed": [{ "affects": ["Unit"], "multiply": 3 }], + }, 3); // Player 1 is ent 3 + for (let i = 20; i <= 80; i += 10) + for (let j = 20; j <= 50; j += 10) + QuickSpawn(gx + i, gy + j, "gaia/tree/acacia"); + for (let i = 10; i <= 90; i += 5) + Do("gather-near-position", { "x": gx + i, "z": gy + 10, "resourceType": { "generic": "wood", "specific": "tree" }, "resourceTemplate": "gaia/tree/acacia" }, + QuickSpawn(gx + i, gy, REG_UNIT_TEMPLATE)); +}; + +perf_experiments.WoodCutting = { + "spawn": () => { + for (let i = 0; i < 8; i++) + for (let j = 0; j < 8; j++) + { + woodcutting(20 + i*100, 20 + j*100); + } + } +}; + +var cmpTrigger = Engine.QueryInterface(SYSTEM_ENTITY, IID_Trigger); + +Trigger.prototype.Setup = function() +{ + let start = Engine.QueryInterface(SYSTEM_ENTITY, IID_Timer).GetTime(); + + // /* + let gx = 100; + let gy = 100; + for (let key in experiments) + { + experiments[key].spawn(gx, gy); + gx += 60; + if (gx > 20*16*4-20) + { + gx = 20; + gy += 100; + } + } + /**/ + /* + let time = 0; + for (let key in perf_experiments) + { + cmpTrigger.DoAfterDelay(1000 + time * 10000, "RunExperiment", { "exp": key }); + time++; + } + /**/ +}; + +Trigger.prototype.Cleanup = function() +{ + warn("cleanup"); + let cmpRangeManager = Engine.QueryInterface(SYSTEM_ENTITY, IID_RangeManager); + let ents = cmpRangeManager.GetEntitiesByPlayer(1).concat(cmpRangeManager.GetEntitiesByPlayer(2)); + for (let ent of ents) + Engine.DestroyEntity(ent); +}; + +Trigger.prototype.RunExperiment = function(data) +{ + warn("Start of " + data.exp); + perf_experiments[data.exp].spawn(); + cmpTrigger.DoAfterDelay(9500, "Cleanup", {}); +}; + +Trigger.prototype.EndGame = function() +{ + Engine.QueryInterface(4, IID_Player).SetState("defeated", "trigger"); + Engine.QueryInterface(3, IID_Player).SetState("won", "trigger"); +}; + +/* +var cmpModifiersManager = Engine.QueryInterface(SYSTEM_ENTITY, IID_ModifiersManager); + +// Reduce player 1 vision range (or patrolling units reacct) +cmpModifiersManager.AddModifiers("no_promotion", { + "Vision/Range": [{ "affects": ["Unit"], "replace": 5 }], +}, 3); // player 1 is ent 3 + +// Prevent promotions, messes up things. +cmpModifiersManager.AddModifiers("no_promotion_A", { + "Promotion/RequiredXp": [{ "affects": ["Unit"], "replace": 50000 }], +}, 3); +cmpModifiersManager.AddModifiers("no_promotion_B", { + "Promotion/RequiredXp": [{ "affects": ["Unit"], "replace": 50000 }], +}, 4); // player 2 is ent 4 +*/ + +cmpTrigger.DoAfterDelay(4000, "Setup", {}); + +cmpTrigger.DoAfterDelay(300000, "EndGame", {}); Index: binaries/data/mods/public/maps/scenarios/unit_pushing_test.xml =================================================================== --- /dev/null +++ binaries/data/mods/public/maps/scenarios/unit_pushing_test.xml @@ -0,0 +1,66 @@ + + + + + + default + + + + + + 0 + 0.5 + + + + + ocean + + + 5 + 4 + 0.45 + 0 + + + + 0 + 1 + 0.99 + 0.1999 + default + + + + + + + + + + + + Index: source/simulation2/components/CCmpUnitMotion.h =================================================================== --- source/simulation2/components/CCmpUnitMotion.h +++ source/simulation2/components/CCmpUnitMotion.h @@ -55,10 +55,10 @@ * smaller ranges might miss some legitimate routes around large obstacles.) * NB: keep the max-range in sync with the vertex pathfinder "move the search space" heuristic. */ -static const entity_pos_t SHORT_PATH_MIN_SEARCH_RANGE = entity_pos_t::FromInt(TERRAIN_TILE_SIZE*3)/2; +static const entity_pos_t SHORT_PATH_MIN_SEARCH_RANGE = entity_pos_t::FromInt(TERRAIN_TILE_SIZE*3); static const entity_pos_t SHORT_PATH_MAX_SEARCH_RANGE = entity_pos_t::FromInt(TERRAIN_TILE_SIZE*14); static const entity_pos_t SHORT_PATH_SEARCH_RANGE_INCREMENT = entity_pos_t::FromInt(TERRAIN_TILE_SIZE*1); -static const u8 SHORT_PATH_SEARCH_RANGE_INCREASE_DELAY = 2; +static const u8 SHORT_PATH_SEARCH_RANGE_INCREASE_DELAY = 1; /** * When using the short-pathfinder to rejoin a long-path waypoint, aim for a circle of this radius around the waypoint. @@ -155,7 +155,8 @@ bool m_FacePointAfterMove; - // Number of turns since we last managed to move successfully. + // Internal counter used when recovering from obstructed movement. + // Most notably, increases the search range of the vertex pathfinder. // See HandleObstructedMove() for more details. u8 m_FailedMovements = 0; @@ -507,11 +508,6 @@ } private: - bool ShouldAvoidMovingUnits() const - { - return !m_FormationController; - } - bool IsFormationMember() const { // TODO: this really shouldn't be what we are checking for. @@ -721,14 +717,14 @@ */ ControlGroupMovementObstructionFilter GetObstructionFilter() const { - return ControlGroupMovementObstructionFilter(ShouldAvoidMovingUnits(), GetGroup()); + return ControlGroupMovementObstructionFilter(false, GetGroup()); } /** * Filter a specific tag on top of the existing control groups. */ - SkipMovingTagAndControlGroupObstructionFilter GetObstructionFilter(const ICmpObstructionManager::tag_t& tag) const + SkipTagAndControlGroupObstructionFilter GetObstructionFilter(const ICmpObstructionManager::tag_t& tag) const { - return SkipMovingTagAndControlGroupObstructionFilter(tag, GetGroup()); + return SkipTagAndControlGroupObstructionFilter(tag, false, GetGroup()); } /** @@ -920,6 +916,15 @@ // If we were idle and will still be, no need for an update. state.needUpdate = state.cmpPosition->IsInWorld() && (m_CurSpeed != fixed::Zero() || m_MoveRequest.m_Type != MoveRequest::NONE); + + state.controlGroup = IsFormationMember() ? m_MoveRequest.m_Entity : INVALID_ENTITY; + + // Update moving flag, this is an internal construct used for pushing, + // so it does not really reflect whether the unit is actually moving or not. + state.isMoving = state.needUpdate; + CmpPtr cmpObstruction(GetEntityHandle()); + if (cmpObstruction) + cmpObstruction->SetMovingFlag(state.isMoving); } void CCmpUnitMotion::Move(CCmpUnitMotionManager::MotionState& state, fixed dt) @@ -946,9 +951,12 @@ else { // Update the Position component after our movement (if we actually moved anywhere) - // When moving always set the angle in the direction of the movement. CFixedVector2D offset = state.pos - state.initialPos; - state.angle = atan2_approx(offset.X, offset.Y); + // When moving always set the angle in the direction of the movement, + // if we are not trying to move, assume this is pushing-related movement, + // and maintain the current angle instead. + if (IsMoveRequested()) + state.angle = atan2_approx(offset.X, offset.Y); state.cmpPosition->MoveAndTurnTo(state.pos.X, state.pos.Y, state.angle); // Calculate the mean speed over this past turn. @@ -960,6 +968,10 @@ else if (!state.wasObstructed && state.pos != state.initialPos) m_FailedMovements = 0; + // If we moved straight, and didn't quite finish the path, reset - we'll update it next turn if still OK. + if (state.wentStraight && !state.wasObstructed) + m_ShortPath.m_Waypoints.clear(); + // We may need to recompute our path sometimes (e.g. if our target moves). // Since we request paths asynchronously anyways, this does not need to be done before moving. if (!state.wentStraight && PathingUpdateNeeded(state.pos)) @@ -1132,24 +1144,12 @@ void CCmpUnitMotion::UpdateMovementState(entity_pos_t speed) { - CmpPtr cmpObstruction(GetEntityHandle()); CmpPtr cmpVisual(GetEntityHandle()); - // Idle this turn. - if (speed == fixed::Zero()) + if (cmpVisual) { - // Update moving flag if we moved last turn. - if (m_CurSpeed > fixed::Zero() && cmpObstruction) - cmpObstruction->SetMovingFlag(false); - if (cmpVisual) + if (speed == fixed::Zero()) cmpVisual->SelectMovementAnimation("idle", fixed::FromInt(1)); - } - // Moved this turn - else - { - // Update moving flag if we didn't move last turn. - if (m_CurSpeed == fixed::Zero() && cmpObstruction) - cmpObstruction->SetMovingFlag(true); - if (cmpVisual) + else cmpVisual->SelectMovementAnimation(speed > (m_WalkSpeed / 2).Multiply(m_RunMultiplier + fixed::FromInt(1)) ? "run" : "walk", speed); } @@ -1298,6 +1298,12 @@ bool CCmpUnitMotion::TryGoingStraightToTarget(const CFixedVector2D& from) { + // Assume if we have short paths we want to follow them. + // Exception: offset movement (formations) generally have very short deltas + // and do look good we need them to walk-straight most of the time. + if (!IsFormationMember() && !m_ShortPath.m_Waypoints.empty()) + return false; + CFixedVector2D targetPos; if (!ComputeTargetPosition(targetPos)) return false; @@ -1332,15 +1338,15 @@ specificIgnore = cmpTargetObstruction->GetObstruction(); } + // Check movement against units - we want to use the short pathfinder to walk around those if needed. if (specificIgnore.valid()) { - if (!cmpPathfinder->CheckMovement(SkipTagObstructionFilter(specificIgnore), from.X, from.Y, goalPos.X, goalPos.Y, m_Clearance, m_PassClass)) + if (!cmpPathfinder->CheckMovement(GetObstructionFilter(specificIgnore), from.X, from.Y, goalPos.X, goalPos.Y, m_Clearance, m_PassClass)) return false; } else if (!cmpPathfinder->CheckMovement(GetObstructionFilter(), from.X, from.Y, goalPos.X, goalPos.Y, m_Clearance, m_PassClass)) return false; - // That route is okay, so update our path m_LongPath.m_Waypoints.clear(); m_ShortPath.m_Waypoints.clear(); Index: source/simulation2/components/CCmpUnitMotionManager.h =================================================================== --- source/simulation2/components/CCmpUnitMotionManager.h +++ source/simulation2/components/CCmpUnitMotionManager.h @@ -22,6 +22,8 @@ #include "ICmpUnitMotionManager.h" #include "simulation2/MessageTypes.h" +#include "simulation2/components/ICmpTerrain.h" +#include "simulation2/helpers/Grid.h" #include "simulation2/system/EntityMap.h" class CCmpUnitMotion; @@ -31,6 +33,7 @@ public: static void ClassInit(CComponentManager& componentManager) { + componentManager.SubscribeToMessageType(MT_TerrainChanged); componentManager.SubscribeToMessageType(MT_TurnStart); componentManager.SubscribeToMessageType(MT_Update_Final); componentManager.SubscribeToMessageType(MT_Update_MotionUnit); @@ -42,6 +45,8 @@ // Persisted state for each unit. struct MotionState { + MotionState(CmpPtr cmpPos, CCmpUnitMotion* cmpMotion); + // Component references - these must be kept alive for the duration of motion. // NB: this is generally not something one should do, but because of the tight coupling here it's doable. CmpPtr cmpPosition; @@ -52,22 +57,31 @@ // Transient position during the movement. CFixedVector2D pos; + // Accumulated "pushing" from nearby units. + CFixedVector2D push; + fixed initialAngle; fixed angle; + // Used for formations - units with the same control group won't push at a distance. + // (this is required because formations may be tight and large units may end up never settling. + entity_id_t controlGroup = INVALID_ENTITY; + // If true, the entity needs to be handled during movement. - bool needUpdate; + bool needUpdate = false; - // 'Leak' from UnitMotion. - bool wentStraight; - bool wasObstructed; + bool wentStraight = false; + bool wasObstructed = false; + + // Clone of the obstruction manager flag for efficiency + bool isMoving = false; }; EntityMap m_Units; EntityMap m_FormationControllers; - // Temporary vector, reconstructed each turn (stored here to avoid memory reallocations). - std::vector::iterator> m_MovingUnits; + // The vectors are cleared each frame. + Grid::iterator>> m_MovingUnits; bool m_ComputingMotion; @@ -78,7 +92,6 @@ virtual void Init(const CParamNode& UNUSED(paramNode)) { - m_MovingUnits.reserve(40); } virtual void Deinit() @@ -92,12 +105,20 @@ virtual void Deserialize(const CParamNode& paramNode, IDeserializer& UNUSED(deserialize)) { Init(paramNode); + ResetSubdivisions(); } virtual void HandleMessage(const CMessage& msg, bool UNUSED(global)) { switch (msg.GetType()) { + case MT_TerrainChanged: + { + CmpPtr cmpTerrain(GetSystemEntity()); + if (cmpTerrain->GetVerticesPerSide() != m_MovingUnits.width()) + ResetSubdivisions(); + break; + } case MT_TurnStart: { OnTurnStart(); @@ -130,13 +151,27 @@ return m_ComputingMotion; } +private: + void ResetSubdivisions(); void OnTurnStart(); void MoveUnits(fixed dt); void MoveFormations(fixed dt); void Move(EntityMap& ents, fixed dt); + + void Push(EntityMap::value_type& a, EntityMap::value_type& b, fixed dt); }; +void CCmpUnitMotionManager::ResetSubdivisions() +{ + CmpPtr cmpTerrain(GetSystemEntity()); + if (!cmpTerrain) + return; + + size_t size = cmpTerrain->GetVerticesPerSide() - 1; + m_MovingUnits.resize(size * TERRAIN_TILE_SIZE / 20 + 1, size * TERRAIN_TILE_SIZE / 20 + 1); +} + REGISTER_COMPONENT_TYPE(UnitMotionManager) #endif // INCLUDED_CCMPUNITMOTIONMANAGER Index: source/simulation2/components/CCmpUnitMotion_System.cpp =================================================================== --- source/simulation2/components/CCmpUnitMotion_System.cpp +++ source/simulation2/components/CCmpUnitMotion_System.cpp @@ -28,18 +28,14 @@ // but UnitMotion needs access to MotionState (defined in UnitMotionManager). // To avoid inclusion issues, implementation of UnitMotionManager that uses UnitMotion is here. +CCmpUnitMotionManager::MotionState::MotionState(CmpPtr cmpPos, CCmpUnitMotion* cmpMotion) + : cmpPosition(cmpPos), cmpUnitMotion(cmpMotion) +{ +} + void CCmpUnitMotionManager::Register(CCmpUnitMotion* component, entity_id_t ent, bool formationController) { - MotionState state = { - CmpPtr(GetSimContext(), ent), - component, - CFixedVector2D(), - CFixedVector2D(), - fixed::Zero(), - fixed::Zero(), - false, - false - }; + MotionState state(CmpPtr(GetSimContext(), ent), component); if (!formationController) m_Units.insert(ent, state); else @@ -80,22 +76,182 @@ void CCmpUnitMotionManager::Move(EntityMap& ents, fixed dt) { - m_MovingUnits.clear(); + PROFILE2("MotionMgr_Move"); + std::set::iterator>*> assigned; for (EntityMap::iterator it = ents.begin(); it != ents.end(); ++it) { - it->second.cmpUnitMotion->PreMove(it->second); - if (!it->second.needUpdate) + if (!it->second.cmpPosition->IsInWorld()) + { + it->second.needUpdate = false; continue; - m_MovingUnits.push_back(it); + } + else + it->second.cmpUnitMotion->PreMove(it->second); it->second.initialPos = it->second.cmpPosition->GetPosition2D(); it->second.initialAngle = it->second.cmpPosition->GetRotation().Y; it->second.pos = it->second.initialPos; it->second.angle = it->second.initialAngle; + ENSURE(it->second.pos.X.ToInt_RoundToZero() / 20 < m_MovingUnits.width() && it->second.pos.Y.ToInt_RoundToZero() / 20 < m_MovingUnits.height()); + std::vector::iterator>& subdiv = m_MovingUnits.get(it->second.pos.X.ToInt_RoundToZero() / 20, it->second.pos.Y.ToInt_RoundToZero() / 20); + subdiv.emplace_back(it); + assigned.emplace(&subdiv); } - for (EntityMap::iterator& it : m_MovingUnits) + for (std::vector::iterator>* vec : assigned) + for (EntityMap::iterator& it : *vec) + if (it->second.needUpdate) + it->second.cmpUnitMotion->Move(it->second, dt); + + if (&ents == &m_Units) + { + PROFILE2("MotionMgr_Pushing"); + for (std::vector::iterator>* vec : assigned) + { + ENSURE(!vec->empty()); + + std::vector::iterator>::iterator cit1 = vec->begin(); + do + { + std::vector::iterator>::iterator cit2 = cit1; + while(++cit2 != vec->end()) + Push(**cit1, **cit2, dt); + } + while(++cit1 != vec->end()); + } + } + + { + PROFILE2("MotionMgr_PushAdjust"); + CmpPtr cmpPathfinder(GetSystemEntity()); + for (std::vector::iterator>* vec : assigned) + { + for (EntityMap::iterator& it : *vec) + { + + if (!it->second.needUpdate) + continue; + + // Prevent pushed units from crossing uncrossable boundaries + // (we can assume that normal movement didn't push units into impassable terrain). + if ((it->second.push.X != entity_pos_t::Zero() || it->second.push.Y != entity_pos_t::Zero()) && + !cmpPathfinder->CheckMovement(it->second.cmpUnitMotion->GetObstructionFilter(), + it->second.pos.X, it->second.pos.Y, + it->second.pos.X + it->second.push.X, it->second.pos.Y + it->second.push.Y, + it->second.cmpUnitMotion->m_Clearance, + it->second.cmpUnitMotion->m_PassClass)) + { + // Mark them as obstructed - this could possibly be optimised + // perhaps it'd make more sense to mark the pushers as blocked. + it->second.wasObstructed = true; + it->second.wentStraight = false; + it->second.push = CFixedVector2D(); + } + // Only apply pushing if the effect is significant enough. + if (it->second.push.CompareLength(entity_pos_t::FromInt(1)/10) > 0) + { + // If there was an attempt at movement, and the pushed movement is in a sufficiently different direction + // (measured by an extremely arbitrary dot product) + // then mark the unit as obstructed still. + if (it->second.pos != it->second.initialPos && + (it->second.pos - it->second.initialPos).Dot(it->second.pos + it->second.push - it->second.initialPos) < entity_pos_t::FromInt(1)/2) + { + it->second.wasObstructed = true; + it->second.wentStraight = false; + // Push anyways. + } + it->second.pos += it->second.push; + } + it->second.push = CFixedVector2D(); + } + } + } + { + PROFILE2("MotionMgr_PostMove"); + for (EntityMap::value_type& data : ents) + { + if (!data.second.needUpdate) + continue; + data.second.cmpUnitMotion->PostMove(data.second, dt); + } + } + for (std::vector::iterator>* vec : assigned) + vec->clear(); +} + +// TODO: ought to better simulate in-flight pushing, e.g. if units would cross in-between turns. +void CCmpUnitMotionManager::Push(EntityMap::value_type& a, EntityMap::value_type& b, fixed dt) +{ + // The hard problem for pushing is knowing when to actually use the pathfinder to go around unpushable obstacles. + // For simplicitly, the current logic separates moving & stopped entities: + // moving entities will push moving entities, but not stopped ones, and vice-versa. + // this still delivers most of the value of pushing, without a lot of the complexity. + int movingPush = a.second.isMoving + b.second.isMoving; + + // Exception: units in the same control group (i.e. the same formation) never push farther than themselves + // and are also allowed to push idle units (obstructions are ignored within formations, + // so pushing idle units makes one member crossing the formation look better). + if (a.second.controlGroup != INVALID_ENTITY && a.second.controlGroup == b.second.controlGroup) + movingPush = 0; + + if (movingPush == 1) + return; + + // Treat the clearances as a circle - they're defined as squares, so we'll slightly overcompensate the diagonal + // (they're also full-width instead of half, so we want to divide by two. sqrt(2)/2 is about 0.71 < 5/7). + entity_pos_t combinedClearance = (a.second.cmpUnitMotion->m_Clearance + b.second.cmpUnitMotion->m_Clearance) * 5 / 7; + entity_pos_t maxDist = combinedClearance; + if (movingPush) + maxDist += entity_pos_t::FromInt(1); + + + CFixedVector2D offset = a.second.pos - b.second.pos; + if (offset.CompareLength(maxDist) > 0) + return; + + entity_pos_t offsetLength = offset.Length(); + // If the offset is small enough that precision would be problematic, pick an arbitrary vector instead. + if (offsetLength <= entity_pos_t::Epsilon() * 10) + { + // Throw in some 'randomness' so that clumped units unclump more naturally. + bool dir = a.first % 2; + offset.X = entity_pos_t::FromInt(dir ? 1 : 0); + offset.Y = entity_pos_t::FromInt(dir ? 0 : 1); + offsetLength = entity_pos_t::FromInt(1); + } + else { - it->second.cmpUnitMotion->Move(it->second, dt); - it->second.cmpUnitMotion->PostMove(it->second, dt); + offset.X = offset.X / offsetLength; + offset.Y = offset.Y / offsetLength; } + + // If the units are moving in opposite direction, check if they might have phased through each other. + // If it looks like yes, move them perpendicularily so it looks like they avoid each other. + // NB: this isn't very precise, nor will it catch 100% of intersections - it's meant as a cheap improvement. + if (movingPush && (a.second.pos - a.second.initialPos).Dot(b.second.pos - b.second.initialPos) < entity_pos_t::Zero()) + // Perform some finer checking. + if (Geometry::TestRayAASquare(a.second.initialPos - b.second.initialPos, a.second.pos - b.second.initialPos, + CFixedVector2D(combinedClearance, combinedClearance)) + || + Geometry::TestRayAASquare(a.second.initialPos - b.second.pos, a.second.pos - b.second.pos, + CFixedVector2D(combinedClearance, combinedClearance))) + { + offset = offset.Perpendicular(); + offsetLength = fixed::Zero(); + } + + + + // The formula expects 'normal' pushing if the two entities edges are touching. + entity_pos_t distanceFactor = movingPush ? (maxDist - offsetLength) / (maxDist - combinedClearance) : combinedClearance - offsetLength + entity_pos_t::FromInt(1); + distanceFactor = std::clamp(distanceFactor, entity_pos_t::Zero(), entity_pos_t::FromInt(2)); + + // Mark both as needing an update so they actually get moved. + a.second.needUpdate = true; + b.second.needUpdate = true; + + CFixedVector2D pushingDir = offset.Multiply(distanceFactor); + + // Divide by an arbitrary constant to avoid pushing too much. + a.second.push += pushingDir.Multiply(movingPush ? dt : dt / 2); + b.second.push -= pushingDir.Multiply(movingPush ? dt : dt / 2); } Index: source/simulation2/components/ICmpObstructionManager.h =================================================================== --- source/simulation2/components/ICmpObstructionManager.h +++ source/simulation2/components/ICmpObstructionManager.h @@ -1,4 +1,4 @@ -/* Copyright (C) 2020 Wildfire Games. +/* Copyright (C) 2021 Wildfire Games. * This file is part of 0 A.D. * * 0 A.D. is free software: you can redistribute it and/or modify @@ -92,7 +92,7 @@ FLAG_BLOCK_FOUNDATION = (1 << 1), // prevents foundations being placed on this shape FLAG_BLOCK_CONSTRUCTION = (1 << 2), // prevents buildings being constructed on this shape FLAG_BLOCK_PATHFINDING = (1 << 3), // prevents the tile pathfinder choosing paths through this shape - FLAG_MOVING = (1 << 4), // indicates this unit is currently moving + FLAG_MOVING = (1 << 4), // reserved for unitMotion - indicates intention to move. FLAG_DELETE_UPON_CONSTRUCTION = (1 << 5) // this entity is deleted when construction of a building placed on top of this entity starts }; @@ -530,27 +530,30 @@ }; /** - * Obstruction test filter that reject shapes in a given control group or with the given tag (if that tag is moving), - * and rejects shapes that don't block unit movement. See D3482 for why this exists. + * Similar to ControlGroupMovementObstructionFilter, but also ignoring a specific tag. See D3482 for why this exists. */ -class SkipMovingTagAndControlGroupObstructionFilter : public IObstructionTestFilter +class SkipTagAndControlGroupObstructionFilter : public IObstructionTestFilter { entity_id_t m_Group; tag_t m_Tag; + bool m_AvoidMoving; public: - SkipMovingTagAndControlGroupObstructionFilter(tag_t tag, entity_id_t group) : - m_Tag(tag), m_Group(group) + SkipTagAndControlGroupObstructionFilter(tag_t tag, bool avoidMoving, entity_id_t group) : + m_Tag(tag), m_Group(group), m_AvoidMoving(avoidMoving) {} virtual bool TestShape(tag_t tag, flags_t flags, entity_id_t group, entity_id_t group2) const { - if (tag.n == m_Tag.n && (flags & ICmpObstructionManager::FLAG_MOVING)) + if (tag.n == m_Tag.n) return false; if (group == m_Group || (group2 != INVALID_ENTITY && group2 == m_Group)) return false; + if ((flags & ICmpObstructionManager::FLAG_MOVING) && !m_AvoidMoving) + return false; + if (!(flags & ICmpObstructionManager::FLAG_BLOCK_MOVEMENT)) return false; Index: source/simulation2/helpers/LongPathfinder.h =================================================================== --- source/simulation2/helpers/LongPathfinder.h +++ source/simulation2/helpers/LongPathfinder.h @@ -1,4 +1,4 @@ -/* Copyright (C) 2020 Wildfire Games. +/* Copyright (C) 2021 Wildfire Games. * This file is part of 0 A.D. * * 0 A.D. is free software: you can redistribute it and/or modify @@ -260,9 +260,7 @@ /** * Given a path with an arbitrary collection of waypoints, updates the - * waypoints to be nicer. Calls "Testline" between waypoints - * so that bended paths can become straight if there's nothing in between - * (this happens because A* is 8-direction, and the map isn't actually a grid). + * waypoints to be nicer. * If @param maxDist is non-zero, path waypoints will be espaced by at most @param maxDist. * In that case the distance between (x0, z0) and the first waypoint will also be made less than maxDist. */