Index: binaries/data/mods/public/maps/scenarios/unit_motion_integration_test.js =================================================================== --- binaries/data/mods/public/maps/scenarios/unit_motion_integration_test.js +++ binaries/data/mods/public/maps/scenarios/unit_motion_integration_test.js @@ -292,6 +292,23 @@ } }; +/** + * Regression test for #5795 + * Before the fix, the units were pathing to the bottom-right dead-end, + * before going back through the corridor. + * After the fix, that should mostly not happen: units should just wait. + * (note that it's not an entirely perfect fix, but it should just be a few units, not half) + */ +experiments.small_exit_of_hill = { + "spawn": () => { + let x = 350; + let y = 615; + for (let i = -5; i <= 5; i += 1) + for (let j = -5; j <= 5; j += 1) + WalkTo(350, 500, QuickSpawn(x + i, y + j, UNIT_TEMPLATE)); + } +}; + var cmpTrigger = Engine.QueryInterface(SYSTEM_ENTITY, IID_Trigger); Trigger.prototype.SetupUnits = function() Index: binaries/data/mods/public/maps/scenarios/unit_motion_integration_test.xml =================================================================== --- binaries/data/mods/public/maps/scenarios/unit_motion_integration_test.xml +++ binaries/data/mods/public/maps/scenarios/unit_motion_integration_test.xml @@ -1,7 +1,6 @@ - default @@ -12,13 +11,13 @@ 0 0.5 - + ocean - - + + 5 4 0.45 @@ -34,7 +33,7 @@ - + @@ -48,6 +47,7 @@ ], "Name": "Unit Motion Integration Test", "PlayerData": [ + null, { "Civ": "athen" }, Index: source/simulation2/components/CCmpUnitMotion.cpp =================================================================== --- source/simulation2/components/CCmpUnitMotion.cpp +++ source/simulation2/components/CCmpUnitMotion.cpp @@ -51,7 +51,8 @@ */ 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_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*2); +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_START = 2; /** * When using the short-pathfinder to rejoin a long-path waypoint, aim for a circle of this radius around the waypoint. @@ -61,7 +62,7 @@ /** * Minimum distance to goal for a long path request */ -static const entity_pos_t LONG_PATH_MIN_DIST = entity_pos_t::FromInt(TERRAIN_TILE_SIZE*4); +static const entity_pos_t LONG_PATH_MIN_DIST = entity_pos_t::FromInt(TERRAIN_TILE_SIZE*3); /** * If we are this close to our target entity/point, then think about heading @@ -87,17 +88,17 @@ static const u8 KNOWN_IMPERFECT_PATH_RESET_COUNTDOWN = 12; /** - * When we fail more than this many path computations in a row, inform other components that the move will fail. + * When we fail to move this many turns in a row, inform other components that the move will fail. * Experimentally, this number needs to be somewhat high or moving groups of units will lead to stuck units. * However, too high means units will look idle for a long time when they are failing to move. * TODO: if UnitMotion could send differentiated "unreachable" and "currently stuck" failing messages, * this could probably be lowered. * TODO: when unit pushing is implemented, this number can probably be lowered. */ -static const u8 MAX_FAILED_PATH_COMPUTATIONS = 15; +static const u8 MAX_FAILED_MOVEMENTS = 30; /** - * If we have failed path computations this many times and ComputePathToGoal is called, + * If we have failed to move this many times and ComputePathToGoal is called, * run the opposite path type to what we normally would, to avoid getting stuck sometimes. */ static const u8 ALTERNATE_PATH_TYPE_ON = 3; @@ -141,10 +142,9 @@ bool m_FacePointAfterMove; - // Number of path computations that failed (in a row). - // When this gets above MAX_FAILED_PATH_COMPUTATIONS, inform other components - // that the move will likely fail. - u8 m_FailedPathComputations = 0; + // Number of turns since we last managed to move successfully. + // See HandleObstructedMove() for more details. + u8 m_FailedMovements = 0; // If > 0, PathingUpdateNeeded returns false always. // This exists because the goal may be unreachable to the short/long pathfinder. @@ -263,7 +263,7 @@ serialize.NumberU32_Unbounded("ticket", m_ExpectedPathTicket.m_Ticket); SerializeU8_Enum()(serialize, "ticket type", m_ExpectedPathTicket.m_Type); - serialize.NumberU8_Unbounded("failed path computations", m_FailedPathComputations); + serialize.NumberU8_Unbounded("failed movements", m_FailedMovements); serialize.NumberU8_Unbounded("followknownimperfectpath", m_FollowKnownImperfectPathCountdown); SerializeU8_Enum()(serialize, "target type", m_MoveRequest.m_Type); @@ -560,16 +560,16 @@ } /** - * Increment the number of failed path computations and notify other components if required. + * Increment the number of failed movements and notify other components if required. * @returns true if the failure was notified, false otherwise. */ - bool IncrementFailedPathComputationAndMaybeNotify() + bool IncrementFailedMovementsAndMaybeNotify() { - m_FailedPathComputations++; - if (m_FailedPathComputations >= MAX_FAILED_PATH_COMPUTATIONS) + m_FailedMovements++; + if (m_FailedMovements >= MAX_FAILED_MOVEMENTS) { MoveFailed(); - m_FailedPathComputations = 0; + m_FailedMovements = 0; return true; } return false; @@ -580,20 +580,20 @@ */ bool RejectFartherPaths(const PathGoal& goal, const WaypointPath& path, const CFixedVector2D& pos) const; - /** - * If there are 2 waypoints of more remaining in longPath, return SHORT_PATH_LONG_WAYPOINT_RANGE. - * Otherwise the pathing should be exact. - */ - entity_pos_t ShortPathWaypointRange(const WaypointPath& longPath) const - { - return longPath.m_Waypoints.size() >= 2 ? SHORT_PATH_LONG_WAYPOINT_RANGE : entity_pos_t::Zero(); - } - bool InShortPathRange(const PathGoal& goal, const CFixedVector2D& pos) const { return goal.DistanceToPoint(pos) < LONG_PATH_MIN_DIST; } + entity_pos_t ShortPathSearchRange() + { + u8 multiple = m_FailedMovements < SHORT_PATH_SEARCH_RANGE_INCREASE_START ? 0 : m_FailedMovements - SHORT_PATH_SEARCH_RANGE_INCREASE_START; + fixed searchRange = SHORT_PATH_MIN_SEARCH_RANGE + SHORT_PATH_SEARCH_RANGE_INCREMENT * multiple; + if (searchRange > SHORT_PATH_MAX_SEARCH_RANGE) + searchRange = SHORT_PATH_MAX_SEARCH_RANGE; + return searchRange; + } + /** * Handle the result of an asynchronous path query. */ @@ -626,9 +626,10 @@ /** * React if our move was obstructed. + * @param moved - true if the unit still managed to move. * @returns true if the obstruction required handling, false otherwise. */ - bool HandleObstructedMove(); + bool HandleObstructedMove(bool moved); /** * Returns true if the target position is valid. False otherwise. @@ -736,111 +737,63 @@ Ticket::Type ticketType = m_ExpectedPathTicket.m_Type; m_ExpectedPathTicket.clear(); - // Check that we are still able to do something with that path + // An empty path means the pathing request failed, so do nothing + // and the regular Move() calls will handle the failure. + if (path.m_Waypoints.empty()) + return; + + // If we not longer have a position, we won't be able to do much. + // Again, we'll fail in the next Move() call. CmpPtr cmpPosition(GetEntityHandle()); if (!cmpPosition || !cmpPosition->IsInWorld()) - { - // We will probably fail to move so inform components but keep on trying anyways. - MoveFailed(); return; - } CFixedVector2D pos = cmpPosition->GetPosition2D(); + // Assume all long paths were towards the goal, and assume short paths were if there are no long waypoints. + bool pathedTowardsGoal = ticketType == Ticket::LONG_PATH || m_LongPath.m_Waypoints.empty(); + PathGoal goal; - // If we can't compute a goal, we'll fail in the next Move() call so do nothing special. - if (!ComputeGoal(goal, m_MoveRequest)) + // Reject paths that would take the unit further away from the goal. + // This assumes that we prefer being closer 'as the crow flies' to unreachable goals. + // This is a hack of sorts around units 'dancing' between two positions (see e.g. #3144), + // but never actually failing to move, ergo never actually informing unitAI that it succeeds/fails. + // (for short paths, only do so if aiming directly for the goal + // as sub-goals may be farther than we are). + if (pathedTowardsGoal && ComputeGoal(goal, m_MoveRequest) && RejectFartherPaths(goal, path, pos)) + { + IncrementFailedMovementsAndMaybeNotify(); return; + } if (ticketType == Ticket::LONG_PATH) - { - if (RejectFartherPaths(goal, path, pos)) - { - IncrementFailedPathComputationAndMaybeNotify(); - return; - } - m_LongPath = path; - - m_FollowKnownImperfectPathCountdown = 0; - - // If there's no waypoints then we couldn't get near the target. - // Sort of hack: Just try going directly to the goal point instead - // (via the short pathfinder over the next turns), so if we're stuck and the user clicks - // close enough to the unit then we can probably get unstuck - // NB: this relies on HandleObstructedMove requesting short paths if we still have long waypoints. - if (m_LongPath.m_Waypoints.empty()) - { - IncrementFailedPathComputationAndMaybeNotify(); - CFixedVector2D targetPos; - if (ComputeTargetPosition(targetPos)) - m_LongPath.m_Waypoints.emplace_back(Waypoint{ targetPos.X, targetPos.Y }); - } - // If this new path won't put us in range, it's highly likely that we are going somewhere unreachable. - // This means we will try to recompute the path every turn. - // To avoid this, act as if our current path leads us to the correct destination. - // (we will still fail the move when we arrive to the best possible position, and if we were blocked by - // an obstruction and it goes away we will notice when getting there as having no waypoint goes through - // HandleObstructedMove, so this is safe). - else if (PathingUpdateNeeded(pos)) - { - // Inform other components early, as they might have better behaviour than waiting for the path to carry out. - // Send OBSTRUCTED at first - moveFailed is likely to trigger path recomputation and we might end up - // recomputing too often for nothing. - if (!IncrementFailedPathComputationAndMaybeNotify()) - MoveObstructed(); - m_FollowKnownImperfectPathCountdown = KNOWN_IMPERFECT_PATH_RESET_COUNTDOWN; - } - return; - } - - // Reject new short paths if they were aiming at the goal directly (i.e. no long waypoints still exists). - if (m_LongPath.m_Waypoints.empty() && RejectFartherPaths(goal, path, pos)) - { - IncrementFailedPathComputationAndMaybeNotify(); - return; - } - - m_ShortPath = path; + else + m_ShortPath = path; m_FollowKnownImperfectPathCountdown = 0; - if (!m_ShortPath.m_Waypoints.empty()) - { - if (PathingUpdateNeeded(pos)) - { - // Inform other components early, as they might have better behaviour than waiting for the path to carry out. - // Send OBSTRUCTED at first - moveFailed is likely to trigger path recomputation and we might end up - // recomputing too often for nothing. - if (!IncrementFailedPathComputationAndMaybeNotify()) - MoveObstructed(); - m_FollowKnownImperfectPathCountdown = KNOWN_IMPERFECT_PATH_RESET_COUNTDOWN; - } + + if (!pathedTowardsGoal) return; - } - if (m_FailedPathComputations >= 1) - // Inform other components - we might be ordered to stop, and computeGoal will then fail and return early. - MoveObstructed(); - - IncrementFailedPathComputationAndMaybeNotify(); - - // If there's no waypoints then we couldn't get near the target - // If we're globally following a long path, try to remove the next waypoint, - // it might be obstructed (e.g. by idle entities which the long-range pathfinder doesn't see). - if (!m_LongPath.m_Waypoints.empty()) + // If we were pathing towards the goal and this new path won't put us in range, + // it's highly likely that we are going somewhere unreachable. + // However, Move() will try to recompute the path every turn. + // To avoid this, act as if our current path leads us to the correct destination. + // NB: for short-paths, the problem might be that the search space is too small + // but we'll still follow this path until the end and try again then. + // Because we reject farther paths, it works out. + if (PathingUpdateNeeded(pos)) { - m_LongPath.m_Waypoints.pop_back(); - if (!m_LongPath.m_Waypoints.empty()) - { - // Get close enough - this will likely help the short path efficiency, and if we end up taking a wrong way - // we'll easily be able to revert it using a long path. - goal = { PathGoal::CIRCLE, m_LongPath.m_Waypoints.back().x, m_LongPath.m_Waypoints.back().z, ShortPathWaypointRange(m_LongPath) }; - RequestShortPath(pos, goal, true); - return; - } + // Inform other components early, as they might have better behaviour than waiting for the path to carry out. + // Send OBSTRUCTED at first - moveFailed is likely to trigger path recomputation and we might end up + // recomputing too often for nothing. + if (!IncrementFailedMovementsAndMaybeNotify()) + MoveObstructed(); + // We'll automatically recompute a path when this reaches 0, as a way to improve behaviour. + // (See D665 - this is needed because the target may be moving, and we should adjust to that). + m_FollowKnownImperfectPathCountdown = KNOWN_IMPERFECT_PATH_RESET_COUNTDOWN; } - - ComputePathToGoal(pos, goal); } void CCmpUnitMotion::Move(fixed dt) @@ -899,10 +852,10 @@ UpdateMovementState(offset.Length() / dt); } - if (wasObstructed && HandleObstructedMove()) + if (wasObstructed && HandleObstructedMove(pos != initialPos)) return; else if (!wasObstructed) - m_FailedPathComputations = 0; + 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. @@ -1059,15 +1012,20 @@ m_CurSpeed = speed; } -bool CCmpUnitMotion::HandleObstructedMove() +bool CCmpUnitMotion::HandleObstructedMove(bool moved) { CmpPtr cmpPosition(GetEntityHandle()); if (!cmpPosition || !cmpPosition->IsInWorld()) return false; - if (m_FailedPathComputations >= 1) - // Inform other components - we might be ordered to stop, and computeGoal will then fail and return early. - MoveObstructed(); + // We failed to move: increment the counter and possibly inform components. + // (don't send messages on the first failure, as that would be too noisy). + // Also don't increment above the initial MoveObstructed message if we actually manage to move a little. + if (!moved || m_FailedMovements < 2) + { + if (!IncrementFailedMovementsAndMaybeNotify() && m_FailedMovements >= 2) + MoveObstructed(); + } PathGoal goal; if (!ComputeGoal(goal, m_MoveRequest)) @@ -1076,28 +1034,42 @@ // At this point we have a position in the world since ComputeGoal checked for that. CFixedVector2D pos = cmpPosition->GetPosition2D(); - if (!InShortPathRange(goal, pos)) - { - // If we still have long waypoints, try and compute a short path to our next long waypoint. - // Assume the next waypoint is impassable and pop it. This helps unstuck entities in some cases, and we'll just - // end up recomputing a long path if we pop all of them, so it's safe. - if (m_LongPath.m_Waypoints.size() >= 1) + // Assume that we are merely obstructed and the long path is salvageable, so try going around the obstruction. + // This could be a separate function, but it doesn't really make sense to call it outside of here, and I can't find a name. + // I use an IIFE to have nice 'return' semantics still. + if ([&]() -> bool { + if (m_LongPath.m_Waypoints.size() < 2) + return false; + + // If the goal is close enough, we should ignore any remaining long waypoint and just + // short path there directly, as that improves behaviour in general - see D2095). + if (InShortPathRange(goal, pos)) + return false; + + // Delete the next waypoint if it's reasonably close, + // because it might be blocked by units and thus unreachable. + // NB: this number is tricky. Make it too high, and units start going down dead ends, which looks odd (#5795) + // Make it too low, and they might get stuck behind other obstructed entities. + // It also has performance implications because it calls the short-pathfinder. + fixed skipbeyond = ShortPathSearchRange() / 3; + if ((pos - CFixedVector2D(m_LongPath.m_Waypoints.back().x, m_LongPath.m_Waypoints.back().z)).CompareLength(skipbeyond) < 0) m_LongPath.m_Waypoints.pop_back(); - if (!m_LongPath.m_Waypoints.empty()) - { - // Get close enough - this will likely help the short path efficiency, and if we end up taking a wrong way - // we'll easily be able to revert it using a long path. - goal = { PathGoal::CIRCLE, m_LongPath.m_Waypoints.back().x, m_LongPath.m_Waypoints.back().z, ShortPathWaypointRange(m_LongPath) }; - RequestShortPath(pos, goal, true); - return true; - } - } + else if (m_FailedMovements == MAX_FAILED_MOVEMENTS - 3) + // Recompute the whole thing once, in case we got stuck in a dead end because of this heuristic. + return false; + static_assert(MAX_FAILED_MOVEMENTS > 3, "short pathfinder fallback heuristic won't work."); - // Else, just entirely recompute. This will ensure we occasionally run a long path so avoid getting stuck - // in the short pathfinder, which can happen when an entity is right ober an obstruction's edge. + // Compute a short path in the general vicinity of the next waypoint, to help pathfinding in crowds. + // The goal here is to manage to move in the general direction of our target, not to be super accurate. + fixed radius = Clamp(skipbeyond/3, fixed::FromInt(TERRAIN_TILE_SIZE), fixed::FromInt(TERRAIN_TILE_SIZE*3)); + PathGoal subgoal = { PathGoal::CIRCLE, m_LongPath.m_Waypoints.back().x, m_LongPath.m_Waypoints.back().z, radius }; + RequestShortPath(pos, subgoal, true); + return true; + }()) return true; + + // If we couldn't use a workaround, try recomputing the entire path. ComputePathToGoal(pos, goal); - // potential TODO: We could switch the short-range pathfinder for something else entirely. return true; } @@ -1442,7 +1414,7 @@ // If the target is close and we can reach it in a straight line, // then we'll just go along the straight line instead of computing a path. - if (m_FailedPathComputations != ALTERNATE_PATH_TYPE_ON && TryGoingStraightToTarget(from)) + if (m_FailedMovements != ALTERNATE_PATH_TYPE_ON && TryGoingStraightToTarget(from)) return; // Otherwise we need to compute a path. @@ -1456,10 +1428,10 @@ // Likewise, we want to compile a short-path occasionally when the target is far because we might be stuck // on a navcell surrounded by impassable navcells, but the short-pathfinder could move us out of there. bool shortPath = InShortPathRange(goal, from); - if (m_FailedPathComputations == ALTERNATE_PATH_TYPE_ON) + if (m_FailedMovements == ALTERNATE_PATH_TYPE_ON) { shortPath = !shortPath; - m_FailedPathComputations++; // This makes sure we don't end up stuck in this special state which can break pathing. + m_FailedMovements++; // This makes sure we don't end up stuck in this special state which can break pathing. } if (shortPath) { @@ -1496,9 +1468,7 @@ if (!cmpPathfinder) return; - fixed searchRange = SHORT_PATH_MIN_SEARCH_RANGE + SHORT_PATH_SEARCH_RANGE_INCREMENT * m_FailedPathComputations; - if (searchRange > SHORT_PATH_MAX_SEARCH_RANGE) - searchRange = SHORT_PATH_MAX_SEARCH_RANGE; + entity_pos_t searchRange = ShortPathSearchRange(); m_ExpectedPathTicket.m_Type = Ticket::SHORT_PATH; m_ExpectedPathTicket.m_Ticket = cmpPathfinder->ComputeShortPathAsync(from.X, from.Y, m_Clearance, searchRange, goal, m_PassClass, avoidMovingUnits, GetGroup(), GetEntityId()); @@ -1520,7 +1490,7 @@ return false; m_MoveRequest = request; - m_FailedPathComputations = 0; + m_FailedMovements = 0; m_FollowKnownImperfectPathCountdown = 0; ComputePathToGoal(cmpPosition->GetPosition2D(), goal);