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,327 @@ +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 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.interlapping = { + "spawn": (gx, gy) => { + for (let i = 0; i < 20; ++i) + QuickSpawn(gx, gy, REG_UNIT_TEMPLATE); + } +}; + +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 = 12; + 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 = 36; + 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 = 36; + 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) + { + let ent = QuickSpawn(x + i, z + 20 * (i%2), 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 = 4; + 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 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: binaries/data/mods/public/simulation/templates/template_gaia_tree.xml =================================================================== --- binaries/data/mods/public/simulation/templates/template_gaia_tree.xml +++ binaries/data/mods/public/simulation/templates/template_gaia_tree.xml @@ -7,6 +7,7 @@ Tree Chop trees for wood. + Tree gaia/flora_tree_generic.png Index: source/main.cpp =================================================================== --- source/main.cpp +++ source/main.cpp @@ -475,7 +475,10 @@ g_Profiler.Frame(); if (g_Game->IsGameFinished()) + { + g_Profiler2.SaveToFile(); QuitEngine(); + } } static void MainControllerInit() Index: source/simulation2/components/CCmpPathfinder_Common.h =================================================================== --- source/simulation2/components/CCmpPathfinder_Common.h +++ source/simulation2/components/CCmpPathfinder_Common.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 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. @@ -524,11 +520,6 @@ return cmpControllerMotion && cmpControllerMotion->IsMoveRequested(); } - entity_id_t GetGroup() const - { - return IsFormationMember() ? m_MoveRequest.m_Entity : GetEntityId(); - } - /** * Warns other components that our current movement will likely fail (e.g. we won't be able to reach our target) * This should only be called before the actual movement in a given turn, or units might both move and try to do things @@ -721,14 +712,14 @@ */ ControlGroupMovementObstructionFilter GetObstructionFilter() const { - return ControlGroupMovementObstructionFilter(ShouldAvoidMovingUnits(), GetGroup()); + return ControlGroupMovementObstructionFilter(false, GetEntityId()); } /** * 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, GetEntityId()); } /** @@ -920,6 +911,13 @@ // 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); + + // 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 +944,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 +961,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 +1137,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 +1291,10 @@ bool CCmpUnitMotion::TryGoingStraightToTarget(const CFixedVector2D& from) { + // Assume if we have short paths we want to follow them. + if (!m_ShortPath.m_Waypoints.empty()) + return false; + CFixedVector2D targetPos; if (!ComputeTargetPosition(targetPos)) return false; @@ -1332,15 +1329,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(); @@ -1640,7 +1637,7 @@ } m_ExpectedPathTicket.m_Type = Ticket::SHORT_PATH; - m_ExpectedPathTicket.m_Ticket = cmpPathfinder->ComputeShortPathAsync(from.X, from.Y, m_Clearance, searchRange, goal, m_PassClass, true, GetGroup(), GetEntityId()); + m_ExpectedPathTicket.m_Ticket = cmpPathfinder->ComputeShortPathAsync(from.X, from.Y, m_Clearance, searchRange, goal, m_PassClass, true, GetEntityId(), GetEntityId()); } bool CCmpUnitMotion::MoveTo(MoveRequest request) 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); @@ -52,22 +55,27 @@ // Transient position during the movement. CFixedVector2D pos; + // Accumulated "pushing" from nearby units. + CFixedVector2D push; + fixed initialAngle; fixed angle; // If true, the entity needs to be handled during movement. bool needUpdate; - // 'Leak' from UnitMotion. bool wentStraight; bool wasObstructed; + + // Clone of the obstruction manager flag for efficiency + bool isMoving; }; 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 +86,6 @@ virtual void Init(const CParamNode& UNUSED(paramNode)) { - m_MovingUnits.reserve(40); } virtual void Deinit() @@ -92,12 +99,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 +145,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 @@ -35,9 +35,12 @@ component, CFixedVector2D(), CFixedVector2D(), + CFixedVector2D(fixed::FromInt(0), fixed::FromInt(0)), fixed::Zero(), fixed::Zero(), false, + false, + false, false }; if (!formationController) @@ -80,22 +83,174 @@ 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) { - it->second.cmpUnitMotion->Move(it->second, dt); - it->second.cmpUnitMotion->PostMove(it->second, dt); + 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; + 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 + { + 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. */