Line data Source code
1 : /* Copyright (C) 2022 Wildfire Games.
2 : * This file is part of 0 A.D.
3 : *
4 : * 0 A.D. is free software: you can redistribute it and/or modify
5 : * it under the terms of the GNU General Public License as published by
6 : * the Free Software Foundation, either version 2 of the License, or
7 : * (at your option) any later version.
8 : *
9 : * 0 A.D. is distributed in the hope that it will be useful,
10 : * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 : * GNU General Public License for more details.
13 : *
14 : * You should have received a copy of the GNU General Public License
15 : * along with 0 A.D. If not, see <http://www.gnu.org/licenses/>.
16 : */
17 :
18 : #ifndef INCLUDED_CCMPUNITMOTION
19 : #define INCLUDED_CCMPUNITMOTION
20 :
21 : #include "simulation2/system/Component.h"
22 : #include "ICmpUnitMotion.h"
23 :
24 : #include "simulation2/components/CCmpUnitMotionManager.h"
25 : #include "simulation2/components/ICmpObstruction.h"
26 : #include "simulation2/components/ICmpObstructionManager.h"
27 : #include "simulation2/components/ICmpOwnership.h"
28 : #include "simulation2/components/ICmpPosition.h"
29 : #include "simulation2/components/ICmpPathfinder.h"
30 : #include "simulation2/components/ICmpRangeManager.h"
31 : #include "simulation2/components/ICmpValueModificationManager.h"
32 : #include "simulation2/components/ICmpVisual.h"
33 : #include "simulation2/helpers/Geometry.h"
34 : #include "simulation2/helpers/Render.h"
35 : #include "simulation2/MessageTypes.h"
36 : #include "simulation2/serialization/SerializedPathfinder.h"
37 : #include "simulation2/serialization/SerializedTypes.h"
38 :
39 : #include "graphics/Overlay.h"
40 : #include "maths/FixedVector2D.h"
41 : #include "ps/CLogger.h"
42 : #include "ps/Profile.h"
43 : #include "renderer/Scene.h"
44 :
45 : #include <algorithm>
46 :
47 : // NB: this implementation of ICmpUnitMotion is very tightly coupled with UnitMotionManager.
48 : // As such, both are compiled in the same TU.
49 :
50 : // For debugging; units will start going straight to the target
51 : // instead of calling the pathfinder
52 : #define DISABLE_PATHFINDER 0
53 :
54 : namespace
55 : {
56 : /**
57 : * Min/Max range to restrict short path queries to. (Larger ranges are (much) slower,
58 : * smaller ranges might miss some legitimate routes around large obstacles.)
59 : * NB: keep the max-range in sync with the vertex pathfinder "move the search space" heuristic.
60 : */
61 : constexpr entity_pos_t SHORT_PATH_MIN_SEARCH_RANGE = entity_pos_t::FromInt(12 * Pathfinding::NAVCELL_SIZE_INT);
62 : constexpr entity_pos_t SHORT_PATH_MAX_SEARCH_RANGE = entity_pos_t::FromInt(56 * Pathfinding::NAVCELL_SIZE_INT);
63 : constexpr entity_pos_t SHORT_PATH_SEARCH_RANGE_INCREMENT = entity_pos_t::FromInt(4 * Pathfinding::NAVCELL_SIZE_INT);
64 : constexpr u8 SHORT_PATH_SEARCH_RANGE_INCREASE_DELAY = 1;
65 :
66 : /**
67 : * When using the short-pathfinder to rejoin a long-path waypoint, aim for a circle of this radius around the waypoint.
68 : */
69 : constexpr entity_pos_t SHORT_PATH_LONG_WAYPOINT_RANGE = entity_pos_t::FromInt(4 * Pathfinding::NAVCELL_SIZE_INT);
70 :
71 : /**
72 : * Minimum distance to goal for a long path request
73 : */
74 : constexpr entity_pos_t LONG_PATH_MIN_DIST = entity_pos_t::FromInt(16 * Pathfinding::NAVCELL_SIZE_INT);
75 :
76 : /**
77 : * If we are this close to our target entity/point, then think about heading
78 : * for it in a straight line instead of pathfinding.
79 : */
80 : constexpr entity_pos_t DIRECT_PATH_RANGE = entity_pos_t::FromInt(24 * Pathfinding::NAVCELL_SIZE_INT);
81 :
82 : /**
83 : * To avoid recomputing paths too often, have some leeway for target range checks
84 : * based on our distance to the target. Increase that incertainty by one navcell
85 : * for every this many tiles of distance.
86 : */
87 : constexpr entity_pos_t TARGET_UNCERTAINTY_MULTIPLIER = entity_pos_t::FromInt(8 * Pathfinding::NAVCELL_SIZE_INT);
88 :
89 : /**
90 : * When following a known imperfect path (i.e. a path that won't take us in range of our goal
91 : * we still recompute a new path every N turn to adapt to moving targets (for example, ships that must pickup
92 : * units may easily end up in this state, they still need to adjust to moving units).
93 : * This is rather arbitrary and mostly for simplicity & optimisation (a better recomputing algorithm
94 : * would not need this).
95 : */
96 : constexpr u8 KNOWN_IMPERFECT_PATH_RESET_COUNTDOWN = 12;
97 :
98 : /**
99 : * When we fail to move this many turns in a row, inform other components that the move will fail.
100 : * Experimentally, this number needs to be somewhat high or moving groups of units will lead to stuck units.
101 : * However, too high means units will look idle for a long time when they are failing to move.
102 : * TODO: if UnitMotion could send differentiated "unreachable" and "currently stuck" failing messages,
103 : * this could probably be lowered.
104 : * TODO: when unit pushing is implemented, this number can probably be lowered.
105 : */
106 : constexpr u8 MAX_FAILED_MOVEMENTS = 35;
107 :
108 : /**
109 : * When computing paths but failing to move, we want to occasionally alternate pathfinder systems
110 : * to avoid getting stuck (the short pathfinder can unstuck the long-range one and vice-versa, depending).
111 : */
112 : constexpr u8 ALTERNATE_PATH_TYPE_DELAY = 3;
113 : constexpr u8 ALTERNATE_PATH_TYPE_EVERY = 6;
114 :
115 : /**
116 : * Units can occasionally get stuck near corners. The cause is a mismatch between CheckMovement and the short pathfinder.
117 : * The problem is the short pathfinder finds an impassable path when units are right on an obstruction edge.
118 : * Fixing this math mismatch is perhaps possible, but fixing it in UM is rather easy: just try backing up a bit
119 : * and that will probably un-stuck the unit. This is the 'failed movement' turn on which to try that.
120 : */
121 : constexpr u8 BACKUP_HACK_DELAY = 10;
122 :
123 : /**
124 : * After this many failed computations, start sending "VERY_OBSTRUCTED" messages instead.
125 : * Should probably be larger than ALTERNATE_PATH_TYPE_DELAY.
126 : */
127 : constexpr u8 VERY_OBSTRUCTED_THRESHOLD = 10;
128 :
129 1 : const CColor OVERLAY_COLOR_LONG_PATH(1, 1, 1, 1);
130 1 : const CColor OVERLAY_COLOR_SHORT_PATH(1, 0, 0, 1);
131 : } // anonymous namespace
132 :
133 0 : class CCmpUnitMotion final : public ICmpUnitMotion
134 : {
135 : friend class CCmpUnitMotionManager;
136 : public:
137 116 : static void ClassInit(CComponentManager& componentManager)
138 : {
139 116 : componentManager.SubscribeToMessageType(MT_Create);
140 116 : componentManager.SubscribeToMessageType(MT_Destroy);
141 116 : componentManager.SubscribeToMessageType(MT_PathResult);
142 116 : componentManager.SubscribeToMessageType(MT_OwnershipChanged);
143 116 : componentManager.SubscribeToMessageType(MT_ValueModification);
144 116 : componentManager.SubscribeToMessageType(MT_MovementObstructionChanged);
145 116 : componentManager.SubscribeToMessageType(MT_Deserialized);
146 116 : }
147 :
148 0 : DEFAULT_COMPONENT_ALLOCATOR(UnitMotion)
149 :
150 : bool m_DebugOverlayEnabled;
151 : std::vector<SOverlayLine> m_DebugOverlayLongPathLines;
152 : std::vector<SOverlayLine> m_DebugOverlayShortPathLines;
153 :
154 : // Template state:
155 :
156 : bool m_IsFormationController;
157 :
158 : fixed m_TemplateWalkSpeed, m_TemplateRunMultiplier, m_TemplateAcceleration, m_TemplateWeight;
159 : pass_class_t m_PassClass;
160 : std::string m_PassClassName;
161 :
162 : // Dynamic state:
163 :
164 : entity_pos_t m_Clearance;
165 :
166 : // cached for efficiency
167 : fixed m_WalkSpeed, m_RunMultiplier;
168 :
169 : bool m_FacePointAfterMove;
170 :
171 : // Whether the unit participates in pushing.
172 : bool m_Pushing = false;
173 :
174 : // Whether the unit blocks movement (& is blocked by movement blockers)
175 : // Cached from ICmpObstruction.
176 : bool m_BlockMovement = false;
177 :
178 : // Internal counter used when recovering from obstructed movement.
179 : // Most notably, increases the search range of the vertex pathfinder.
180 : // See HandleObstructedMove() for more details.
181 : u8 m_FailedMovements = 0;
182 :
183 : // If > 0, PathingUpdateNeeded returns false always.
184 : // This exists because the goal may be unreachable to the short/long pathfinder.
185 : // In such cases, we would compute inacceptable paths and PathingUpdateNeeded would trigger every turn,
186 : // which would be quite bad for performance.
187 : // To avoid that, when we know the new path is imperfect, treat it as OK and follow it anyways.
188 : // When reaching the end, we'll go through HandleObstructedMove and reset regardless.
189 : // To still recompute now and then (the target may be moving), this is a countdown decremented on each frame.
190 : u8 m_FollowKnownImperfectPathCountdown = 0;
191 :
192 0 : struct Ticket {
193 : u32 m_Ticket = 0; // asynchronous request ID we're waiting for, or 0 if none
194 : enum Type {
195 : SHORT_PATH,
196 : LONG_PATH
197 : } m_Type = SHORT_PATH; // Pick some default value to avoid UB.
198 :
199 0 : void clear() { m_Ticket = 0; }
200 : } m_ExpectedPathTicket;
201 :
202 : struct MoveRequest {
203 : enum Type {
204 : NONE,
205 : POINT,
206 : ENTITY,
207 : OFFSET
208 : } m_Type = NONE;
209 : entity_id_t m_Entity = INVALID_ENTITY;
210 : CFixedVector2D m_Position;
211 : entity_pos_t m_MinRange, m_MaxRange;
212 :
213 : // For readability
214 0 : CFixedVector2D GetOffset() const { return m_Position; };
215 :
216 0 : MoveRequest() = default;
217 0 : MoveRequest(CFixedVector2D pos, entity_pos_t minRange, entity_pos_t maxRange) : m_Type(POINT), m_Position(pos), m_MinRange(minRange), m_MaxRange(maxRange) {};
218 0 : MoveRequest(entity_id_t target, entity_pos_t minRange, entity_pos_t maxRange) : m_Type(ENTITY), m_Entity(target), m_MinRange(minRange), m_MaxRange(maxRange) {};
219 0 : MoveRequest(entity_id_t target, CFixedVector2D offset) : m_Type(OFFSET), m_Entity(target), m_Position(offset) {};
220 : } m_MoveRequest;
221 :
222 : // If this is not INVALID_ENTITY, the unit is a formation member.
223 : entity_id_t m_FormationController = INVALID_ENTITY;
224 :
225 : // If the entity moves, it will do so at m_WalkSpeed * m_SpeedMultiplier.
226 : fixed m_SpeedMultiplier;
227 : // This caches the resulting speed from m_WalkSpeed * m_SpeedMultiplier for convenience.
228 : fixed m_Speed;
229 :
230 : // Mean speed over the last turn.
231 : fixed m_LastTurnSpeed;
232 :
233 : // The speed achieved at the end of the current turn.
234 : fixed m_CurrentSpeed;
235 :
236 : fixed m_InstantTurnAngle;
237 :
238 : fixed m_Acceleration;
239 :
240 : // Currently active paths (storing waypoints in reverse order).
241 : // The last item in each path is the point we're currently heading towards.
242 : WaypointPath m_LongPath;
243 : WaypointPath m_ShortPath;
244 :
245 116 : static std::string GetSchema()
246 : {
247 : return
248 : "<a:help>Provides the unit with the ability to move around the world by itself.</a:help>"
249 : "<a:example>"
250 : "<WalkSpeed>7.0</WalkSpeed>"
251 : "<PassabilityClass>default</PassabilityClass>"
252 : "</a:example>"
253 : "<element name='FormationController'>"
254 : "<data type='boolean'/>"
255 : "</element>"
256 : "<element name='WalkSpeed' a:help='Basic movement speed (in metres per second).'>"
257 : "<ref name='positiveDecimal'/>"
258 : "</element>"
259 : "<optional>"
260 : "<element name='RunMultiplier' a:help='How much faster the unit goes when running (as a multiple of walk speed).'>"
261 : "<ref name='positiveDecimal'/>"
262 : "</element>"
263 : "</optional>"
264 : "<element name='InstantTurnAngle' a:help='Angle we can turn instantly. Any value greater than pi will disable turning times. Avoid zero since it stops the entity every turn.'>"
265 : "<ref name='positiveDecimal'/>"
266 : "</element>"
267 : "<element name='Acceleration' a:help='Acceleration (in metres per second^2).'>"
268 : "<ref name='positiveDecimal'/>"
269 : "</element>"
270 : "<element name='PassabilityClass' a:help='Identifies the terrain passability class (values are defined in special/pathfinder.xml).'>"
271 : "<text/>"
272 : "</element>"
273 : "<element name='Weight' a:help='Makes this unit both push harder and harder to push. 10 is considered the base value.'>"
274 : "<ref name='positiveDecimal'/>"
275 : "</element>"
276 : "<optional>"
277 : "<element name='DisablePushing'>"
278 : "<data type='boolean'/>"
279 : "</element>"
280 116 : "</optional>";
281 : }
282 :
283 0 : void Init(const CParamNode& paramNode) override
284 : {
285 0 : m_IsFormationController = paramNode.GetChild("FormationController").ToBool();
286 :
287 0 : m_FacePointAfterMove = true;
288 :
289 0 : m_WalkSpeed = m_TemplateWalkSpeed = m_Speed = paramNode.GetChild("WalkSpeed").ToFixed();
290 0 : m_SpeedMultiplier = fixed::FromInt(1);
291 0 : m_LastTurnSpeed = m_CurrentSpeed = fixed::Zero();
292 :
293 0 : m_RunMultiplier = m_TemplateRunMultiplier = fixed::FromInt(1);
294 0 : if (paramNode.GetChild("RunMultiplier").IsOk())
295 0 : m_RunMultiplier = m_TemplateRunMultiplier = paramNode.GetChild("RunMultiplier").ToFixed();
296 :
297 0 : m_InstantTurnAngle = paramNode.GetChild("InstantTurnAngle").ToFixed();
298 :
299 0 : m_Acceleration = m_TemplateAcceleration = paramNode.GetChild("Acceleration").ToFixed();
300 :
301 0 : m_TemplateWeight = paramNode.GetChild("Weight").ToFixed();
302 :
303 0 : m_PassClassName = paramNode.GetChild("PassabilityClass").ToString();
304 0 : SetPassabilityData(m_PassClassName);
305 :
306 0 : CmpPtr<ICmpObstruction> cmpObstruction(GetEntityHandle());
307 0 : if (cmpObstruction)
308 0 : m_BlockMovement = cmpObstruction->GetBlockMovementFlag(true);
309 :
310 0 : SetParticipateInPushing(!paramNode.GetChild("DisablePushing").IsOk() || !paramNode.GetChild("DisablePushing").ToBool());
311 :
312 0 : m_DebugOverlayEnabled = false;
313 0 : }
314 :
315 0 : void Deinit() override
316 : {
317 0 : }
318 :
319 : template<typename S>
320 0 : void SerializeCommon(S& serialize)
321 : {
322 : // m_Clearance and m_PassClass are constructed from this.
323 0 : serialize.StringASCII("pass class", m_PassClassName, 0, 64);
324 :
325 0 : serialize.NumberU32_Unbounded("ticket", m_ExpectedPathTicket.m_Ticket);
326 0 : Serializer(serialize, "ticket type", m_ExpectedPathTicket.m_Type, Ticket::Type::LONG_PATH);
327 :
328 0 : serialize.NumberU8_Unbounded("failed movements", m_FailedMovements);
329 0 : serialize.NumberU8_Unbounded("followknownimperfectpath", m_FollowKnownImperfectPathCountdown);
330 :
331 0 : Serializer(serialize, "target type", m_MoveRequest.m_Type, MoveRequest::Type::OFFSET);
332 0 : serialize.NumberU32_Unbounded("target entity", m_MoveRequest.m_Entity);
333 0 : serialize.NumberFixed_Unbounded("target pos x", m_MoveRequest.m_Position.X);
334 0 : serialize.NumberFixed_Unbounded("target pos y", m_MoveRequest.m_Position.Y);
335 0 : serialize.NumberFixed_Unbounded("target min range", m_MoveRequest.m_MinRange);
336 0 : serialize.NumberFixed_Unbounded("target max range", m_MoveRequest.m_MaxRange);
337 :
338 0 : serialize.NumberU32_Unbounded("formation controller", m_FormationController);
339 :
340 0 : serialize.NumberFixed_Unbounded("speed multiplier", m_SpeedMultiplier);
341 :
342 0 : serialize.NumberFixed_Unbounded("last turn speed", m_LastTurnSpeed);
343 0 : serialize.NumberFixed_Unbounded("current speed", m_CurrentSpeed);
344 :
345 0 : serialize.NumberFixed_Unbounded("instant turn angle", m_InstantTurnAngle);
346 :
347 0 : serialize.NumberFixed_Unbounded("acceleration", m_Acceleration);
348 :
349 0 : serialize.Bool("facePointAfterMove", m_FacePointAfterMove);
350 0 : serialize.Bool("pushing", m_Pushing);
351 :
352 0 : Serializer(serialize, "long path", m_LongPath.m_Waypoints);
353 0 : Serializer(serialize, "short path", m_ShortPath.m_Waypoints);
354 0 : }
355 :
356 0 : void Serialize(ISerializer& serialize) override
357 : {
358 0 : SerializeCommon(serialize);
359 0 : }
360 :
361 0 : void Deserialize(const CParamNode& paramNode, IDeserializer& deserialize) override
362 : {
363 0 : Init(paramNode);
364 :
365 0 : SerializeCommon(deserialize);
366 :
367 0 : SetPassabilityData(m_PassClassName);
368 :
369 0 : CmpPtr<ICmpObstruction> cmpObstruction(GetEntityHandle());
370 0 : if (cmpObstruction)
371 0 : m_BlockMovement = cmpObstruction->GetBlockMovementFlag(false);
372 0 : }
373 :
374 0 : void HandleMessage(const CMessage& msg, bool UNUSED(global)) override
375 : {
376 0 : switch (msg.GetType())
377 : {
378 0 : case MT_RenderSubmit:
379 : {
380 0 : PROFILE("UnitMotion::RenderSubmit");
381 0 : const CMessageRenderSubmit& msgData = static_cast<const CMessageRenderSubmit&> (msg);
382 0 : RenderSubmit(msgData.collector);
383 0 : break;
384 : }
385 0 : case MT_PathResult:
386 : {
387 0 : const CMessagePathResult& msgData = static_cast<const CMessagePathResult&> (msg);
388 0 : PathResult(msgData.ticket, msgData.path);
389 0 : break;
390 : }
391 0 : case MT_Create:
392 : {
393 0 : if (!ENTITY_IS_LOCAL(GetEntityId()))
394 0 : CmpPtr<ICmpUnitMotionManager>(GetSystemEntity())->Register(this, GetEntityId(), m_IsFormationController);
395 0 : break;
396 : }
397 0 : case MT_Destroy:
398 : {
399 0 : if (!ENTITY_IS_LOCAL(GetEntityId()))
400 0 : CmpPtr<ICmpUnitMotionManager>(GetSystemEntity())->Unregister(GetEntityId());
401 0 : break;
402 : }
403 0 : case MT_MovementObstructionChanged:
404 : {
405 0 : CmpPtr<ICmpObstruction> cmpObstruction(GetEntityHandle());
406 0 : if (cmpObstruction)
407 0 : m_BlockMovement = cmpObstruction->GetBlockMovementFlag(false);
408 0 : break;
409 : }
410 0 : case MT_ValueModification:
411 : {
412 0 : const CMessageValueModification& msgData = static_cast<const CMessageValueModification&> (msg);
413 0 : if (msgData.component != L"UnitMotion")
414 0 : break;
415 : FALLTHROUGH;
416 : }
417 : case MT_OwnershipChanged:
418 : {
419 0 : OnValueModification();
420 0 : break;
421 : }
422 0 : case MT_Deserialized:
423 : {
424 0 : OnValueModification();
425 0 : break;
426 : }
427 : }
428 0 : }
429 :
430 0 : void UpdateMessageSubscriptions()
431 : {
432 0 : bool needRender = m_DebugOverlayEnabled;
433 0 : GetSimContext().GetComponentManager().DynamicSubscriptionNonsync(MT_RenderSubmit, this, needRender);
434 0 : }
435 :
436 0 : bool IsMoveRequested() const override
437 : {
438 0 : return m_MoveRequest.m_Type != MoveRequest::NONE;
439 : }
440 :
441 0 : fixed GetSpeedMultiplier() const override
442 : {
443 0 : return m_SpeedMultiplier;
444 : }
445 :
446 0 : void SetSpeedMultiplier(fixed multiplier) override
447 : {
448 0 : m_SpeedMultiplier = std::min(multiplier, m_RunMultiplier);
449 0 : m_Speed = m_SpeedMultiplier.Multiply(GetWalkSpeed());
450 0 : }
451 :
452 0 : fixed GetSpeed() const override
453 : {
454 0 : return m_Speed;
455 : }
456 :
457 0 : fixed GetWalkSpeed() const override
458 : {
459 0 : return m_WalkSpeed;
460 : }
461 :
462 0 : fixed GetRunMultiplier() const override
463 : {
464 0 : return m_RunMultiplier;
465 : }
466 :
467 0 : CFixedVector2D EstimateFuturePosition(const fixed dt) const override
468 : {
469 0 : CmpPtr<ICmpPosition> cmpPosition(GetEntityHandle());
470 0 : if (!cmpPosition || !cmpPosition->IsInWorld())
471 0 : return CFixedVector2D();
472 :
473 : // TODO: formation members should perhaps try to use the controller's position.
474 :
475 0 : CFixedVector2D pos = cmpPosition->GetPosition2D();
476 0 : entity_angle_t angle = cmpPosition->GetRotation().Y;
477 0 : fixed speed = m_CurrentSpeed;
478 : // Copy the path so we don't change it.
479 0 : WaypointPath shortPath = m_ShortPath;
480 0 : WaypointPath longPath = m_LongPath;
481 :
482 0 : PerformMove(dt, cmpPosition->GetTurnRate(), shortPath, longPath, pos, speed, angle, 0);
483 0 : return pos;
484 : }
485 :
486 0 : fixed GetAcceleration() const override
487 : {
488 0 : return m_Acceleration;
489 : }
490 :
491 0 : void SetAcceleration(fixed acceleration) override
492 : {
493 0 : m_Acceleration = acceleration;
494 0 : }
495 :
496 0 : virtual entity_pos_t GetWeight() const
497 : {
498 0 : return m_TemplateWeight;
499 : }
500 :
501 0 : pass_class_t GetPassabilityClass() const override
502 : {
503 0 : return m_PassClass;
504 : }
505 :
506 0 : std::string GetPassabilityClassName() const override
507 : {
508 0 : return m_PassClassName;
509 : }
510 :
511 0 : void SetPassabilityClassName(const std::string& passClassName) override
512 : {
513 0 : if (!m_IsFormationController)
514 : {
515 0 : LOGWARNING("Only formation controllers can change their passability class");
516 0 : return;
517 : }
518 0 : SetPassabilityData(passClassName);
519 : }
520 :
521 0 : fixed GetCurrentSpeed() const override
522 : {
523 0 : return m_CurrentSpeed;
524 : }
525 :
526 0 : void SetFacePointAfterMove(bool facePointAfterMove) override
527 : {
528 0 : m_FacePointAfterMove = facePointAfterMove;
529 0 : }
530 :
531 0 : bool GetFacePointAfterMove() const override
532 : {
533 0 : return m_FacePointAfterMove;
534 : }
535 :
536 0 : void SetDebugOverlay(bool enabled) override
537 : {
538 0 : m_DebugOverlayEnabled = enabled;
539 0 : UpdateMessageSubscriptions();
540 0 : }
541 :
542 0 : bool MoveToPointRange(entity_pos_t x, entity_pos_t z, entity_pos_t minRange, entity_pos_t maxRange) override
543 : {
544 0 : return MoveTo(MoveRequest(CFixedVector2D(x, z), minRange, maxRange));
545 : }
546 :
547 0 : bool MoveToTargetRange(entity_id_t target, entity_pos_t minRange, entity_pos_t maxRange) override
548 : {
549 0 : return MoveTo(MoveRequest(target, minRange, maxRange));
550 : }
551 :
552 0 : void MoveToFormationOffset(entity_id_t controller, entity_pos_t x, entity_pos_t z) override
553 : {
554 : // Pass the controller to the move request anyways.
555 0 : MoveTo(MoveRequest(controller, CFixedVector2D(x, z)));
556 0 : }
557 :
558 0 : void SetMemberOfFormation(entity_id_t controller) override
559 : {
560 0 : m_FormationController = controller;
561 0 : }
562 :
563 : bool IsTargetRangeReachable(entity_id_t target, entity_pos_t minRange, entity_pos_t maxRange) override;
564 :
565 : void FaceTowardsPoint(entity_pos_t x, entity_pos_t z) override;
566 :
567 : /**
568 : * Clears the current MoveRequest - the unit will stop and no longer try and move.
569 : * This should never be called from UnitMotion, since MoveToX orders are given
570 : * by other components - these components should also decide when to stop.
571 : */
572 0 : void StopMoving() override
573 : {
574 0 : if (m_FacePointAfterMove)
575 : {
576 0 : CmpPtr<ICmpPosition> cmpPosition(GetEntityHandle());
577 0 : if (cmpPosition && cmpPosition->IsInWorld())
578 : {
579 0 : CFixedVector2D targetPos;
580 0 : if (ComputeTargetPosition(targetPos))
581 0 : FaceTowardsPointFromPos(cmpPosition->GetPosition2D(), targetPos.X, targetPos.Y);
582 : }
583 : }
584 :
585 0 : m_MoveRequest = MoveRequest();
586 0 : m_ExpectedPathTicket.clear();
587 0 : m_LongPath.m_Waypoints.clear();
588 0 : m_ShortPath.m_Waypoints.clear();
589 0 : }
590 :
591 0 : entity_pos_t GetUnitClearance() const override
592 : {
593 0 : return m_Clearance;
594 : }
595 :
596 : private:
597 0 : bool IsFormationMember() const
598 : {
599 0 : return m_FormationController != INVALID_ENTITY;
600 : }
601 :
602 0 : bool IsMovingAsFormation() const
603 : {
604 0 : return IsFormationMember() && m_MoveRequest.m_Type == MoveRequest::OFFSET;
605 : }
606 :
607 0 : bool IsFormationControllerMoving() const
608 : {
609 0 : CmpPtr<ICmpUnitMotion> cmpControllerMotion(GetSimContext(), m_FormationController);
610 0 : return cmpControllerMotion && cmpControllerMotion->IsMoveRequested();
611 : }
612 :
613 0 : entity_id_t GetGroup() const
614 : {
615 0 : return IsFormationMember() ? m_FormationController : GetEntityId();
616 : }
617 :
618 0 : void SetParticipateInPushing(bool pushing)
619 : {
620 0 : CmpPtr<ICmpUnitMotionManager> cmpUnitMotionManager(GetSystemEntity());
621 0 : m_Pushing = pushing && cmpUnitMotionManager->IsPushingActivated();
622 0 : }
623 :
624 0 : void SetPassabilityData(const std::string& passClassName)
625 : {
626 0 : m_PassClassName = passClassName;
627 0 : CmpPtr<ICmpPathfinder> cmpPathfinder(GetSystemEntity());
628 0 : if (cmpPathfinder)
629 : {
630 0 : m_PassClass = cmpPathfinder->GetPassabilityClass(passClassName);
631 0 : m_Clearance = cmpPathfinder->GetClearance(m_PassClass);
632 :
633 0 : CmpPtr<ICmpObstruction> cmpObstruction(GetEntityHandle());
634 0 : if (cmpObstruction)
635 0 : cmpObstruction->SetUnitClearance(m_Clearance);
636 : }
637 0 : }
638 :
639 : /**
640 : * Warns other components that our current movement will likely fail (e.g. we won't be able to reach our target)
641 : * This should only be called before the actual movement in a given turn, or units might both move and try to do things
642 : * on the same turn, leading to gliding units.
643 : */
644 0 : void MoveFailed()
645 : {
646 : // Don't notify if we are a formation member in a moving formation - we can occasionally be stuck for a long time
647 : // if our current offset is unreachable, but we don't want to end up stuck.
648 : // (If the formation controller has stopped moving however, we can safely message).
649 0 : if (IsFormationMember() && IsFormationControllerMoving())
650 0 : return;
651 :
652 0 : CMessageMotionUpdate msg(CMessageMotionUpdate::LIKELY_FAILURE);
653 0 : GetSimContext().GetComponentManager().PostMessage(GetEntityId(), msg);
654 : }
655 :
656 : /**
657 : * Warns other components that our current movement is likely over (i.e. we probably reached our destination)
658 : * This should only be called before the actual movement in a given turn, or units might both move and try to do things
659 : * on the same turn, leading to gliding units.
660 : */
661 0 : void MoveSucceeded()
662 : {
663 : // Don't notify if we are a formation member in a moving formation - we can occasionally be stuck for a long time
664 : // if our current offset is unreachable, but we don't want to end up stuck.
665 : // (If the formation controller has stopped moving however, we can safely message).
666 0 : if (IsFormationMember() && IsFormationControllerMoving())
667 0 : return;
668 :
669 0 : CMessageMotionUpdate msg(CMessageMotionUpdate::LIKELY_SUCCESS);
670 0 : GetSimContext().GetComponentManager().PostMessage(GetEntityId(), msg);
671 : }
672 :
673 : /**
674 : * Warns other components that our current movement was obstructed (i.e. we failed to move this turn).
675 : * This should only be called before the actual movement in a given turn, or units might both move and try to do things
676 : * on the same turn, leading to gliding units.
677 : */
678 0 : void MoveObstructed()
679 : {
680 : // Don't notify if we are a formation member in a moving formation - we can occasionally be stuck for a long time
681 : // if our current offset is unreachable, but we don't want to end up stuck.
682 : // (If the formation controller has stopped moving however, we can safely message).
683 0 : if (IsFormationMember() && IsFormationControllerMoving())
684 0 : return;
685 :
686 0 : CMessageMotionUpdate msg(m_FailedMovements >= VERY_OBSTRUCTED_THRESHOLD ?
687 0 : CMessageMotionUpdate::VERY_OBSTRUCTED : CMessageMotionUpdate::OBSTRUCTED);
688 0 : GetSimContext().GetComponentManager().PostMessage(GetEntityId(), msg);
689 : }
690 :
691 : /**
692 : * Increment the number of failed movements and notify other components if required.
693 : * @returns true if the failure was notified, false otherwise.
694 : */
695 0 : bool IncrementFailedMovementsAndMaybeNotify()
696 : {
697 0 : m_FailedMovements++;
698 0 : if (m_FailedMovements >= MAX_FAILED_MOVEMENTS)
699 : {
700 0 : MoveFailed();
701 0 : m_FailedMovements = 0;
702 0 : return true;
703 : }
704 0 : return false;
705 : }
706 :
707 : /**
708 : * If path would take us farther away from the goal than pos currently is, return false, else return true.
709 : */
710 : bool RejectFartherPaths(const PathGoal& goal, const WaypointPath& path, const CFixedVector2D& pos) const;
711 :
712 0 : bool ShouldAlternatePathfinder() const
713 : {
714 0 : return (m_FailedMovements == ALTERNATE_PATH_TYPE_DELAY) || ((MAX_FAILED_MOVEMENTS - ALTERNATE_PATH_TYPE_DELAY) % ALTERNATE_PATH_TYPE_EVERY == 0);
715 : }
716 :
717 0 : bool InShortPathRange(const PathGoal& goal, const CFixedVector2D& pos) const
718 : {
719 0 : return goal.DistanceToPoint(pos) < LONG_PATH_MIN_DIST;
720 : }
721 :
722 0 : entity_pos_t ShortPathSearchRange() const
723 : {
724 0 : u8 multiple = m_FailedMovements < SHORT_PATH_SEARCH_RANGE_INCREASE_DELAY ? 0 : m_FailedMovements - SHORT_PATH_SEARCH_RANGE_INCREASE_DELAY;
725 0 : fixed searchRange = SHORT_PATH_MIN_SEARCH_RANGE + SHORT_PATH_SEARCH_RANGE_INCREMENT * multiple;
726 0 : if (searchRange > SHORT_PATH_MAX_SEARCH_RANGE)
727 0 : searchRange = SHORT_PATH_MAX_SEARCH_RANGE;
728 0 : return searchRange;
729 : }
730 :
731 : /**
732 : * Handle the result of an asynchronous path query.
733 : */
734 : void PathResult(u32 ticket, const WaypointPath& path);
735 :
736 0 : void OnValueModification()
737 : {
738 0 : CmpPtr<ICmpValueModificationManager> cmpValueModificationManager(GetSystemEntity());
739 0 : if (!cmpValueModificationManager)
740 0 : return;
741 :
742 0 : m_WalkSpeed = cmpValueModificationManager->ApplyModifications(L"UnitMotion/WalkSpeed", m_TemplateWalkSpeed, GetEntityId());
743 0 : m_RunMultiplier = cmpValueModificationManager->ApplyModifications(L"UnitMotion/RunMultiplier", m_TemplateRunMultiplier, GetEntityId());
744 :
745 : // For MT_Deserialize compute m_Speed from the serialized m_SpeedMultiplier.
746 : // For MT_ValueModification and MT_OwnershipChanged, adjust m_SpeedMultiplier if needed
747 : // (in case then new m_RunMultiplier value is lower than the old).
748 0 : SetSpeedMultiplier(m_SpeedMultiplier);
749 : }
750 :
751 : /**
752 : * Check if we are at destination early in the turn, this both lets units react faster
753 : * and ensure that distance comparisons are done while units are not being moved
754 : * (otherwise they won't be commutative).
755 : */
756 : void OnTurnStart();
757 :
758 : void PreMove(CCmpUnitMotionManager::MotionState& state);
759 : void Move(CCmpUnitMotionManager::MotionState& state, fixed dt);
760 : void PostMove(CCmpUnitMotionManager::MotionState& state, fixed dt);
761 :
762 : /**
763 : * Returns true if we are possibly at our destination.
764 : * Since the concept of being at destination is dependent on why the move was requested,
765 : * UnitMotion can only ever hint about this, hence the conditional tone.
766 : */
767 : bool PossiblyAtDestination() const;
768 :
769 : /**
770 : * Process the move the unit will do this turn.
771 : * This does not send actually change the position.
772 : * @returns true if the move was obstructed.
773 : */
774 : bool PerformMove(fixed dt, const fixed& turnRate, WaypointPath& shortPath, WaypointPath& longPath, CFixedVector2D& pos, fixed& speed, entity_angle_t& angle, uint8_t pushingPressure) const;
775 :
776 : /**
777 : * Update other components on our speed.
778 : * (For performance, this should try to avoid sending messages).
779 : */
780 : void UpdateMovementState(entity_pos_t speed, entity_pos_t meanSpeed);
781 :
782 : /**
783 : * React if our move was obstructed.
784 : * @param moved - true if the unit still managed to move.
785 : * @returns true if the obstruction required handling, false otherwise.
786 : */
787 : bool HandleObstructedMove(bool moved);
788 :
789 : /**
790 : * Returns true if the target position is valid. False otherwise.
791 : * (this may indicate that the target is e.g. out of the world/dead).
792 : * NB: for code-writing convenience, if we have no target, this returns true.
793 : */
794 : bool TargetHasValidPosition(const MoveRequest& moveRequest) const;
795 0 : bool TargetHasValidPosition() const
796 : {
797 0 : return TargetHasValidPosition(m_MoveRequest);
798 : }
799 :
800 : /**
801 : * Computes the current location of our target entity (plus offset).
802 : * Returns false if no target entity or no valid position.
803 : */
804 : bool ComputeTargetPosition(CFixedVector2D& out, const MoveRequest& moveRequest) const;
805 0 : bool ComputeTargetPosition(CFixedVector2D& out) const
806 : {
807 0 : return ComputeTargetPosition(out, m_MoveRequest);
808 : }
809 :
810 : /**
811 : * Attempts to replace the current path with a straight line to the target,
812 : * if it's close enough and the route is not obstructed.
813 : */
814 : bool TryGoingStraightToTarget(const CFixedVector2D& from, bool updatePaths);
815 :
816 : /**
817 : * Returns whether our we need to recompute a path to reach our target.
818 : */
819 : bool PathingUpdateNeeded(const CFixedVector2D& from) const;
820 :
821 : /**
822 : * Rotate to face towards the target point, given the current pos
823 : */
824 : void FaceTowardsPointFromPos(const CFixedVector2D& pos, entity_pos_t x, entity_pos_t z);
825 :
826 : /**
827 : * Units in 'pushing' mode are marked as 'moving' in the obstruction manager.
828 : * Units in 'pushing' mode should skip them in checkMovement (to enable pushing).
829 : * However, units for which pushing is deactivated should collide against everyone.
830 : * Units that don't block movement never participate in pushing, but they also
831 : * shouldn't collide with pushing units.
832 : */
833 0 : bool ShouldCollideWithMovingUnits() const
834 : {
835 0 : return !m_Pushing && m_BlockMovement;
836 : }
837 :
838 : /**
839 : * Returns an appropriate obstruction filter for use with path requests.
840 : */
841 0 : ControlGroupMovementObstructionFilter GetObstructionFilter() const
842 : {
843 0 : return ControlGroupMovementObstructionFilter(ShouldCollideWithMovingUnits(), GetGroup());
844 : }
845 : /**
846 : * Filter a specific tag on top of the existing control groups.
847 : */
848 0 : SkipTagAndControlGroupObstructionFilter GetObstructionFilter(const ICmpObstructionManager::tag_t& tag) const
849 : {
850 0 : return SkipTagAndControlGroupObstructionFilter(tag, ShouldCollideWithMovingUnits(), GetGroup());
851 : }
852 :
853 : /**
854 : * Decide whether to approximate the given range from a square target as a circle,
855 : * rather than as a square.
856 : */
857 : bool ShouldTreatTargetAsCircle(entity_pos_t range, entity_pos_t circleRadius) const;
858 :
859 : /**
860 : * Create a PathGoal from a move request.
861 : * @returns true if the goal was successfully created.
862 : */
863 : bool ComputeGoal(PathGoal& out, const MoveRequest& moveRequest) const;
864 :
865 : /**
866 : * Compute a path to the given goal from the given position.
867 : * Might go in a straight line immediately, or might start an asynchronous path request.
868 : */
869 : void ComputePathToGoal(const CFixedVector2D& from, const PathGoal& goal);
870 :
871 : /**
872 : * Start an asynchronous long path query.
873 : */
874 : void RequestLongPath(const CFixedVector2D& from, const PathGoal& goal);
875 :
876 : /**
877 : * Start an asynchronous short path query.
878 : * @param extendRange - if true, extend the search range to at least the distance to the goal.
879 : */
880 : void RequestShortPath(const CFixedVector2D& from, const PathGoal& goal, bool extendRange);
881 :
882 : /**
883 : * General handler for MoveTo interface functions.
884 : */
885 : bool MoveTo(MoveRequest request);
886 :
887 : /**
888 : * Convert a path into a renderable list of lines
889 : */
890 : void RenderPath(const WaypointPath& path, std::vector<SOverlayLine>& lines, CColor color);
891 :
892 : void RenderSubmit(SceneCollector& collector);
893 : };
894 :
895 116 : REGISTER_COMPONENT_TYPE(UnitMotion)
896 :
897 0 : bool CCmpUnitMotion::RejectFartherPaths(const PathGoal& goal, const WaypointPath& path, const CFixedVector2D& pos) const
898 : {
899 0 : if (path.m_Waypoints.empty())
900 0 : return false;
901 :
902 : // Reject the new path if it does not lead us closer to the target's position.
903 0 : if (goal.DistanceToPoint(pos) <= goal.DistanceToPoint(CFixedVector2D(path.m_Waypoints.front().x, path.m_Waypoints.front().z)))
904 0 : return true;
905 :
906 0 : return false;
907 : }
908 :
909 0 : void CCmpUnitMotion::PathResult(u32 ticket, const WaypointPath& path)
910 : {
911 : // Ignore obsolete path requests
912 0 : if (ticket != m_ExpectedPathTicket.m_Ticket || m_MoveRequest.m_Type == MoveRequest::NONE)
913 0 : return;
914 :
915 0 : Ticket::Type ticketType = m_ExpectedPathTicket.m_Type;
916 0 : m_ExpectedPathTicket.clear();
917 :
918 : // If we not longer have a position, we won't be able to do much.
919 : // Fail in the next Move() call.
920 0 : CmpPtr<ICmpPosition> cmpPosition(GetEntityHandle());
921 0 : if (!cmpPosition || !cmpPosition->IsInWorld())
922 0 : return;
923 0 : CFixedVector2D pos = cmpPosition->GetPosition2D();
924 :
925 : // Assume all long paths were towards the goal, and assume short paths were if there are no long waypoints.
926 0 : bool pathedTowardsGoal = ticketType == Ticket::LONG_PATH || m_LongPath.m_Waypoints.empty();
927 :
928 : // Check if we need to run the short-path hack (warning: tricky control flow).
929 0 : bool shortPathHack = false;
930 0 : if (path.m_Waypoints.empty())
931 : {
932 : // No waypoints means pathing failed. If this was a long-path, try the short-path hack.
933 0 : if (!pathedTowardsGoal)
934 0 : return;
935 0 : shortPathHack = ticketType == Ticket::LONG_PATH;
936 : }
937 0 : else if (PathGoal goal; pathedTowardsGoal && ComputeGoal(goal, m_MoveRequest) && RejectFartherPaths(goal, path, pos))
938 : {
939 : // Reject paths that would take the unit further away from the goal.
940 : // This assumes that we prefer being closer 'as the crow flies' to unreachable goals.
941 : // This is a hack of sorts around units 'dancing' between two positions (see e.g. #3144),
942 : // but never actually failing to move, ergo never actually informing unitAI that it succeeds/fails.
943 : // (for short paths, only do so if aiming directly for the goal
944 : // as sub-goals may be farther than we are).
945 :
946 : // If this was a long-path and we no longer have waypoints, try the short-path hack.
947 0 : if (!m_LongPath.m_Waypoints.empty())
948 0 : return;
949 0 : shortPathHack = ticketType == Ticket::LONG_PATH;
950 : }
951 :
952 : // Short-path hack: if the long-range pathfinder doesn't find an acceptable path, push a fake waypoint at the goal.
953 : // This means HandleObstructedMove will use the short-pathfinder to try and reach it,
954 : // and that may find a path as the vertex pathfinder is more precise.
955 0 : if (shortPathHack)
956 : {
957 : // If we're resorting to the short-path hack, the situation is dire. Most likely, the goal is unreachable.
958 : // We want to find a path or fail fast. Bump failed movements so the short pathfinder will run at max-range
959 : // right away. This is safe from a performance PoV because it can only happen if the target is unreachable to
960 : // the long-range pathfinder, which is rare, and since the entity will fail to move if the goal is actually unreachable,
961 : // the failed movements will be increased to MAX anyways, so just shortcut.
962 0 : m_FailedMovements = MAX_FAILED_MOVEMENTS - 2;
963 :
964 0 : CFixedVector2D targetPos;
965 0 : if (ComputeTargetPosition(targetPos))
966 0 : m_LongPath.m_Waypoints.emplace_back(Waypoint{ targetPos.X, targetPos.Y });
967 0 : return;
968 : }
969 :
970 0 : if (ticketType == Ticket::LONG_PATH)
971 : {
972 0 : m_LongPath = path;
973 : // Long paths don't properly follow diagonals because of JPS/the grid. Since units now take time turning,
974 : // they can actually slow down substantially if they have to do a one navcell diagonal movement,
975 : // which is somewhat common at the beginning of a new path.
976 : // For that reason, if the first waypoint is really close, check if we can't go directly to the second.
977 0 : if (m_LongPath.m_Waypoints.size() >= 2)
978 : {
979 0 : const Waypoint& firstWpt = m_LongPath.m_Waypoints.back();
980 0 : if (CFixedVector2D(firstWpt.x - pos.X, firstWpt.z - pos.Y).CompareLength(Pathfinding::NAVCELL_SIZE * 4) <= 0)
981 : {
982 0 : CmpPtr<ICmpPathfinder> cmpPathfinder(GetSystemEntity());
983 0 : ENSURE(cmpPathfinder);
984 0 : const Waypoint& secondWpt = m_LongPath.m_Waypoints[m_LongPath.m_Waypoints.size() - 2];
985 0 : if (cmpPathfinder->CheckMovement(GetObstructionFilter(), pos.X, pos.Y, secondWpt.x, secondWpt.z, m_Clearance, m_PassClass))
986 0 : m_LongPath.m_Waypoints.pop_back();
987 : }
988 :
989 : }
990 : }
991 : else
992 0 : m_ShortPath = path;
993 :
994 0 : m_FollowKnownImperfectPathCountdown = 0;
995 :
996 0 : if (!pathedTowardsGoal)
997 0 : return;
998 :
999 : // Performance hack: If we were pathing towards the goal and this new path won't put us in range,
1000 : // it's highly likely that we are going somewhere unreachable.
1001 : // However, Move() will try to recompute the path every turn, which can be quite slow.
1002 : // To avoid this, act as if our current path leads us to the correct destination.
1003 : // NB: for short-paths, the problem might be that the search space is too small
1004 : // but we'll still follow this path until the en and try again then.
1005 : // Because we reject farther paths, it works out.
1006 0 : if (PathingUpdateNeeded(pos))
1007 : {
1008 : // Inform other components early, as they might have better behaviour than waiting for the path to carry out.
1009 : // Send OBSTRUCTED at first - moveFailed is likely to trigger path recomputation and we might end up
1010 : // recomputing too often for nothing.
1011 0 : if (!IncrementFailedMovementsAndMaybeNotify())
1012 0 : MoveObstructed();
1013 : // We'll automatically recompute a path when this reaches 0, as a way to improve behaviour.
1014 : // (See D665 - this is needed because the target may be moving, and we should adjust to that).
1015 0 : m_FollowKnownImperfectPathCountdown = KNOWN_IMPERFECT_PATH_RESET_COUNTDOWN;
1016 : }
1017 : }
1018 :
1019 0 : void CCmpUnitMotion::OnTurnStart()
1020 : {
1021 0 : if (PossiblyAtDestination())
1022 0 : MoveSucceeded();
1023 0 : else if (!TargetHasValidPosition())
1024 : {
1025 : // Scrap waypoints - we don't know where to go.
1026 : // If the move request remains unchanged and the target again has a valid position later on,
1027 : // moving will be resumed.
1028 : // Units may want to move to move to the target's last known position,
1029 : // but that should be decided by UnitAI (handling MoveFailed), not UnitMotion.
1030 0 : m_LongPath.m_Waypoints.clear();
1031 0 : m_ShortPath.m_Waypoints.clear();
1032 :
1033 0 : MoveFailed();
1034 : }
1035 0 : }
1036 :
1037 0 : void CCmpUnitMotion::PreMove(CCmpUnitMotionManager::MotionState& state)
1038 : {
1039 0 : state.ignore = !m_Pushing || !m_BlockMovement;
1040 :
1041 0 : state.wasObstructed = false;
1042 0 : state.wentStraight = false;
1043 :
1044 : // If we were idle and will still be, no need for an update.
1045 0 : state.needUpdate = state.cmpPosition->IsInWorld() &&
1046 0 : (m_CurrentSpeed != fixed::Zero() || m_LastTurnSpeed != fixed::Zero() || m_MoveRequest.m_Type != MoveRequest::NONE);
1047 :
1048 0 : if (!m_BlockMovement)
1049 0 : return;
1050 :
1051 0 : state.controlGroup = IsFormationMember() ? m_FormationController : INVALID_ENTITY;
1052 :
1053 : // Update moving flag, this is an internal construct used for pushing,
1054 : // so it does not really reflect whether the unit is actually moving or not.
1055 0 : state.isMoving = m_Pushing && m_MoveRequest.m_Type != MoveRequest::NONE;
1056 0 : CmpPtr<ICmpObstruction> cmpObstruction(GetEntityHandle());
1057 0 : if (cmpObstruction)
1058 0 : cmpObstruction->SetMovingFlag(state.isMoving);
1059 : }
1060 :
1061 0 : void CCmpUnitMotion::Move(CCmpUnitMotionManager::MotionState& state, fixed dt)
1062 : {
1063 0 : PROFILE("Move");
1064 :
1065 : // If we're chasing a potentially-moving unit and are currently close
1066 : // enough to its current position, and we can head in a straight line
1067 : // to it, then throw away our current path and go straight to it.
1068 0 : state.wentStraight = TryGoingStraightToTarget(state.initialPos, true);
1069 :
1070 0 : state.wasObstructed = PerformMove(dt, state.cmpPosition->GetTurnRate(), m_ShortPath, m_LongPath, state.pos, state.speed, state.angle, state.pushingPressure);
1071 0 : }
1072 :
1073 0 : void CCmpUnitMotion::PostMove(CCmpUnitMotionManager::MotionState& state, fixed dt)
1074 : {
1075 : // Update our speed over this turn so that the visual actor shows the correct animation.
1076 0 : if (state.pos == state.initialPos)
1077 : {
1078 0 : if (state.angle != state.initialAngle)
1079 0 : state.cmpPosition->TurnTo(state.angle);
1080 0 : UpdateMovementState(fixed::Zero(), fixed::Zero());
1081 : }
1082 : else
1083 : {
1084 : // Update the Position component after our movement (if we actually moved anywhere)
1085 0 : CFixedVector2D offset = state.pos - state.initialPos;
1086 0 : state.cmpPosition->MoveAndTurnTo(state.pos.X, state.pos.Y, state.angle);
1087 :
1088 : // Calculate the mean speed over this past turn.
1089 0 : UpdateMovementState(state.speed, offset.Length() / dt);
1090 : }
1091 :
1092 0 : if (state.wasObstructed && HandleObstructedMove(state.pos != state.initialPos))
1093 0 : return;
1094 0 : else if (!state.wasObstructed && state.pos != state.initialPos)
1095 0 : m_FailedMovements = 0;
1096 :
1097 : // If we moved straight, and didn't quite finish the path, reset - we'll update it next turn if still OK.
1098 0 : if (state.wentStraight && !state.wasObstructed)
1099 0 : m_ShortPath.m_Waypoints.clear();
1100 :
1101 : // We may need to recompute our path sometimes (e.g. if our target moves).
1102 : // Since we request paths asynchronously anyways, this does not need to be done before moving.
1103 0 : if (!state.wentStraight && PathingUpdateNeeded(state.pos))
1104 : {
1105 0 : PathGoal goal;
1106 0 : if (ComputeGoal(goal, m_MoveRequest))
1107 0 : ComputePathToGoal(state.pos, goal);
1108 : }
1109 0 : else if (m_FollowKnownImperfectPathCountdown > 0)
1110 0 : --m_FollowKnownImperfectPathCountdown;
1111 : }
1112 :
1113 0 : bool CCmpUnitMotion::PossiblyAtDestination() const
1114 : {
1115 0 : if (m_MoveRequest.m_Type == MoveRequest::NONE)
1116 0 : return false;
1117 :
1118 0 : CmpPtr<ICmpObstructionManager> cmpObstructionManager(GetSystemEntity());
1119 0 : ENSURE(cmpObstructionManager);
1120 :
1121 0 : if (m_MoveRequest.m_Type == MoveRequest::POINT)
1122 0 : return cmpObstructionManager->IsInPointRange(GetEntityId(), m_MoveRequest.m_Position.X, m_MoveRequest.m_Position.Y, m_MoveRequest.m_MinRange, m_MoveRequest.m_MaxRange, false);
1123 0 : if (m_MoveRequest.m_Type == MoveRequest::ENTITY)
1124 0 : return cmpObstructionManager->IsInTargetRange(GetEntityId(), m_MoveRequest.m_Entity, m_MoveRequest.m_MinRange, m_MoveRequest.m_MaxRange, false);
1125 0 : if (m_MoveRequest.m_Type == MoveRequest::OFFSET)
1126 : {
1127 0 : CmpPtr<ICmpUnitMotion> cmpControllerMotion(GetSimContext(), m_MoveRequest.m_Entity);
1128 0 : if (cmpControllerMotion && cmpControllerMotion->IsMoveRequested())
1129 0 : return false;
1130 :
1131 : // In formation, return a match only if we are exactly at the target position.
1132 : // Otherwise, units can go in an infinite "walzting" loop when the Idle formation timer
1133 : // reforms them.
1134 0 : CFixedVector2D targetPos;
1135 0 : ComputeTargetPosition(targetPos);
1136 0 : CmpPtr<ICmpPosition> cmpPosition(GetEntityHandle());
1137 0 : return (targetPos-cmpPosition->GetPosition2D()).CompareLength(fixed::Zero()) <= 0;
1138 : }
1139 0 : return false;
1140 : }
1141 :
1142 0 : bool CCmpUnitMotion::PerformMove(fixed dt, const fixed& turnRate, WaypointPath& shortPath, WaypointPath& longPath, CFixedVector2D& pos, fixed& speed, entity_angle_t& angle, uint8_t pushingPressure) const
1143 : {
1144 : // If there are no waypoint, behave as though we were obstructed and let HandleObstructedMove handle it.
1145 0 : if (shortPath.m_Waypoints.empty() && longPath.m_Waypoints.empty())
1146 0 : return true;
1147 :
1148 : // Wrap the angle to (-Pi, Pi].
1149 0 : while (angle > entity_angle_t::Pi())
1150 0 : angle -= entity_angle_t::Pi() * 2;
1151 0 : while (angle < -entity_angle_t::Pi())
1152 0 : angle += entity_angle_t::Pi() * 2;
1153 :
1154 0 : CmpPtr<ICmpPathfinder> cmpPathfinder(GetSystemEntity());
1155 0 : ENSURE(cmpPathfinder);
1156 :
1157 0 : fixed basicSpeed = m_Speed;
1158 : // If in formation, run to keep up; otherwise just walk.
1159 0 : if (IsMovingAsFormation())
1160 0 : basicSpeed = m_Speed.Multiply(m_RunMultiplier);
1161 :
1162 : // If pushing pressure is applied, slow the unit down.
1163 0 : if (pushingPressure)
1164 : {
1165 : // Values below this pressure don't slow the unit down (avoids slowing groups down).
1166 0 : constexpr int pressureMinThreshold = 10;
1167 :
1168 : // Lower speed up to a floor to prevent units from getting stopped.
1169 : // This helped pushing particularly for fast units, since they'll end up slowing down.
1170 0 : constexpr int maxPressure = CCmpUnitMotionManager::MAX_PRESSURE - pressureMinThreshold - 80;
1171 0 : constexpr entity_pos_t floorSpeed = entity_pos_t::FromFraction(3, 2);
1172 : static_assert(maxPressure > 0);
1173 :
1174 0 : uint8_t slowdown = maxPressure - std::min(maxPressure, std::max(0, pushingPressure - pressureMinThreshold));
1175 0 : basicSpeed = basicSpeed.Multiply(fixed::FromInt(slowdown) / maxPressure);
1176 : // NB: lowering this too much will make the units behave a lot like viscous fluid
1177 : // when the density becomes extreme. While perhaps realistic (and kind of neat),
1178 : // it's not very helpful for gameplay. Empirically, a value of 1.5 avoids most of the effect
1179 : // while still slowing down movement significantly, and seems like a good balance.
1180 : // Min with the template speed to allow units that are explicitly absurdly slow.
1181 0 : basicSpeed = std::max(std::min(m_TemplateWalkSpeed, floorSpeed), basicSpeed);
1182 : }
1183 :
1184 : // TODO: would be nice to support terrain-dependent speed again.
1185 0 : fixed maxSpeed = basicSpeed;
1186 :
1187 0 : fixed timeLeft = dt;
1188 0 : fixed zero = fixed::Zero();
1189 :
1190 0 : ICmpObstructionManager::tag_t specificIgnore;
1191 0 : if (m_MoveRequest.m_Type == MoveRequest::ENTITY)
1192 : {
1193 0 : CmpPtr<ICmpObstruction> cmpTargetObstruction(GetSimContext(), m_MoveRequest.m_Entity);
1194 0 : if (cmpTargetObstruction)
1195 0 : specificIgnore = cmpTargetObstruction->GetObstruction();
1196 : }
1197 :
1198 0 : while (timeLeft > zero)
1199 : {
1200 : // If we ran out of path, we have to stop.
1201 0 : if (shortPath.m_Waypoints.empty() && longPath.m_Waypoints.empty())
1202 0 : break;
1203 :
1204 0 : CFixedVector2D target;
1205 0 : if (shortPath.m_Waypoints.empty())
1206 0 : target = CFixedVector2D(longPath.m_Waypoints.back().x, longPath.m_Waypoints.back().z);
1207 : else
1208 0 : target = CFixedVector2D(shortPath.m_Waypoints.back().x, shortPath.m_Waypoints.back().z);
1209 :
1210 0 : CFixedVector2D offset = target - pos;
1211 :
1212 0 : if (turnRate > zero && !offset.IsZero())
1213 : {
1214 0 : fixed angleDiff = angle - atan2_approx(offset.X, offset.Y);
1215 0 : fixed absoluteAngleDiff = angleDiff.Absolute();
1216 0 : if (absoluteAngleDiff > entity_angle_t::Pi())
1217 0 : absoluteAngleDiff = entity_angle_t::Pi() * 2 - absoluteAngleDiff;
1218 :
1219 : // We only rotate to the instantTurnAngle angle. The rest we rotate during movement.
1220 0 : if (absoluteAngleDiff > m_InstantTurnAngle)
1221 : {
1222 : // Stop moving when rotating this far.
1223 0 : speed = zero;
1224 :
1225 0 : fixed maxRotation = turnRate.Multiply(timeLeft);
1226 :
1227 : // Figure out whether rotating will increase or decrease the angle, and how far we need to rotate in that direction.
1228 0 : int direction = (entity_angle_t::Zero() < angleDiff && angleDiff <= entity_angle_t::Pi()) || angleDiff < -entity_angle_t::Pi() ? -1 : 1;
1229 :
1230 : // Can't rotate far enough, just rotate in the correct direction.
1231 0 : if (absoluteAngleDiff - m_InstantTurnAngle > maxRotation)
1232 : {
1233 0 : angle += maxRotation * direction;
1234 0 : if (angle * direction > entity_angle_t::Pi())
1235 0 : angle -= entity_angle_t::Pi() * 2 * direction;
1236 0 : break;
1237 : }
1238 : // Rotate towards the next waypoint and continue moving.
1239 0 : angle = atan2_approx(offset.X, offset.Y);
1240 0 : timeLeft = std::min(maxRotation, maxRotation - absoluteAngleDiff + m_InstantTurnAngle) / turnRate;
1241 : }
1242 : else
1243 : {
1244 : // Modify the speed depending on the angle difference.
1245 0 : fixed sin, cos;
1246 0 : sincos_approx(angleDiff, sin, cos);
1247 0 : speed = speed.Multiply(cos);
1248 0 : angle = atan2_approx(offset.X, offset.Y);
1249 : }
1250 : }
1251 :
1252 : // Work out how far we can travel in timeLeft.
1253 0 : fixed accelTime = std::min(timeLeft, (maxSpeed - speed) / m_Acceleration);
1254 0 : fixed accelDist = speed.Multiply(accelTime) + accelTime.Square().Multiply(m_Acceleration) / 2;
1255 0 : fixed maxdist = accelDist + maxSpeed.Multiply(timeLeft - accelTime);
1256 :
1257 : // If the target is close, we can move there directly.
1258 0 : fixed offsetLength = offset.Length();
1259 0 : if (offsetLength <= maxdist)
1260 : {
1261 0 : if (cmpPathfinder->CheckMovement(GetObstructionFilter(specificIgnore), pos.X, pos.Y, target.X, target.Y, m_Clearance, m_PassClass))
1262 : {
1263 0 : pos = target;
1264 :
1265 : // Spend the rest of the time heading towards the next waypoint.
1266 : // Either we still need to accelerate after, or we have reached maxSpeed.
1267 : // The former is much less likely than the latter: usually we can reach
1268 : // maxSpeed within one waypoint. So the Sqrt is not too bad.
1269 0 : if (offsetLength <= accelDist)
1270 : {
1271 0 : fixed requiredTime = (-speed + (speed.Square() + offsetLength.Multiply(m_Acceleration).Multiply(fixed::FromInt(2))).Sqrt()) / m_Acceleration;
1272 0 : timeLeft -= requiredTime;
1273 0 : speed += m_Acceleration.Multiply(requiredTime);
1274 : }
1275 : else
1276 : {
1277 0 : timeLeft -= accelTime + (offsetLength - accelDist) / maxSpeed;
1278 0 : speed = maxSpeed;
1279 : }
1280 :
1281 0 : if (shortPath.m_Waypoints.empty())
1282 0 : longPath.m_Waypoints.pop_back();
1283 : else
1284 0 : shortPath.m_Waypoints.pop_back();
1285 :
1286 0 : continue;
1287 : }
1288 : else
1289 : {
1290 : // Error - path was obstructed.
1291 0 : return true;
1292 : }
1293 : }
1294 : else
1295 : {
1296 : // Not close enough, so just move in the right direction.
1297 0 : offset.Normalize(maxdist);
1298 0 : target = pos + offset;
1299 :
1300 0 : speed = std::min(maxSpeed, speed + m_Acceleration.Multiply(timeLeft));
1301 :
1302 0 : if (cmpPathfinder->CheckMovement(GetObstructionFilter(specificIgnore), pos.X, pos.Y, target.X, target.Y, m_Clearance, m_PassClass))
1303 0 : pos = target;
1304 : else
1305 0 : return true;
1306 :
1307 0 : break;
1308 : }
1309 : }
1310 0 : return false;
1311 : }
1312 :
1313 0 : void CCmpUnitMotion::UpdateMovementState(entity_pos_t speed, entity_pos_t meanSpeed)
1314 : {
1315 0 : CmpPtr<ICmpVisual> cmpVisual(GetEntityHandle());
1316 0 : if (cmpVisual)
1317 : {
1318 0 : if (meanSpeed == fixed::Zero())
1319 0 : cmpVisual->SelectMovementAnimation("idle", fixed::FromInt(1));
1320 : else
1321 0 : cmpVisual->SelectMovementAnimation(meanSpeed > (m_WalkSpeed / 2).Multiply(m_RunMultiplier + fixed::FromInt(1)) ? "run" : "walk", meanSpeed);
1322 : }
1323 :
1324 0 : m_LastTurnSpeed = meanSpeed;
1325 0 : m_CurrentSpeed = speed;
1326 0 : }
1327 :
1328 0 : bool CCmpUnitMotion::HandleObstructedMove(bool moved)
1329 : {
1330 0 : CmpPtr<ICmpPosition> cmpPosition(GetEntityHandle());
1331 0 : if (!cmpPosition || !cmpPosition->IsInWorld())
1332 0 : return false;
1333 :
1334 : // We failed to move, inform other components as they might handle it.
1335 : // (don't send messages on the first failure, as that would be too noisy).
1336 : // Also don't increment above the initial MoveObstructed message if we actually manage to move a little.
1337 0 : if (!moved || m_FailedMovements < 2)
1338 : {
1339 0 : if (!IncrementFailedMovementsAndMaybeNotify() && m_FailedMovements >= 2)
1340 0 : MoveObstructed();
1341 : }
1342 :
1343 0 : PathGoal goal;
1344 0 : if (!ComputeGoal(goal, m_MoveRequest))
1345 0 : return false;
1346 :
1347 : // At this point we have a position in the world since ComputeGoal checked for that.
1348 0 : CFixedVector2D pos = cmpPosition->GetPosition2D();
1349 :
1350 : // Assume that we are merely obstructed and the long path is salvageable, so try going around the obstruction.
1351 : // 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.
1352 : // I use an IIFE to have nice 'return' semantics still.
1353 0 : if ([&]() -> bool {
1354 : // If the goal is close enough, we should ignore any remaining long waypoint and just
1355 : // short path there directly, as that improves behaviour in general - see D2095).
1356 0 : if (InShortPathRange(goal, pos))
1357 0 : return false;
1358 :
1359 : // On rare occasions, when following a short path, we can end up in a position where
1360 : // the short pathfinder thinks we are inside an obstruction (and can leave)
1361 : // but the CheckMovement logic doesn't. I believe the cause is a small numerical difference
1362 : // in their calculation, but haven't been able to pinpoint it precisely.
1363 : // In those cases, the solution is to back away to prevent the short-pathfinder from being confused.
1364 : // TODO: this should only be done if we're obstructed by a static entity.
1365 0 : if (!m_ShortPath.m_Waypoints.empty() && m_FailedMovements == BACKUP_HACK_DELAY)
1366 : {
1367 0 : Waypoint next = m_ShortPath.m_Waypoints.back();
1368 0 : CFixedVector2D backUp(pos.X - next.x, pos.Y - next.z);
1369 0 : backUp.Normalize();
1370 0 : next.x = pos.X + backUp.X;
1371 0 : next.z = pos.Y + backUp.Y;
1372 0 : m_ShortPath.m_Waypoints.push_back(next);
1373 0 : return true;
1374 : }
1375 : // Delete the next waypoint if it's reasonably close,
1376 : // because it might be blocked by units and thus unreachable.
1377 : // NB: this number is tricky. Make it too high, and units start going down dead ends, which looks odd (#5795)
1378 : // Make it too low, and they might get stuck behind other obstructed entities.
1379 : // It also has performance implications because it calls the short-pathfinder.
1380 0 : fixed skipbeyond = std::max(ShortPathSearchRange() / 3, Pathfinding::NAVCELL_SIZE * 8);
1381 0 : if (m_LongPath.m_Waypoints.size() > 1 &&
1382 0 : (pos - CFixedVector2D(m_LongPath.m_Waypoints.back().x, m_LongPath.m_Waypoints.back().z)).CompareLength(skipbeyond) < 0)
1383 : {
1384 0 : m_LongPath.m_Waypoints.pop_back();
1385 : }
1386 0 : else if (ShouldAlternatePathfinder())
1387 : {
1388 : // Recompute the whole thing occasionally, in case we got stuck in a dead end from removing long waypoints.
1389 0 : RequestLongPath(pos, goal);
1390 0 : return true;
1391 : }
1392 :
1393 0 : if (m_LongPath.m_Waypoints.empty())
1394 0 : return false;
1395 :
1396 : // Compute a short path in the general vicinity of the next waypoint, to help pathfinding in crowds.
1397 : // The goal here is to manage to move in the general direction of our target, not to be super accurate.
1398 0 : fixed radius = Clamp(skipbeyond/3, Pathfinding::NAVCELL_SIZE * 4, Pathfinding::NAVCELL_SIZE * 12);
1399 0 : PathGoal subgoal = { PathGoal::CIRCLE, m_LongPath.m_Waypoints.back().x, m_LongPath.m_Waypoints.back().z, radius };
1400 0 : RequestShortPath(pos, subgoal, false);
1401 0 : return true;
1402 0 : }()) return true;
1403 :
1404 : // If we couldn't use a workaround, try recomputing the entire path.
1405 0 : ComputePathToGoal(pos, goal);
1406 :
1407 0 : return true;
1408 : }
1409 :
1410 0 : bool CCmpUnitMotion::TargetHasValidPosition(const MoveRequest& moveRequest) const
1411 : {
1412 0 : if (moveRequest.m_Type != MoveRequest::ENTITY)
1413 0 : return true;
1414 :
1415 0 : CmpPtr<ICmpPosition> cmpPosition(GetSimContext(), moveRequest.m_Entity);
1416 0 : return cmpPosition && cmpPosition->IsInWorld();
1417 : }
1418 :
1419 0 : bool CCmpUnitMotion::ComputeTargetPosition(CFixedVector2D& out, const MoveRequest& moveRequest) const
1420 : {
1421 0 : if (moveRequest.m_Type == MoveRequest::POINT)
1422 : {
1423 0 : out = moveRequest.m_Position;
1424 0 : return true;
1425 : }
1426 :
1427 0 : CmpPtr<ICmpPosition> cmpTargetPosition(GetSimContext(), moveRequest.m_Entity);
1428 0 : if (!cmpTargetPosition || !cmpTargetPosition->IsInWorld())
1429 0 : return false;
1430 :
1431 0 : if (moveRequest.m_Type == MoveRequest::OFFSET)
1432 : {
1433 : // There is an offset, so compute it relative to orientation
1434 0 : entity_angle_t angle = cmpTargetPosition->GetRotation().Y;
1435 0 : CFixedVector2D offset = moveRequest.GetOffset().Rotate(angle);
1436 0 : out = cmpTargetPosition->GetPosition2D() + offset;
1437 : }
1438 : else
1439 : {
1440 0 : out = cmpTargetPosition->GetPosition2D();
1441 : // Position is only updated after all units have moved & pushed.
1442 : // Therefore, we may need to interpolate the target position, depending on when this call takes place during the turn:
1443 : // - On "Turn Start", we'll check positions directly without interpolation.
1444 : // - During movement, we'll call this for direct-pathing & we need to interpolate
1445 : // (this way, we move where the unit will end up at the end of _this_ turn, making it match on next turn start).
1446 : // - After movement, we'll call this to request paths & we need to interpolate
1447 : // (this way, we'll move where the unit ends up in the end of _next_ turn, making it a match in 2 turns).
1448 : // TODO: This does not really aim many turns in advance, with orthogonal trajectories it probably should.
1449 0 : CmpPtr<ICmpUnitMotion> cmpUnitMotion(GetSimContext(), moveRequest.m_Entity);
1450 0 : CmpPtr<ICmpUnitMotionManager> cmpUnitMotionManager(GetSystemEntity());
1451 0 : bool needInterpolation = cmpUnitMotion && cmpUnitMotion->IsMoveRequested() && cmpUnitMotionManager->ComputingMotion();
1452 0 : if (needInterpolation)
1453 : {
1454 : // Add predicted movement.
1455 0 : CFixedVector2D tempPos = out + (out - cmpTargetPosition->GetPreviousPosition2D());
1456 0 : out = tempPos;
1457 : }
1458 : }
1459 0 : return true;
1460 : }
1461 :
1462 0 : bool CCmpUnitMotion::TryGoingStraightToTarget(const CFixedVector2D& from, bool updatePaths)
1463 : {
1464 : // Assume if we have short paths we want to follow them.
1465 : // Exception: offset movement (formations) generally have very short deltas
1466 : // and to look good we need them to walk-straight most of the time.
1467 0 : if (!IsFormationMember() && !m_ShortPath.m_Waypoints.empty())
1468 0 : return false;
1469 :
1470 0 : CFixedVector2D targetPos;
1471 0 : if (!ComputeTargetPosition(targetPos))
1472 0 : return false;
1473 :
1474 0 : CmpPtr<ICmpPathfinder> cmpPathfinder(GetSystemEntity());
1475 0 : if (!cmpPathfinder)
1476 0 : return false;
1477 :
1478 : // Move the goal to match the target entity's new position
1479 0 : PathGoal goal;
1480 0 : if (!ComputeGoal(goal, m_MoveRequest))
1481 0 : return false;
1482 0 : goal.x = targetPos.X;
1483 0 : goal.z = targetPos.Y;
1484 : // (we ignore changes to the target's rotation, since only buildings are
1485 : // square and buildings don't move)
1486 :
1487 : // Find the point on the goal shape that we should head towards
1488 0 : CFixedVector2D goalPos = goal.NearestPointOnGoal(from);
1489 :
1490 : // Fail if the target is too far away
1491 0 : if ((goalPos - from).CompareLength(DIRECT_PATH_RANGE) > 0)
1492 0 : return false;
1493 :
1494 : // Check if there's any collisions on that route.
1495 : // For entity goals, skip only the specific obstruction tag or with e.g. walls we might ignore too many entities.
1496 0 : ICmpObstructionManager::tag_t specificIgnore;
1497 0 : if (m_MoveRequest.m_Type == MoveRequest::ENTITY)
1498 : {
1499 0 : CmpPtr<ICmpObstruction> cmpTargetObstruction(GetSimContext(), m_MoveRequest.m_Entity);
1500 0 : if (cmpTargetObstruction)
1501 0 : specificIgnore = cmpTargetObstruction->GetObstruction();
1502 : }
1503 :
1504 : // Check movement against units - we want to use the short pathfinder to walk around those if needed.
1505 0 : if (specificIgnore.valid())
1506 : {
1507 0 : if (!cmpPathfinder->CheckMovement(GetObstructionFilter(specificIgnore), from.X, from.Y, goalPos.X, goalPos.Y, m_Clearance, m_PassClass))
1508 0 : return false;
1509 : }
1510 0 : else if (!cmpPathfinder->CheckMovement(GetObstructionFilter(), from.X, from.Y, goalPos.X, goalPos.Y, m_Clearance, m_PassClass))
1511 0 : return false;
1512 :
1513 0 : if (!updatePaths)
1514 0 : return true;
1515 :
1516 : // That route is okay, so update our path
1517 0 : m_LongPath.m_Waypoints.clear();
1518 0 : m_ShortPath.m_Waypoints.clear();
1519 0 : m_ShortPath.m_Waypoints.emplace_back(Waypoint{ goalPos.X, goalPos.Y });
1520 0 : return true;
1521 : }
1522 :
1523 0 : bool CCmpUnitMotion::PathingUpdateNeeded(const CFixedVector2D& from) const
1524 : {
1525 0 : if (m_MoveRequest.m_Type == MoveRequest::NONE)
1526 0 : return false;
1527 :
1528 0 : CFixedVector2D targetPos;
1529 0 : if (!ComputeTargetPosition(targetPos))
1530 0 : return false;
1531 :
1532 0 : if (m_FollowKnownImperfectPathCountdown > 0 && (!m_LongPath.m_Waypoints.empty() || !m_ShortPath.m_Waypoints.empty()))
1533 0 : return false;
1534 :
1535 0 : if (PossiblyAtDestination())
1536 0 : return false;
1537 :
1538 : // Get the obstruction shape and translate it where we estimate the target to be.
1539 0 : ICmpObstructionManager::ObstructionSquare estimatedTargetShape;
1540 0 : if (m_MoveRequest.m_Type == MoveRequest::ENTITY)
1541 : {
1542 0 : CmpPtr<ICmpObstruction> cmpTargetObstruction(GetSimContext(), m_MoveRequest.m_Entity);
1543 0 : if (cmpTargetObstruction)
1544 0 : cmpTargetObstruction->GetObstructionSquare(estimatedTargetShape);
1545 : }
1546 :
1547 0 : estimatedTargetShape.x = targetPos.X;
1548 0 : estimatedTargetShape.z = targetPos.Y;
1549 :
1550 0 : CmpPtr<ICmpObstruction> cmpObstruction(GetEntityHandle());
1551 0 : ICmpObstructionManager::ObstructionSquare shape;
1552 0 : if (cmpObstruction)
1553 0 : cmpObstruction->GetObstructionSquare(shape);
1554 :
1555 : // Translate our own obstruction shape to our last waypoint or our current position, lacking that.
1556 0 : if (m_LongPath.m_Waypoints.empty() && m_ShortPath.m_Waypoints.empty())
1557 : {
1558 0 : shape.x = from.X;
1559 0 : shape.z = from.Y;
1560 : }
1561 : else
1562 : {
1563 0 : const Waypoint& lastWaypoint = m_LongPath.m_Waypoints.empty() ? m_ShortPath.m_Waypoints.front() : m_LongPath.m_Waypoints.front();
1564 0 : shape.x = lastWaypoint.x;
1565 0 : shape.z = lastWaypoint.z;
1566 : }
1567 :
1568 0 : CmpPtr<ICmpObstructionManager> cmpObstructionManager(GetSystemEntity());
1569 0 : ENSURE(cmpObstructionManager);
1570 :
1571 : // Increase the ranges with distance, to avoid recomputing every turn against units that are moving and far-away for example.
1572 0 : entity_pos_t distance = (from - CFixedVector2D(estimatedTargetShape.x, estimatedTargetShape.z)).Length();
1573 :
1574 : // TODO: it could be worth computing this based on time to collision instead of linear distance.
1575 0 : entity_pos_t minRange = std::max(m_MoveRequest.m_MinRange - distance / TARGET_UNCERTAINTY_MULTIPLIER, entity_pos_t::Zero());
1576 0 : entity_pos_t maxRange = m_MoveRequest.m_MaxRange < entity_pos_t::Zero() ? m_MoveRequest.m_MaxRange :
1577 0 : m_MoveRequest.m_MaxRange + distance / TARGET_UNCERTAINTY_MULTIPLIER;
1578 :
1579 0 : if (cmpObstructionManager->AreShapesInRange(shape, estimatedTargetShape, minRange, maxRange, false))
1580 0 : return false;
1581 :
1582 0 : return true;
1583 : }
1584 :
1585 0 : void CCmpUnitMotion::FaceTowardsPoint(entity_pos_t x, entity_pos_t z)
1586 : {
1587 0 : CmpPtr<ICmpPosition> cmpPosition(GetEntityHandle());
1588 0 : if (!cmpPosition || !cmpPosition->IsInWorld())
1589 0 : return;
1590 :
1591 0 : CFixedVector2D pos = cmpPosition->GetPosition2D();
1592 0 : FaceTowardsPointFromPos(pos, x, z);
1593 : }
1594 :
1595 0 : void CCmpUnitMotion::FaceTowardsPointFromPos(const CFixedVector2D& pos, entity_pos_t x, entity_pos_t z)
1596 : {
1597 0 : CFixedVector2D target(x, z);
1598 0 : CFixedVector2D offset = target - pos;
1599 0 : if (!offset.IsZero())
1600 : {
1601 0 : entity_angle_t angle = atan2_approx(offset.X, offset.Y);
1602 :
1603 0 : CmpPtr<ICmpPosition> cmpPosition(GetEntityHandle());
1604 0 : if (!cmpPosition)
1605 0 : return;
1606 0 : cmpPosition->TurnTo(angle);
1607 : }
1608 : }
1609 :
1610 : // The pathfinder cannot go to "rounded rectangles" goals, which are what happens with square targets and a non-null range.
1611 : // Depending on what the best approximation is, we either pretend the target is a circle or a square.
1612 : // One needs to be careful that the approximated geometry will be in the range.
1613 0 : bool CCmpUnitMotion::ShouldTreatTargetAsCircle(entity_pos_t range, entity_pos_t circleRadius) const
1614 : {
1615 : // Given a square, plus a target range we should reach, the shape at that distance
1616 : // is a round-cornered square which we can approximate as either a circle or as a square.
1617 : // Previously, we used the shape that minimized the worst-case error.
1618 : // However that is unsage in some situations. So let's be less clever and
1619 : // just check if our range is at least three times bigger than the circleradius
1620 0 : return (range > circleRadius*3);
1621 : }
1622 :
1623 0 : bool CCmpUnitMotion::ComputeGoal(PathGoal& out, const MoveRequest& moveRequest) const
1624 : {
1625 0 : if (moveRequest.m_Type == MoveRequest::NONE)
1626 0 : return false;
1627 :
1628 0 : CmpPtr<ICmpPosition> cmpPosition(GetEntityHandle());
1629 0 : if (!cmpPosition || !cmpPosition->IsInWorld())
1630 0 : return false;
1631 :
1632 0 : CFixedVector2D pos = cmpPosition->GetPosition2D();
1633 :
1634 0 : CFixedVector2D targetPosition;
1635 0 : if (!ComputeTargetPosition(targetPosition, moveRequest))
1636 0 : return false;
1637 :
1638 0 : ICmpObstructionManager::ObstructionSquare targetObstruction;
1639 0 : if (moveRequest.m_Type == MoveRequest::ENTITY)
1640 : {
1641 0 : CmpPtr<ICmpObstruction> cmpTargetObstruction(GetSimContext(), moveRequest.m_Entity);
1642 0 : if (cmpTargetObstruction)
1643 0 : cmpTargetObstruction->GetObstructionSquare(targetObstruction);
1644 : }
1645 0 : targetObstruction.x = targetPosition.X;
1646 0 : targetObstruction.z = targetPosition.Y;
1647 :
1648 0 : ICmpObstructionManager::ObstructionSquare obstruction;
1649 0 : CmpPtr<ICmpObstruction> cmpObstruction(GetEntityHandle());
1650 0 : if (cmpObstruction)
1651 0 : cmpObstruction->GetObstructionSquare(obstruction);
1652 : else
1653 : {
1654 0 : obstruction.x = pos.X;
1655 0 : obstruction.z = pos.Y;
1656 : }
1657 :
1658 0 : CmpPtr<ICmpObstructionManager> cmpObstructionManager(GetSystemEntity());
1659 0 : ENSURE(cmpObstructionManager);
1660 :
1661 0 : entity_pos_t distance = cmpObstructionManager->DistanceBetweenShapes(obstruction, targetObstruction);
1662 :
1663 0 : out.x = targetObstruction.x;
1664 0 : out.z = targetObstruction.z;
1665 0 : out.hw = targetObstruction.hw;
1666 0 : out.hh = targetObstruction.hh;
1667 0 : out.u = targetObstruction.u;
1668 0 : out.v = targetObstruction.v;
1669 :
1670 0 : if (moveRequest.m_MinRange > fixed::Zero() || moveRequest.m_MaxRange > fixed::Zero() ||
1671 0 : targetObstruction.hw > fixed::Zero())
1672 0 : out.type = PathGoal::SQUARE;
1673 : else
1674 : {
1675 0 : out.type = PathGoal::POINT;
1676 0 : return true;
1677 : }
1678 :
1679 0 : entity_pos_t circleRadius = CFixedVector2D(targetObstruction.hw, targetObstruction.hh).Length();
1680 :
1681 : // TODO: because we cannot move to rounded rectangles, we have to make conservative approximations.
1682 : // This means we might end up in a situation where cons(max-range) < min range < max range < cons(min-range)
1683 : // When going outside of the min-range or inside the max-range, the unit will still go through the correct range
1684 : // but if it moves fast enough, this might not be picked up by PossiblyAtDestination().
1685 : // Fixing this involves moving to rounded rectangles, or checking more often in PerformMove().
1686 : // In the meantime, one should avoid that 'Speed over a turn' > MaxRange - MinRange, in case where
1687 : // min-range is not 0 and max-range is not infinity.
1688 0 : if (distance < moveRequest.m_MinRange)
1689 : {
1690 : // Distance checks are nearest edge to nearest edge, so we need to account for our clearance
1691 : // and we must make sure diagonals also fit so multiply by slightly more than sqrt(2)
1692 0 : entity_pos_t goalDistance = moveRequest.m_MinRange + m_Clearance * 3 / 2;
1693 :
1694 0 : if (ShouldTreatTargetAsCircle(moveRequest.m_MinRange, circleRadius))
1695 : {
1696 : // We are safely away from the obstruction itself if we are away from the circumscribing circle
1697 0 : out.type = PathGoal::INVERTED_CIRCLE;
1698 0 : out.hw = circleRadius + goalDistance;
1699 : }
1700 : else
1701 : {
1702 0 : out.type = PathGoal::INVERTED_SQUARE;
1703 0 : out.hw = targetObstruction.hw + goalDistance;
1704 0 : out.hh = targetObstruction.hh + goalDistance;
1705 : }
1706 : }
1707 0 : else if (moveRequest.m_MaxRange >= fixed::Zero() && distance > moveRequest.m_MaxRange)
1708 : {
1709 0 : if (ShouldTreatTargetAsCircle(moveRequest.m_MaxRange, circleRadius))
1710 : {
1711 0 : entity_pos_t goalDistance = moveRequest.m_MaxRange;
1712 : // We must go in-range of the inscribed circle, not the circumscribing circle.
1713 0 : circleRadius = std::min(targetObstruction.hw, targetObstruction.hh);
1714 :
1715 0 : out.type = PathGoal::CIRCLE;
1716 0 : out.hw = circleRadius + goalDistance;
1717 : }
1718 : else
1719 : {
1720 : // The target is large relative to our range, so treat it as a square and
1721 : // get close enough that the diagonals come within range
1722 :
1723 0 : entity_pos_t goalDistance = moveRequest.m_MaxRange * 2 / 3; // multiply by slightly less than 1/sqrt(2)
1724 :
1725 0 : out.type = PathGoal::SQUARE;
1726 0 : entity_pos_t delta = std::max(goalDistance, m_Clearance + entity_pos_t::FromInt(4)/16); // ensure it's far enough to not intersect the building itself
1727 0 : out.hw = targetObstruction.hw + delta;
1728 0 : out.hh = targetObstruction.hh + delta;
1729 : }
1730 : }
1731 : // Do nothing in particular in case we are already in range.
1732 0 : return true;
1733 : }
1734 :
1735 0 : void CCmpUnitMotion::ComputePathToGoal(const CFixedVector2D& from, const PathGoal& goal)
1736 : {
1737 : #if DISABLE_PATHFINDER
1738 : {
1739 : CmpPtr<ICmpPathfinder> cmpPathfinder (GetSimContext(), SYSTEM_ENTITY);
1740 : CFixedVector2D goalPos = m_FinalGoal.NearestPointOnGoal(from);
1741 : m_LongPath.m_Waypoints.clear();
1742 : m_ShortPath.m_Waypoints.clear();
1743 : m_ShortPath.m_Waypoints.emplace_back(Waypoint{ goalPos.X, goalPos.Y });
1744 : return;
1745 : }
1746 : #endif
1747 :
1748 : // If the target is close enough, hope that we'll be able to go straight next turn.
1749 0 : if (!ShouldAlternatePathfinder() && TryGoingStraightToTarget(from, false))
1750 : {
1751 : // NB: since we may fail to move straight next turn, we should edge our bets.
1752 : // Since the 'go straight' logic currently fires only if there's no short path,
1753 : // we'll compute a long path regardless to make sure _that_ stays up to date.
1754 : // (it's also extremely likely to be very fast to compute, so no big deal).
1755 0 : m_ShortPath.m_Waypoints.clear();
1756 0 : RequestLongPath(from, goal);
1757 0 : return;
1758 : }
1759 :
1760 : // Otherwise we need to compute a path.
1761 :
1762 : // If it's close then just do a short path, not a long path
1763 : // TODO: If it's close on the opposite side of a river then we really
1764 : // need a long path, so we shouldn't simply check linear distance
1765 : // the check is arbitrary but should be a reasonably small distance.
1766 : // We want to occasionally compute a long path if we're computing short-paths, because the short path domain
1767 : // is bounded and thus it can't around very large static obstacles.
1768 : // Likewise, we want to compile a short-path occasionally when the target is far because we might be stuck
1769 : // on a navcell surrounded by impassable navcells, but the short-pathfinder could move us out of there.
1770 0 : bool shortPath = InShortPathRange(goal, from);
1771 0 : if (ShouldAlternatePathfinder())
1772 0 : shortPath = !shortPath;
1773 0 : if (shortPath)
1774 : {
1775 0 : m_LongPath.m_Waypoints.clear();
1776 : // Extend the range so that our first path is probably valid.
1777 0 : RequestShortPath(from, goal, true);
1778 : }
1779 : else
1780 : {
1781 0 : m_ShortPath.m_Waypoints.clear();
1782 0 : RequestLongPath(from, goal);
1783 : }
1784 : }
1785 :
1786 0 : void CCmpUnitMotion::RequestLongPath(const CFixedVector2D& from, const PathGoal& goal)
1787 : {
1788 0 : CmpPtr<ICmpPathfinder> cmpPathfinder(GetSystemEntity());
1789 0 : if (!cmpPathfinder)
1790 0 : return;
1791 :
1792 : // this is by how much our waypoints will be apart at most.
1793 : // this value here seems sensible enough.
1794 0 : PathGoal improvedGoal = goal;
1795 0 : improvedGoal.maxdist = SHORT_PATH_MIN_SEARCH_RANGE - entity_pos_t::FromInt(1);
1796 :
1797 0 : cmpPathfinder->SetDebugPath(from.X, from.Y, improvedGoal, m_PassClass);
1798 :
1799 0 : m_ExpectedPathTicket.m_Type = Ticket::LONG_PATH;
1800 0 : m_ExpectedPathTicket.m_Ticket = cmpPathfinder->ComputePathAsync(from.X, from.Y, improvedGoal, m_PassClass, GetEntityId());
1801 : }
1802 :
1803 0 : void CCmpUnitMotion::RequestShortPath(const CFixedVector2D &from, const PathGoal& goal, bool extendRange)
1804 : {
1805 0 : CmpPtr<ICmpPathfinder> cmpPathfinder(GetSystemEntity());
1806 0 : if (!cmpPathfinder)
1807 0 : return;
1808 :
1809 0 : entity_pos_t searchRange = ShortPathSearchRange();
1810 0 : if (extendRange)
1811 : {
1812 0 : CFixedVector2D dist(from.X - goal.x, from.Y - goal.z);
1813 0 : if (dist.CompareLength(searchRange - entity_pos_t::FromInt(1)) >= 0)
1814 : {
1815 0 : searchRange = dist.Length() + fixed::FromInt(1);
1816 0 : if (searchRange > SHORT_PATH_MAX_SEARCH_RANGE)
1817 0 : searchRange = SHORT_PATH_MAX_SEARCH_RANGE;
1818 : }
1819 : }
1820 :
1821 0 : m_ExpectedPathTicket.m_Type = Ticket::SHORT_PATH;
1822 0 : m_ExpectedPathTicket.m_Ticket = cmpPathfinder->ComputeShortPathAsync(from.X, from.Y, m_Clearance, searchRange, goal, m_PassClass, ShouldCollideWithMovingUnits(), GetGroup(), GetEntityId());
1823 : }
1824 :
1825 0 : bool CCmpUnitMotion::MoveTo(MoveRequest request)
1826 : {
1827 0 : PROFILE("MoveTo");
1828 :
1829 0 : if (request.m_MinRange == request.m_MaxRange && !request.m_MinRange.IsZero())
1830 0 : LOGWARNING("MaxRange must be larger than MinRange; See CCmpUnitMotion.cpp for more information");
1831 :
1832 0 : CmpPtr<ICmpPosition> cmpPosition(GetEntityHandle());
1833 0 : if (!cmpPosition || !cmpPosition->IsInWorld())
1834 0 : return false;
1835 :
1836 0 : PathGoal goal;
1837 0 : if (!ComputeGoal(goal, request))
1838 0 : return false;
1839 :
1840 0 : m_MoveRequest = request;
1841 0 : m_FailedMovements = 0;
1842 0 : m_FollowKnownImperfectPathCountdown = 0;
1843 :
1844 0 : ComputePathToGoal(cmpPosition->GetPosition2D(), goal);
1845 0 : return true;
1846 : }
1847 :
1848 0 : bool CCmpUnitMotion::IsTargetRangeReachable(entity_id_t target, entity_pos_t minRange, entity_pos_t maxRange)
1849 : {
1850 0 : CmpPtr<ICmpPosition> cmpPosition(GetEntityHandle());
1851 0 : if (!cmpPosition || !cmpPosition->IsInWorld())
1852 0 : return false;
1853 :
1854 0 : MoveRequest request(target, minRange, maxRange);
1855 0 : PathGoal goal;
1856 0 : if (!ComputeGoal(goal, request))
1857 0 : return false;
1858 :
1859 0 : CmpPtr<ICmpPathfinder> cmpPathfinder(GetSimContext(), SYSTEM_ENTITY);
1860 0 : CFixedVector2D pos = cmpPosition->GetPosition2D();
1861 0 : return cmpPathfinder->IsGoalReachable(pos.X, pos.Y, goal, m_PassClass);
1862 : }
1863 :
1864 :
1865 0 : void CCmpUnitMotion::RenderPath(const WaypointPath& path, std::vector<SOverlayLine>& lines, CColor color)
1866 : {
1867 0 : bool floating = false;
1868 0 : CmpPtr<ICmpPosition> cmpPosition(GetEntityHandle());
1869 0 : if (cmpPosition)
1870 0 : floating = cmpPosition->CanFloat();
1871 :
1872 0 : lines.clear();
1873 0 : std::vector<float> waypointCoords;
1874 0 : for (size_t i = 0; i < path.m_Waypoints.size(); ++i)
1875 : {
1876 0 : float x = path.m_Waypoints[i].x.ToFloat();
1877 0 : float z = path.m_Waypoints[i].z.ToFloat();
1878 0 : waypointCoords.push_back(x);
1879 0 : waypointCoords.push_back(z);
1880 0 : lines.push_back(SOverlayLine());
1881 0 : lines.back().m_Color = color;
1882 0 : SimRender::ConstructSquareOnGround(GetSimContext(), x, z, 1.0f, 1.0f, 0.0f, lines.back(), floating);
1883 : }
1884 0 : float x = cmpPosition->GetPosition2D().X.ToFloat();
1885 0 : float z = cmpPosition->GetPosition2D().Y.ToFloat();
1886 0 : waypointCoords.push_back(x);
1887 0 : waypointCoords.push_back(z);
1888 0 : lines.push_back(SOverlayLine());
1889 0 : lines.back().m_Color = color;
1890 0 : SimRender::ConstructLineOnGround(GetSimContext(), waypointCoords, lines.back(), floating);
1891 :
1892 0 : }
1893 :
1894 0 : void CCmpUnitMotion::RenderSubmit(SceneCollector& collector)
1895 : {
1896 0 : if (!m_DebugOverlayEnabled)
1897 0 : return;
1898 :
1899 0 : RenderPath(m_LongPath, m_DebugOverlayLongPathLines, OVERLAY_COLOR_LONG_PATH);
1900 0 : RenderPath(m_ShortPath, m_DebugOverlayShortPathLines, OVERLAY_COLOR_SHORT_PATH);
1901 :
1902 0 : for (size_t i = 0; i < m_DebugOverlayLongPathLines.size(); ++i)
1903 0 : collector.Submit(&m_DebugOverlayLongPathLines[i]);
1904 :
1905 0 : for (size_t i = 0; i < m_DebugOverlayShortPathLines.size(); ++i)
1906 0 : collector.Submit(&m_DebugOverlayShortPathLines[i]);
1907 : }
1908 :
1909 : #endif // INCLUDED_CCMPUNITMOTION
|
