LCOV - code coverage report
Current view: top level - source/simulation2/helpers - Pathfinding.h (source / functions) Hit Total Coverage
Test: 0 A.D. test coverage report Lines: 9 37 24.3 %
Date: 2023-01-19 00:18:29 Functions: 2 22 9.1 %

          Line data    Source code
       1             : /* Copyright (C) 2022 Wildfire Games.
       2             :  * This file is part of 0 A.D.
       3             :  *
       4             :  * 0 A.D. is free software: you can redistribute it and/or modify
       5             :  * it under the terms of the GNU General Public License as published by
       6             :  * the Free Software Foundation, either version 2 of the License, or
       7             :  * (at your option) any later version.
       8             :  *
       9             :  * 0 A.D. is distributed in the hope that it will be useful,
      10             :  * but WITHOUT ANY WARRANTY; without even the implied warranty of
      11             :  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      12             :  * GNU General Public License for more details.
      13             :  *
      14             :  * You should have received a copy of the GNU General Public License
      15             :  * along with 0 A.D.  If not, see <http://www.gnu.org/licenses/>.
      16             :  */
      17             : 
      18             : #ifndef INCLUDED_PATHFINDING
      19             : #define INCLUDED_PATHFINDING
      20             : 
      21             : #include "graphics/Terrain.h"
      22             : #include "maths/MathUtil.h"
      23             : 
      24             : #include "simulation2/system/Entity.h"
      25             : #include "PathGoal.h"
      26             : 
      27             : class CParamNode;
      28             : 
      29             : typedef u16 pass_class_t;
      30             : template<typename T>
      31             : class Grid;
      32             : 
      33           0 : struct LongPathRequest
      34             : {
      35             :     u32 ticket;
      36             :     entity_pos_t x0;
      37             :     entity_pos_t z0;
      38             :     PathGoal goal;
      39             :     pass_class_t passClass;
      40             :     entity_id_t notify;
      41             : };
      42             : 
      43           0 : struct ShortPathRequest
      44             : {
      45             :     u32 ticket;
      46             :     entity_pos_t x0;
      47             :     entity_pos_t z0;
      48             :     entity_pos_t clearance;
      49             :     entity_pos_t range;
      50             :     PathGoal goal;
      51             :     pass_class_t passClass;
      52             :     bool avoidMovingUnits;
      53             :     entity_id_t group;
      54             :     entity_id_t notify;
      55             : };
      56             : 
      57           0 : struct Waypoint
      58             : {
      59             :     entity_pos_t x, z;
      60             : };
      61             : 
      62             : /**
      63             :  * Returned path.
      64             :  * Waypoints are in *reverse* order (the earliest is at the back of the list)
      65             :  */
      66           0 : struct WaypointPath
      67             : {
      68             :     std::vector<Waypoint> m_Waypoints;
      69             : };
      70             : 
      71             : /**
      72             :  * Represents the cost of a path consisting of horizontal/vertical and
      73             :  * diagonal movements over a uniform-cost grid.
      74             :  * Maximum path length before overflow is about 45K steps.
      75             :  */
      76             : struct PathCost
      77             : {
      78           0 :     PathCost() : data(0) { }
      79             : 
      80             :     /// Construct from a number of horizontal/vertical and diagonal steps
      81           0 :     PathCost(u16 hv, u16 d)
      82           0 :         : data(hv * 65536 + d * 92682) // 2^16 * sqrt(2) == 92681.9
      83             :     {
      84           0 :     }
      85             : 
      86             :     /// Construct for horizontal/vertical movement of given number of steps
      87           0 :     static PathCost horizvert(u16 n)
      88             :     {
      89           0 :         return PathCost(n, 0);
      90             :     }
      91             : 
      92             :     /// Construct for diagonal movement of given number of steps
      93           0 :     static PathCost diag(u16 n)
      94             :     {
      95           0 :         return PathCost(0, n);
      96             :     }
      97             : 
      98           0 :     PathCost operator+(const PathCost& a) const
      99             :     {
     100           0 :         PathCost c;
     101           0 :         c.data = data + a.data;
     102           0 :         return c;
     103             :     }
     104             : 
     105           0 :     PathCost& operator+=(const PathCost& a)
     106             :     {
     107           0 :         data += a.data;
     108           0 :         return *this;
     109             :     }
     110             : 
     111             :     bool operator<=(const PathCost& b) const { return data <= b.data; }
     112           0 :     bool operator< (const PathCost& b) const { return data <  b.data; }
     113           0 :     bool operator>=(const PathCost& b) const { return data >= b.data; }
     114           0 :     bool operator>(const PathCost& b) const { return data >  b.data; }
     115             : 
     116             :     u32 ToInt()
     117             :     {
     118             :         return data;
     119             :     }
     120             : 
     121             : private:
     122             :     u32 data;
     123             : };
     124             : 
     125             : inline constexpr int PASS_CLASS_BITS = 16;
     126             : typedef u16 NavcellData; // 1 bit per passability class (up to PASS_CLASS_BITS)
     127             : #define IS_PASSABLE(item, classmask) (((item) & (classmask)) == 0)
     128             : #define PASS_CLASS_MASK_FROM_INDEX(id) ((pass_class_t)(1u << id))
     129             : #define SPECIAL_PASS_CLASS PASS_CLASS_MASK_FROM_INDEX((PASS_CLASS_BITS-1)) // 16th bit, used for special in-place computations
     130             : 
     131             : namespace Pathfinding
     132             : {
     133             :     /**
     134             :      * The long-range pathfinder operates primarily over a navigation grid (a uniform-cost
     135             :      * 2D passability grid, with horizontal/vertical (not diagonal) connectivity).
     136             :      * This is based on the terrain tile passability, plus the rasterized shapes of
     137             :      * obstructions, all expanded outwards by the radius of the units.
     138             :      * Since units are much smaller than terrain tiles, the nav grid should be
     139             :      * higher resolution than the tiles.
     140             :      * We therefore split each the world into NxN "nav cells" (for some integer N,
     141             :      * preferably a power of two).
     142             :      */
     143      956018 :     inline constexpr fixed NAVCELL_SIZE = fixed::FromInt(1);
     144             :     inline constexpr int NAVCELL_SIZE_INT = 1;
     145             :     inline constexpr int NAVCELL_SIZE_LOG2 = 0;
     146             : 
     147             :     /**
     148             :      * The terrain grid is coarser, and it is often convenient to convert from one to the other.
     149             :      */
     150             :     inline constexpr int NAVCELLS_PER_TERRAIN_TILE = TERRAIN_TILE_SIZE / NAVCELL_SIZE_INT;
     151             :     static_assert(TERRAIN_TILE_SIZE % NAVCELL_SIZE_INT == 0, "Terrain tile size is not a multiple of navcell size");
     152             : 
     153             :     /**
     154             :      * To make sure the long-range pathfinder is more strict than the short-range one,
     155             :      * we need to slightly over-rasterize. So we extend the clearance radius by 1.
     156             :      */
     157             :     inline constexpr entity_pos_t CLEARANCE_EXTENSION_RADIUS = fixed::FromInt(1);
     158             : 
     159             :     /**
     160             :      * Compute the navcell indexes on the grid nearest to a given point
     161             :      * w, h are the grid dimensions, i.e. the number of navcells per side
     162             :      */
     163          49 :     inline void NearestNavcell(entity_pos_t x, entity_pos_t z, u16& i, u16& j, u16 w, u16 h)
     164             :     {
     165             :         // Use NAVCELL_SIZE_INT to save the cost of dividing by a fixed
     166          49 :         i = static_cast<u16>(Clamp((x / NAVCELL_SIZE_INT).ToInt_RoundToNegInfinity(), 0, w - 1));
     167          49 :         j = static_cast<u16>(Clamp((z / NAVCELL_SIZE_INT).ToInt_RoundToNegInfinity(), 0, h - 1));
     168          49 :     }
     169             : 
     170             :     /**
     171             :      * Returns the position of the center of the given terrain tile
     172             :      */
     173           0 :     inline void TerrainTileCenter(u16 i, u16 j, entity_pos_t& x, entity_pos_t& z)
     174             :     {
     175             :         static_assert(TERRAIN_TILE_SIZE % 2 == 0);
     176           0 :         x = entity_pos_t::FromInt(i*(int)TERRAIN_TILE_SIZE + (int)TERRAIN_TILE_SIZE / 2);
     177           0 :         z = entity_pos_t::FromInt(j*(int)TERRAIN_TILE_SIZE + (int)TERRAIN_TILE_SIZE / 2);
     178           0 :     }
     179             : 
     180           6 :     inline void NavcellCenter(u16 i, u16 j, entity_pos_t& x, entity_pos_t& z)
     181             :     {
     182           6 :         x = entity_pos_t::FromInt(i * 2 + 1).Multiply(NAVCELL_SIZE / 2);
     183           6 :         z = entity_pos_t::FromInt(j * 2 + 1).Multiply(NAVCELL_SIZE / 2);
     184           6 :     }
     185             : 
     186             :     /*
     187             :      * Checks that the line (x0,z0)-(x1,z1) does not intersect any impassable navcells.
     188             :      */
     189             :     bool CheckLineMovement(entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1,
     190             :                                   pass_class_t passClass, const Grid<NavcellData>& grid);
     191             : }
     192             : 
     193             : /*
     194             :  * For efficient pathfinding we want to try hard to minimise the per-tile search cost,
     195             :  * so we precompute the tile passability flags for the various different types of unit.
     196             :  * We also want to minimise memory usage (there can easily be 100K tiles so we don't want
     197             :  * to store many bytes for each).
     198             :  *
     199             :  * To handle passability efficiently, we have a small number of passability classes
     200             :  * (e.g. "infantry", "ship"). Each unit belongs to a single passability class, and
     201             :  * uses that for all its pathfinding.
     202             :  * Passability is determined by water depth, terrain slope, forestness, buildingness.
     203             :  * We need at least one bit per class per tile to represent passability.
     204             :  *
     205             :  * Not all pass classes are used for actual pathfinding. The pathfinder calls
     206             :  * CCmpObstructionManager's Rasterize() to add shapes onto the passability grid.
     207             :  * Which shapes are rasterized depend on the value of the m_Obstructions of each passability
     208             :  * class.
     209             :  *
     210             :  * Passabilities not used for unit pathfinding should not use the Clearance attribute, and
     211             :  * will get a zero clearance value.
     212             :  */
     213             : class PathfinderPassability
     214             : {
     215             : public:
     216             :     PathfinderPassability(pass_class_t mask, const CParamNode& node);
     217             : 
     218           0 :     bool IsPassable(fixed waterdepth, fixed steepness, fixed shoredist) const
     219             :     {
     220           0 :         return ((m_MinDepth <= waterdepth && waterdepth <= m_MaxDepth) && (steepness < m_MaxSlope) && (m_MinShore <= shoredist && shoredist <= m_MaxShore));
     221             :     }
     222             : 
     223             :     pass_class_t m_Mask;
     224             : 
     225             :     fixed m_Clearance; // min distance from static obstructions
     226             : 
     227             :     enum ObstructionHandling
     228             :     {
     229             :         NONE,
     230             :         PATHFINDING,
     231             :         FOUNDATION
     232             :     };
     233             :     ObstructionHandling m_Obstructions;
     234             : 
     235             : private:
     236             :     fixed m_MinDepth;
     237             :     fixed m_MaxDepth;
     238             :     fixed m_MaxSlope;
     239             :     fixed m_MinShore;
     240             :     fixed m_MaxShore;
     241             : };
     242             : 
     243             : #endif // INCLUDED_PATHFINDING

Generated by: LCOV version 1.13