Index: binaries/data/mods/public/maps/scenarios/unit_pushing_test.js =================================================================== --- binaries/data/mods/public/maps/scenarios/unit_pushing_test.js +++ binaries/data/mods/public/maps/scenarios/unit_pushing_test.js @@ -279,7 +279,8 @@ { cmpTrigger.DoAfterDelay(1000 + time * 10000, "RunExperiment", { "exp": key }); time++; - }*/ + } + */ }; Trigger.prototype.Cleanup = function() @@ -294,7 +295,7 @@ Trigger.prototype.RunExperiment = function(data) { warn("Start of " + data.exp); - experiments[data.exp].spawn(); + perf_experiments[data.exp].spawn(); cmpTrigger.DoAfterDelay(9500, "Cleanup", {}); }; 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/CCmpObstructionManager.cpp =================================================================== --- source/simulation2/components/CCmpObstructionManager.cpp +++ source/simulation2/components/CCmpObstructionManager.cpp @@ -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/CCmpPathfinder.cpp =================================================================== --- source/simulation2/components/CCmpPathfinder.cpp +++ source/simulation2/components/CCmpPathfinder.cpp @@ -898,8 +898,6 @@ PROFILE2_IFSPIKE("Check Movement", 0.001); // Test against obstructions first. filter may discard pathfinding-blocking obstructions. - // Use more permissive version of TestLine to allow unit-unit collisions to overlap slightly. - // This makes movement smoother and more natural for units, overall. CmpPtr cmpObstructionManager(GetSystemEntity()); if (!cmpObstructionManager || cmpObstructionManager->TestLine(filter, x0, z0, x1, z1, r, true)) return false; 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 @@ -155,7 +155,9 @@ 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. + // Currently resets on new move orders & when reaching the maximum. // See HandleObstructedMove() for more details. u8 m_FailedMovements = 0; @@ -507,11 +509,6 @@ } private: - bool ShouldAvoidMovingUnits() const - { - return !m_FormationController; - } - bool IsFormationMember() const { // TODO: this really shouldn't be what we are checking for. @@ -721,14 +718,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 +917,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 +950,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. @@ -957,8 +964,6 @@ if (state.wasObstructed && HandleObstructedMove(state.pos != state.initialPos)) return; - else if (!state.wasObstructed && state.pos != state.initialPos) - m_FailedMovements = 0; // 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. @@ -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(); 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; + } + else + 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. */