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 "simulation2/system/Component.h"
21 : #include "ICmpFootprint.h"
22 :
23 : #include "ps/Profile.h"
24 : #include "simulation2/components/ICmpObstruction.h"
25 : #include "simulation2/components/ICmpObstructionManager.h"
26 : #include "simulation2/components/ICmpPathfinder.h"
27 : #include "simulation2/components/ICmpPosition.h"
28 : #include "simulation2/components/ICmpRallyPoint.h"
29 : #include "simulation2/components/ICmpUnitMotion.h"
30 : #include "simulation2/helpers/Geometry.h"
31 : #include "simulation2/MessageTypes.h"
32 : #include "maths/FixedVector2D.h"
33 :
34 0 : class CCmpFootprint final : public ICmpFootprint
35 : {
36 : public:
37 116 : static void ClassInit(CComponentManager& UNUSED(componentManager))
38 : {
39 116 : }
40 :
41 0 : DEFAULT_COMPONENT_ALLOCATOR(Footprint)
42 :
43 : EShape m_Shape;
44 : entity_pos_t m_Size0; // width/radius
45 : entity_pos_t m_Size1; // height/radius
46 : entity_pos_t m_Height;
47 : entity_pos_t m_MaxSpawnDistance;
48 :
49 116 : static std::string GetSchema()
50 : {
51 : return
52 : "<a:help>Approximation of the entity's shape, for collision detection and may be used for outline rendering or to determine selectable bounding box. "
53 : "Shapes are flat horizontal squares or circles, extended vertically to a given height.</a:help>"
54 : "<a:example>"
55 : "<Square width='3.0' height='3.0'/>"
56 : "<Height>0.0</Height>"
57 : "<MaxSpawnDistance>8</MaxSpawnDistance>"
58 : "</a:example>"
59 : "<a:example>"
60 : "<Circle radius='0.5'/>"
61 : "<Height>0.0</Height>"
62 : "<MaxSpawnDistance>8</MaxSpawnDistance>"
63 : "</a:example>"
64 : "<choice>"
65 : "<element name='Square' a:help='Set the footprint to a square of the given size'>"
66 : "<attribute name='width' a:help='Size of the footprint along the left/right direction (in metres)'>"
67 : "<data type='decimal'>"
68 : "<param name='minExclusive'>0.0</param>"
69 : "</data>"
70 : "</attribute>"
71 : "<attribute name='depth' a:help='Size of the footprint along the front/back direction (in metres)'>"
72 : "<data type='decimal'>"
73 : "<param name='minExclusive'>0.0</param>"
74 : "</data>"
75 : "</attribute>"
76 : "</element>"
77 : "<element name='Circle' a:help='Set the footprint to a circle of the given size'>"
78 : "<attribute name='radius' a:help='Radius of the footprint (in metres)'>"
79 : "<data type='decimal'>"
80 : "<param name='minExclusive'>0.0</param>"
81 : "</data>"
82 : "</attribute>"
83 : "</element>"
84 : "</choice>"
85 : "<element name='Height' a:help='Vertical extent of the footprint (in metres)'>"
86 : "<ref name='nonNegativeDecimal'/>"
87 : "</element>"
88 : "<optional>"
89 : "<element name='MaxSpawnDistance' a:help='Farthest distance units can spawn away from the edge of this entity'>"
90 : "<ref name='nonNegativeDecimal'/>"
91 : "</element>"
92 116 : "</optional>";
93 : }
94 :
95 0 : void Init(const CParamNode& paramNode) override
96 : {
97 0 : if (paramNode.GetChild("Square").IsOk())
98 : {
99 0 : m_Shape = SQUARE;
100 0 : m_Size0 = paramNode.GetChild("Square").GetChild("@width").ToFixed();
101 0 : m_Size1 = paramNode.GetChild("Square").GetChild("@depth").ToFixed();
102 : }
103 0 : else if (paramNode.GetChild("Circle").IsOk())
104 : {
105 0 : m_Shape = CIRCLE;
106 0 : m_Size0 = m_Size1 = paramNode.GetChild("Circle").GetChild("@radius").ToFixed();
107 : }
108 : else
109 : {
110 : // Error - pick some default
111 0 : m_Shape = CIRCLE;
112 0 : m_Size0 = m_Size1 = entity_pos_t::FromInt(1);
113 : }
114 :
115 0 : m_Height = paramNode.GetChild("Height").ToFixed();
116 :
117 0 : if (paramNode.GetChild("MaxSpawnDistance").IsOk())
118 0 : m_MaxSpawnDistance = paramNode.GetChild("MaxSpawnDistance").ToFixed();
119 : else
120 : // Pick some default
121 0 : m_MaxSpawnDistance = entity_pos_t::FromInt(7);
122 0 : }
123 :
124 0 : void Deinit() override
125 : {
126 0 : }
127 :
128 0 : void Serialize(ISerializer& UNUSED(serialize)) override
129 : {
130 : // No dynamic state to serialize
131 0 : }
132 :
133 0 : void Deserialize(const CParamNode& paramNode, IDeserializer& UNUSED(deserialize)) override
134 : {
135 0 : Init(paramNode);
136 0 : }
137 :
138 0 : void GetShape(EShape& shape, entity_pos_t& size0, entity_pos_t& size1, entity_pos_t& height) const override
139 : {
140 0 : shape = m_Shape;
141 0 : size0 = m_Size0;
142 0 : size1 = m_Size1;
143 0 : height = m_Height;
144 0 : }
145 :
146 0 : CFixedVector3D PickSpawnPoint(entity_id_t spawned) const override
147 : {
148 0 : PROFILE3("PickSpawnPoint");
149 :
150 : // Try to find a free space around the building's footprint.
151 : // (Note that we use the footprint, not the obstruction shape - this might be a bit dodgy
152 : // because the footprint might be inside the obstruction, but it hopefully gives us a nicer
153 : // shape.)
154 :
155 0 : const CFixedVector3D error(fixed::FromInt(-1), fixed::FromInt(-1), fixed::FromInt(-1));
156 :
157 0 : CmpPtr<ICmpPosition> cmpPosition(GetEntityHandle());
158 0 : if (!cmpPosition || !cmpPosition->IsInWorld())
159 0 : return error;
160 :
161 0 : CmpPtr<ICmpObstructionManager> cmpObstructionManager(GetSystemEntity());
162 0 : if (!cmpObstructionManager)
163 0 : return error;
164 :
165 : // If no spawned obstruction, use a positive radius to avoid division by zero errors.
166 0 : entity_pos_t spawnedRadius = entity_pos_t::FromInt(1);
167 0 : ICmpObstructionManager::tag_t spawnedTag;
168 :
169 0 : CmpPtr<ICmpObstruction> cmpSpawnedObstruction(GetSimContext(), spawned);
170 0 : if (cmpSpawnedObstruction)
171 : {
172 0 : spawnedRadius = cmpSpawnedObstruction->GetSize();
173 : // Force a positive radius to avoid division by zero errors.
174 0 : if (spawnedRadius == entity_pos_t::Zero())
175 0 : spawnedRadius = entity_pos_t::FromInt(1);
176 0 : spawnedTag = cmpSpawnedObstruction->GetObstruction();
177 : }
178 :
179 : // Get passability class from UnitMotion.
180 0 : CmpPtr<ICmpUnitMotion> cmpUnitMotion(GetSimContext(), spawned);
181 0 : if (!cmpUnitMotion)
182 0 : return error;
183 :
184 0 : pass_class_t spawnedPass = cmpUnitMotion->GetPassabilityClass();
185 0 : CmpPtr<ICmpPathfinder> cmpPathfinder(GetSystemEntity());
186 0 : if (!cmpPathfinder)
187 0 : return error;
188 :
189 : // Ignore collisions with the spawned entity and entities that don't block movement.
190 0 : SkipTagRequireFlagsObstructionFilter filter(spawnedTag, ICmpObstructionManager::FLAG_BLOCK_MOVEMENT);
191 :
192 0 : CFixedVector2D initialPos = cmpPosition->GetPosition2D();
193 0 : entity_angle_t initialAngle = cmpPosition->GetRotation().Y;
194 :
195 0 : CFixedVector2D u = CFixedVector2D(fixed::Zero(), fixed::FromInt(1)).Rotate(initialAngle);
196 0 : CFixedVector2D v = u.Perpendicular();
197 :
198 : // Obstructions are squares, so multiply its radius by 2*sqrt(2) ~= 3 to determine the distance between units.
199 0 : entity_pos_t gap = spawnedRadius * 3;
200 0 : int rows = std::max(1, (m_MaxSpawnDistance / gap).ToInt_RoundToInfinity());
201 :
202 : // The first row of units will be half a gap away from the footprint.
203 0 : CFixedVector2D halfSize = m_Shape == CIRCLE ?
204 : CFixedVector2D(m_Size1 + gap / 2, m_Size0 + gap / 2) :
205 0 : CFixedVector2D((m_Size1 + gap) / 2, (m_Size0 + gap) / 2);
206 :
207 : // Figure out how many units can fit on each halfside of the rectangle.
208 : // Since 2*pi/6 ~= 1, this is also how many units can fit on a sixth of the circle.
209 0 : int distX = std::max(1, (halfSize.X / gap).ToInt_RoundToNegInfinity());
210 0 : int distY = std::max(1, (halfSize.Y / gap).ToInt_RoundToNegInfinity());
211 :
212 : // Try more spawning points for large units in case some of them are partially blocked.
213 0 : if (rows == 1)
214 : {
215 0 : distX *= 2;
216 0 : distY *= 2;
217 : }
218 :
219 : // Store the position of the spawning point within each row that's closest to the spawning angle.
220 0 : std::vector<int> offsetPoints(rows, 0);
221 :
222 0 : CmpPtr<ICmpRallyPoint> cmpRallyPoint(GetEntityHandle());
223 0 : if (cmpRallyPoint && cmpRallyPoint->HasPositions())
224 : {
225 0 : CFixedVector2D rallyPointPos = cmpRallyPoint->GetFirstPosition();
226 0 : if (m_Shape == CIRCLE)
227 : {
228 0 : entity_angle_t offsetAngle = atan2_approx(rallyPointPos.X - initialPos.X, rallyPointPos.Y - initialPos.Y) - initialAngle;
229 :
230 : // There are 6*(distX+r) points in row r, so multiply that by angle/2pi to find the offset within the row.
231 0 : for (int r = 0; r < rows; ++r)
232 0 : offsetPoints[r] = (offsetAngle * 3 * (distX + r) / fixed::Pi()).ToInt_RoundToNearest();
233 : }
234 : else
235 : {
236 0 : CFixedVector2D offsetPos = Geometry::NearestPointOnSquare(rallyPointPos - initialPos, u, v, halfSize);
237 :
238 : // Scale and convert the perimeter coordinates of the point to its offset within the row.
239 0 : int x = (offsetPos.Dot(u) * distX / halfSize.X).ToInt_RoundToNearest();
240 0 : int y = (offsetPos.Dot(v) * distY / halfSize.Y).ToInt_RoundToNearest();
241 0 : for (int r = 0; r < rows; ++r)
242 0 : offsetPoints[r] = Geometry::GetPerimeterDistance(
243 : distX + r,
244 : distY + r,
245 0 : x >= distX ? distX + r : x <= -distX ? -distX - r : x,
246 0 : y >= distY ? distY + r : y <= -distY ? -distY - r : y);
247 : }
248 : }
249 :
250 0 : for (int k = 0; k < 2 * (distX + distY + 2 * rows); k = k > 0 ? -k : 1 - k)
251 0 : for (int r = 0; r < rows; ++r)
252 : {
253 0 : CFixedVector2D pos = initialPos;
254 0 : if (m_Shape == CIRCLE)
255 : // Multiply the point by 2pi / 6*(distX+r) to get the angle.
256 0 : pos += u.Rotate(fixed::Pi() * (offsetPoints[r] + k) / (3 * (distX + r))).Multiply(halfSize.X + gap * r );
257 : else
258 : {
259 : // Convert the point to coordinates and scale.
260 0 : std::pair<int, int> p = Geometry::GetPerimeterCoordinates(distX + r, distY + r, offsetPoints[r] + k);
261 0 : pos += u.Multiply((halfSize.X + gap * r) * p.first / (distX + r)) +
262 0 : v.Multiply((halfSize.Y + gap * r) * p.second / (distY + r));
263 : }
264 :
265 0 : if (cmpPathfinder->CheckUnitPlacement(filter, pos.X, pos.Y, spawnedRadius, spawnedPass) == ICmpObstruction::FOUNDATION_CHECK_SUCCESS)
266 0 : return CFixedVector3D(pos.X, fixed::Zero(), pos.Y);
267 : }
268 :
269 0 : return error;
270 : }
271 :
272 0 : CFixedVector3D PickSpawnPointBothPass(entity_id_t spawned) const override
273 : {
274 0 : PROFILE3("PickSpawnPointBothPass");
275 :
276 : // Try to find a free space inside and around this footprint
277 : // at the intersection between the footprint passability and the unit passability.
278 : // (useful for example for destroyed ships where the spawning point should be in the intersection
279 : // of the unit and ship passabilities).
280 : // As the overlap between these passabilities regions may be narrow, we need a small step (1 meter)
281 :
282 0 : const CFixedVector3D error(fixed::FromInt(-1), fixed::FromInt(-1), fixed::FromInt(-1));
283 :
284 0 : CmpPtr<ICmpPosition> cmpPosition(GetEntityHandle());
285 0 : if (!cmpPosition || !cmpPosition->IsInWorld())
286 0 : return error;
287 :
288 0 : CmpPtr<ICmpObstructionManager> cmpObstructionManager(GetSystemEntity());
289 0 : if (!cmpObstructionManager)
290 0 : return error;
291 :
292 0 : entity_pos_t spawnedRadius;
293 0 : ICmpObstructionManager::tag_t spawnedTag;
294 :
295 0 : CmpPtr<ICmpObstruction> cmpSpawnedObstruction(GetSimContext(), spawned);
296 0 : if (cmpSpawnedObstruction)
297 : {
298 0 : spawnedRadius = cmpSpawnedObstruction->GetSize();
299 0 : spawnedTag = cmpSpawnedObstruction->GetObstruction();
300 : }
301 : // else use zero radius
302 :
303 : // Get passability class from UnitMotion
304 0 : CmpPtr<ICmpUnitMotion> cmpUnitMotion(GetSimContext(), spawned);
305 0 : if (!cmpUnitMotion)
306 0 : return error;
307 :
308 0 : pass_class_t spawnedPass = cmpUnitMotion->GetPassabilityClass();
309 0 : CmpPtr<ICmpPathfinder> cmpPathfinder(GetSystemEntity());
310 0 : if (!cmpPathfinder)
311 0 : return error;
312 :
313 : // Get the Footprint entity passability
314 0 : CmpPtr<ICmpUnitMotion> cmpEntityMotion(GetEntityHandle());
315 0 : if (!cmpEntityMotion)
316 0 : return error;
317 0 : pass_class_t entityPass = cmpEntityMotion->GetPassabilityClass();
318 :
319 0 : CFixedVector2D initialPos = cmpPosition->GetPosition2D();
320 0 : entity_angle_t initialAngle = cmpPosition->GetRotation().Y;
321 :
322 : // Max spawning distance + 1 (in meters)
323 0 : const i32 maxSpawningDistance = 13;
324 :
325 0 : if (m_Shape == CIRCLE)
326 : {
327 : // Expand outwards from foundation with a fixed step of 1 meter
328 0 : for (i32 dist = 0; dist <= maxSpawningDistance; ++dist)
329 : {
330 : // The spawn point should be far enough from this footprint to fit the unit, plus a little gap
331 0 : entity_pos_t clearance = spawnedRadius + entity_pos_t::FromInt(1+dist);
332 0 : entity_pos_t radius = m_Size0 + clearance;
333 :
334 : // Try equally-spaced points around the circle in alternating directions, starting from the front
335 0 : const i32 numPoints = 31 + 2*dist;
336 0 : for (i32 i = 0; i < (numPoints+1)/2; i = (i > 0 ? -i : 1-i)) // [0, +1, -1, +2, -2, ... (np-1)/2, -(np-1)/2]
337 : {
338 0 : entity_angle_t angle = initialAngle + (entity_angle_t::Pi()*2).Multiply(entity_angle_t::FromInt(i)/(int)numPoints);
339 :
340 0 : fixed s, c;
341 0 : sincos_approx(angle, s, c);
342 :
343 0 : CFixedVector3D pos (initialPos.X + s.Multiply(radius), fixed::Zero(), initialPos.Y + c.Multiply(radius));
344 :
345 0 : SkipTagObstructionFilter filter(spawnedTag); // ignore collisions with the spawned entity
346 0 : if (cmpPathfinder->CheckUnitPlacement(filter, pos.X, pos.Z, spawnedRadius, spawnedPass) == ICmpObstruction::FOUNDATION_CHECK_SUCCESS &&
347 0 : cmpPathfinder->CheckUnitPlacement(filter, pos.X, pos.Z, spawnedRadius, entityPass) == ICmpObstruction::FOUNDATION_CHECK_SUCCESS)
348 0 : return pos; // this position is okay, so return it
349 : }
350 : }
351 : }
352 : else
353 : {
354 0 : fixed s, c;
355 0 : sincos_approx(initialAngle, s, c);
356 :
357 : // Expand outwards from foundation with a fixed step of 1 meter
358 0 : for (i32 dist = 0; dist <= maxSpawningDistance; ++dist)
359 : {
360 : // The spawn point should be far enough from this footprint to fit the unit, plus a little gap
361 0 : entity_pos_t clearance = spawnedRadius + entity_pos_t::FromInt(1+dist);
362 :
363 0 : for (i32 edge = 0; edge < 4; ++edge)
364 : {
365 : // Compute the direction and length of the current edge
366 0 : CFixedVector2D dir;
367 0 : fixed sx, sy;
368 0 : switch (edge)
369 : {
370 0 : case 0:
371 0 : dir = CFixedVector2D(c, -s);
372 0 : sx = m_Size0;
373 0 : sy = m_Size1;
374 0 : break;
375 0 : case 1:
376 0 : dir = CFixedVector2D(-s, -c);
377 0 : sx = m_Size1;
378 0 : sy = m_Size0;
379 0 : break;
380 0 : case 2:
381 0 : dir = CFixedVector2D(s, c);
382 0 : sx = m_Size1;
383 0 : sy = m_Size0;
384 0 : break;
385 0 : case 3:
386 0 : dir = CFixedVector2D(-c, s);
387 0 : sx = m_Size0;
388 0 : sy = m_Size1;
389 0 : break;
390 : }
391 0 : sx = sx/2 + clearance;
392 0 : sy = sy/2 + clearance;
393 : // Try equally-spaced (1 meter) points along the edge in alternating directions, starting from the middle
394 0 : i32 numPoints = 1 + 2*sx.ToInt_RoundToNearest();
395 0 : CFixedVector2D center = initialPos - dir.Perpendicular().Multiply(sy);
396 0 : for (i32 i = 0; i < (numPoints+1)/2; i = (i > 0 ? -i : 1-i)) // [0, +1, -1, +2, -2, ... (np-1)/2, -(np-1)/2]
397 : {
398 0 : CFixedVector2D pos (center + dir*i);
399 :
400 0 : SkipTagObstructionFilter filter(spawnedTag); // ignore collisions with the spawned entity
401 0 : if (cmpPathfinder->CheckUnitPlacement(filter, pos.X, pos.Y, spawnedRadius, spawnedPass) == ICmpObstruction::FOUNDATION_CHECK_SUCCESS &&
402 0 : cmpPathfinder->CheckUnitPlacement(filter, pos.X, pos.Y, spawnedRadius, entityPass) == ICmpObstruction::FOUNDATION_CHECK_SUCCESS)
403 0 : return CFixedVector3D(pos.X, fixed::Zero(), pos.Y); // this position is okay, so return it
404 : }
405 : }
406 : }
407 : }
408 :
409 0 : return error;
410 : }
411 : };
412 :
413 119 : REGISTER_COMPONENT_TYPE(Footprint)
|
