LCOV - code coverage report
Current view: top level - source/simulation2/helpers - Pathfinding.cpp (source / functions) Hit Total Coverage
Test: 0 A.D. test coverage report Lines: 21 64 32.8 %
Date: 2023-01-19 00:18:29 Functions: 1 2 50.0 %

          Line data    Source code
       1             : /* Copyright (C) 2021 Wildfire Games.
       2             :  * This file is part of 0 A.D.
       3             :  *
       4             :  * 0 A.D. is free software: you can redistribute it and/or modify
       5             :  * it under the terms of the GNU General Public License as published by
       6             :  * the Free Software Foundation, either version 2 of the License, or
       7             :  * (at your option) any later version.
       8             :  *
       9             :  * 0 A.D. is distributed in the hope that it will be useful,
      10             :  * but WITHOUT ANY WARRANTY; without even the implied warranty of
      11             :  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      12             :  * GNU General Public License for more details.
      13             :  *
      14             :  * You should have received a copy of the GNU General Public License
      15             :  * along with 0 A.D.  If not, see <http://www.gnu.org/licenses/>.
      16             :  */
      17             : 
      18             : #include "precompiled.h"
      19             : 
      20             : #include "Pathfinding.h"
      21             : 
      22             : #include "graphics/Terrain.h"
      23             : #include "ps/CLogger.h"
      24             : #include "simulation2/helpers/Grid.h"
      25             : #include "simulation2/system/ParamNode.h"
      26             : 
      27             : namespace Pathfinding
      28             : {
      29           0 :     bool CheckLineMovement(entity_pos_t x0, entity_pos_t z0, entity_pos_t x1, entity_pos_t z1,
      30             :                                   pass_class_t passClass, const Grid<NavcellData>& grid)
      31             :     {
      32             :         // We shouldn't allow lines between diagonally-adjacent navcells.
      33             :         // It doesn't matter whether we allow lines precisely along the edge
      34             :         // of an impassable navcell.
      35             : 
      36             :         // To rasterise the line:
      37             :         // If the line is (e.g.) aiming up-right, then we start at the navcell
      38             :         // containing the start point and the line must either end in that navcell
      39             :         // or else exit along the top edge or the right edge (or through the top-right corner,
      40             :         // which we'll arbitrary treat as the horizontal edge).
      41             :         // So we jump into the adjacent navcell across that edge, and continue.
      42             : 
      43             :         // To handle the special case of units that are stuck on impassable cells,
      44             :         // we allow them to move from an impassable to a passable cell (but not
      45             :         // vice versa).
      46             : 
      47             :         u16 i0, j0, i1, j1;
      48           0 :         NearestNavcell(x0, z0, i0, j0, grid.m_W, grid.m_H);
      49           0 :         NearestNavcell(x1, z1, i1, j1, grid.m_W, grid.m_H);
      50             : 
      51             :         // Find which direction the line heads in
      52           0 :         int di = (i0 < i1 ? +1 : i1 < i0 ? -1 : 0);
      53           0 :         int dj = (j0 < j1 ? +1 : j1 < j0 ? -1 : 0);
      54             : 
      55           0 :         u16 i = i0;
      56           0 :         u16 j = j0;
      57             : 
      58           0 :         bool currentlyOnImpassable = !IS_PASSABLE(grid.get(i0, j0), passClass);
      59             : 
      60             :         while (true)
      61             :         {
      62             :             // Make sure we are still in the limits
      63           0 :             ENSURE(
      64             :                    ((di > 0 && i0 <= i && i <= i1) || (di < 0 && i1 <= i && i <= i0) || (di == 0 && i == i0)) &&
      65             :                    ((dj > 0 && j0 <= j && j <= j1) || (dj < 0 && j1 <= j && j <= j0) || (dj == 0 && j == j0)));
      66             : 
      67             :             // Fail if we're moving onto an impassable navcell
      68           0 :             bool passable = IS_PASSABLE(grid.get(i, j), passClass);
      69           0 :             if (passable)
      70           0 :                 currentlyOnImpassable = false;
      71           0 :             else if (!currentlyOnImpassable)
      72           0 :                 return false;
      73             : 
      74             :             // Succeed if we're at the target
      75           0 :             if (i == i1 && j == j1)
      76           0 :                 return true;
      77             : 
      78             :             // If we can only move horizontally/vertically, then just move in that direction
      79             :             // If we are reaching the limits, we can go straight to the end
      80           0 :             if (di == 0 || i == i1)
      81             :             {
      82           0 :                 j += dj;
      83           0 :                 continue;
      84             :             }
      85           0 :             else if (dj == 0 || j == j1)
      86             :             {
      87           0 :                 i += di;
      88           0 :                 continue;
      89             :             }
      90             : 
      91             :             // Otherwise we need to check which cell to move into:
      92             : 
      93             :             // Check whether the line intersects the horizontal (top/bottom) edge of
      94             :             // the current navcell.
      95             :             // Horizontal edge is (i, j + (dj>0?1:0)) .. (i + 1, j + (dj>0?1:0))
      96             :             // Since we already know the line is moving from this navcell into a different
      97             :             // navcell, we simply need to test that the edge's endpoints are not both on the
      98             :             // same side of the line.
      99             : 
     100             :             // If we are crossing exactly a vertex of the grid, we will get dota or dotb equal
     101             :             // to 0. In that case we arbitrarily choose to move of dj.
     102             :             // This only works because we handle the case (i == i1 || j == j1) beforehand.
     103             :             // Otherwise we could go outside the j limits and never reach the final navcell.
     104             : 
     105           0 :             entity_pos_t xia = entity_pos_t::FromInt(i).Multiply(Pathfinding::NAVCELL_SIZE);
     106           0 :             entity_pos_t xib = entity_pos_t::FromInt(i+1).Multiply(Pathfinding::NAVCELL_SIZE);
     107           0 :             entity_pos_t zj = entity_pos_t::FromInt(j + (dj+1)/2).Multiply(Pathfinding::NAVCELL_SIZE);
     108             : 
     109           0 :             CFixedVector2D perp = CFixedVector2D(x1 - x0, z1 - z0).Perpendicular();
     110           0 :             entity_pos_t dota = (CFixedVector2D(xia, zj) - CFixedVector2D(x0, z0)).Dot(perp);
     111           0 :             entity_pos_t dotb = (CFixedVector2D(xib, zj) - CFixedVector2D(x0, z0)).Dot(perp);
     112             : 
     113             :             // If the horizontal edge is fully on one side of the line, so the line doesn't
     114             :             // intersect it, we should move across the vertical edge instead
     115           0 :             if ((dota < entity_pos_t::Zero() && dotb < entity_pos_t::Zero()) ||
     116           0 :                 (dota > entity_pos_t::Zero() && dotb > entity_pos_t::Zero()))
     117           0 :                 i += di;
     118             :             else
     119           0 :                 j += dj;
     120           0 :         }
     121             :     }
     122             : }
     123             : 
     124          15 : PathfinderPassability::PathfinderPassability(pass_class_t mask, const CParamNode& node) : m_Mask(mask)
     125             : {
     126          15 :     if (node.GetChild("MinWaterDepth").IsOk())
     127           3 :         m_MinDepth = node.GetChild("MinWaterDepth").ToFixed();
     128             :     else
     129          12 :         m_MinDepth = std::numeric_limits<fixed>::min();
     130             : 
     131          15 :     if (node.GetChild("MaxWaterDepth").IsOk())
     132           6 :         m_MaxDepth = node.GetChild("MaxWaterDepth").ToFixed();
     133             :     else
     134           9 :         m_MaxDepth = std::numeric_limits<fixed>::max();
     135             : 
     136          15 :     if (node.GetChild("MaxTerrainSlope").IsOk())
     137           9 :         m_MaxSlope = node.GetChild("MaxTerrainSlope").ToFixed();
     138             :     else
     139           6 :         m_MaxSlope = std::numeric_limits<fixed>::max();
     140             : 
     141          15 :     if (node.GetChild("MinShoreDistance").IsOk())
     142           3 :         m_MinShore = node.GetChild("MinShoreDistance").ToFixed();
     143             :     else
     144          12 :         m_MinShore = std::numeric_limits<fixed>::min();
     145             : 
     146          15 :     if (node.GetChild("MaxShoreDistance").IsOk())
     147           3 :         m_MaxShore = node.GetChild("MaxShoreDistance").ToFixed();
     148             :     else
     149          12 :         m_MaxShore = std::numeric_limits<fixed>::max();
     150             : 
     151          15 :     if (node.GetChild("Clearance").IsOk())
     152             :     {
     153           0 :         m_Clearance = node.GetChild("Clearance").ToFixed();
     154             : 
     155             :         /* According to Philip who designed the original doc (in docs/pathfinder.pdf),
     156             :          * clearance should usually be integer to ensure consistent behavior when rasterizing
     157             :          * the passability map.
     158             :          * This seems doubtful to me and my pathfinder fix makes having a clearance of 0.8 quite convenient
     159             :          * so I comment out this check, but leave it here for the purpose of documentation should a bug arise.
     160             : 
     161             :          if (!(m_Clearance % Pathfinding::NAVCELL_SIZE).IsZero())
     162             :          {
     163             :          // If clearance isn't an integer number of navcells then we'll
     164             :          // probably get weird behaviour when expanding the navcell grid
     165             :          // by clearance, vs expanding static obstructions by clearance
     166             :          LOGWARNING("Pathfinder passability class has clearance %f, should be multiple of %f",
     167             :          m_Clearance.ToFloat(), Pathfinding::NAVCELL_SIZE.ToFloat());
     168             :          }*/
     169             :     }
     170             :     else
     171          15 :         m_Clearance = fixed::Zero();
     172             : 
     173          15 :     if (node.GetChild("Obstructions").IsOk())
     174             :     {
     175           0 :         const std::string& obstructions = node.GetChild("Obstructions").ToString();
     176           0 :         if (obstructions == "none")
     177           0 :             m_Obstructions = NONE;
     178           0 :         else if (obstructions == "pathfinding")
     179           0 :             m_Obstructions = PATHFINDING;
     180           0 :         else if (obstructions == "foundation")
     181           0 :             m_Obstructions = FOUNDATION;
     182             :         else
     183             :         {
     184           0 :             LOGERROR("Invalid value for Obstructions in pathfinder.xml for pass class %d", mask);
     185           0 :             m_Obstructions = NONE;
     186             :         }
     187             :     }
     188             :     else
     189          15 :         m_Obstructions = NONE;
     190          15 : }

Generated by: LCOV version 1.13