LCOV - code coverage report
Current view: top level - source/simulation2/helpers - LongPathfinder.h (source / functions) Hit Total Coverage
Test: 0 A.D. test coverage report Lines: 1 61 1.6 %
Date: 2023-01-19 00:18:29 Functions: 1 26 3.8 %

          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             : #ifndef INCLUDED_LONGPATHFINDER
      19             : #define INCLUDED_LONGPATHFINDER
      20             : 
      21             : #include "Pathfinding.h"
      22             : 
      23             : #include "graphics/Overlay.h"
      24             : #include "renderer/Scene.h"
      25             : #include "renderer/TerrainOverlay.h"
      26             : #include "simulation2/helpers/Grid.h"
      27             : #include "simulation2/helpers/PriorityQueue.h"
      28             : 
      29             : #include <map>
      30             : 
      31             : /**
      32             :  * Represents the 2D coordinates of a tile.
      33             :  * The i/j components are packed into a single u32, since we usually use these
      34             :  * objects for equality comparisons and the VC2010 optimizer doesn't seem to automatically
      35             :  * compare two u16s in a single operation.
      36             :  * TODO: maybe VC2012 will?
      37             :  */
      38             : struct TileID
      39             : {
      40             :     TileID() { }
      41             : 
      42           0 :     TileID(u16 i, u16 j) : data((i << 16) | j) { }
      43             : 
      44           0 :     bool operator==(const TileID& b) const
      45             :     {
      46           0 :         return data == b.data;
      47             :     }
      48             : 
      49             :     /// Returns lexicographic order over (i,j)
      50           0 :     bool operator<(const TileID& b) const
      51             :     {
      52           0 :         return data < b.data;
      53             :     }
      54             : 
      55           0 :     u16 i() const { return data >> 16; }
      56           0 :     u16 j() const { return data & 0xFFFF; }
      57             : 
      58             : private:
      59             :     u32 data;
      60             : };
      61             : 
      62             : /**
      63             :  * Tile data for A* computation.
      64             :  * (We store an array of one of these per terrain tile, so it ought to be optimised for size)
      65             :  */
      66           0 : struct PathfindTile
      67             : {
      68             : public:
      69             :     enum {
      70             :         STATUS_UNEXPLORED = 0,
      71             :         STATUS_OPEN = 1,
      72             :         STATUS_CLOSED = 2
      73             :     };
      74             : 
      75           0 :     bool IsUnexplored() const { return GetStatus() == STATUS_UNEXPLORED; }
      76           0 :     bool IsOpen() const { return GetStatus() == STATUS_OPEN; }
      77           0 :     bool IsClosed() const { return GetStatus() == STATUS_CLOSED; }
      78           0 :     void SetStatusOpen() { SetStatus(STATUS_OPEN); }
      79           0 :     void SetStatusClosed() { SetStatus(STATUS_CLOSED); }
      80             : 
      81             :     // Get pi,pj coords of predecessor to this tile on best path, given i,j coords of this tile
      82           0 :     inline int GetPredI(int i) const { return i + GetPredDI(); }
      83           0 :     inline int GetPredJ(int j) const { return j + GetPredDJ(); }
      84             : 
      85           0 :     inline PathCost GetCost() const { return g; }
      86           0 :     inline void SetCost(PathCost cost) { g = cost; }
      87             : 
      88             : private:
      89             :     PathCost g; // cost to reach this tile
      90             :     u32 data; // 2-bit status; 15-bit PredI; 15-bit PredJ; packed for storage efficiency
      91             : 
      92             : public:
      93           0 :     inline u8 GetStatus() const
      94             :     {
      95           0 :         return data & 3;
      96             :     }
      97             : 
      98           0 :     inline void SetStatus(u8 s)
      99             :     {
     100           0 :         ASSERT(s < 4);
     101           0 :         data &= ~3;
     102           0 :         data |= (s & 3);
     103           0 :     }
     104             : 
     105           0 :     int GetPredDI() const
     106             :     {
     107           0 :         return (i32)data >> 17;
     108             :     }
     109             : 
     110           0 :     int GetPredDJ() const
     111             :     {
     112           0 :         return ((i32)data << 15) >> 17;
     113             :     }
     114             : 
     115             :     // Set the pi,pj coords of predecessor, given i,j coords of this tile
     116           0 :     inline void SetPred(int pi, int pj, int i, int j)
     117             :     {
     118           0 :         int di = pi - i;
     119           0 :         int dj = pj - j;
     120           0 :         ASSERT(-16384 <= di && di < 16384);
     121           0 :         ASSERT(-16384 <= dj && dj < 16384);
     122           0 :         data &= 3;
     123           0 :         data |= (((u32)di & 0x7FFF) << 17) | (((u32)dj & 0x7FFF) << 2);
     124           0 :     }
     125             : };
     126             : 
     127             : struct CircularRegion
     128             : {
     129             :     CircularRegion(entity_pos_t x, entity_pos_t z, entity_pos_t r) : x(x), z(z), r(r) {}
     130             :     entity_pos_t x, z, r;
     131             : };
     132             : 
     133             : typedef PriorityQueueHeap<TileID, PathCost, PathCost> PriorityQueue;
     134             : typedef SparseGrid<PathfindTile> PathfindTileGrid;
     135             : 
     136             : class JumpPointCache;
     137             : 
     138           0 : struct PathfinderState
     139             : {
     140             :     u32 steps; // number of algorithm iterations
     141             : 
     142             :     PathGoal goal;
     143             : 
     144             :     u16 iGoal, jGoal; // goal tile
     145             : 
     146             :     pass_class_t passClass;
     147             : 
     148             :     PriorityQueue open;
     149             :     // (there's no explicit closed list; it's encoded in PathfindTile)
     150             : 
     151             :     PathfindTileGrid* tiles;
     152             :     Grid<NavcellData>* terrain;
     153             : 
     154             :     PathCost hBest; // heuristic of closest discovered tile to goal
     155             :     u16 iBest, jBest; // closest tile
     156             : 
     157             :     const JumpPointCache* jpc;
     158             : };
     159             : 
     160             : class LongOverlay;
     161             : 
     162             : class HierarchicalPathfinder;
     163             : 
     164             : class LongPathfinder
     165             : {
     166             : public:
     167             :     LongPathfinder();
     168             :     ~LongPathfinder();
     169             : 
     170             :     void SetDebugOverlay(bool enabled);
     171             : 
     172           0 :     void SetDebugPath(const HierarchicalPathfinder& hierPath, entity_pos_t x0, entity_pos_t z0, const PathGoal& goal, pass_class_t passClass)
     173             :     {
     174           0 :         if (!m_Debug.Overlay)
     175           0 :             return;
     176             : 
     177           0 :         SAFE_DELETE(m_Debug.Grid);
     178           0 :         delete m_Debug.Path;
     179           0 :         m_Debug.Path = new WaypointPath();
     180           0 :         ComputePath(hierPath, x0, z0, goal, passClass, *m_Debug.Path);
     181           0 :         m_Debug.PassClass = passClass;
     182             :     }
     183             : 
     184           0 :     void Reload(Grid<NavcellData>* passabilityGrid)
     185             :     {
     186           0 :         m_Grid = passabilityGrid;
     187           0 :         ASSERT(passabilityGrid->m_H == passabilityGrid->m_W);
     188           0 :         m_GridSize = passabilityGrid->m_W;
     189             : 
     190           0 :         m_JumpPointCache.clear();
     191           0 :     }
     192             : 
     193           0 :     void Update(Grid<NavcellData>* passabilityGrid)
     194             :     {
     195           0 :         m_Grid = passabilityGrid;
     196           0 :         ASSERT(passabilityGrid->m_H == passabilityGrid->m_W);
     197           0 :         ASSERT(m_GridSize == passabilityGrid->m_H);
     198             : 
     199           0 :         m_JumpPointCache.clear();
     200           0 :     }
     201             : 
     202             :     /**
     203             :      * Compute a tile-based path from the given point to the goal, and return the set of waypoints.
     204             :      * The waypoints correspond to the centers of horizontally/vertically adjacent tiles
     205             :      * along the path.
     206             :      */
     207             :     void ComputePath(const HierarchicalPathfinder& hierPath, entity_pos_t x0, entity_pos_t z0, const PathGoal& origGoal,
     208             :         pass_class_t passClass, WaypointPath& path) const;
     209             : 
     210             :     /**
     211             :      * Compute a tile-based path from the given point to the goal, excluding the regions
     212             :      * specified in excludedRegions (which are treated as impassable) and return the set of waypoints.
     213             :      * The waypoints correspond to the centers of horizontally/vertically adjacent tiles
     214             :      * along the path.
     215             :      */
     216             :     void ComputePath(const HierarchicalPathfinder& hierPath, entity_pos_t x0, entity_pos_t z0, const PathGoal& origGoal,
     217             :         pass_class_t passClass, std::vector<CircularRegion> excludedRegions, WaypointPath& path);
     218             : 
     219           0 :     void GetDebugData(u32& steps, double& time, Grid<u8>& grid) const
     220             :     {
     221           0 :         GetDebugDataJPS(steps, time, grid);
     222           0 :     }
     223             : 
     224             :     Grid<NavcellData>* m_Grid;
     225             :     u16 m_GridSize;
     226             : 
     227             :     // Debugging - output from last pathfind operation.
     228           3 :     struct Debug
     229             :     {
     230             :         // Atomic - used to toggle debugging.
     231             :         std::atomic<LongOverlay*> Overlay = nullptr;
     232             :         // Mutable - set by ComputeJPSPath (thus possibly from different threads).
     233             :         // Synchronized via mutex if necessary.
     234             :         mutable PathfindTileGrid* Grid = nullptr;
     235             :         mutable u32 Steps;
     236             :         mutable double Time;
     237             :         mutable PathGoal Goal;
     238             : 
     239             :         WaypointPath* Path = nullptr;
     240             :         pass_class_t PassClass;
     241             :     } m_Debug;
     242             : 
     243             : private:
     244             :     PathCost CalculateHeuristic(int i, int j, int iGoal, int jGoal) const;
     245             :     void ProcessNeighbour(int pi, int pj, int i, int j, PathCost pg, PathfinderState& state) const;
     246             : 
     247             :     /**
     248             :      * JPS algorithm helper functions
     249             :      * @param detectGoal is not used if m_UseJPSCache is true
     250             :      */
     251             :     void AddJumpedHoriz(int i, int j, int di, PathCost g, PathfinderState& state, bool detectGoal) const;
     252             :     int HasJumpedHoriz(int i, int j, int di, PathfinderState& state, bool detectGoal) const;
     253             :     void AddJumpedVert(int i, int j, int dj, PathCost g, PathfinderState& state, bool detectGoal) const;
     254             :     int HasJumpedVert(int i, int j, int dj, PathfinderState& state, bool detectGoal) const;
     255             :     void AddJumpedDiag(int i, int j, int di, int dj, PathCost g, PathfinderState& state) const;
     256             : 
     257             :     /**
     258             :      * See LongPathfinder.cpp for implementation details
     259             :      * TODO: cleanup documentation
     260             :      */
     261             :     void ComputeJPSPath(const HierarchicalPathfinder& hierPath, entity_pos_t x0, entity_pos_t z0, const PathGoal& origGoal, pass_class_t passClass, WaypointPath& path) const;
     262             :     void GetDebugDataJPS(u32& steps, double& time, Grid<u8>& grid) const;
     263             : 
     264             :     // Helper functions for ComputePath
     265             : 
     266             :     /**
     267             :      * Given a path with an arbitrary collection of waypoints, updates the
     268             :      * waypoints to be nicer.
     269             :      * If @param maxDist is non-zero, path waypoints will be espaced by at most @param maxDist.
     270             :      * In that case the distance between (x0, z0) and the first waypoint will also be made less than maxDist.
     271             :      */
     272             :     void ImprovePathWaypoints(WaypointPath& path, pass_class_t passClass, entity_pos_t maxDist, entity_pos_t x0, entity_pos_t z0) const;
     273             : 
     274             :     /**
     275             :      * Generate a passability map, stored in the 16th bit of navcells, based on passClass,
     276             :      * but with a set of impassable circular regions.
     277             :      */
     278             :     void GenerateSpecialMap(pass_class_t passClass, std::vector<CircularRegion> excludedRegions);
     279             : 
     280             :     bool m_UseJPSCache;
     281             :     // Mutable may be used here as caching does not change the external const-ness of the Long Range pathfinder.
     282             :     // This is thread-safe as it is order independent (no change in the output of the function for a given set of params).
     283             :     // Obviously, this means that the cache should actually be a cache and not return different results
     284             :     // from what would happen if things hadn't been cached.
     285             :     mutable std::map<pass_class_t, std::shared_ptr<JumpPointCache>> m_JumpPointCache;
     286             : };
     287             : 
     288             : #endif // INCLUDED_LONGPATHFINDER

Generated by: LCOV version 1.13