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