LCOV - code coverage report
Current view: top level - source/simulation2/components - CCmpFootprint.cpp (source / functions) Hit Total Coverage
Test: 0 A.D. test coverage report Lines: 5 181 2.8 %
Date: 2023-01-19 00:18:29 Functions: 5 18 27.8 %

          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)

Generated by: LCOV version 1.13