BVB Source Codes

CRYENGINE Show GraphStructures.h Source code

Return Download CRYENGINE: download GraphStructures.h Source code - Download CRYENGINE Source code - Type:.h
  1. // Copyright 2001-2016 Crytek GmbH / Crytek Group. All rights reserved.
  2.  
  3. #ifndef GRAPHSTRUCTURES_H
  4. #define GRAPHSTRUCTURES_H
  5.  
  6. #if _MSC_VER > 1000
  7.         #pragma once
  8. #endif
  9.  
  10. #include "AutoTypeStructs.h"
  11.  
  12. #if CRY_PLATFORM_LINUX || CRY_PLATFORM_ANDROID
  13.         #include <float.h>
  14. #endif
  15.  
  16. #ifdef _DEBUG
  17.         #define DEBUG_GRAPHNODE_IDS
  18. #endif
  19.  
  20. class ObstacleIndexVector
  21. {
  22. public:
  23.         typedef const int* const_iterator;
  24.         typedef int*       iterator;
  25.         ObstacleIndexVector() { clear(); }
  26.         const_iterator begin() const                  { return &m_idx[0]; }
  27.         const_iterator end() const                    { return &m_idx[size()]; }
  28.         iterator       begin()                        { return &m_idx[0]; }
  29.         iterator       end()                          { return &m_idx[size()]; }
  30.         size_t         size() const                   { return (m_idx[2] < 0) ? (size_t)(-m_idx[2] - 1) : 3; }
  31.         size_t         capacity() const               { return 3; }
  32.         bool           empty() const                  { return m_idx[2] == -1; }
  33.         void           reserve(size_t size)           { assert(size <= 3); }
  34.         void           clear()                        { m_idx[0] = -1; m_idx[1] = -1; m_idx[2] = -1; }
  35.         void           swap(ObstacleIndexVector& rhs) { for (int i = 0; i < 3; i++) { int tmp = m_idx[i]; m_idx[i] = rhs.m_idx[i]; rhs.m_idx[i] = tmp; } }
  36.         void           push_back(int val)             { assert(val >= 0); assert(m_idx[2] < 0); m_idx[2]--; m_idx[size() - 1] = val; }
  37.         int            operator[](int idx) const      { assert(idx >= 0 && idx < (int)size()); return m_idx[idx]; }
  38. private:
  39.         int m_idx[3];
  40. };
  41.  
  42. struct GraphNode;
  43. class CGraphNodeManager;
  44. class CSmartObjectClass;
  45. class CSmartObject;
  46. struct SmartObjectHelper;
  47.  
  48. namespace NavGraphUtils
  49. {
  50. ILINE int16 InCentimeters(float distance)
  51. {
  52.         return (int16)(distance * 100.0f);
  53. }
  54.  
  55. ILINE float InMeters(int16 distanceInCm)
  56. {
  57.         return (float)distanceInCm * 0.01f;
  58. }
  59. }
  60.  
  61. //====================================================================
  62. // GraphLinkBidirectionalData
  63. //====================================================================
  64.  
  65. struct GraphLinkBidirectionalData
  66. {
  67.         friend class CGraphLinkManager;
  68.  
  69.         GraphLinkBidirectionalData()
  70.                 : fExposure(0.0f), vEdgeCenter(0.0f, 0.0f, 0.0f)
  71.         {
  72.                 directionalData[0].nextLinkIndex = directionalData[1].nextLinkIndex = 0;
  73.                 directionalData[0].nextNodeIndex = directionalData[1].nextNodeIndex = 0;
  74.                 directionalData[0].waterDepthInCmHigh = directionalData[1].waterDepthInCmHigh = 0;
  75.                 directionalData[0].waterDepthInCmLow = directionalData[1].waterDepthInCmLow = 0;
  76.                 directionalData[0].maxRadiusInCm = directionalData[1].maxRadiusInCm = 0;
  77.                 directionalData[0].origMaxRadiusInCm = directionalData[1].origMaxRadiusInCm = 0;
  78.                 directionalData[0].startIndex = directionalData[1].startIndex = 0;
  79.                 directionalData[0].endIndex = directionalData[1].endIndex = 0;
  80.                 directionalData[0].simplePassabilityCheck = directionalData[1].simplePassabilityCheck = 0;
  81.         }
  82.  
  83. private:
  84.         struct DirectionalData
  85.         {
  86.                 // maximum size sphere that can pass trough this edge
  87.                 signed maxRadiusInCm : 16;
  88.  
  89.                 // links may get modified at run-time - store a copy of their original pass radius
  90.                 signed origMaxRadiusInCm : 16;
  91.  
  92.                 // Links are stored in a linked-list - this is the index of the next link for the nodes at each end.
  93.                 unsigned nextLinkIndex : 23;
  94.  
  95.                 // Indicates if a human waypoint link can use simplified walkability check.  For other link
  96.                 // types is not applicable.
  97.                 //
  98.                 // NOTE Apr 26, 2007: <pvl> in order not to undo memory optimization done earlier this
  99.                 // member is used in a very tricky way.  In directionalData[0] it says whether this
  100.                 // link is "simple" while in directionalData[1] it indicates if the link "simplicity"
  101.                 // has already been computed at all (so when it's 'false' then
  102.                 // directionalData[0].simplePassabilityCheck cannot be considered valid).
  103.                 // This ugliness is encapsulated in GraphLinkManager but anyway ...
  104.                 //
  105.                 // By doing all of this, I sold my soul to MichaelS.
  106.                 unsigned simplePassabilityCheck : 1;
  107.  
  108.                 // Minimum/maximum (depending on which direction we are talking) water depth over this link in cm.
  109.                 // Has to be split up into two to make the bitfields add up to 32 bit blocks (it doesnt seem to pack properly
  110.                 // otherwise).
  111.                 unsigned waterDepthInCmLow  : 8;
  112.                 signed   waterDepthInCmHigh : 8;
  113.  
  114.                 // next graph node this way
  115.                 unsigned nextNodeIndex : 20;
  116.  
  117.                 // indices of the edge vertices of this edge - only valid for 2D navigation
  118.                 // types (triangle and waypoint).
  119.                 unsigned startIndex : 2;
  120.                 unsigned endIndex   : 2;
  121.         };
  122.  
  123.         DirectionalData directionalData[2];
  124.  
  125.         /// The exposure associated with this link
  126.         float fExposure;
  127.         Vec3  vEdgeCenter;
  128. };
  129.  
  130. #include "GraphLinkManager.h"
  131.  
  132. struct SCachedPassabilityResult
  133. {
  134.         SCachedPassabilityResult()
  135.                 : spatialHash(0)
  136.                 , walkableResult(false)
  137.         {
  138.         }
  139.  
  140.         SCachedPassabilityResult(size_t hash, bool walkable)
  141.                 : spatialHash(hash)
  142.                 , walkableResult(walkable)
  143.         {
  144.         }
  145.  
  146.         void Reset(size_t hash, bool walkable)
  147.         {
  148.                 spatialHash = hash;
  149.                 walkableResult = walkable;
  150.         }
  151.  
  152.         size_t spatialHash;
  153.         bool   walkableResult;
  154. };
  155.  
  156. struct IVisArea;
  157.  
  158. struct STriangularNavData
  159. {
  160.         STriangularNavData() : isForbidden(0), isForbiddenDesigner(0) {}
  161.         ObstacleIndexVector vertices;
  162.         /// isForbidden is set for navigation nodes that lie inside a forbidden area
  163.         uint8               isForbidden         : 1;
  164.         /// isForbiddenDesigner is only set for nav nodes inside designer forbidden areas
  165.         uint8               isForbiddenDesigner : 1;
  166.  
  167.         real GetDegeneracyValue();
  168.         void MakeAntiClockwise();
  169.         bool IsAntiClockwise();
  170.         real GetCross(CGraphLinkManager& linkManager, const Vec3r& vCutStart, const Vec3r& vDir, unsigned theLink);
  171. };
  172.  
  173. struct SWaypointNavData
  174. {
  175.         IVisArea*                pArea;
  176.  
  177.         static EWaypointLinkType GetLinkTypeFromRadius(float radius)
  178.         {
  179.                 if (abs(radius - WLT_AUTO_PASS) < 0.001f)
  180.                         return WLT_AUTO_PASS;
  181.                 else if (abs(radius - WLT_EDITOR_PASS) < 0.001f)
  182.                         return WLT_EDITOR_PASS;
  183.                 else if (abs(radius - WLT_EDITOR_IMPASS) < 0.001f)
  184.                         return WLT_EDITOR_IMPASS;
  185.                 else if (abs(radius - WLT_AUTO_IMPASS) < 0.001f)
  186.                         return WLT_AUTO_IMPASS;
  187.                 else
  188.                         return WLT_UNKNOWN_TYPE;
  189.         }
  190.  
  191.         static EWaypointLinkType GetLinkTypeFromRadiusInCm(int16 radius)
  192.         {
  193.                 if (radius == (WLT_AUTO_PASS * 100))
  194.                         return WLT_AUTO_PASS;
  195.                 else if (radius == WLT_EDITOR_PASS * 100)
  196.                         return WLT_EDITOR_PASS;
  197.                 else if (radius == WLT_EDITOR_IMPASS * 100)
  198.                         return WLT_EDITOR_IMPASS;
  199.                 else if (radius == WLT_AUTO_IMPASS * 100)
  200.                         return WLT_AUTO_IMPASS;
  201.                 else
  202.                         return WLT_UNKNOWN_TYPE;
  203.         }
  204.  
  205.         int               nBuildingID;
  206.         EWaypointNodeType type;
  207.  
  208.         // if it's a hide point then store the direction the hide point faces.
  209.         Vec3 dir;
  210.         // Stores the local up (z) axis of the point - used in nav regions where type = 1 (3D surface)
  211.         Vec3 up;
  212.  
  213.         SWaypointNavData() : pArea(0), nBuildingID(-1), type(WNT_UNSET), dir(ZERO), up(0, 0, 1) {}
  214. };
  215.  
  216. struct SFlightNavData
  217. {
  218.         int nSpanIdx;
  219.         //  SFlightNavData() : nSpanIdx(-1) {}
  220. };
  221.  
  222. struct SVolumeNavData
  223. {
  224.         int nVolimeIdx;
  225.         //  SVolumeNavData() : nVolimeIdx(-1) {}
  226. };
  227.  
  228. struct SRoadNavData
  229. {
  230.         /// total width of the road at this point
  231.         float fRoadWidth;
  232.         /// offset for driving (+ve is on the right side of the road)
  233.  
  234.         // As soon as we decided use only Width not needed store this structure separate
  235.         //float fRoadOffset;
  236.         //SRoadNavData() : fRoadWidth(0.0f), fRoadOffset(0.0f) {}
  237. };
  238.  
  239. struct SSmartObjectNavData
  240. {
  241.         CSmartObjectClass* pClass;
  242.         SmartObjectHelper* pHelper;
  243.         CSmartObject*      pSmartObject;
  244. };
  245.  
  246. struct SLayeredMeshNavData
  247. {
  248.         static const unsigned s_polyIndexWidth = 20;
  249.         static const unsigned s_modifIndexWidth = 8;
  250.         static const unsigned s_agentTypeWidth = 4;
  251.  
  252.         static const unsigned s_polyIndexShift = 0;
  253.         static const unsigned s_modifIndexShift = s_polyIndexWidth;
  254.         static const unsigned s_agentTypeShift = s_polyIndexWidth + s_modifIndexWidth;
  255.  
  256.         static const unsigned s_polyIndexMask = (1 << s_polyIndexWidth) - 1;
  257.         static const unsigned s_modifIndexMask = (1 << s_modifIndexWidth) - 1;
  258.         static const unsigned s_agentTypeMask = (1 << s_agentTypeWidth) - 1;
  259.  
  260.         unsigned int          polygonIndex: s_polyIndexWidth;
  261.         unsigned int          navModifIndex: s_modifIndexWidth;
  262.         unsigned int          agentType: s_agentTypeWidth;
  263.  
  264.         // NOTE Feb 18, 2009: <pvl> unpack members from a single int (useful for deserialisation)
  265.         void SetFromPacked(unsigned packed)
  266.         {
  267.                 polygonIndex = (packed >> s_polyIndexShift) & s_polyIndexMask;
  268.                 navModifIndex = (packed >> s_modifIndexShift) & s_modifIndexMask;
  269.                 agentType = (packed >> s_agentTypeShift) & s_agentTypeMask;
  270.         }
  271. };
  272.  
  273. struct PathfindingHeuristicProperties;
  274.  
  275. struct SCustomNavData
  276. {
  277.         typedef float (* CostFunction)(const void* node1Data, const void* node2Data, const PathfindingHeuristicProperties& pathFindProperties);
  278.  
  279.         void*        pCustomData;
  280.         CostFunction pCostFunction;
  281.         uint16       customId;
  282.  
  283.         SCustomNavData() : pCustomData(0), pCostFunction(0), customId(0)
  284.         {}
  285. };
  286.  
  287. //====================================================================
  288. // GraphNode
  289. // In principle this is a constant structure in that the pathfinder
  290. // doesn't modify it. However, in practice during pathfinding it's
  291. // convenient to cache some info along with the node - hence the
  292. // mutable members
  293. // This structure needs to represent different types of nodes - the basic
  294. // info should just represent the generic navigation info, and the data
  295. // specific to the navigation region lives in navData
  296. //====================================================================
  297. struct GraphNode
  298. {
  299.         /// navType is const so that nodes can be stored in lists of their respective types
  300.         const IAISystem::ENavigationType navType;
  301.  
  302.         /// The position of the node The position can only be set indirectly so that
  303.         /// the AI system can update any spatial structures containing this node
  304.         const Vec3&                GetPos() const { return pos; }
  305.  
  306.         STriangularNavData*        GetTriangularNavData();
  307.         SWaypointNavData*          GetWaypointNavData();
  308.         SFlightNavData*            GetFlightNavData();
  309.         SVolumeNavData*            GetVolumeNavData();
  310.         SRoadNavData*              GetRoadNavData();
  311.         SSmartObjectNavData*       GetSmartObjectNavData();
  312.         SLayeredMeshNavData*       GetLayeredMeshNavData();
  313.  
  314.         const STriangularNavData*  GetTriangularNavData() const;
  315.         const SWaypointNavData*    GetWaypointNavData() const;
  316.         const SFlightNavData*      GetFlightNavData() const;
  317.         const SVolumeNavData*      GetVolumeNavData() const;
  318.         const SRoadNavData*        GetRoadNavData() const;
  319.         const SSmartObjectNavData* GetSmartObjectNavData() const;
  320.         const SLayeredMeshNavData* GetLayeredMeshNavData() const;
  321.  
  322.         /// Used as a flag for costs that aren't calculated yet
  323.         static const float fInvalidCost;
  324.  
  325.         // Returns the link index that goes to destNode. -1 if no link found
  326.         int      GetLinkIndex(CGraphNodeManager& nodeManager, CGraphLinkManager& linkManager, const GraphNode* destNode) const;
  327.         unsigned GetLinkTo(CGraphNodeManager& nodeManager, CGraphLinkManager& linkManager, const GraphNode* destNode) const;
  328.         int      GetLinkCount(CGraphLinkManager& linkManager) const;
  329.         void     RemoveLinkTo(CGraphLinkManager& linkManager, unsigned nodeIndex);
  330.  
  331.         /// Returns the maximu radius from all the links
  332.         float GetMaxLinkRadius(CGraphLinkManager& linkManager) const
  333.         {
  334.                 float r = -FLT_MAX;
  335.                 //for (unsigned i = links.size() ; i-- != 0 ;)
  336.                 for (unsigned link = firstLinkIndex; link; link = linkManager.GetNextLink(link))
  337.                         if (linkManager.GetRadius(link) > r)
  338.                                 r = linkManager.GetRadius(link);
  339.                 return r;
  340.         }
  341.  
  342.         unsigned FindNewLink(CGraphLinkManager& linkManager);
  343.  
  344.         bool     Release()
  345.         {
  346.                 assert(nRefCount >= 1);
  347.                 --nRefCount;
  348.                 if (nRefCount == 0)
  349.                         return true;
  350.                 return false;
  351.         }
  352.  
  353.         void AddRef()
  354.         {
  355.                 assert(nRefCount < std::numeric_limits<TRefCount>::max());
  356.                 ++nRefCount;
  357.         }
  358.  
  359.         // this resets our IDs and assigns a unique ID to all the nodes in the container.
  360.         // Should just be called on navigation graph saving. pNodeForID1 is a special node
  361.         // that will have ID 1 assigned to it
  362.         static void ResetIDs(CGraphNodeManager & nodeManager, class CAllNodesContainer & allNodes, GraphNode * pNodeForID1);
  363.  
  364.         size_t      MemStats();
  365.  
  366.         static void ClearFreeIDs() { stl::free_container(freeIDs); }
  367.  
  368.         // This must ONLY be called via the graph node deletion function
  369.         ~GraphNode();
  370.  
  371. protected:
  372.         /// This must ONLY be called via the graph node creation function.
  373.         /// If _ID == 0 then an ID will be assigned automatically
  374.         GraphNode(IAISystem::ENavigationType type, const Vec3& inpos, unsigned int _ID);
  375.  
  376. private:
  377.         friend class CGraph;
  378.         friend struct GraphNodesPool;
  379.  
  380.         void SetPos(const Vec3& newPos) { pos = newPos; }
  381.  
  382. public:
  383.         // Links are stored in a linked-list - this is the index of the next link for the nodes at each end.
  384.         unsigned firstLinkIndex;
  385.  
  386. private:
  387.         // stuff below here is basically constant (i.e. not modified by pathfinding), unless
  388.         // the world changes.
  389.         // unique ID - preserved when saving.
  390.         unsigned int                     ID;
  391.  
  392.         Vec3                             pos;
  393.         /// The pool of free IDs - populated when nodes are deleted
  394.         static std::vector<unsigned int> freeIDs;
  395.         /// The highest ID currently in use (0 is invalid), so maxID+1 is a valid unique ID
  396. #ifdef DEBUG_GRAPHNODE_IDS
  397.         static std::vector<unsigned int> usedIds;
  398. #endif
  399.  
  400.         static unsigned int maxID;
  401. public:
  402.         typedef unsigned short TRefCount;
  403.         TRefCount nRefCount;
  404.  
  405.         /// General marker used to help traversing the graph of nodes. If you use this
  406.         /// be careful about calling other functions that use it! Not used by pathfinder
  407.         mutable unsigned char mark;//:1;
  408.  
  409. };
  410.  
  411. struct GraphNode_Unset : public GraphNode
  412. {
  413. private:
  414.         friend class CGraph;
  415.         friend struct GraphNodesPool;
  416.         friend class CGraphNodeManager;
  417.  
  418.         GraphNode_Unset(IAISystem::ENavigationType type, const Vec3& inpos, unsigned int _ID)
  419.                 : GraphNode(type, inpos, _ID) {}
  420.  
  421.         // This must ONLY be called via the graph node deletion function
  422.         ~GraphNode_Unset() {}
  423. };
  424.  
  425. struct GraphNode_Triangular : public GraphNode
  426. {
  427. private:
  428.         friend struct GraphNode;
  429.         friend class CGraph;
  430.         friend struct GraphNodesPool;
  431.         friend class CGraphNodeManager;
  432.  
  433.         GraphNode_Triangular(IAISystem::ENavigationType type, const Vec3& inpos, unsigned int _ID)
  434.                 : GraphNode(type, inpos, _ID) {}
  435.  
  436.         // This must ONLY be called via the graph node deletion function
  437.         ~GraphNode_Triangular() {}
  438.  
  439.         STriangularNavData navData;
  440. };
  441.  
  442. struct GraphNode_Waypoint : public GraphNode
  443. {
  444. protected:
  445.         friend struct GraphNode;
  446.         friend class CGraph;
  447.         friend struct GraphNodesPool;
  448.         friend class CGraphNodeManager;
  449.  
  450.         GraphNode_Waypoint(IAISystem::ENavigationType type, const Vec3& inpos, unsigned int _ID)
  451.                 : GraphNode(type, inpos, _ID) {}
  452.  
  453.         // This must ONLY be called via the graph node deletion function
  454.         ~GraphNode_Waypoint() {}
  455.  
  456.         SWaypointNavData navData;
  457. };
  458.  
  459. struct GraphNode_WaypointHuman : public GraphNode_Waypoint
  460. {
  461. private:
  462.         friend struct GraphNode;
  463.         friend class CGraph;
  464.         friend struct GraphNodesPool;
  465.         friend class CGraphNodeManager;
  466.  
  467.         GraphNode_WaypointHuman(IAISystem::ENavigationType type, const Vec3& inpos, unsigned int _ID)
  468.                 : GraphNode_Waypoint(type, inpos, _ID) {}
  469.  
  470.         // This must ONLY be called via the graph node deletion function
  471.         ~GraphNode_WaypointHuman() {}
  472. };
  473.  
  474. struct GraphNode_Waypoint3DSurface : public GraphNode_Waypoint
  475. {
  476. private:
  477.         friend struct GraphNode;
  478.         friend class CGraph;
  479.         friend struct GraphNodesPool;
  480.         friend class CGraphNodeManager;
  481.  
  482.         GraphNode_Waypoint3DSurface(IAISystem::ENavigationType type, const Vec3& inpos, unsigned int _ID)
  483.                 : GraphNode_Waypoint(type, inpos, _ID) {}
  484.  
  485.         // This must ONLY be called via the graph node deletion function
  486.         ~GraphNode_Waypoint3DSurface() {}
  487. };
  488.  
  489. struct GraphNode_Flight : public GraphNode
  490. {
  491. private:
  492.         friend struct GraphNode;
  493.         friend class CGraph;
  494.         friend struct GraphNodesPool;
  495.         friend class CGraphNodeManager;
  496.  
  497.         GraphNode_Flight(IAISystem::ENavigationType type, const Vec3& inpos, unsigned int _ID)
  498.                 : GraphNode(type, inpos, _ID) {}
  499.  
  500.         // This must ONLY be called via the graph node deletion function
  501.         ~GraphNode_Flight() {}
  502.  
  503.         SFlightNavData navData;
  504. };
  505.  
  506. struct GraphNode_Volume : public GraphNode
  507. {
  508. private:
  509.         friend struct GraphNode;
  510.         friend class CGraph;
  511.         friend struct GraphNodesPool;
  512.         friend class CGraphNodeManager;
  513.  
  514.         GraphNode_Volume(IAISystem::ENavigationType type, const Vec3& inpos, unsigned int _ID)
  515.                 : GraphNode(type, inpos, _ID) {}
  516.  
  517.         // This must ONLY be called via the graph node deletion function
  518.         ~GraphNode_Volume() {}
  519.  
  520.         SVolumeNavData navData;
  521. };
  522.  
  523. struct GraphNode_Road : public GraphNode
  524. {
  525. private:
  526.         friend struct GraphNode;
  527.         friend class CGraph;
  528.         friend struct GraphNodesPool;
  529.         friend class CGraphNodeManager;
  530.  
  531.         GraphNode_Road(IAISystem::ENavigationType type, const Vec3& inpos, unsigned int _ID)
  532.                 : GraphNode(type, inpos, _ID) {}
  533.  
  534.         // This must ONLY be called via the graph node deletion function
  535.         ~GraphNode_Road() {}
  536.  
  537.         SRoadNavData navData;
  538. };
  539.  
  540. struct GraphNode_SmartObject : public GraphNode
  541. {
  542. private:
  543.         friend struct GraphNode;
  544.         friend class CGraph;
  545.         friend struct GraphNodesPool;
  546.         friend class CGraphNodeManager;
  547.  
  548.         GraphNode_SmartObject(IAISystem::ENavigationType type, const Vec3& inpos, unsigned int _ID)
  549.                 : GraphNode(type, inpos, _ID) {}
  550.  
  551.         // This must ONLY be called via the graph node deletion function
  552.         ~GraphNode_SmartObject() {}
  553.  
  554.         SSmartObjectNavData navData;
  555. };
  556.  
  557. struct GraphNode_Free2D : public GraphNode
  558. {
  559. private:
  560.         friend struct GraphNode;
  561.         friend class CGraph;
  562.         friend struct GraphNodesPool;
  563.         friend class CGraphNodeManager;
  564.  
  565.         GraphNode_Free2D(IAISystem::ENavigationType type, const Vec3& inpos, unsigned int _ID)
  566.                 : GraphNode(type, inpos, _ID) {}
  567.  
  568.         // This must ONLY be called via the graph node deletion function
  569.         ~GraphNode_Free2D() {}
  570. };
  571.  
  572. struct GraphNode_CustomNav : public GraphNode
  573. {
  574.         friend struct GraphNode;
  575.         friend class CGraph;
  576.         friend struct GraphNodesPool;
  577.         friend class CGraphNodeManager;
  578.  
  579.         GraphNode_CustomNav(IAISystem::ENavigationType type, const Vec3& inpos, unsigned int _ID) : GraphNode(type, inpos, _ID)
  580.         {}
  581.  
  582.         // This must ONLY be called via the graph node deletion function
  583.         ~GraphNode_CustomNav()
  584.         {}
  585.  
  586.         SCustomNavData navData;
  587.  
  588. public:
  589.  
  590.         void SetCustomData(void* customData)
  591.         {
  592.                 navData.pCustomData = customData;
  593.         }
  594.  
  595.         void SetCustomId(uint16 customId)
  596.         {
  597.                 navData.customId = customId;
  598.         }
  599.  
  600.         void* GetCustomData()
  601.         {
  602.                 return navData.pCustomData;
  603.         }
  604.  
  605.         const void* GetCustomData() const
  606.         {
  607.                 return navData.pCustomData;
  608.         }
  609.  
  610.         uint16 GetCustomId()
  611.         {
  612.                 return navData.customId;
  613.         }
  614.  
  615.         uint16 GetCustomId() const
  616.         {
  617.                 return navData.customId;
  618.         }
  619.  
  620.         void SetCostFunction(SCustomNavData::CostFunction pCostFunction)
  621.         {
  622.                 navData.pCostFunction = pCostFunction;
  623.         }
  624.  
  625.         float CustomLinkCostFactor(const void* node1Data, const void* node2Data, const PathfindingHeuristicProperties& pathFindProperties) const
  626.         {
  627.                 float ret = FLT_MAX;
  628.  
  629.                 if (navData.pCostFunction)
  630.                 {
  631.                         ret = navData.pCostFunction(node1Data, node2Data, pathFindProperties);
  632.                 }
  633.  
  634.                 return ret;
  635.         };
  636. };
  637.  
  638. #include "GraphNodeManager.h"
  639.  
  640. inline STriangularNavData*        GraphNode::GetTriangularNavData()        { assert(navType == IAISystem::NAV_TRIANGULAR); return &((GraphNode_Triangular*)this)->navData; }
  641. inline SWaypointNavData*          GraphNode::GetWaypointNavData()          { assert(navType == IAISystem::NAV_WAYPOINT_3DSURFACE || navType == IAISystem::NAV_WAYPOINT_HUMAN); return &((GraphNode_Waypoint*)this)->navData; }
  642. inline SFlightNavData*            GraphNode::GetFlightNavData()            { assert(navType == IAISystem::NAV_FLIGHT); return &((GraphNode_Flight*)this)->navData; }
  643. inline SVolumeNavData*            GraphNode::GetVolumeNavData()            { assert(navType == IAISystem::NAV_VOLUME); return &((GraphNode_Volume*)this)->navData; }
  644. inline SRoadNavData*              GraphNode::GetRoadNavData()              { assert(navType == IAISystem::NAV_ROAD); return &((GraphNode_Road*)this)->navData; }
  645. inline SSmartObjectNavData*       GraphNode::GetSmartObjectNavData()       { assert(navType == IAISystem::NAV_SMARTOBJECT); return &((GraphNode_SmartObject*)this)->navData; }
  646.  
  647. inline const STriangularNavData*  GraphNode::GetTriangularNavData() const  { assert(navType == IAISystem::NAV_TRIANGULAR); return &((GraphNode_Triangular*)this)->navData; }
  648. inline const SWaypointNavData*    GraphNode::GetWaypointNavData() const    { assert(navType == IAISystem::NAV_WAYPOINT_3DSURFACE || navType == IAISystem::NAV_WAYPOINT_HUMAN); return &((GraphNode_Waypoint*)this)->navData; }
  649. inline const SFlightNavData*      GraphNode::GetFlightNavData() const      { assert(navType == IAISystem::NAV_FLIGHT); return &((GraphNode_Flight*)this)->navData; }
  650. inline const SVolumeNavData*      GraphNode::GetVolumeNavData() const      { assert(navType == IAISystem::NAV_VOLUME); return &((GraphNode_Volume*)this)->navData; }
  651. inline const SRoadNavData*        GraphNode::GetRoadNavData() const        { assert(navType == IAISystem::NAV_ROAD); return &((GraphNode_Road*)this)->navData; }
  652. inline const SSmartObjectNavData* GraphNode::GetSmartObjectNavData() const { assert(navType == IAISystem::NAV_SMARTOBJECT); return &((GraphNode_SmartObject*)this)->navData; }
  653.  
  654. enum EObstacleFlags
  655. {
  656.         OBSTACLE_COLLIDABLE = BIT(0),
  657.         OBSTACLE_HIDEABLE   = BIT(1),
  658. };
  659.  
  660. struct ObstacleData
  661. {
  662.         Vec3 vPos;
  663.         Vec3 vDir;
  664.         /// this radius is approximate - it is estimated during link generation. if -ve it means
  665.         /// that it shouldn't be used (i.e. object is significantly non-circular)
  666.         float       fApproxRadius;
  667.         uint8       flags;
  668.         uint8       approxHeight; // height in 4.4 fixed point format.
  669.  
  670.         inline void SetCollidable(bool state) { state ? (flags |= OBSTACLE_COLLIDABLE) : (flags &= ~OBSTACLE_COLLIDABLE); }
  671.         inline void SetHideable(bool state)   { state ? (flags |= OBSTACLE_HIDEABLE) : (flags &= ~OBSTACLE_HIDEABLE); }
  672.         inline bool IsCollidable() const      { return (flags & OBSTACLE_COLLIDABLE) != 0; }
  673.         inline bool IsHideable() const        { return (flags & OBSTACLE_HIDEABLE) != 0; }
  674.  
  675.         /// Sets the approximate height and does the necessary conversion.
  676.         inline void  SetApproxHeight(float h) { approxHeight = (uint8)(clamp_tpl(h * (1 << 4), 0.0f, 255.0f)); }
  677.         /// Returns the approximate height and does the necessary conversion.
  678.         inline float GetApproxHeight() const  { return (float)approxHeight / (float)(1 << 4); }
  679.         /// Gets the navigation node that this obstacle is attached to (and caches the result). The result should be
  680.         /// safe in game, but might be invalid in editor if the navigation gets modified whilst AI/physics is running
  681.         /// so I advise against dereferencing the result (unless you validate it first).
  682.         /// The calculation assumes that this obstacle is only attached to triangular nodes
  683.         const std::vector<const GraphNode*>& GetNavNodes() const;
  684.         void ClearNavNodes() { navNodes.clear(); }
  685.         // mechanisms for setting the nav nodes on a temporary obstacle object
  686.         void SetNavNodes(const std::vector<const GraphNode*>& nodes);
  687.         void AddNavNode(const GraphNode* pNode);
  688.  
  689.         /// Note - this is used during triangulation where we can't have two objects
  690.         /// sitting on top of each other - even if they have different directions etc
  691.         bool operator==(const ObstacleData& other) const { return ((fabs(vPos.x - other.vPos.x) < 0.001f) && (fabs(vPos.y - other.vPos.y) < 0.001f)); }
  692.  
  693.         ObstacleData(const Vec3& pos = Vec3(0, 0, 0), const Vec3& dir = Vec3(0, 0, 0))
  694.                 : vPos(pos)
  695.                 , vDir(dir)
  696.                 , fApproxRadius(-1.0f)
  697.                 , flags(OBSTACLE_COLLIDABLE)
  698.                 , approxHeight(0)
  699.                 , needToEvaluateNavNodes(false)
  700.         {}
  701.  
  702.         void Serialize(TSerialize ser);
  703.  
  704. private:
  705.         // pointer to the triangular navigation nodes that contains us (result of GetEnclosing).
  706.         mutable std::vector<const GraphNode*> navNodes;
  707.         mutable bool                          needToEvaluateNavNodes;
  708. };
  709.  
  710. #ifdef _DEBUG
  711. typedef std::vector<ObstacleData> Obstacles;
  712. #else
  713. typedef DynArray<ObstacleData>    Obstacles;
  714. #endif
  715.  
  716. inline int GraphNode::GetLinkIndex(CGraphNodeManager& nodeManager, CGraphLinkManager& linkManager, const GraphNode* destNode) const
  717. {
  718.         int linkIndexIndex = -1;
  719.         int i = 0;
  720.         for (unsigned link = firstLinkIndex; link; link = linkManager.GetNextLink(link), ++i)
  721.                 if (nodeManager.GetNode(linkManager.GetNextNode(link)) == destNode)
  722.                         linkIndexIndex = i;
  723.         return linkIndexIndex;
  724. }
  725.  
  726. inline unsigned GraphNode::GetLinkTo(CGraphNodeManager& nodeManager, CGraphLinkManager& linkManager, const GraphNode* destNode) const
  727. {
  728.         unsigned correctLink = 0;
  729.         for (unsigned link = firstLinkIndex; link; link = linkManager.GetNextLink(link))
  730.                 if (nodeManager.GetNode(linkManager.GetNextNode(link)) == destNode)
  731.                         correctLink = link;
  732.         return correctLink;
  733. }
  734.  
  735. inline int GraphNode::GetLinkCount(CGraphLinkManager& linkManager) const
  736. {
  737.         int count = 0;
  738.         for (unsigned link = firstLinkIndex; link; link = linkManager.GetNextLink(link))
  739.                 ++count;
  740.         return count;
  741. }
  742.  
  743. inline void GraphNode::RemoveLinkTo(CGraphLinkManager& linkManager, unsigned nodeIndex)
  744. {
  745.         unsigned prevLink = 0;
  746.         for (unsigned link = firstLinkIndex; link; )
  747.         {
  748.                 unsigned nextLink = linkManager.GetNextLink(link);
  749.                 if (linkManager.GetNextNode(link) == nodeIndex)
  750.                 {
  751.                         if (!prevLink)
  752.                                 firstLinkIndex = nextLink;
  753.                         else
  754.                                 linkManager.SetNextLink(prevLink, nextLink);
  755.                 }
  756.                 prevLink = link;
  757.                 link = nextLink;
  758.         }
  759. }
  760.  
  761. #endif
  762.  
downloadGraphStructures.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