BVB Source Codes

CRYENGINE Show Graph.h Source code

Return Download CRYENGINE: download Graph.h Source code - Download CRYENGINE Source code - Type:.h
  1. // Copyright 2001-2016 Crytek GmbH / Crytek Group. All rights reserved.
  2.  
  3. /********************************************************************
  4.    -------------------------------------------------------------------------
  5.    File name:   Graph.h
  6.    $Id$
  7.    Description: interface for the CGraph class.
  8.  
  9.    -------------------------------------------------------------------------
  10.    History:
  11.    - ?
  12.  
  13.  *********************************************************************/
  14.  
  15. #if !defined(AFX_GRAPH_H__6D059D2E_5A74_4352_B3BF_2C88D446A2E1__INCLUDED_)
  16. #define AFX_GRAPH_H__6D059D2E_5A74_4352_B3BF_2C88D446A2E1__INCLUDED_
  17.  
  18. #if _MSC_VER > 1000
  19.         #pragma once
  20. #endif // _MSC_VER > 1000
  21.  
  22. #include <CryAISystem/IAISystem.h>
  23. #include <CryAISystem/IAgent.h>
  24. #include "NavPath.h"
  25. #include "AIHash.h"
  26. #include "AILog.h"
  27. #include "AllNodesContainer.h"
  28. #include "AutoTypeStructs.h"
  29.  
  30. #include <list>
  31. #include <map>
  32. #include <set>
  33. #include <vector>
  34. #include <CryCore/Containers/CryArray.h>
  35. #include <CryCore/Containers/VectorMap.h>
  36.  
  37. class CCryFile;
  38. class CGraphLinkManager;
  39.  
  40. enum EPathfinderResult
  41. {
  42.         PATHFINDER_STILLFINDING,
  43.         PATHFINDER_BEAUTIFYINGPATH,
  44.         PATHFINDER_POPNEWREQUEST,
  45.         PATHFINDER_PATHFOUND,
  46.         PATHFINDER_NOPATH,
  47.         PATHFINDER_ABORT,
  48.         PATHFINDER_MAXVALUE
  49. };
  50. class CAISystem;
  51. struct IStatObj;
  52. class ICrySizer;
  53. class CAIObject;
  54. class CVolumeNavRegion;
  55. class CFlightNavRegion;
  56. class CGraphNodeManager;
  57.  
  58. class CSmartObject;
  59. struct CCondition;
  60.  
  61. struct IVisArea;
  62.  
  63. inline int TypeIndexFromType(IAISystem::tNavCapMask type)
  64. {
  65.         int typeIndex;
  66.         for (typeIndex = IAISystem::NAV_TYPE_COUNT - 1; typeIndex >= 0 && ((1 << typeIndex) & type) == 0; --typeIndex)
  67.                 ;
  68.         return typeIndex;
  69. }
  70.  
  71. inline const char* StringFromTypeIndex(int typeIndex)
  72. {
  73.         static const char* navTypeStrings[] = {
  74.                 "NAV_UNSET",
  75.                 "NAV_TRIANGULAR",
  76.                 "NAV_WAYPOINT_HUMAN",
  77.                 "NAV_WAYPOINT_3DSURFACE",
  78.                 "NAV_FLIGHT",
  79.                 "NAV_VOLUME",
  80.                 "NAV_ROAD",
  81.                 "NAV_SMARTOBJECT",
  82.                 "NAV_FREE_2D",
  83.                 "NAV_CUSTOM_NAVIGATION",
  84.         };
  85.         const int STRING_COUNT = CRY_ARRAY_COUNT(navTypeStrings);
  86.  
  87.         static_assert(STRING_COUNT == static_cast<int>(IAISystem::NAV_TYPE_COUNT), "Unexpected array size!");
  88.  
  89.         if (typeIndex < 0)
  90.                 return "<Invalid Nav Type>";
  91.         else
  92.                 return navTypeStrings[typeIndex];
  93. }
  94.  
  95. inline const char* StringFromType(IAISystem::ENavigationType type)
  96. {
  97.         return StringFromTypeIndex(TypeIndexFromType(type));
  98. }
  99.  
  100. //====================================================================
  101. // CObstacleRef
  102. //====================================================================
  103. class CObstacleRef
  104. {
  105. protected:
  106.         CWeakRef<CAIObject> m_refAnchor;   // designer defined hiding point
  107.         int                 m_vertexIndex; // index of vertex
  108.         unsigned            m_nodeIndex;   // for indoors nodes could be hide points
  109.         GraphNode*          m_pNode;
  110.         CSmartObject*       m_pSmartObject; // pointer to smart object to be used for hiding
  111.         CCondition*         m_pRule;        // pointer to smart object rule to be used for hiding
  112.  
  113. public:
  114.         CAIObject*        GetAnchor() const      { return m_refAnchor.GetAIObject(); }
  115.         int               GetVertex() const      { return m_vertexIndex; }
  116.         const unsigned    GetNodeIndex() const   { return m_nodeIndex; }
  117.         const GraphNode*  GetNode() const        { return m_pNode; }
  118.         CSmartObject*     GetSmartObject() const { return m_pSmartObject; }
  119.         const CCondition* GetRule() const        { return m_pRule; }
  120.  
  121.         CObstacleRef() : m_vertexIndex(-1), m_nodeIndex(0), m_pNode(0), m_pSmartObject(NULL), m_pRule(NULL) {}
  122.         CObstacleRef(const CObstacleRef& other) : m_refAnchor(other.m_refAnchor), m_vertexIndex(other.m_vertexIndex), m_nodeIndex(other.m_nodeIndex), m_pNode(other.m_pNode),
  123.                 m_pSmartObject(other.m_pSmartObject), m_pRule(other.m_pRule) {}
  124.         CObstacleRef(CWeakRef<CAIObject> refAnchor) : m_refAnchor(refAnchor), m_vertexIndex(-1), m_nodeIndex(0), m_pNode(0), m_pSmartObject(NULL), m_pRule(NULL) {}
  125.         CObstacleRef(int vertexIndex) : m_vertexIndex(vertexIndex), m_nodeIndex(0), m_pNode(0), m_pSmartObject(NULL), m_pRule(NULL) {}
  126.         CObstacleRef(unsigned nodeIndex, GraphNode* pNode) : m_vertexIndex(-1), m_nodeIndex(nodeIndex), m_pNode(pNode), m_pSmartObject(NULL), m_pRule(NULL) {}
  127.         CObstacleRef(CSmartObject* pSmartObject, CCondition* pRule) : m_vertexIndex(-1), m_nodeIndex(0), m_pNode(0)
  128.                 , m_pSmartObject(pSmartObject), m_pRule(pRule) {}
  129.  
  130.         Vec3                GetPos() const;
  131.         float               GetApproxRadius() const;
  132.         const CObstacleRef& operator=(const CObstacleRef& other)
  133.         {
  134.                 m_refAnchor = other.m_refAnchor;
  135.                 m_vertexIndex = other.m_vertexIndex;
  136.                 m_nodeIndex = other.m_nodeIndex;
  137.                 m_pNode = other.m_pNode;
  138.                 m_pSmartObject = other.m_pSmartObject;
  139.                 m_pRule = other.m_pRule;
  140.                 return *this;
  141.         }
  142.  
  143.         bool operator==(const CObstacleRef& other) const
  144.         {
  145.                 return m_refAnchor == other.m_refAnchor && m_vertexIndex == other.m_vertexIndex && m_nodeIndex == other.m_nodeIndex
  146.                        && m_pNode == other.m_pNode && m_pSmartObject == other.m_pSmartObject && m_pRule == other.m_pRule;
  147.         }
  148.         bool operator!=(const CObstacleRef& other) const
  149.         {
  150.                 return m_refAnchor != other.m_refAnchor || m_vertexIndex != other.m_vertexIndex || m_nodeIndex != other.m_nodeIndex
  151.                        || m_pNode != other.m_pNode || m_pSmartObject != other.m_pSmartObject || m_pRule != other.m_pRule;
  152.         }
  153.         bool operator<(const CObstacleRef& other) const
  154.         {
  155.                 return
  156.                   m_nodeIndex < other.m_nodeIndex || m_nodeIndex == other.m_nodeIndex &&
  157.                   (m_refAnchor < other.m_refAnchor || m_refAnchor == other.m_refAnchor &&
  158.                    (m_vertexIndex < other.m_vertexIndex || m_vertexIndex == other.m_vertexIndex &&
  159.                     (m_pSmartObject < other.m_pSmartObject || m_pSmartObject < other.m_pSmartObject &&
  160.                      m_pRule < other.m_pRule)));
  161.         }
  162.         operator bool() const
  163.         {
  164.                 return m_refAnchor.IsValid() || m_vertexIndex >= 0 || m_nodeIndex || m_pSmartObject && m_pRule;
  165.         }
  166.         bool operator!() const
  167.         {
  168.                 return !m_refAnchor.IsValid() && m_vertexIndex < 0 && !m_nodeIndex && (!m_pSmartObject || !m_pRule);
  169.         }
  170.  
  171. private:
  172.         operator int() const
  173.         {
  174.                 // it is illegal to cast CObstacleRef to an int!!!
  175.                 // are you still using old code?
  176.                 AIAssert(0);
  177.                 return 0;
  178.         }
  179. };
  180.  
  181. // NOTE: int64 here avoids a tiny performance impact on 32-bit platform
  182. // for the cost of loss of full compatibility: 64-bit generated BAI files
  183. // can't be used on 32-bit platform safely. Change the key to int64 to
  184. // make it fully compatible. The code that uses this map will be recompiled
  185. // to use the full 64-bit key on both 32-bit and 64-bit platforms.
  186. typedef std::multimap<int64, unsigned>                EntranceMap;
  187. typedef std::vector<Vec3>                             ListPositions;
  188. typedef std::vector<ObstacleData>                     ListObstacles;
  189. typedef std::multimap<float, ObstacleData>            MultimapRangeObstacles;
  190. typedef std::vector<NodeDescriptor>                   NodeDescBuffer;
  191. typedef std::vector<LinkDescriptor>                   LinkDescBuffer;
  192. typedef std::list<unsigned>                           ListNodeIds;
  193. typedef std::set<GraphNode*>                          SetNodes;
  194. typedef std::set<const GraphNode*>                    SetConstNodes;
  195. typedef std::list<const GraphNode*>                   ListConstNodes;
  196. typedef std::vector<const GraphNode*>                 VectorConstNodes;
  197. typedef std::vector<unsigned>                         VectorConstNodeIndices;
  198. typedef std::multimap<float, GraphNode*>              CandidateMap;
  199. typedef std::multimap<float, unsigned>                CandidateIdMap;
  200. typedef std::set<CObstacleRef>                        SetObstacleRefs;
  201. typedef VectorMap<unsigned, SCachedPassabilityResult> PassabilityCache;
  202.  
  203. // [Mikko] Note: The Vector map is faster when traversing, and the normal map with pool allocator seems
  204. // to be a little faster in CGraph.GetNodesInRange. Both are faster than normal std::map.
  205. //typedef stl::STLPoolAllocator< std::pair<const GraphNode*, float> > NodeMapAllocator;
  206. //typedef std::map<const GraphNode*, float, std::less<const GraphNode*>, NodeMapAllocator> MapConstNodesDistance;
  207. typedef VectorMap<const GraphNode*, float> MapConstNodesDistance;
  208.  
  209. //====================================================================
  210. // CGraph
  211. //====================================================================
  212. class CGraph
  213. {
  214. public:
  215.         CGraph();
  216.         ~CGraph();
  217.  
  218.         CGraphLinkManager&       GetLinkManager()       { return *m_pGraphLinkManager; }
  219.         const CGraphLinkManager& GetLinkManager() const { return *m_pGraphLinkManager; }
  220.  
  221.         CGraphNodeManager&       GetNodeManager()       { return *m_pGraphNodeManager; }
  222.         const CGraphNodeManager& GetNodeManager() const { return *m_pGraphNodeManager; }
  223.  
  224.         /// Restores the graph to the initial state (i.e. restores pass radii etc).
  225.         void Reset();
  226.  
  227.         /// Calls CGraphNode::ResetIDs() with the correct arguments for this graph
  228.         void ResetIDs();
  229.  
  230.         /// removes all nodes and stuff associated with navTypes matching the bitmask
  231.         void Clear(IAISystem::tNavCapMask navTypeMask);
  232.  
  233.         /// Connects (two-way) two nodes, optionally returning pointers to the new links
  234.         void ConnectInCm(unsigned oneIndex, unsigned twoIndex, int16 radiusOneToTwoCm = 10000, int16 radiusTwoToOneCm = 10000,
  235.                          unsigned* pLinkOneTwo = 0, unsigned* pLinkTwoOne = 0);
  236.  
  237.         /// Connects (two-way) two nodes, optionally returning pointers to the new links
  238.         void Connect(unsigned oneIndex, unsigned twoIndex, float radiusOneToTwo = 100.0f, float radiusTwoToOne = 100.0f,
  239.                      unsigned* pLinkOneTwo = 0, unsigned* pLinkTwoOne = 0);
  240.  
  241.         /// Disconnects a node from its neighbours. if bDelete then pNode will be deleted. Note that
  242.         /// the previously connected nodes will not be deleted, even if they
  243.         /// end up with no nodes.
  244.         void Disconnect(unsigned nodeIndex, bool bDelete = true);
  245.  
  246.         /// Removes an individual link from a node (and removes the reciprocal link) -
  247.         /// doesn't delete it.
  248.         void Disconnect(unsigned nodeIndex, unsigned linkId);
  249.  
  250.         /// Checks the graph is OK (as far as possible). Asserts if not, and then
  251.         /// returns true/false to indicate if it's OK
  252.         /// msg should indicate where this is being called from (for writing error msgs)
  253.         bool Validate(const char* msg, bool checkPassable) const;
  254.  
  255.         /// Checks that a node exists (should be quick). If fullCheck is true it will do some further
  256.         /// checks which will be slower
  257.         bool ValidateNode(unsigned nodeIndex, bool fullCheck) const;
  258.         bool ValidateHashSpace() { return m_allNodes.ValidateHashSpace(); }
  259.  
  260.         /// Restores all node/links
  261.         void RestoreAllNavigation();
  262.  
  263.         /// Reads the AI graph from a specified file
  264.         bool ReadFromFile(const char* szName);
  265.  
  266.         /// Returns all nodes that are in the graph - not all nodes will be
  267.         /// connected (even indirectly) to each other
  268.         CAllNodesContainer&       GetAllNodes()       { return m_allNodes; }
  269.         const CAllNodesContainer& GetAllNodes() const { return m_allNodes; }
  270.  
  271.         /// Checks that the graph is empty. Pass in a bitmask of IAISystem::ENavigationType to
  272.         /// specify the types to check
  273.         bool CheckForEmpty(IAISystem::tNavCapMask navTypeMask = IAISystem::NAVMASK_ALL) const;
  274.  
  275.         /// uses mark for internal graph operation without disturbing the pathfinder
  276.         void MarkNode(unsigned nodeIndex) const;
  277.         /// clears the marked nodes
  278.         void ClearMarks() const;
  279.  
  280.         // defines bounding rectangle of this graph
  281.         void SetBBox(const Vec3& min, const Vec3& max);
  282.         // how is that for descriptive naming of functions ??
  283.         bool InsideOfBBox(const Vec3& pos) const;  // returns true if pos is inside of bbox (but not on boundaries)
  284.  
  285.         /// Creates a new node of the specified type (which can't be subsequently changed). Note that
  286.         /// to delete the node use the disconnect function.
  287.         unsigned         CreateNewNode(IAISystem::tNavCapMask type, const Vec3& pos, unsigned ID = 0);
  288.         GraphNode*       GetNode(unsigned index);
  289.         const GraphNode* GetNode(unsigned index) const;
  290.  
  291.         /// Moves a node, updating spatial structures
  292.         void MoveNode(unsigned nodeIndex, const Vec3& newPos);
  293.  
  294.         /// finds all nodes within range of startPos and their distance from vStart.
  295.         /// pStart is just used as a hint.
  296.         /// returns a reference to the input/output so it's easy to use in a test.
  297.         /// traverseForbiddenHideLink should be true if you want to pass through
  298.         /// links between hide waypoints that have been marked as impassable
  299.         /// SmartObjects will only be considered if pRequester != 0
  300.         MapConstNodesDistance& GetNodesInRange(MapConstNodesDistance& result, const Vec3& startPos, float maxDist,
  301.                                                IAISystem::tNavCapMask navCapMask, float passRadius, unsigned startNodeIndex = 0, const class CAIObject* pRequester = 0);
  302.  
  303.         // Returns memory usage not including nodes
  304.         size_t MemStats();
  305.  
  306.         // Returns the memory usage for nodes of the type passed in (bitmask)
  307.         size_t NodeMemStats(unsigned navTypeMask);
  308.  
  309.         void   GetMemoryStatistics(ICrySizer* pSizer);
  310.  
  311.         struct SBadGraphData
  312.         {
  313.                 enum EType {BAD_PASSABLE, BAD_IMPASSABLE};
  314.                 EType mType;
  315.                 Vec3  mPos1, mPos2;
  316.         };
  317.         /// List of bad stuff we found during the last validation. mutable because it's
  318.         /// debug - Validate(...) should really be a const method, since it wouldn't change
  319.         /// any "real" data
  320.         mutable std::vector<SBadGraphData> mBadGraphData;
  321.  
  322.         GraphNode*                         m_pSafeFirst;
  323.         unsigned                           m_safeFirstIndex;
  324.  
  325.         CGraphNodeManager*                 m_pGraphNodeManager;
  326.  
  327. private:
  328.  
  329.         /// Finds nodes within a distance of pNode that can be accessed by something with
  330.         /// passRadius. If pRequester != 0 then smart object links will be checked as well.
  331.         void FindNodesWithinRange(MapConstNodesDistance& result, float curDist, float maxDist,
  332.                                   const GraphNode* pNode, float passRadius, const class CAIObject* pRequester) const;
  333.  
  334.         bool DbgCheckList(ListNodeIds& nodesList) const;
  335.  
  336. public:
  337.         /// deletes (disconnects too) all nodes with a type matching the bitmask
  338.         void DeleteGraph(IAISystem::tNavCapMask navTypeMask);
  339.  
  340. private:
  341.         GraphNode* GetEntrance(int nBuildingID, const Vec3& pos);
  342.         bool       GetEntrances(int nBuildingID, const Vec3& pos, std::vector<unsigned>& nodes);
  343.         // reads all the nodes in a map
  344.         bool       ReadNodes(CCryFile& file);
  345.         /// Deletes the node, which should have been disconnected first (warning if not)
  346.         void       DeleteNode(unsigned nodeIndex);
  347.  
  348.         // helper called from ValidateNode only (to get ValidateNode to be inlined inside
  349.         // Graph.cpp)
  350.         bool ValidateNodeFullCheck(const GraphNode* pNode) const;
  351.  
  352.         unsigned   m_currentIndex;
  353.         GraphNode* m_pCurrent;
  354.         unsigned   m_firstIndex;
  355.         GraphNode* m_pFirst;
  356.  
  357.         /// All the nodes we've marked
  358.         mutable VectorConstNodeIndices m_markedNodes;
  359.         /// All the nodes we've tagged
  360.         mutable VectorConstNodeIndices m_taggedNodes;
  361.  
  362.         /// nodes are allocated/deleted via a single interface, so keep track of them
  363.         /// all - for memory tracking and to allow quick iteration
  364.         CAllNodesContainer m_allNodes;
  365.  
  366.         CGraphLinkManager* m_pGraphLinkManager;
  367.  
  368.         /// Bounding box of the triangular area
  369.         AABB        m_triangularBBox;
  370.  
  371.         EntranceMap m_mapEntrances;
  372.         EntranceMap m_mapExits;
  373.         friend class CFlightNavRegion;
  374.         friend class CVolumeNavRegion;
  375. };
  376.  
  377. // Check whether a position is within a node's triangle
  378. bool PointInTriangle(const Vec3& pos, GraphNode* pNode);
  379.  
  380. //====================================================================
  381. // SMarkClearer
  382. // Helper - the constructor and destructor clear marks
  383. //====================================================================
  384. struct SMarkClearer
  385. {
  386.         SMarkClearer(const CGraph* pGraph) : m_pGraph(pGraph) { m_pGraph->ClearMarks(); }
  387.         ~SMarkClearer() { m_pGraph->ClearMarks(); }
  388. private:
  389.         const CGraph* m_pGraph;
  390. };
  391.  
  392. #endif // !defined(AFX_GRAPH_H__6D059D2E_5A74_4352_B3BF_2C88D446A2E1__INCLUDED_)
  393.  
downloadGraph.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