Changeset View
Changeset View
Standalone View
Standalone View
ps/trunk/source/simulation2/components/CCmpUnitMotion.cpp
Show All 40 Lines | |||||
#include "ps/Profile.h" | #include "ps/Profile.h" | ||||
#include "renderer/Scene.h" | #include "renderer/Scene.h" | ||||
// For debugging; units will start going straight to the target | // For debugging; units will start going straight to the target | ||||
// instead of calling the pathfinder | // instead of calling the pathfinder | ||||
#define DISABLE_PATHFINDER 0 | #define DISABLE_PATHFINDER 0 | ||||
/** | /** | ||||
* Min/Max range to restrict short path queries to. (Larger ranges are slower, | |||||
* Min/Max range to restrict short path queries to. (Larger ranges are (much) slower, | * Min/Max range to restrict short path queries to. (Larger ranges are (much) slower, | ||||
* smaller ranges might miss some legitimate routes around large obstacles.) | * 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)/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_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_DELAY = 2; | |||||
/** | /** | ||||
* When using the short-pathfinder to rejoin a long-path waypoint, aim for a circle of this radius around the waypoint. | * When using the short-pathfinder to rejoin a long-path waypoint, aim for a circle of this radius around the waypoint. | ||||
*/ | */ | ||||
static const entity_pos_t SHORT_PATH_LONG_WAYPOINT_RANGE = entity_pos_t::FromInt(TERRAIN_TILE_SIZE*1); | static const entity_pos_t SHORT_PATH_LONG_WAYPOINT_RANGE = entity_pos_t::FromInt(TERRAIN_TILE_SIZE*1); | ||||
/** | /** | ||||
* Minimum distance to goal for a long path request | * Minimum distance to goal for a long path request | ||||
Show All 19 Lines | |||||
* units may easily end up in this state, they still need to adjust to moving units). | * units may easily end up in this state, they still need to adjust to moving units). | ||||
* This is rather arbitrary and mostly for simplicity & optimisation (a better recomputing algorithm | * This is rather arbitrary and mostly for simplicity & optimisation (a better recomputing algorithm | ||||
* would not need this). | * would not need this). | ||||
* Keep in mind that MP turns are currently 500ms. | * Keep in mind that MP turns are currently 500ms. | ||||
*/ | */ | ||||
static const u8 KNOWN_IMPERFECT_PATH_RESET_COUNTDOWN = 12; | 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. | * 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. | * 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, | * TODO: if UnitMotion could send differentiated "unreachable" and "currently stuck" failing messages, | ||||
* this could probably be lowered. | * this could probably be lowered. | ||||
* TODO: when unit pushing is implemented, this number can 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 = 40; | ||||
/** | /** | ||||
* If we have failed path computations this many times and ComputePathToGoal is called, | * When computing paths but failing to move, we want to occasionally alternate pathfinder systems | ||||
* run the opposite path type to what we normally would, to avoid getting stuck sometimes. | * to avoid getting stuck (the short pathfinder can unstuck the long-range one and vice-versa, depending). | ||||
*/ | */ | ||||
static const u8 ALTERNATE_PATH_TYPE_ON = 3; | static const u8 ALTERNATE_PATH_TYPE_DELAY = 3; | ||||
static const u8 ALTERNATE_PATH_TYPE_EVERY = 6; | |||||
static const CColor OVERLAY_COLOR_LONG_PATH(1, 1, 1, 1); | static const CColor OVERLAY_COLOR_LONG_PATH(1, 1, 1, 1); | ||||
static const CColor OVERLAY_COLOR_SHORT_PATH(1, 0, 0, 1); | static const CColor OVERLAY_COLOR_SHORT_PATH(1, 0, 0, 1); | ||||
class CCmpUnitMotion : public ICmpUnitMotion | class CCmpUnitMotion : public ICmpUnitMotion | ||||
{ | { | ||||
public: | public: | ||||
static void ClassInit(CComponentManager& componentManager) | static void ClassInit(CComponentManager& componentManager) | ||||
Show All 24 Lines | public: | ||||
entity_pos_t m_Clearance; | entity_pos_t m_Clearance; | ||||
// cached for efficiency | // cached for efficiency | ||||
fixed m_WalkSpeed, m_RunMultiplier; | fixed m_WalkSpeed, m_RunMultiplier; | ||||
bool m_FacePointAfterMove; | bool m_FacePointAfterMove; | ||||
// Number of path computations that failed (in a row). | // Number of turns since we last managed to move successfully. | ||||
// When this gets above MAX_FAILED_PATH_COMPUTATIONS, inform other components | // See HandleObstructedMove() for more details. | ||||
// that the move will likely fail. | u8 m_FailedMovements = 0; | ||||
u8 m_FailedPathComputations = 0; | |||||
// If > 0, PathingUpdateNeeded returns false always. | // If > 0, PathingUpdateNeeded returns false always. | ||||
// This exists because the goal may be unreachable to the short/long pathfinder. | // This exists because the goal may be unreachable to the short/long pathfinder. | ||||
// In such cases, we would compute inacceptable paths and PathingUpdateNeeded would trigger every turn, | // In such cases, we would compute inacceptable paths and PathingUpdateNeeded would trigger every turn, | ||||
// which would be quite bad for performance. | // which would be quite bad for performance. | ||||
// To avoid that, when we know the new path is imperfect, treat it as OK and follow it anyways. | // To avoid that, when we know the new path is imperfect, treat it as OK and follow it anyways. | ||||
// When reaching the end, we'll go through HandleObstructedMove and reset regardless. | // When reaching the end, we'll go through HandleObstructedMove and reset regardless. | ||||
// To still recompute now and then (the target may be moving), this is a countdown decremented on each frame. | // To still recompute now and then (the target may be moving), this is a countdown decremented on each frame. | ||||
▲ Show 20 Lines • Show All 102 Lines • ▼ Show 20 Lines | public: | ||||
template<typename S> | template<typename S> | ||||
void SerializeCommon(S& serialize) | void SerializeCommon(S& serialize) | ||||
{ | { | ||||
serialize.StringASCII("pass class", m_PassClassName, 0, 64); | serialize.StringASCII("pass class", m_PassClassName, 0, 64); | ||||
serialize.NumberU32_Unbounded("ticket", m_ExpectedPathTicket.m_Ticket); | serialize.NumberU32_Unbounded("ticket", m_ExpectedPathTicket.m_Ticket); | ||||
Serializer(serialize, "ticket type", m_ExpectedPathTicket.m_Type, Ticket::Type::LONG_PATH); | Serializer(serialize, "ticket type", m_ExpectedPathTicket.m_Type, Ticket::Type::LONG_PATH); | ||||
serialize.NumberU8_Unbounded("failed path computations", m_FailedPathComputations); | serialize.NumberU8_Unbounded("failed movements", m_FailedMovements); | ||||
serialize.NumberU8_Unbounded("followknownimperfectpath", m_FollowKnownImperfectPathCountdown); | serialize.NumberU8_Unbounded("followknownimperfectpath", m_FollowKnownImperfectPathCountdown); | ||||
Serializer(serialize, "target type", m_MoveRequest.m_Type, MoveRequest::Type::OFFSET); | Serializer(serialize, "target type", m_MoveRequest.m_Type, MoveRequest::Type::OFFSET); | ||||
serialize.NumberU32_Unbounded("target entity", m_MoveRequest.m_Entity); | serialize.NumberU32_Unbounded("target entity", m_MoveRequest.m_Entity); | ||||
serialize.NumberFixed_Unbounded("target pos x", m_MoveRequest.m_Position.X); | serialize.NumberFixed_Unbounded("target pos x", m_MoveRequest.m_Position.X); | ||||
serialize.NumberFixed_Unbounded("target pos y", m_MoveRequest.m_Position.Y); | serialize.NumberFixed_Unbounded("target pos y", m_MoveRequest.m_Position.Y); | ||||
serialize.NumberFixed_Unbounded("target min range", m_MoveRequest.m_MinRange); | serialize.NumberFixed_Unbounded("target min range", m_MoveRequest.m_MinRange); | ||||
serialize.NumberFixed_Unbounded("target max range", m_MoveRequest.m_MaxRange); | serialize.NumberFixed_Unbounded("target max range", m_MoveRequest.m_MaxRange); | ||||
▲ Show 20 Lines • Show All 280 Lines • ▼ Show 20 Lines | void MoveObstructed() | ||||
if (IsFormationMember() && IsFormationControllerMoving()) | if (IsFormationMember() && IsFormationControllerMoving()) | ||||
return; | return; | ||||
CMessageMotionUpdate msg(CMessageMotionUpdate::OBSTRUCTED); | CMessageMotionUpdate msg(CMessageMotionUpdate::OBSTRUCTED); | ||||
GetSimContext().GetComponentManager().PostMessage(GetEntityId(), msg); | GetSimContext().GetComponentManager().PostMessage(GetEntityId(), msg); | ||||
} | } | ||||
/** | /** | ||||
* 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. | * @returns true if the failure was notified, false otherwise. | ||||
*/ | */ | ||||
bool IncrementFailedPathComputationAndMaybeNotify() | bool IncrementFailedMovementsAndMaybeNotify() | ||||
{ | { | ||||
m_FailedPathComputations++; | m_FailedMovements++; | ||||
if (m_FailedPathComputations >= MAX_FAILED_PATH_COMPUTATIONS) | if (m_FailedMovements >= MAX_FAILED_MOVEMENTS) | ||||
{ | { | ||||
MoveFailed(); | MoveFailed(); | ||||
m_FailedPathComputations = 0; | m_FailedMovements = 0; | ||||
return true; | return true; | ||||
} | } | ||||
return false; | return false; | ||||
} | } | ||||
/** | /** | ||||
* If path would take us farther away from the goal than pos currently is, return false, else return true. | * If path would take us farther away from the goal than pos currently is, return false, else return true. | ||||
*/ | */ | ||||
bool RejectFartherPaths(const PathGoal& goal, const WaypointPath& path, const CFixedVector2D& pos) const; | bool RejectFartherPaths(const PathGoal& goal, const WaypointPath& path, const CFixedVector2D& pos) const; | ||||
/** | bool ShouldAlternatePathfinder() 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(); | return (m_FailedMovements == ALTERNATE_PATH_TYPE_DELAY) || ((MAX_FAILED_MOVEMENTS - ALTERNATE_PATH_TYPE_DELAY) % ALTERNATE_PATH_TYPE_EVERY == 0); | ||||
} | } | ||||
bool InShortPathRange(const PathGoal& goal, const CFixedVector2D& pos) const | bool InShortPathRange(const PathGoal& goal, const CFixedVector2D& pos) const | ||||
{ | { | ||||
return goal.DistanceToPoint(pos) < LONG_PATH_MIN_DIST; | return goal.DistanceToPoint(pos) < LONG_PATH_MIN_DIST; | ||||
} | } | ||||
entity_pos_t ShortPathSearchRange() const | |||||
{ | |||||
u8 multiple = m_FailedMovements < SHORT_PATH_SEARCH_RANGE_INCREASE_DELAY ? 0 : m_FailedMovements - SHORT_PATH_SEARCH_RANGE_INCREASE_DELAY; | |||||
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. | * Handle the result of an asynchronous path query. | ||||
*/ | */ | ||||
void PathResult(u32 ticket, const WaypointPath& path); | void PathResult(u32 ticket, const WaypointPath& path); | ||||
/** | /** | ||||
* Do the per-turn movement and other updates. | * Do the per-turn movement and other updates. | ||||
*/ | */ | ||||
Show All 16 Lines | private: | ||||
/** | /** | ||||
* Update other components on our speed. | * Update other components on our speed. | ||||
* (For performance, this should try to avoid sending messages). | * (For performance, this should try to avoid sending messages). | ||||
*/ | */ | ||||
void UpdateMovementState(entity_pos_t speed); | void UpdateMovementState(entity_pos_t speed); | ||||
/** | /** | ||||
* React if our move was obstructed. | * 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. | * @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. | * Returns true if the target position is valid. False otherwise. | ||||
* (this may indicate that the target is e.g. out of the world/dead). | * (this may indicate that the target is e.g. out of the world/dead). | ||||
* NB: for code-writing convenience, if we have no target, this returns true. | * NB: for code-writing convenience, if we have no target, this returns true. | ||||
*/ | */ | ||||
bool TargetHasValidPosition(const MoveRequest& moveRequest) const; | bool TargetHasValidPosition(const MoveRequest& moveRequest) const; | ||||
bool TargetHasValidPosition() const | bool TargetHasValidPosition() const | ||||
▲ Show 20 Lines • Show All 91 Lines • ▼ Show 20 Lines | |||||
{ | { | ||||
// Ignore obsolete path requests | // Ignore obsolete path requests | ||||
if (ticket != m_ExpectedPathTicket.m_Ticket || m_MoveRequest.m_Type == MoveRequest::NONE) | if (ticket != m_ExpectedPathTicket.m_Ticket || m_MoveRequest.m_Type == MoveRequest::NONE) | ||||
return; | return; | ||||
Ticket::Type ticketType = m_ExpectedPathTicket.m_Type; | Ticket::Type ticketType = m_ExpectedPathTicket.m_Type; | ||||
m_ExpectedPathTicket.clear(); | m_ExpectedPathTicket.clear(); | ||||
// Check that we are still able to do something with that path | // If we not longer have a position, we won't be able to do much. | ||||
// Fail in the next Move() call. | |||||
CmpPtr<ICmpPosition> cmpPosition(GetEntityHandle()); | CmpPtr<ICmpPosition> cmpPosition(GetEntityHandle()); | ||||
if (!cmpPosition || !cmpPosition->IsInWorld()) | if (!cmpPosition || !cmpPosition->IsInWorld()) | ||||
{ | |||||
// We will probably fail to move so inform components but keep on trying anyways. | |||||
MoveFailed(); | |||||
return; | return; | ||||
} | |||||
CFixedVector2D pos = cmpPosition->GetPosition2D(); | CFixedVector2D pos = cmpPosition->GetPosition2D(); | ||||
PathGoal goal; | // Assume all long paths were towards the goal, and assume short paths were if there are no long waypoints. | ||||
// If we can't compute a goal, we'll fail in the next Move() call so do nothing special. | bool pathedTowardsGoal = ticketType == Ticket::LONG_PATH || m_LongPath.m_Waypoints.empty(); | ||||
if (!ComputeGoal(goal, m_MoveRequest)) | |||||
return; | |||||
if (ticketType == Ticket::LONG_PATH) | // Check if we need to run the short-path hack (warning: tricky control flow). | ||||
{ | bool shortPathHack = false; | ||||
if (RejectFartherPaths(goal, path, pos)) | if (path.m_Waypoints.empty()) | ||||
{ | { | ||||
IncrementFailedPathComputationAndMaybeNotify(); | // No waypoints means pathing failed. If this was a long-path, try the short-path hack. | ||||
if (!pathedTowardsGoal) | |||||
return; | return; | ||||
shortPathHack = ticketType == Ticket::LONG_PATH; | |||||
} | } | ||||
else if (PathGoal goal; pathedTowardsGoal && ComputeGoal(goal, m_MoveRequest) && RejectFartherPaths(goal, path, pos)) | |||||
{ | |||||
// 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). | |||||
m_LongPath = path; | // If this was a long-path and we no longer have waypoints, try the short-path hack. | ||||
if (!m_LongPath.m_Waypoints.empty()) | |||||
return; | |||||
shortPathHack = ticketType == Ticket::LONG_PATH; | |||||
} | |||||
m_FollowKnownImperfectPathCountdown = 0; | // Short-path hack: if the long-range pathfinder doesn't find an acceptable path, push a fake waypoint at the goal. | ||||
// This means HandleObstructedMove will use the short-pathfinder to try and reach it, | |||||
// and that may find a path as the vertex pathfinder is more precise. | |||||
if (shortPathHack) | |||||
{ | |||||
// If we're resorting to the short-path hack, the situation is dire. Most likely, the goal is unreachable. | |||||
// We want to find a path or fail fast. Bump failed movements so the short pathfinder will run at max-range | |||||
// right away. This is safe from a performance PoV because it can only happen if the target is unreachable to | |||||
// the long-range pathfinder, which is rare, and since the entity will fail to move if the goal is actually unreachable, | |||||
// the failed movements will be increased to MAX anyways, so just shortcut. | |||||
m_FailedMovements = MAX_FAILED_MOVEMENTS - 2; | |||||
// 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; | CFixedVector2D targetPos; | ||||
if (ComputeTargetPosition(targetPos)) | if (ComputeTargetPosition(targetPos)) | ||||
m_LongPath.m_Waypoints.emplace_back(Waypoint{ targetPos.X, targetPos.Y }); | 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; | return; | ||||
} | } | ||||
if (ticketType == Ticket::LONG_PATH) | |||||
m_LongPath = path; | |||||
else | |||||
m_ShortPath = path; | m_ShortPath = path; | ||||
m_FollowKnownImperfectPathCountdown = 0; | m_FollowKnownImperfectPathCountdown = 0; | ||||
if (!m_ShortPath.m_Waypoints.empty()) | |||||
{ | if (!pathedTowardsGoal) | ||||
return; | |||||
// Performance hack: 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, which can be quite slow. | |||||
// 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 en and try again then. | |||||
// Because we reject farther paths, it works out. | |||||
if (PathingUpdateNeeded(pos)) | if (PathingUpdateNeeded(pos)) | ||||
{ | { | ||||
// Inform other components early, as they might have better behaviour than waiting for the path to carry out. | // 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 | // Send OBSTRUCTED at first - moveFailed is likely to trigger path recomputation and we might end up | ||||
// recomputing too often for nothing. | // recomputing too often for nothing. | ||||
if (!IncrementFailedPathComputationAndMaybeNotify()) | if (!IncrementFailedMovementsAndMaybeNotify()) | ||||
MoveObstructed(); | 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; | m_FollowKnownImperfectPathCountdown = KNOWN_IMPERFECT_PATH_RESET_COUNTDOWN; | ||||
} | } | ||||
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()) | |||||
{ | |||||
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; | |||||
} | |||||
} | |||||
ComputePathToGoal(pos, goal); | |||||
} | } | ||||
void CCmpUnitMotion::Move(fixed dt) | void CCmpUnitMotion::Move(fixed dt) | ||||
{ | { | ||||
PROFILE("Move"); | PROFILE("Move"); | ||||
// If we were idle and will still be, we can return. | // If we were idle and will still be, we can return. | ||||
// TODO: this will need to be removed if pushing is implemented. | // TODO: this will need to be removed if pushing is implemented. | ||||
▲ Show 20 Lines • Show All 47 Lines • ▼ Show 20 Lines | else | ||||
CFixedVector2D offset = pos - initialPos; | CFixedVector2D offset = pos - initialPos; | ||||
angle = atan2_approx(offset.X, offset.Y); | angle = atan2_approx(offset.X, offset.Y); | ||||
cmpPosition->MoveAndTurnTo(pos.X, pos.Y, angle); | cmpPosition->MoveAndTurnTo(pos.X, pos.Y, angle); | ||||
// Calculate the mean speed over this past turn. | // Calculate the mean speed over this past turn. | ||||
UpdateMovementState(offset.Length() / dt); | UpdateMovementState(offset.Length() / dt); | ||||
} | } | ||||
if (wasObstructed && HandleObstructedMove()) | if (wasObstructed && HandleObstructedMove(pos != initialPos)) | ||||
return; | return; | ||||
else if (!wasObstructed) | else if (!wasObstructed && pos != initialPos) | ||||
m_FailedPathComputations = 0; | m_FailedMovements = 0; | ||||
// We may need to recompute our path sometimes (e.g. if our target moves). | // 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. | // Since we request paths asynchronously anyways, this does not need to be done before moving. | ||||
if (!wentStraight && PathingUpdateNeeded(pos)) | if (!wentStraight && PathingUpdateNeeded(pos)) | ||||
{ | { | ||||
PathGoal goal; | PathGoal goal; | ||||
if (ComputeGoal(goal, m_MoveRequest)) | if (ComputeGoal(goal, m_MoveRequest)) | ||||
ComputePathToGoal(pos, goal); | ComputePathToGoal(pos, goal); | ||||
▲ Show 20 Lines • Show All 170 Lines • ▼ Show 20 Lines | void CCmpUnitMotion::UpdateMovementState(entity_pos_t speed) | ||||
} | } | ||||
// Speed change, update the visual actor if necessary. | // Speed change, update the visual actor if necessary. | ||||
else if (speed != m_CurSpeed && cmpVisual) | else if (speed != m_CurSpeed && cmpVisual) | ||||
cmpVisual->SelectMovementAnimation(speed > m_WalkSpeed ? "run" : "walk", speed); | cmpVisual->SelectMovementAnimation(speed > m_WalkSpeed ? "run" : "walk", speed); | ||||
m_CurSpeed = speed; | m_CurSpeed = speed; | ||||
} | } | ||||
bool CCmpUnitMotion::HandleObstructedMove() | bool CCmpUnitMotion::HandleObstructedMove(bool moved) | ||||
{ | { | ||||
CmpPtr<ICmpPosition> cmpPosition(GetEntityHandle()); | CmpPtr<ICmpPosition> cmpPosition(GetEntityHandle()); | ||||
if (!cmpPosition || !cmpPosition->IsInWorld()) | if (!cmpPosition || !cmpPosition->IsInWorld()) | ||||
return false; | return false; | ||||
if (m_FailedPathComputations >= 1) | // We failed to move, inform other components as they might handle it. | ||||
// Inform other components - we might be ordered to stop, and computeGoal will then fail and return early. | // (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(); | MoveObstructed(); | ||||
} | |||||
PathGoal goal; | PathGoal goal; | ||||
if (!ComputeGoal(goal, m_MoveRequest)) | if (!ComputeGoal(goal, m_MoveRequest)) | ||||
return false; | return false; | ||||
// At this point we have a position in the world since ComputeGoal checked for that. | // At this point we have a position in the world since ComputeGoal checked for that. | ||||
CFixedVector2D pos = cmpPosition->GetPosition2D(); | CFixedVector2D pos = cmpPosition->GetPosition2D(); | ||||
if (!InShortPathRange(goal, pos)) | // 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 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 = std::max(ShortPathSearchRange() / 3, fixed::FromInt(TERRAIN_TILE_SIZE*2)); | |||||
if (m_LongPath.m_Waypoints.size() > 1 && | |||||
(pos - CFixedVector2D(m_LongPath.m_Waypoints.back().x, m_LongPath.m_Waypoints.back().z)).CompareLength(skipbeyond) < 0) | |||||
{ | { | ||||
// 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) | |||||
m_LongPath.m_Waypoints.pop_back(); | m_LongPath.m_Waypoints.pop_back(); | ||||
if (!m_LongPath.m_Waypoints.empty()) | } | ||||
else if (ShouldAlternatePathfinder()) | |||||
{ | { | ||||
// Get close enough - this will likely help the short path efficiency, and if we end up taking a wrong way | // Recompute the whole thing occasionally, in case we got stuck in a dead end from removing long waypoints. | ||||
// we'll easily be able to revert it using a long path. | RequestLongPath(pos, goal); | ||||
goal = { PathGoal::CIRCLE, m_LongPath.m_Waypoints.back().x, m_LongPath.m_Waypoints.back().z, ShortPathWaypointRange(m_LongPath) }; | |||||
RequestShortPath(pos, goal, true); | |||||
return true; | return true; | ||||
} | } | ||||
} | |||||
// Else, just entirely recompute. This will ensure we occasionally run a long path so avoid getting stuck | if (m_LongPath.m_Waypoints.empty()) | ||||
// in the short pathfinder, which can happen when an entity is right ober an obstruction's edge. | return false; | ||||
// 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); | ComputePathToGoal(pos, goal); | ||||
// potential TODO: We could switch the short-range pathfinder for something else entirely. | |||||
return true; | return true; | ||||
} | } | ||||
bool CCmpUnitMotion::TargetHasValidPosition(const MoveRequest& moveRequest) const | bool CCmpUnitMotion::TargetHasValidPosition(const MoveRequest& moveRequest) const | ||||
{ | { | ||||
if (moveRequest.m_Type != MoveRequest::ENTITY) | if (moveRequest.m_Type != MoveRequest::ENTITY) | ||||
return true; | return true; | ||||
▲ Show 20 Lines • Show All 328 Lines • ▼ Show 20 Lines | #if DISABLE_PATHFINDER | ||||
m_ShortPath.m_Waypoints.clear(); | m_ShortPath.m_Waypoints.clear(); | ||||
m_ShortPath.m_Waypoints.emplace_back(Waypoint{ goalPos.X, goalPos.Y }); | m_ShortPath.m_Waypoints.emplace_back(Waypoint{ goalPos.X, goalPos.Y }); | ||||
return; | return; | ||||
} | } | ||||
#endif | #endif | ||||
// If the target is close and we can reach it in a straight line, | // 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. | // then we'll just go along the straight line instead of computing a path. | ||||
if (m_FailedPathComputations != ALTERNATE_PATH_TYPE_ON && TryGoingStraightToTarget(from)) | if (!ShouldAlternatePathfinder() && TryGoingStraightToTarget(from)) | ||||
return; | return; | ||||
// Otherwise we need to compute a path. | // Otherwise we need to compute a path. | ||||
// If it's close then just do a short path, not a long path | // If it's close then just do a short path, not a long path | ||||
// TODO: If it's close on the opposite side of a river then we really | // TODO: If it's close on the opposite side of a river then we really | ||||
// need a long path, so we shouldn't simply check linear distance | // need a long path, so we shouldn't simply check linear distance | ||||
// the check is arbitrary but should be a reasonably small distance. | // the check is arbitrary but should be a reasonably small distance. | ||||
// We want to occasionally compute a long path if we're computing short-paths, because the short path domain | // We want to occasionally compute a long path if we're computing short-paths, because the short path domain | ||||
// is bounded and thus it can't around very large static obstacles. | // is bounded and thus it can't around very large static obstacles. | ||||
// Likewise, we want to compile a short-path occasionally when the target is far because we might be stuck | // 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. | // on a navcell surrounded by impassable navcells, but the short-pathfinder could move us out of there. | ||||
bool shortPath = InShortPathRange(goal, from); | bool shortPath = InShortPathRange(goal, from); | ||||
if (m_FailedPathComputations == ALTERNATE_PATH_TYPE_ON) | if (ShouldAlternatePathfinder()) | ||||
{ | |||||
shortPath = !shortPath; | shortPath = !shortPath; | ||||
m_FailedPathComputations++; // This makes sure we don't end up stuck in this special state which can break pathing. | |||||
} | |||||
if (shortPath) | if (shortPath) | ||||
{ | { | ||||
m_LongPath.m_Waypoints.clear(); | m_LongPath.m_Waypoints.clear(); | ||||
RequestShortPath(from, goal, true); | RequestShortPath(from, goal, true); | ||||
} | } | ||||
else | else | ||||
{ | { | ||||
m_ShortPath.m_Waypoints.clear(); | m_ShortPath.m_Waypoints.clear(); | ||||
Show All 19 Lines | |||||
} | } | ||||
void CCmpUnitMotion::RequestShortPath(const CFixedVector2D &from, const PathGoal& goal, bool avoidMovingUnits) | void CCmpUnitMotion::RequestShortPath(const CFixedVector2D &from, const PathGoal& goal, bool avoidMovingUnits) | ||||
{ | { | ||||
CmpPtr<ICmpPathfinder> cmpPathfinder(GetSystemEntity()); | CmpPtr<ICmpPathfinder> cmpPathfinder(GetSystemEntity()); | ||||
if (!cmpPathfinder) | if (!cmpPathfinder) | ||||
return; | return; | ||||
fixed searchRange = SHORT_PATH_MIN_SEARCH_RANGE + SHORT_PATH_SEARCH_RANGE_INCREMENT * m_FailedPathComputations; | entity_pos_t searchRange = ShortPathSearchRange(); | ||||
if (searchRange > SHORT_PATH_MAX_SEARCH_RANGE) | |||||
searchRange = SHORT_PATH_MAX_SEARCH_RANGE; | |||||
m_ExpectedPathTicket.m_Type = Ticket::SHORT_PATH; | 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()); | m_ExpectedPathTicket.m_Ticket = cmpPathfinder->ComputeShortPathAsync(from.X, from.Y, m_Clearance, searchRange, goal, m_PassClass, avoidMovingUnits, GetGroup(), GetEntityId()); | ||||
} | } | ||||
bool CCmpUnitMotion::MoveTo(MoveRequest request) | bool CCmpUnitMotion::MoveTo(MoveRequest request) | ||||
{ | { | ||||
PROFILE("MoveTo"); | PROFILE("MoveTo"); | ||||
if (request.m_MinRange == request.m_MaxRange && !request.m_MinRange.IsZero()) | if (request.m_MinRange == request.m_MaxRange && !request.m_MinRange.IsZero()) | ||||
LOGWARNING("MaxRange must be larger than MinRange; See CCmpUnitMotion.cpp for more information"); | LOGWARNING("MaxRange must be larger than MinRange; See CCmpUnitMotion.cpp for more information"); | ||||
CmpPtr<ICmpPosition> cmpPosition(GetEntityHandle()); | CmpPtr<ICmpPosition> cmpPosition(GetEntityHandle()); | ||||
if (!cmpPosition || !cmpPosition->IsInWorld()) | if (!cmpPosition || !cmpPosition->IsInWorld()) | ||||
return false; | return false; | ||||
PathGoal goal; | PathGoal goal; | ||||
if (!ComputeGoal(goal, request)) | if (!ComputeGoal(goal, request)) | ||||
return false; | return false; | ||||
m_MoveRequest = request; | m_MoveRequest = request; | ||||
m_FailedPathComputations = 0; | m_FailedMovements = 0; | ||||
m_FollowKnownImperfectPathCountdown = 0; | m_FollowKnownImperfectPathCountdown = 0; | ||||
ComputePathToGoal(cmpPosition->GetPosition2D(), goal); | ComputePathToGoal(cmpPosition->GetPosition2D(), goal); | ||||
return true; | return true; | ||||
} | } | ||||
bool CCmpUnitMotion::IsTargetRangeReachable(entity_id_t target, entity_pos_t minRange, entity_pos_t maxRange) | bool CCmpUnitMotion::IsTargetRangeReachable(entity_id_t target, entity_pos_t minRange, entity_pos_t maxRange) | ||||
{ | { | ||||
▲ Show 20 Lines • Show All 58 Lines • Show Last 20 Lines |
Wildfire Games · Phabricator