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 : #include "precompiled.h"
19 :
20 : #include "CCmpUnitMotion.h"
21 : #include "CCmpUnitMotionManager.h"
22 :
23 : #include "maths/MathUtil.h"
24 : #include "ps/CLogger.h"
25 : #include "ps/Profile.h"
26 :
27 : #include <algorithm>
28 : #include <limits>
29 : #include <unordered_set>
30 : #include <vector>
31 :
32 : #define DEBUG_STATS 0
33 : #define DEBUG_RENDER 0
34 : #define DEBUG_RENDER_ALL_PUSH 0
35 :
36 : // NB: this TU contains the CCmpUnitMotion/CCmpUnitMotionManager couple.
37 : // In practice, UnitMotionManager functions need access to the full implementation of UnitMotion,
38 : // but UnitMotion needs access to MotionState (defined in UnitMotionManager).
39 : // To avoid inclusion issues, implementation of UnitMotionManager that uses UnitMotion is here.
40 :
41 : namespace {
42 : /**
43 : * Units push within their square and neighboring squares (except diagonals). This is the size of each square (in meters).
44 : * I have tested grid sizes from 10 up to 80 and overall it made little difference to the performance,
45 : * mostly, I suspect, because pushing is generally dwarfed by regular motion costs.
46 : * However, the algorithm remains n^2 in comparisons so it's probably best to err on the side of smaller grids, which will have lower spikes.
47 : * The balancing act is between comparisons, unordered_set insertions and unordered_set iterations.
48 : * For these reasons, a value of 20 which is rather small but not overly so was chosen.
49 : */
50 : constexpr int PUSHING_GRID_SIZE = 20;
51 :
52 : /**
53 : * For pushing, treat the clearances as a circle - they're defined as squares,
54 : * so we'll take the circumscribing square (approximately).
55 : * Clerances are also full-width instead of half, so we want to divide by two. sqrt(2)/2 is about 0.71 < 5/7.
56 : */
57 : constexpr entity_pos_t PUSHING_CORRECTION = entity_pos_t::FromFraction(5, 7);
58 :
59 : /**
60 : * Arbitrary constant used to reduce pushing to levels that won't break physics for our turn length.
61 : */
62 : constexpr int PUSHING_REDUCTION_FACTOR = 2;
63 :
64 : /**
65 : * Maximum distance-related multiplier.
66 : * NB: this value interacts with the "minimal pushing" force,
67 : * as two perfectly overlapping units exert MAX_DISTANCE_FACTOR * Turn length in ms / REDUCTION_FACTOR
68 : * of force on each other each turn. If this is below the minimal pushing force, any 2 units can entirely overlap.
69 : */
70 : constexpr entity_pos_t MAX_DISTANCE_FACTOR = entity_pos_t::FromFraction(5, 2);
71 :
72 : /**
73 : * Maximum pushing multiplier for a single push calculation.
74 : * This exists for numerical stability of the system between a lightweight and a heavy unit.
75 : */
76 : constexpr int MAX_PUSHING_MULTIPLIER = 4;
77 :
78 : /**
79 : * When two units collide, if their movement dot product is below this value, give them a perpendicular nudge instead of trying to push in the regular way.
80 : */
81 : constexpr entity_pos_t PERPENDICULAR_NUDGE_THRESHOLD = entity_pos_t::FromFraction(-1, 10);
82 :
83 : /**
84 : * Pushing is dampened by pushing pressure, but this is capped so that units still get pushed.
85 : */
86 : constexpr int MAX_PUSH_DAMPING_PRESSURE = 160;
87 : static_assert(MAX_PUSH_DAMPING_PRESSURE < CCmpUnitMotionManager::MAX_PRESSURE);
88 :
89 : /**
90 : * When units are obstructed because they're being pushed away from where they want to go,
91 : * raise the pushing pressure to at least this value.
92 : */
93 : constexpr int MIN_PRESSURE_IF_OBSTRUCTED = 80;
94 :
95 : /**
96 : * These two numbers are used to calculate pushing pressure between two units.
97 : */
98 : constexpr entity_pos_t PRESSURE_STATIC_FACTOR = entity_pos_t::FromInt(2);
99 : constexpr int PRESSURE_DISTANCE_FACTOR = 5;
100 : }
101 :
102 : #if DEBUG_RENDER
103 : #include "maths/Frustum.h"
104 :
105 : void RenderDebugOverlay(SceneCollector& collector, const CFrustum& frustum, bool culling);
106 :
107 : struct SDebugData {
108 : std::vector<SOverlaySphere> m_Spheres;
109 : std::vector<SOverlayLine> m_Lines;
110 : std::vector<SOverlayQuad> m_Quads;
111 : } debugDataMotionMgr;
112 : #endif
113 :
114 0 : CCmpUnitMotionManager::MotionState::MotionState(ICmpPosition* cmpPos, CCmpUnitMotion* cmpMotion)
115 0 : : cmpPosition(cmpPos), cmpUnitMotion(cmpMotion)
116 : {
117 : static_assert(MAX_PRESSURE <= std::numeric_limits<decltype(pushingPressure)>::max(), "MAX_PRESSURE is higher than the maximum value of the underlying type.");
118 0 : }
119 :
120 116 : void CCmpUnitMotionManager::ClassInit(CComponentManager& componentManager)
121 : {
122 116 : componentManager.SubscribeToMessageType(MT_Deserialized);
123 116 : componentManager.SubscribeToMessageType(MT_TerrainChanged);
124 116 : componentManager.SubscribeToMessageType(MT_TurnStart);
125 116 : componentManager.SubscribeToMessageType(MT_Update_Final);
126 116 : componentManager.SubscribeToMessageType(MT_Update_MotionUnit);
127 116 : componentManager.SubscribeToMessageType(MT_Update_MotionFormation);
128 : #if DEBUG_RENDER
129 : componentManager.SubscribeToMessageType(MT_RenderSubmit);
130 : #endif
131 116 : }
132 :
133 1 : void CCmpUnitMotionManager::HandleMessage(const CMessage& msg, bool UNUSED(global))
134 : {
135 1 : switch (msg.GetType())
136 : {
137 0 : case MT_TerrainChanged:
138 : {
139 0 : CmpPtr<ICmpTerrain> cmpTerrain(GetSystemEntity());
140 0 : if (cmpTerrain->GetVerticesPerSide() != m_MovingUnits.width())
141 0 : ResetSubdivisions();
142 0 : break;
143 : }
144 1 : case MT_TurnStart:
145 : {
146 1 : OnTurnStart();
147 1 : break;
148 : }
149 0 : case MT_Update_MotionFormation:
150 : {
151 0 : fixed dt = static_cast<const CMessageUpdate_MotionFormation&>(msg).turnLength;
152 0 : m_ComputingMotion = true;
153 0 : MoveFormations(dt);
154 0 : m_ComputingMotion = false;
155 0 : break;
156 : }
157 0 : case MT_Update_MotionUnit:
158 : {
159 0 : fixed dt = static_cast<const CMessageUpdate_MotionUnit&>(msg).turnLength;
160 0 : m_ComputingMotion = true;
161 0 : MoveUnits(dt);
162 0 : m_ComputingMotion = false;
163 0 : break;
164 : }
165 0 : case MT_Deserialized:
166 : {
167 0 : OnDeserialized();
168 0 : break;
169 : }
170 : #if DEBUG_RENDER
171 : case MT_RenderSubmit:
172 : {
173 : const CMessageRenderSubmit& msgData = static_cast<const CMessageRenderSubmit&> (msg);
174 : RenderDebugOverlay(msgData.collector, msgData.frustum, msgData.culling);
175 : break;
176 : }
177 : #endif
178 : }
179 1 : }
180 3 : void CCmpUnitMotionManager::Init(const CParamNode&)
181 : {
182 : // Load some data - see CCmpPathfinder.xml.
183 : // This assumes the pathfinder component is initialised first and registers the validator.
184 : // TODO: there seems to be no real reason why we could not register a 'system' entity somewhere instead.
185 6 : CParamNode externalParamNode;
186 3 : CParamNode::LoadXML(externalParamNode, L"simulation/data/pathfinder.xml", "pathfinder");
187 6 : CParamNode pushingNode = externalParamNode.GetChild("Pathfinder").GetChild("Pushing");
188 :
189 : // NB: all values are given sane default, but they are not treated as optional in the schema,
190 : // so the XML file is the reference.
191 :
192 : {
193 6 : const CParamNode spread = pushingNode.GetChild("MovingSpread");
194 3 : if (spread.IsOk())
195 : {
196 0 : m_MovingPushingSpread = Clamp(spread.ToFixed(), entity_pos_t::Zero(), entity_pos_t::FromInt(1));
197 0 : if (m_MovingPushingSpread != spread.ToFixed())
198 0 : LOGWARNING("Moving pushing spread was clamped to the 0-1 range.");
199 : }
200 : else
201 3 : m_MovingPushingSpread = entity_pos_t::FromInt(5) / 8;
202 : }
203 :
204 : {
205 6 : const CParamNode spread = pushingNode.GetChild("StaticSpread");
206 3 : if (spread.IsOk())
207 : {
208 0 : m_StaticPushingSpread = Clamp(spread.ToFixed(), entity_pos_t::Zero(), entity_pos_t::FromInt(1));
209 0 : if (m_StaticPushingSpread != spread.ToFixed())
210 0 : LOGWARNING("Static pushing spread was clamped to the 0-1 range.");
211 : }
212 : else
213 3 : m_StaticPushingSpread = entity_pos_t::FromInt(5) / 8;
214 : }
215 :
216 6 : const CParamNode radius = pushingNode.GetChild("Radius");
217 3 : if (radius.IsOk())
218 : {
219 0 : m_PushingRadiusMultiplier = radius.ToFixed();
220 0 : if (m_PushingRadiusMultiplier < entity_pos_t::Zero())
221 : {
222 0 : LOGWARNING("Pushing radius multiplier cannot be below 0. De-activating pushing but 'pathfinder.xml' should be updated.");
223 0 : m_PushingRadiusMultiplier = entity_pos_t::Zero();
224 : }
225 : // No upper value, but things won't behave sanely if values are too high.
226 : }
227 : else
228 3 : m_PushingRadiusMultiplier = entity_pos_t::FromInt(8) / 5;
229 :
230 6 : const CParamNode minForce = pushingNode.GetChild("MinimalForce");
231 3 : if (minForce.IsOk())
232 0 : m_MinimalPushing = minForce.ToFixed();
233 : else
234 3 : m_MinimalPushing = entity_pos_t::FromInt(2) / 10;
235 :
236 6 : const CParamNode movingExt = pushingNode.GetChild("MovingExtension");
237 6 : const CParamNode staticExt = pushingNode.GetChild("StaticExtension");
238 3 : if (movingExt.IsOk() && staticExt.IsOk())
239 : {
240 0 : m_MovingPushExtension = movingExt.ToFixed();
241 0 : m_StaticPushExtension = staticExt.ToFixed();
242 : }
243 : else
244 : {
245 3 : m_MovingPushExtension = entity_pos_t::FromInt(5) / 2;
246 3 : m_StaticPushExtension = entity_pos_t::FromInt(2);
247 : }
248 :
249 6 : const CParamNode pressureStrength = pushingNode.GetChild("PressureStrength");
250 3 : if (pressureStrength.IsOk())
251 : {
252 0 : m_PushingPressureStrength = pressureStrength.ToFixed();
253 0 : if (m_PushingPressureStrength < entity_pos_t::Zero())
254 : {
255 0 : LOGWARNING("Pushing pressure strength cannot be below 0. 'pathfinder.xml' should be updated.");
256 0 : m_PushingPressureStrength = entity_pos_t::Zero();
257 : }
258 : // No upper value, but things won't behave sanely if values are too high.
259 : }
260 : else
261 3 : m_PushingPressureStrength = entity_pos_t::FromInt(1);
262 :
263 6 : const CParamNode pushingPressure = pushingNode.GetChild("PressureDecay");
264 3 : if (pushingPressure.IsOk())
265 : {
266 0 : m_PushingPressureDecay = Clamp(pushingPressure.ToFixed(), entity_pos_t::Zero(), entity_pos_t::FromInt(1));
267 0 : if (m_PushingPressureDecay != pushingPressure.ToFixed())
268 0 : LOGWARNING("Pushing pressure decay was clamped to the 0-1 range.");
269 : }
270 : else
271 3 : m_PushingPressureDecay = entity_pos_t::FromInt(6) / 10;
272 :
273 3 : }
274 :
275 : template<>
276 : struct SerializeHelper<CCmpUnitMotionManager::MotionState>
277 : {
278 : template<typename S>
279 0 : void operator()(S& serialize, const char* UNUSED(name), Serialize::qualify<S, CCmpUnitMotionManager::MotionState> value)
280 : {
281 0 : Serializer(serialize, "pushing pressure", value.pushingPressure);
282 0 : }
283 : };
284 :
285 : template<>
286 : struct SerializeHelper<EntityMap<CCmpUnitMotionManager::MotionState>>
287 : {
288 0 : void operator()(ISerializer& serialize, const char* UNUSED(name), EntityMap<CCmpUnitMotionManager::MotionState>& value)
289 : {
290 : // Serialize manually, we don't have a default-constructor for deserialization.
291 0 : Serializer(serialize, "size", static_cast<u32>(value.size()));
292 0 : for (EntityMap<CCmpUnitMotionManager::MotionState>::iterator it = value.begin(); it != value.end(); ++it)
293 : {
294 0 : Serializer(serialize, "ent id", it->first);
295 0 : Serializer(serialize, "state", it->second);
296 : }
297 0 : }
298 :
299 0 : void operator()(IDeserializer& deserialize, const char* UNUSED(name), EntityMap<CCmpUnitMotionManager::MotionState>& value)
300 : {
301 0 : u32 units = 0;
302 0 : Serializer(deserialize, "size", units);
303 0 : for (u32 i = 0; i < units; ++i)
304 : {
305 0 : entity_id_t ent = INVALID_ENTITY;
306 0 : Serializer(deserialize, "ent id", ent);
307 : // Insert an invalid motion state, will be cleared up in MT_Deserialized.
308 0 : CCmpUnitMotionManager::MotionState state(nullptr, nullptr);
309 0 : Serializer(deserialize, "state", state);
310 0 : value.insert(ent, state);
311 : }
312 0 : }
313 : };
314 :
315 0 : void CCmpUnitMotionManager::Serialize(ISerializer& serialize)
316 : {
317 0 : Serializer(serialize, "m_Units", m_Units);
318 0 : Serializer(serialize, "m_FormationControllers", m_FormationControllers);
319 0 : }
320 :
321 0 : void CCmpUnitMotionManager::Deserialize(const CParamNode& paramNode, IDeserializer& deserialize)
322 : {
323 0 : Init(paramNode);
324 0 : ResetSubdivisions();
325 0 : Serializer(deserialize, "m_Units", m_Units);
326 0 : Serializer(deserialize, "m_FormationControllers", m_FormationControllers);
327 0 : }
328 :
329 : /**
330 : * This deserialization process is rather ugly, but it's required to store some data in the motion states.
331 : * Ideally, the motion state would actually be CCmpUnitMotion themselves, but for data locality
332 : * (because our components are stored randomly on the heap right now) they're not.
333 : * If we ever change the simulation so that components could be registered by their managers and exposed,
334 : * then we could just use CCmpUnitMotion directly and clean this code uglyness.
335 : */
336 0 : void CCmpUnitMotionManager::OnDeserialized()
337 : {
338 : // Fetch the components now that they exist.
339 : // The rest of the data was already deserialized or will be reconstructed.
340 0 : for (EntityMap<MotionState>::iterator it = m_Units.begin(); it != m_Units.end(); ++it)
341 : {
342 0 : it->second.cmpPosition = static_cast<ICmpPosition*>(QueryInterface(GetSimContext(), it->first, IID_Position));
343 : // We can know for a fact that these are CCmpUnitMotion because those are the ones registering with us
344 : // (and to ensure that they pass a CCmpUnitMotion pointer when registering).
345 0 : it->second.cmpUnitMotion = static_cast<CCmpUnitMotion*>(static_cast<ICmpUnitMotion*>(QueryInterface(GetSimContext(), it->first, IID_UnitMotion)));
346 : }
347 0 : for (EntityMap<MotionState>::iterator it = m_FormationControllers.begin(); it != m_FormationControllers.end(); ++it)
348 : {
349 0 : it->second.cmpPosition = static_cast<ICmpPosition*>(QueryInterface(GetSimContext(), it->first, IID_Position));
350 0 : it->second.cmpUnitMotion = static_cast<CCmpUnitMotion*>(static_cast<ICmpUnitMotion*>(QueryInterface(GetSimContext(), it->first, IID_UnitMotion)));
351 : }
352 0 : }
353 :
354 0 : void CCmpUnitMotionManager::ResetSubdivisions()
355 : {
356 0 : CmpPtr<ICmpTerrain> cmpTerrain(GetSystemEntity());
357 0 : if (!cmpTerrain)
358 0 : return;
359 :
360 0 : size_t size = cmpTerrain->GetMapSize();
361 0 : u16 gridSquareSize = static_cast<u16>(size / PUSHING_GRID_SIZE + 1);
362 0 : m_MovingUnits.resize(gridSquareSize, gridSquareSize);
363 : }
364 :
365 0 : void CCmpUnitMotionManager::Register(CCmpUnitMotion* component, entity_id_t ent, bool formationController)
366 : {
367 0 : MotionState state(static_cast<ICmpPosition*>(QueryInterface(GetSimContext(), ent, IID_Position)), component);
368 0 : if (!formationController)
369 0 : m_Units.insert(ent, state);
370 : else
371 0 : m_FormationControllers.insert(ent, state);
372 0 : }
373 :
374 0 : void CCmpUnitMotionManager::Unregister(entity_id_t ent)
375 : {
376 0 : EntityMap<MotionState>::iterator it = m_Units.find(ent);
377 0 : if (it != m_Units.end())
378 : {
379 0 : m_Units.erase(it);
380 0 : return;
381 : }
382 0 : it = m_FormationControllers.find(ent);
383 0 : if (it != m_FormationControllers.end())
384 0 : m_FormationControllers.erase(it);
385 : }
386 :
387 1 : void CCmpUnitMotionManager::OnTurnStart()
388 : {
389 1 : for (EntityMap<MotionState>::value_type& data : m_FormationControllers)
390 0 : data.second.cmpUnitMotion->OnTurnStart();
391 :
392 1 : for (EntityMap<MotionState>::value_type& data : m_Units)
393 0 : data.second.cmpUnitMotion->OnTurnStart();
394 1 : }
395 :
396 0 : void CCmpUnitMotionManager::MoveUnits(fixed dt)
397 : {
398 0 : Move(m_Units, dt);
399 0 : }
400 :
401 0 : void CCmpUnitMotionManager::MoveFormations(fixed dt)
402 : {
403 0 : Move(m_FormationControllers, dt);
404 0 : }
405 :
406 0 : void CCmpUnitMotionManager::Move(EntityMap<MotionState>& ents, fixed dt)
407 : {
408 : #if DEBUG_RENDER
409 : debugDataMotionMgr.m_Spheres.clear();
410 : debugDataMotionMgr.m_Lines.clear();
411 : debugDataMotionMgr.m_Quads.clear();
412 : #endif
413 : #if DEBUG_STATS
414 : int comparisons = 0;
415 : double start = timer_Time();
416 : #endif
417 :
418 0 : PROFILE2("MotionMgr_Move");
419 0 : std::unordered_set<std::vector<EntityMap<MotionState>::iterator>*> assigned;
420 0 : for (EntityMap<MotionState>::iterator it = ents.begin(); it != ents.end(); ++it)
421 : {
422 0 : if (!it->second.cmpPosition->IsInWorld())
423 : {
424 0 : it->second.needUpdate = false;
425 0 : continue;
426 : }
427 : else
428 0 : it->second.cmpUnitMotion->PreMove(it->second);
429 0 : it->second.initialPos = it->second.cmpPosition->GetPosition2D();
430 0 : it->second.initialAngle = it->second.cmpPosition->GetRotation().Y;
431 0 : it->second.pos = it->second.initialPos;
432 0 : it->second.speed = it->second.cmpUnitMotion->GetCurrentSpeed();
433 0 : it->second.angle = it->second.initialAngle;
434 0 : ENSURE(it->second.pos.X.ToInt_RoundToZero() / PUSHING_GRID_SIZE < m_MovingUnits.width() &&
435 : it->second.pos.Y.ToInt_RoundToZero() / PUSHING_GRID_SIZE < m_MovingUnits.height());
436 : std::vector<EntityMap<MotionState>::iterator>& subdiv = m_MovingUnits.get(
437 0 : it->second.pos.X.ToInt_RoundToZero() / PUSHING_GRID_SIZE,
438 0 : it->second.pos.Y.ToInt_RoundToZero() / PUSHING_GRID_SIZE
439 0 : );
440 0 : subdiv.emplace_back(it);
441 0 : assigned.emplace(&subdiv);
442 : }
443 :
444 0 : for (std::vector<EntityMap<MotionState>::iterator>* vec : assigned)
445 : {
446 : #if DEBUG_RENDER
447 : {
448 : SOverlayLine gridL;
449 : auto it = (*vec)[0];
450 : gridL.PushCoords(CVector3D(it->second.pos.X.ToInt_RoundToZero() / PUSHING_GRID_SIZE * PUSHING_GRID_SIZE,
451 : it->second.cmpPosition->GetHeightFixed().ToDouble() + 2.f,
452 : it->second.pos.Y.ToInt_RoundToZero() / PUSHING_GRID_SIZE * PUSHING_GRID_SIZE));
453 : gridL.PushCoords(CVector3D(it->second.pos.X.ToInt_RoundToZero() / PUSHING_GRID_SIZE * PUSHING_GRID_SIZE + PUSHING_GRID_SIZE,
454 : it->second.cmpPosition->GetHeightFixed().ToDouble() + 2.f,
455 : it->second.pos.Y.ToInt_RoundToZero() / PUSHING_GRID_SIZE * PUSHING_GRID_SIZE));
456 : gridL.PushCoords(CVector3D(it->second.pos.X.ToInt_RoundToZero() / PUSHING_GRID_SIZE * PUSHING_GRID_SIZE + PUSHING_GRID_SIZE,
457 : it->second.cmpPosition->GetHeightFixed().ToDouble() + 2.f,
458 : it->second.pos.Y.ToInt_RoundToZero() / PUSHING_GRID_SIZE * PUSHING_GRID_SIZE + PUSHING_GRID_SIZE));
459 : gridL.PushCoords(CVector3D(it->second.pos.X.ToInt_RoundToZero() / PUSHING_GRID_SIZE * PUSHING_GRID_SIZE,
460 : it->second.cmpPosition->GetHeightFixed().ToDouble() + 2.f,
461 : it->second.pos.Y.ToInt_RoundToZero() / PUSHING_GRID_SIZE * PUSHING_GRID_SIZE + PUSHING_GRID_SIZE));
462 : gridL.PushCoords(CVector3D(it->second.pos.X.ToInt_RoundToZero() / PUSHING_GRID_SIZE * PUSHING_GRID_SIZE,
463 : it->second.cmpPosition->GetHeightFixed().ToDouble() + 2.f,
464 : it->second.pos.Y.ToInt_RoundToZero() / PUSHING_GRID_SIZE * PUSHING_GRID_SIZE));
465 : gridL.m_Color = CColor(1, 1, 0, 1);
466 : debugDataMotionMgr.m_Lines.push_back(gridL);
467 : }
468 : #endif
469 0 : for (EntityMap<MotionState>::iterator& it : *vec)
470 : {
471 0 : if (it->second.needUpdate)
472 0 : it->second.cmpUnitMotion->Move(it->second, dt);
473 : // Decay pressure after moving so we can get the full 0-MAX_PRESSURE range of values.
474 0 : it->second.pushingPressure = (m_PushingPressureDecay * it->second.pushingPressure).ToInt_RoundToZero();
475 : }
476 : }
477 :
478 : // Skip pushing entirely if the radius is 0
479 0 : if (&ents == &m_Units && IsPushingActivated())
480 : {
481 0 : PROFILE2("MotionMgr_Pushing");
482 0 : for (std::vector<EntityMap<MotionState>::iterator>* vec : assigned)
483 : {
484 0 : ENSURE(!vec->empty());
485 0 : std::vector< std::vector<EntityMap<MotionState>::iterator>* > consider = { vec };
486 :
487 0 : int x = (*vec)[0]->second.pos.X.ToInt_RoundToZero() / PUSHING_GRID_SIZE;
488 0 : int z = (*vec)[0]->second.pos.Y.ToInt_RoundToZero() / PUSHING_GRID_SIZE;
489 0 : if (x + 1 < m_MovingUnits.width())
490 0 : consider.push_back(&m_MovingUnits.get(x + 1, z));
491 0 : if (x > 0)
492 0 : consider.push_back(&m_MovingUnits.get(x - 1, z));
493 0 : if (z + 1 < m_MovingUnits.height())
494 0 : consider.push_back(&m_MovingUnits.get(x, z + 1));
495 0 : if (z > 0)
496 0 : consider.push_back(&m_MovingUnits.get(x, z - 1));
497 :
498 0 : for (EntityMap<MotionState>::iterator& it : *vec)
499 : {
500 0 : if (it->second.ignore)
501 0 : continue;
502 :
503 : #if DEBUG_RENDER
504 : // Plop a sphere at the unit end-pos.
505 : {
506 : SOverlaySphere sph;
507 : sph.m_Center = CVector3D(it->second.pos.X.ToDouble(), it->second.cmpPosition->GetHeightFixed().ToDouble() + 13.f, it->second.pos.Y.ToDouble());
508 : sph.m_Radius = it->second.cmpUnitMotion->m_Clearance.Multiply(PUSHING_CORRECTION).ToDouble();
509 : // Color the sphere: the redder, the more 'bogged down' it is.
510 : sph.m_Color = CColor(it->second.pushingPressure / static_cast<float>(MAX_PRESSURE), 0, 0, 1);
511 : debugDataMotionMgr.m_Spheres.push_back(sph);
512 : }
513 : /* Show the pushing sphere, kinda unreadable.
514 : {
515 : SOverlaySphere sph;
516 : sph.m_Center = CVector3D(it->second.pos.X.ToDouble(), it->second.cmpPosition->GetHeightFixed().ToDouble() + 13.f, it->second.pos.Y.ToDouble());
517 : sph.m_Radius = (it->second.cmpUnitMotion->m_Clearance.Multiply(PUSHING_CORRECTION).Multiply(m_PushingRadiusMultiplier) + (it->second.isMoving ? m_StaticPushExtension : m_MovingPushExtension)).ToDouble();
518 : // Color the sphere: the redder, the more 'bogged down' it is.
519 : sph.m_Color = CColor(it->second.pushingPressure / static_cast<float>(MAX_PRESSURE), 0, 0, 0.1);
520 : debugDataMotionMgr.m_Spheres.push_back(sph);
521 : }*/
522 : // Show the travel over this turn.
523 : SOverlayLine line;
524 : line.PushCoords(CVector3D(it->second.initialPos.X.ToDouble(),
525 : it->second.cmpPosition->GetHeightFixed().ToDouble() + 13.f,
526 : it->second.initialPos.Y.ToDouble()));
527 : line.PushCoords(CVector3D(it->second.pos.X.ToDouble(),
528 : it->second.cmpPosition->GetHeightFixed().ToDouble() + 13.f,
529 : it->second.pos.Y.ToDouble()));
530 : line.m_Color = CColor(1, 0, 1, 0.5);
531 : debugDataMotionMgr.m_Lines.push_back(line);
532 : #endif
533 0 : for (std::vector<EntityMap<MotionState>::iterator>* vec2 : consider)
534 0 : for (EntityMap<MotionState>::iterator& it2 : *vec2)
535 0 : if (it->first < it2->first && !it2->second.ignore)
536 : {
537 : #if DEBUG_STATS
538 : ++comparisons;
539 : #endif
540 0 : Push(*it, *it2, dt);
541 : }
542 : }
543 : }
544 : }
545 :
546 0 : if (IsPushingActivated())
547 : {
548 0 : PROFILE2("MotionMgr_PushAdjust");
549 0 : CmpPtr<ICmpPathfinder> cmpPathfinder(GetSystemEntity());
550 0 : for (std::vector<EntityMap<MotionState>::iterator>* vec : assigned)
551 : {
552 0 : for (EntityMap<MotionState>::iterator& it : *vec)
553 : {
554 :
555 0 : if (!it->second.needUpdate || it->second.ignore)
556 0 : continue;
557 :
558 : #if DEBUG_RENDER
559 : SOverlayLine line;
560 : line.PushCoords(CVector3D(it->second.pos.X.ToDouble(),
561 : it->second.cmpPosition->GetHeightFixed().ToDouble() + 15.1f ,
562 : it->second.pos.Y.ToDouble()));
563 : line.PushCoords(CVector3D(it->second.pos.X.ToDouble() + it->second.push.X.ToDouble() * 10.f,
564 : it->second.cmpPosition->GetHeightFixed().ToDouble() + 15.1f ,
565 : it->second.pos.Y.ToDouble() + it->second.push.Y.ToDouble() * 10.f));
566 : line.m_Thickness = 0.05f;
567 : #endif
568 :
569 : // Only apply pushing if the effect is significant enough.
570 0 : if (it->second.push.CompareLength(m_MinimalPushing) <= 0)
571 : {
572 : #if DEBUG_RENDER
573 : line.m_Color = CColor(1, 1, 0, 0.6);
574 : debugDataMotionMgr.m_Lines.push_back(line);
575 : #endif
576 0 : it->second.push = CFixedVector2D();
577 0 : continue;
578 : }
579 :
580 : // If there was an attempt at movement, and we're getting pushed significantly and
581 : // away from where we'd like to go (measured by a low dot product)
582 : // then mark the unit as obstructed, but push anyways.
583 : // (this helps units stop earlier in many situations in a realistic-ish manner).
584 0 : if (it->second.pos != it->second.initialPos
585 0 : && (it->second.pos - it->second.initialPos).Dot(it->second.pos + it->second.push - it->second.initialPos) < entity_pos_t::FromInt(1)/2 && it->second.pushingPressure > 30)
586 : {
587 0 : it->second.wasObstructed = true;
588 0 : it->second.pushingPressure = std::max<uint8_t>(MIN_PRESSURE_IF_OBSTRUCTED, it->second.pushingPressure);
589 : // Push anyways.
590 : }
591 : #if DEBUG_RENDER
592 : if (it->second.wasObstructed)
593 : line.m_Color = CColor(1, 0, 0, 1);
594 : else
595 : line.m_Color = CColor(0, 1, 0, 1);
596 : debugDataMotionMgr.m_Lines.push_back(line);
597 : #endif
598 : // Dampen the pushing by the current pushing pressure
599 : // (but prevent full dampening so that clumped units still get unclumped).
600 0 : it->second.push = it->second.push * (MAX_PRESSURE - std::min<uint8_t>(MAX_PUSH_DAMPING_PRESSURE, it->second.pushingPressure)) / MAX_PRESSURE;
601 :
602 : // Prevent pushed units from crossing uncrossable boundaries
603 : // (we can assume that normal movement didn't push units into impassable terrain).
604 0 : if ((it->second.push.X != entity_pos_t::Zero() || it->second.push.Y != entity_pos_t::Zero()) &&
605 0 : !cmpPathfinder->CheckMovement(it->second.cmpUnitMotion->GetObstructionFilter(),
606 0 : it->second.pos.X, it->second.pos.Y,
607 0 : it->second.pos.X + it->second.push.X, it->second.pos.Y + it->second.push.Y,
608 0 : it->second.cmpUnitMotion->m_Clearance,
609 0 : it->second.cmpUnitMotion->m_PassClass))
610 : {
611 : // Mark them as obstructed - this could possibly be optimised
612 : // perhaps it'd make more sense to mark the pushers as blocked.
613 0 : it->second.wasObstructed = true;
614 0 : it->second.wentStraight = false;
615 0 : it->second.push = CFixedVector2D();
616 0 : continue;
617 : }
618 0 : it->second.pos += it->second.push;
619 0 : it->second.push = CFixedVector2D();
620 : }
621 : }
622 : }
623 : {
624 0 : PROFILE2("MotionMgr_PostMove");
625 0 : for (EntityMap<MotionState>::value_type& data : ents)
626 : {
627 0 : if (!data.second.needUpdate)
628 0 : continue;
629 0 : data.second.cmpUnitMotion->PostMove(data.second, dt);
630 : }
631 : }
632 : #if DEBUG_STATS
633 : int size = 0;
634 : for (std::vector<EntityMap<MotionState>::iterator>* vec : assigned)
635 : size += vec->size();
636 : double time = timer_Time() - start;
637 : if (comparisons > 0)
638 : printf(">> %i comparisons over %li grids, %f units per grid in %f secs\n", comparisons, assigned.size(), size / (float)(assigned.size()), time);
639 : #endif
640 0 : for (std::vector<EntityMap<MotionState>::iterator>* vec : assigned)
641 0 : vec->clear();
642 0 : }
643 :
644 : // TODO: ought to better simulate in-flight pushing, e.g. if units would cross in-between turns.
645 0 : void CCmpUnitMotionManager::Push(EntityMap<MotionState>::value_type& a, EntityMap<MotionState>::value_type& b, fixed dt)
646 : {
647 : // The hard problem for pushing is knowing when to actually use the pathfinder to go around unpushable obstacles.
648 : // For simplicitly, the current logic separates moving & stopped entities:
649 : // moving entities will push moving entities, but not stopped ones, and vice-versa.
650 : // this still delivers most of the value of pushing, without a lot of the complexity.
651 0 : int movingPush = a.second.isMoving + b.second.isMoving;
652 :
653 : // Exception: units in the same control group (i.e. the same formation) never push farther than themselves
654 : // and are also allowed to push idle units (obstructions are ignored within formations,
655 : // so pushing idle units makes one member crossing the formation look better).
656 0 : bool sameControlGroup = a.second.controlGroup != INVALID_ENTITY && a.second.controlGroup == b.second.controlGroup;
657 0 : if (sameControlGroup)
658 0 : movingPush = 0;
659 :
660 0 : if (movingPush == 1)
661 0 : return;
662 :
663 0 : entity_pos_t combinedClearance = (a.second.cmpUnitMotion->m_Clearance + b.second.cmpUnitMotion->m_Clearance).Multiply(PUSHING_CORRECTION);
664 0 : entity_pos_t maxDist = combinedClearance;
665 0 : if (!sameControlGroup)
666 0 : maxDist = combinedClearance.Multiply(m_PushingRadiusMultiplier) + (movingPush ? m_MovingPushExtension : m_StaticPushExtension);
667 0 : combinedClearance = maxDist.Multiply(movingPush ? m_MovingPushingSpread : m_StaticPushingSpread);
668 :
669 : // Compare the average position of the two units over the turn - this makes overall behaviour better,
670 : // as we really care more about units that end up either crossing paths or staying together.
671 0 : CFixedVector2D offset = ((a.second.pos + a.second.initialPos) - (b.second.pos + b.second.initialPos)) / 2;
672 :
673 : #if DEBUG_RENDER
674 : SOverlayLine line;
675 : line.PushCoords(CVector3D(a.second.pos.X.ToDouble(),
676 : a.second.cmpPosition->GetHeightFixed().ToDouble() + 8,
677 : a.second.pos.Y.ToDouble()));
678 : line.PushCoords(CVector3D(b.second.pos.X.ToDouble(),
679 : b.second.cmpPosition->GetHeightFixed().ToDouble() + 8,
680 : b.second.pos.Y.ToDouble()));
681 : if (offset.CompareLength(maxDist) > 0)
682 : {
683 : #if DEBUG_RENDER_ALL_PUSH
684 : line.m_Thickness = 0.01f;
685 : line.m_Color = CColor(0, 0, 1, 0.4);
686 : debugDataMotionMgr.m_Lines.push_back(line);
687 : // then will return
688 : #endif
689 : }
690 : #endif
691 0 : if (offset.CompareLength(maxDist) > 0)
692 0 : return;
693 :
694 0 : entity_pos_t offsetLength;
695 :
696 : // If the units appear to have crossed paths, give them a strong perpendicular nudge.
697 : // Ideally, this will make them look like they avoided each other.
698 : // Worst case, either the collision detection isn't picked up or they'll end up bogged down.
699 : // NB: the dot product mostly works because we used average positions earlier.
700 : // NB: this kinda works only because our turn lengths are large enough to make this relevant.
701 : // In an ideal world, we'd anticipate here instead.
702 : // Turn it off for formations - our current 'reforming' code is bad and leads to bad behaviour.
703 0 : if (!sameControlGroup && (a.second.pos - b.second.pos).Dot(a.second.initialPos - b.second.initialPos) < PERPENDICULAR_NUDGE_THRESHOLD)
704 : {
705 0 : CFixedVector2D posDelta = (a.second.pos - b.second.pos) - (a.second.initialPos - b.second.initialPos);
706 0 : CFixedVector2D perp = posDelta.Perpendicular();
707 : // Pick the best direction to avoid the target.
708 0 : if (offset.Dot(perp) < (-offset).Dot(perp))
709 0 : offset = -perp;
710 : else
711 0 : offset = perp;
712 0 : offsetLength = offset.Length();
713 0 : if (offsetLength > entity_pos_t::Epsilon() * 10)
714 : {
715 : // This needs to be a strong effect or it won't really work.
716 0 : offset.X = offset.X / offsetLength * 3;
717 0 : offset.Y = offset.Y / offsetLength * 3;
718 : }
719 0 : offsetLength = entity_pos_t::Zero();
720 : }
721 : else
722 : {
723 0 : offsetLength = offset.Length();
724 : // If the offset is small enough that precision would be problematic, pick an arbitrary vector instead.
725 0 : if (offsetLength <= entity_pos_t::Epsilon() * 10)
726 : {
727 : // Throw in some 'randomness' so that clumped units unclump more naturaslly.
728 0 : bool dir = a.first % 2;
729 0 : offset.X = entity_pos_t::FromInt(dir ? 1 : 0);
730 0 : offset.Y = entity_pos_t::FromInt(dir ? 0 : 1);
731 0 : offsetLength = entity_pos_t::Epsilon() * 10;
732 : }
733 : else
734 : {
735 0 : offset.X = offset.X / offsetLength;
736 0 : offset.Y = offset.Y / offsetLength;
737 : }
738 : }
739 :
740 : // The pushing distance factor is 1 at the spread-modified combined clearance, >1 up to MAX if the units 'overlap', < 1 otherwise.
741 0 : entity_pos_t distanceFactor = maxDist - combinedClearance;
742 : // Force units that overlap a lot to have the maximum factor.
743 0 : if (distanceFactor <= entity_pos_t::Zero() || offsetLength < combinedClearance / 2)
744 0 : distanceFactor = MAX_DISTANCE_FACTOR;
745 : else
746 0 : distanceFactor = Clamp((maxDist - offsetLength) / distanceFactor, entity_pos_t::Zero(), MAX_DISTANCE_FACTOR);
747 :
748 : // Mark both as needing an update so they actually get moved.
749 0 : a.second.needUpdate = true;
750 0 : b.second.needUpdate = true;
751 :
752 0 : CFixedVector2D pushingDir = offset.Multiply(distanceFactor);
753 :
754 : // These cannot be zero, checked in the schema.
755 0 : entity_pos_t aWeight = a.second.cmpUnitMotion->GetWeight();
756 0 : entity_pos_t bWeight = b.second.cmpUnitMotion->GetWeight();
757 :
758 : // Final corrections:
759 : // - divide by an arbitrary constant to avoid pushing too much.
760 : // - multiply by the weight ratio (limiting the maximum positive push for numerical accuracy).
761 0 : entity_pos_t timeFactor = dt / PUSHING_REDUCTION_FACTOR;
762 0 : entity_pos_t maxPushing = timeFactor * MAX_PUSHING_MULTIPLIER;
763 0 : a.second.push += pushingDir.Multiply(std::min(bWeight.MulDiv(timeFactor, aWeight), maxPushing));
764 0 : b.second.push -= pushingDir.Multiply(std::min(aWeight.MulDiv(timeFactor, bWeight), maxPushing));
765 :
766 : // Use a constant factor to get a more general slowdown in crowded area.
767 : // The distance factor heavily dampens units that are overlapping.
768 0 : int addedPressure = std::max(0, (PRESSURE_STATIC_FACTOR + (distanceFactor + entity_pos_t::FromInt(-2)/3) * PRESSURE_DISTANCE_FACTOR).Multiply(m_PushingPressureStrength).ToInt_RoundToZero());
769 0 : a.second.pushingPressure = std::min(MAX_PRESSURE, a.second.pushingPressure + addedPressure);
770 0 : b.second.pushingPressure = std::min(MAX_PRESSURE, b.second.pushingPressure + addedPressure);
771 :
772 : #if DEBUG_RENDER
773 : // Make the lines thicker if the force is stronger.
774 : line.m_Thickness = distanceFactor.ToDouble() / 10.0;
775 : line.m_Color = CColor(1, addedPressure / 20.f, 0, 0.8);
776 : debugDataMotionMgr.m_Lines.push_back(line);
777 : #endif
778 3 : }
779 :
780 : #if DEBUG_RENDER
781 : void RenderDebugOverlay(SceneCollector& collector, const CFrustum& frustum, bool UNUSED(culling))
782 : {
783 : for (SOverlaySphere& sph: debugDataMotionMgr.m_Spheres)
784 : if (frustum.IsSphereVisible(sph.m_Center, sph.m_Radius))
785 : collector.Submit(&sph);
786 : for (SOverlayLine& l: debugDataMotionMgr.m_Lines)
787 : if (frustum.IsPointVisible(l.m_Coords[0]) || frustum.IsPointVisible(l.m_Coords[1]))
788 : collector.Submit(&l);
789 : for (SOverlayQuad& quad: debugDataMotionMgr.m_Quads)
790 : collector.Submit(&quad);
791 : }
792 : #endif
793 :
794 : #undef DEBUG_STATS
795 : #undef DEBUG_RENDER
796 : #undef DEBUG_RENDER_ALL_PUSH
|
