BVB Source Codes

CRYENGINE Show AStarSolver.h Source code

Return Download CRYENGINE: download AStarSolver.h Source code - Download CRYENGINE Source code - Type:.h
  1. // Copyright 2001-2016 Crytek GmbH / Crytek Group. All rights reserved.
  2.  
  3. #ifndef ASTARSOLVER_H
  4. #define ASTARSOLVER_H
  5.  
  6. #if _MSC_VER > 1000
  7.         #pragma once
  8. #endif
  9.  
  10. #include <CryAISystem/IAgent.h>
  11. #include "AStarOpenList.h"
  12. #include <CryNetwork/SerializeFwd.h>
  13. #include "AILog.h"
  14. #include <CryAISystem/IPathfinder.h> // For NavigationBlockers
  15.  
  16. class CGraph;
  17.  
  18. enum EAStarResult
  19. {
  20.         ASTAR_NOPATH,
  21.         ASTAR_STILLSOLVING,
  22.         ASTAR_PATHFOUND,
  23. };
  24.  
  25. class CHeuristic
  26. {
  27. public:
  28.         CHeuristic() {};
  29.         virtual ~CHeuristic() {};
  30.  
  31.         /// Estimate the cost from one node to another - this estimate must be a minimum
  32.         /// bound on the cost in order for AStar to work correctly (though it may run faster
  33.         /// if the estimate more a best-guess than a lower-bound)
  34.         virtual float EstimateCost(const AStarSearchNode& node0, const AStarSearchNode& node1) const = 0;
  35.  
  36.         /// Calculate the cost from one node to another via a specific link. This calculation
  37.         /// should include anything specific like terrain costs, stealth vs speed etc
  38.         /// A return value < 0 means that this link is absolutely impassable.
  39.         virtual float CalculateCost(const CGraph* graph, const AStarSearchNode& node0, unsigned linkIndex0,
  40.                                     const AStarSearchNode& node1, const NavigationBlockers& navigationBlockers) const = 0;
  41.  
  42.         /// Can be overridden to bypass expensive calculations in CalculateCost
  43.         virtual bool IsLinkPassable(const CGraph* graph,
  44.                                     const AStarSearchNode& node0, unsigned linkIndex0,
  45.                                     const AStarSearchNode& node1,
  46.                                     const NavigationBlockers& navigationBlockers) const
  47.         {
  48.                 return CalculateCost(graph, node0, linkIndex0, node1, navigationBlockers) >= 0.0f;
  49.         }
  50.  
  51.         virtual const struct PathfindingHeuristicProperties* GetProperties() const { return 0; }
  52.  
  53. };
  54.  
  55. class CCalculationStopper;
  56.  
  57. //====================================================================
  58. // CAStarSolver
  59. // Implements A*, supporting splitting the solving over multiple calls.
  60. //====================================================================
  61. class CAStarSolver
  62. {
  63. public:
  64.         CAStarSolver(CGraphNodeManager& nodeManager);
  65.         ~CAStarSolver();
  66.  
  67.         /// Setup the path search. A warning will be generated if a path is already in progress - if so
  68.         /// that path will be aborted and the new one started.
  69.         /// Also pass in a collection of navigation blockers - this collection will be copied (to make
  70.         /// sure it doesn't change as the search proceeds)
  71.         EAStarResult SetupAStar(
  72.           CCalculationStopper& stopper,
  73.           const CGraph* pGraph,
  74.           const CHeuristic* pHeuristic,
  75.           unsigned startIndex, unsigned endIndex,
  76.           const NavigationBlockers& navigationBlockers,
  77.           bool bDebugDrawOpenList);
  78.         /// Continue the path search - all pointers passed in to SetupAStar must still be valid
  79.         EAStarResult ContinueAStar(CCalculationStopper& stopper);
  80.  
  81.         /// Cancel any existing path request
  82.         void AbortAStar();
  83.  
  84.         /// returns the current heuristic
  85.         ILINE const CHeuristic* GetHeuristic() const
  86.         {
  87.                 return m_request.m_pHeuristic;
  88.         }
  89.  
  90.         typedef std::vector<unsigned> tPathNodes;
  91.  
  92.         /// Returns the path - only valid once pathfinding has returned ASTAR_PATHFOUND, and before
  93.         /// the next path is requested
  94.         ILINE const tPathNodes& GetPathNodes()
  95.         {
  96.                 return m_pathNodes;
  97.         }
  98.  
  99.         /// If the last result was ASTAR_NOPATH then this calculates and returns a partial path that ends
  100.         /// up as close as possible (according to the heuristic) to the requested destination
  101.         const tPathNodes& CalculateAndGetPartialPath();
  102.  
  103.         /// returns the memory usage in bytes
  104.         size_t                 MemStats();
  105.  
  106.         ILINE AStarSearchNode* GetAStarNode(unsigned index)
  107.         {
  108.                 return m_AStarNodeManager.GetAStarNode(index);
  109.         }
  110.  
  111.         ILINE const AStarSearchNodeVector& GetTaggedNodesVector()
  112.         {
  113.                 return m_AStarNodeManager.GetTaggedNodesVector();
  114.         }
  115.  
  116. private:
  117.         /// If continue/start found a path then this will actually ratify it - again all pointers
  118.         /// must still be valid
  119.         EAStarResult WalkBack(const CCalculationStopper& stopper);
  120.  
  121.         void         ASTARStep(const AStarSearchNode* pEnd);
  122.  
  123.         /// Everything we need to know to continue/recreate this request
  124.         struct CRequest
  125.         {
  126.                 // Cached state - i.e. state set up when a path is requested and maintained across
  127.                 // subsequent calls to ContinueAStar
  128.  
  129.                 /// Pointer to the graph currently being used. If 0 means we're not currently solving.
  130.                 const CGraph*     m_pGraph;
  131.                 /// A* heuristic
  132.                 const CHeuristic* m_pHeuristic;
  133.                 /// Pointer to the start graph node
  134.                 unsigned          m_startIndex;
  135.  
  136.                 /// Pointer to the end graph node
  137.                 unsigned m_endIndex;
  138.         };
  139.  
  140.         /// Our request
  141.         CRequest m_request;
  142.  
  143.         /// Final path we store - can be picked up using GetPathNodes()
  144.         tPathNodes m_pathNodes;
  145.  
  146.         /// current node we're working on
  147.         AStarSearchNode* m_pathfinderCurrent;
  148.  
  149.         /// Dynamic Node management including: The open list (nodes that still need investigating). Rather than using a closed
  150.         /// list, "closed" nodes will be tagged but not on the open list
  151.         CAStarNodeListManager m_AStarNodeManager;
  152.  
  153.         /// Searching for the path, or walking back to identify it after it's found?
  154.         bool m_bWalkingBack;
  155.  
  156.         /// Debug draw open list
  157.         bool m_bDebugDrawOpenList;
  158.  
  159.         /// collection of blockers used to dynamically modify the links
  160.         NavigationBlockers m_navigationBlockers;
  161.  
  162.         static int         s_instances;
  163.  
  164.         // Prevent copying which will break the instance count
  165.         CAStarSolver(const CAStarSolver&);
  166.         CAStarSolver& operator=(const CAStarSolver&);
  167. };
  168.  
  169. #endif
  170.  
downloadAStarSolver.h Source code - Download CRYENGINE Source code
Related Source Codes/Software:
postal - 2017-06-11
reactide - Reactide is the first dedicated IDE for React web ... 2017-06-11
rkt - rkt is a pod-native container engine for Linux. It... 2017-06-11
uWebSockets - Tiny WebSockets https://for... 2017-06-11
realworld - TodoMVC for the RealWorld - Exemplary fullstack Me... 2017-06-11
CRYENGINE - CRYENGINE is a powerful real-time game development... 2017-06-11
goreplay - GoReplay is an open-source tool for capturing and ... 2017-06-10
pyenv - Simple Python version management 2017-06-10
redux-saga - An alternative side effect model for Redux apps ... 2017-06-10
angular-starter - 2017-06-10

 Back to top