BVB Source Codes

CRYENGINE Show GraphLinkManager.h Source code

Return Download CRYENGINE: download GraphLinkManager.h Source code - Download CRYENGINE Source code - Type:.h
  1. // Copyright 2001-2016 Crytek GmbH / Crytek Group. All rights reserved.
  2.  
  3. #ifndef __GRAPHLINKMANAGER_H__
  4. #define __GRAPHLINKMANAGER_H__
  5.  
  6. #include "GraphStructures.h"
  7.  
  8. class CGraphLinkManager
  9. {
  10. public:
  11.         enum
  12.         {
  13.                 BUCKET_SIZE_SHIFT = 7
  14.         };
  15.         enum
  16.         {
  17.                 BUCKET_SIZE = 128
  18.         };
  19.  
  20.         CGraphLinkManager();
  21.         ~CGraphLinkManager();
  22.  
  23.         void           Clear();
  24.  
  25.         unsigned       CreateLink();
  26.         void           DestroyLink(unsigned linkIndex);
  27.  
  28.         ILINE unsigned GetNextNode(unsigned linkId) const
  29.         {
  30.                 return GetBidirectionalData(linkId)->directionalData[GetReversed(linkId)].nextNodeIndex;
  31.         }
  32.         void           SetNextNode(unsigned linkId, unsigned nodeIndex) { GetBidirectionalData(linkId)->directionalData[GetReversed(linkId)].nextNodeIndex = nodeIndex; }
  33.  
  34.         ILINE unsigned GetPrevNode(unsigned linkId) const
  35.         {
  36.                 return GetBidirectionalData(linkId)->directionalData[GetReversed(linkId ^ 1)].nextNodeIndex;
  37.         }
  38.  
  39.         ILINE unsigned GetNextLink(unsigned linkId) const
  40.         {
  41.                 return GetBidirectionalData(linkId)->directionalData[GetReversed(linkId)].nextLinkIndex;
  42.         }
  43.         void SetNextLink(unsigned linkId, unsigned nextLink)
  44.         {
  45.                 GetBidirectionalData(linkId)->directionalData[GetReversed(linkId)].nextLinkIndex = nextLink;
  46.         }
  47.  
  48.         void SetMaxWaterDepth(unsigned linkId, float depth)
  49.         {
  50.                 depth *= 100.0f;
  51.                 Limit<float>(depth, (float)-std::numeric_limits<short>::max(), (float)std::numeric_limits<short>::max());
  52.  
  53.                 int16 depthInCm = NavGraphUtils::InCentimeters(depth);
  54.                 GetBidirectionalData(linkId)->directionalData[1].waterDepthInCmLow = depthInCm & 0xff;
  55.                 GetBidirectionalData(linkId)->directionalData[1].waterDepthInCmHigh = (depthInCm >> 8);
  56.         }
  57.  
  58.         void SetMinWaterDepth(unsigned linkId, float depth)
  59.         {
  60.                 depth *= 100.0f;
  61.                 Limit<float>(depth, (float)-std::numeric_limits<short>::max(), (float)std::numeric_limits<short>::max());
  62.  
  63.                 int16 depthInCm = NavGraphUtils::InCentimeters(depth);
  64.                 GetBidirectionalData(linkId)->directionalData[0].waterDepthInCmLow = depthInCm & 0xff;
  65.                 GetBidirectionalData(linkId)->directionalData[0].waterDepthInCmHigh = (depthInCm >> 8);
  66.         }
  67.  
  68.         ILINE float GetMaxWaterDepth(unsigned linkId) const
  69.         {
  70.                 return NavGraphUtils::InMeters(GetMaxWaterDepthInCm(linkId));
  71.         }
  72.         ILINE float GetMinWaterDepth(unsigned linkId) const
  73.         {
  74.                 return NavGraphUtils::InMeters(GetMinWaterDepthInCm(linkId));
  75.         }
  76.  
  77.         ILINE int16 GetMaxWaterDepthInCm(unsigned linkId) const
  78.         {
  79.                 int low = GetBidirectionalData(linkId)->directionalData[1].waterDepthInCmLow;
  80.                 int high = GetBidirectionalData(linkId)->directionalData[1].waterDepthInCmHigh;
  81.                 return (int16)((high << 8) | low);
  82.         }
  83.  
  84.         ILINE int16 GetMinWaterDepthInCm(unsigned linkId) const
  85.         {
  86.                 int low = GetBidirectionalData(linkId)->directionalData[0].waterDepthInCmLow;
  87.                 int high = GetBidirectionalData(linkId)->directionalData[0].waterDepthInCmHigh;
  88.                 return (int16)((high << 8) | low);
  89.         }
  90.  
  91.         /// Use this when setting up the radius during creation
  92.         void        SetRadius(unsigned linkId, float radius);
  93.         void        SetRadiusInCm(unsigned linkId, int16 radius);
  94.  
  95.         ILINE float GetRadius(unsigned linkId) const
  96.         {
  97.                 return NavGraphUtils::InMeters(GetBidirectionalData(linkId)->directionalData[GetReversed(linkId)].maxRadiusInCm);
  98.         }
  99.         ILINE float GetOrigRadius(unsigned linkId) const
  100.         {
  101.                 return NavGraphUtils::InMeters(GetBidirectionalData(linkId)->directionalData[GetReversed(linkId)].origMaxRadiusInCm);
  102.         }
  103.  
  104.         ILINE int16 GetRadiusInCm(unsigned linkId) const
  105.         {
  106.                 return GetBidirectionalData(linkId)->directionalData[GetReversed(linkId)].maxRadiusInCm;
  107.         }
  108.         ILINE int16 GetOrigRadiusInCm(unsigned linkId) const
  109.         {
  110.                 return GetBidirectionalData(linkId)->directionalData[GetReversed(linkId)].origMaxRadiusInCm;
  111.         }
  112.  
  113.         /// Use this when modifying the radius during game
  114.         void ModifyRadius(unsigned linkId, float radius)
  115.         {
  116.                 int radiusInCm = (int)(radius * 100.0f);
  117.                 Limit<int>(radiusInCm, -std::numeric_limits<short>::max(), std::numeric_limits<short>::max());
  118.                 GetBidirectionalData(linkId)->directionalData[GetReversed(linkId)].maxRadiusInCm = radiusInCm;
  119.         }
  120.  
  121.         /// Use this when modifying the radius during game
  122.         void ModifyRadiusInCm(unsigned linkId, int16 radius)
  123.         {
  124.                 GetBidirectionalData(linkId)->directionalData[GetReversed(linkId)].maxRadiusInCm = radius;
  125.         }
  126.  
  127.         /// Indicates if a link has been changed from its original value
  128.         ILINE bool IsLinkModified(unsigned linkId) const
  129.         {
  130.                 return abs(GetRadiusInCm(linkId) - GetOrigRadiusInCm(linkId)) > 1;
  131.         }
  132.  
  133.         /// Restores the link radius to its original value
  134.         void RestoreLink(unsigned linkId)
  135.         {
  136.                 GetBidirectionalData(linkId)->directionalData[GetReversed(linkId)].maxRadiusInCm = GetBidirectionalData(linkId)->directionalData[GetReversed(linkId)].origMaxRadiusInCm;
  137.         }
  138.  
  139.         ILINE bool IsNewLink(unsigned linkId) const
  140.         {
  141.                 if (abs(GetRadiusInCm(linkId) + 25) < 25)
  142.                         return true;
  143.                 return false;
  144.         }
  145.  
  146.         ILINE unsigned int GetStartIndex(unsigned linkId) const
  147.         {
  148.                 return GetBidirectionalData(linkId)->directionalData[GetReversed(linkId)].startIndex;
  149.         }
  150.  
  151.         void               SetStartIndex(unsigned linkId, unsigned int index);
  152.         ILINE unsigned int GetEndIndex(unsigned linkId) const
  153.         {
  154.                 return GetBidirectionalData(linkId)->directionalData[GetReversed(linkId)].endIndex;
  155.         }
  156.         void        SetEndIndex(unsigned linkId, unsigned int index);
  157.  
  158.         void        SetEdgeCenter(unsigned linkId, const Vec3& center) { GetBidirectionalData(linkId)->vEdgeCenter = center; }
  159.         ILINE Vec3& GetEdgeCenter(unsigned linkId)
  160.         {
  161.                 return GetBidirectionalData(linkId)->vEdgeCenter;
  162.         }
  163.         ILINE const Vec3& GetEdgeCenter(unsigned linkId) const
  164.         {
  165.                 return GetBidirectionalData(linkId)->vEdgeCenter;
  166.         }
  167.  
  168.         void        SetExposure(unsigned linkId, float fExposure) { GetBidirectionalData(linkId)->fExposure = fExposure; }
  169.         ILINE float GetExposure(unsigned linkId) const
  170.         {
  171.                 return GetBidirectionalData(linkId)->fExposure;
  172.         }
  173.  
  174.         // NOTE Apr 26, 2007: <pvl> "simplicity" of a link makes sense only with
  175.         // human waypoint links.  For criterion of simplicity see
  176.         // CWaypointHumanNavRegion::CheckWaypointLinkWalkability().
  177.         ILINE unsigned IsSimple(unsigned linkId) const
  178.         {
  179.                 return GetBidirectionalData(linkId)->directionalData[0].simplePassabilityCheck;
  180.         }
  181.         void SetSimple(unsigned linkId, bool linear)
  182.         {
  183.                 GraphLinkBidirectionalData* data = GetBidirectionalData(linkId);
  184.                 data->directionalData[0].simplePassabilityCheck = linear;
  185.                 data->directionalData[1].simplePassabilityCheck = true;
  186.         }
  187.  
  188.         ILINE bool SimplicityComputed(unsigned linkId) const
  189.         {
  190.                 return GetBidirectionalData(linkId)->directionalData[1].simplePassabilityCheck;
  191.         }
  192.  
  193.         // NOTE Oct 28, 2009: <pvl> memory allocated for link data buckets
  194.         size_t MemoryAllocated() const;
  195.  
  196.         // NOTE Oct 28, 2009: <pvl> bucket memory that's allocated but on the free list
  197.         size_t MemoryUnused() const;
  198.  
  199.         // NOTE Oct 28, 2009: <pvl> just for convenience - difference between allocated and unused
  200.         size_t MemoryUsed() const;
  201.  
  202.         // NOTE Oct 29, 2009: <pvl> deallocate buckets that only contain unused link data
  203.         void CollectGarbage();
  204.  
  205.         void GetMemoryStatistics(ICrySizer* pSizer) const
  206.         {
  207.                 pSizer->AddContainer(m_buckets);
  208.                 for (size_t i = 0; i < m_buckets.size(); ++i)
  209.                         pSizer->AddObject(m_buckets[i], sizeof(GraphLinkBidirectionalData), BUCKET_SIZE);
  210.         };
  211.  
  212. private:
  213.         // The low bit of the pointer is a flag - it must be masked out.
  214.         GraphLinkBidirectionalData*       GetBidirectionalData(unsigned linkId);
  215.         const GraphLinkBidirectionalData* GetBidirectionalData(unsigned linkId) const;
  216.  
  217.         bool                              GetReversed(unsigned linkId) const { return (linkId & 1) != 0; }
  218.  
  219.         bool                              IsBucketInUse(unsigned bucketIndex) const;
  220.         void                              MarkBucketForDeletion(unsigned bucketIndex);
  221.         void                              MarkUnused(GraphLinkBidirectionalData* data) const;
  222.         void                              MarkUsed(GraphLinkBidirectionalData* data) const;
  223.         bool                              IsUsed(const GraphLinkBidirectionalData* data) const;
  224.         void                              MarkToBeDeleted(GraphLinkBidirectionalData* data) const;
  225.         bool                              IsToBeDeleted(const GraphLinkBidirectionalData* data) const;
  226.  
  227.         std::vector<GraphLinkBidirectionalData*> m_buckets;
  228.         unsigned m_freeList;
  229. };
  230.  
  231. inline CGraphLinkManager::CGraphLinkManager()
  232.         : m_freeList(0)
  233. {
  234. }
  235.  
  236. inline CGraphLinkManager::~CGraphLinkManager()
  237. {
  238.         Clear();
  239. }
  240.  
  241. inline void CGraphLinkManager::Clear()
  242. {
  243.         for (int i = 0, count = int(m_buckets.size()); i < count; ++i)
  244.                 delete[] m_buckets[i];
  245.         m_buckets.clear();
  246.  
  247.         m_freeList = 0;
  248. }
  249.  
  250. inline void CGraphLinkManager::SetRadius(unsigned linkId, float radius)
  251. {
  252.         int radiusInCm = NavGraphUtils::InCentimeters(radius);
  253.         // NOTE Jul 27, 2007: <pvl> radius being 0.0 seems to have a special interpretation,
  254.         // don't let it go to zero (i.e. completely impassable) just because of
  255.         // quantization - set it to 1cm instead.  This prevents graph consistency
  256.         // checking from getting confused and flagging false errors.
  257.         if (radiusInCm == 0 && radius != 0)
  258.                 radiusInCm = (radius > 0);
  259.  
  260.         GetBidirectionalData(linkId)->directionalData[GetReversed(linkId)].maxRadiusInCm = radiusInCm;
  261.         GetBidirectionalData(linkId)->directionalData[GetReversed(linkId)].origMaxRadiusInCm = radiusInCm;
  262. }
  263.  
  264. inline void CGraphLinkManager::SetRadiusInCm(unsigned linkId, int16 radiusInCm)
  265. {
  266.         // NOTE Jul 27, 2007: <pvl> radius being 0.0 seems to have a special interpretation,
  267.         // don't let it go to zero (i.e. completely impassable) just because of
  268.         // quantization - set it to 1cm instead.  This prevents graph consistency
  269.         // checking from getting confused and flagging false errors.
  270.         GetBidirectionalData(linkId)->directionalData[GetReversed(linkId)].maxRadiusInCm = radiusInCm;
  271.         GetBidirectionalData(linkId)->directionalData[GetReversed(linkId)].origMaxRadiusInCm = radiusInCm;
  272. }
  273.  
  274. inline void CGraphLinkManager::SetStartIndex(unsigned linkId, unsigned int index)
  275. {
  276.         assert(index < 3 && index >= 0);
  277.         GetBidirectionalData(linkId)->directionalData[GetReversed(linkId)].startIndex = index;
  278. }
  279.  
  280. inline void CGraphLinkManager::SetEndIndex(unsigned linkId, unsigned int index)
  281. {
  282.         assert(index < 3 && index >= 0);
  283.         GetBidirectionalData(linkId)->directionalData[GetReversed(linkId)].endIndex = index;
  284. }
  285.  
  286. inline GraphLinkBidirectionalData* CGraphLinkManager::GetBidirectionalData(unsigned linkId)
  287. {
  288.         unsigned bidirectionalIndex = (linkId >> 1) - 1;
  289.         return &m_buckets[bidirectionalIndex >> BUCKET_SIZE_SHIFT][bidirectionalIndex & (BUCKET_SIZE - 1)];
  290. }
  291.  
  292. inline const GraphLinkBidirectionalData* CGraphLinkManager::GetBidirectionalData(unsigned linkId) const
  293. {
  294.         unsigned bidirectionalIndex = (linkId >> 1) - 1;
  295.         return &m_buckets[bidirectionalIndex >> BUCKET_SIZE_SHIFT][bidirectionalIndex & (BUCKET_SIZE - 1)];
  296. }
  297.  
  298. inline void CGraphLinkManager::MarkUnused(GraphLinkBidirectionalData* data) const
  299. {
  300.         data->directionalData[1].nextLinkIndex = 0x7ffff;
  301. }
  302.  
  303. inline void CGraphLinkManager::MarkUsed(GraphLinkBidirectionalData* data) const
  304. {
  305.         data->directionalData[1].nextLinkIndex = 0;
  306. }
  307.  
  308. inline bool CGraphLinkManager::IsUsed(const GraphLinkBidirectionalData* data) const
  309. {
  310.         return data->directionalData[1].nextLinkIndex != 0x7ffff;
  311. }
  312.  
  313. inline void CGraphLinkManager::MarkToBeDeleted(GraphLinkBidirectionalData* data) const
  314. {
  315.         data->directionalData[1].nextLinkIndex = 0x80000;
  316. }
  317.  
  318. inline bool CGraphLinkManager::IsToBeDeleted(const GraphLinkBidirectionalData* data) const
  319. {
  320.         return data->directionalData[1].nextLinkIndex == 0x80000;
  321. }
  322.  
  323. inline unsigned CGraphLinkManager::CreateLink()
  324. {
  325.         MEMSTAT_CONTEXT(EMemStatContextTypes::MSC_Navigation, 0, "Links");
  326.         if (!m_freeList)
  327.         {
  328.                 m_buckets.push_back(new GraphLinkBidirectionalData[BUCKET_SIZE]);
  329.                 GraphLinkBidirectionalData* pLinks = m_buckets.back();
  330.                 pLinks[0].directionalData[0].nextLinkIndex = m_freeList;
  331.                 MarkUnused(&pLinks[0]);
  332.                 unsigned nextLink = m_freeList;
  333.                 for (int i = 1; i < BUCKET_SIZE; ++i)
  334.                 {
  335.                         pLinks[i].directionalData[0].nextLinkIndex = nextLink;
  336.                         MarkUnused(&pLinks[i]);
  337.                         nextLink = ((((m_buckets.size() - 1) << BUCKET_SIZE_SHIFT) + i) + 1) << 1;
  338.                 }
  339.                 m_freeList = nextLink;
  340.         }
  341.  
  342.         unsigned link = m_freeList;
  343.         GraphLinkBidirectionalData* bidirectionalData = GetBidirectionalData(link);
  344.         m_freeList = bidirectionalData->directionalData[0].nextLinkIndex;
  345.         bidirectionalData->directionalData[0].nextLinkIndex = 0;
  346.         MarkUsed(bidirectionalData);
  347.         return link;
  348. }
  349.  
  350. inline void CGraphLinkManager::DestroyLink(unsigned linkIndex)
  351. {
  352.         linkIndex = linkIndex & ~1;
  353.         if (GraphLinkBidirectionalData* pData = GetBidirectionalData(linkIndex))
  354.         {
  355.                 *pData = GraphLinkBidirectionalData();
  356.                 pData->directionalData[0].nextLinkIndex = m_freeList;
  357.                 MarkUnused(pData);
  358.                 m_freeList = linkIndex;
  359.         }
  360. }
  361.  
  362. inline size_t CGraphLinkManager::MemoryAllocated() const
  363. {
  364.         size_t mem = 0;
  365.  
  366.         for (int i = 0, count = int(m_buckets.size()); i < count; ++i)
  367.         {
  368.                 if (!m_buckets[i])
  369.                         continue;
  370.                 mem += sizeof(GraphLinkBidirectionalData) * BUCKET_SIZE;
  371.         }
  372.  
  373.         return mem;
  374. }
  375.  
  376. inline size_t CGraphLinkManager::MemoryUnused() const
  377. {
  378.         size_t mem = 0;
  379.  
  380.         unsigned freeLink = m_freeList;
  381.         while (freeLink)
  382.         {
  383.                 mem += sizeof(GraphLinkBidirectionalData);
  384.                 const GraphLinkBidirectionalData* freeLinkData = GetBidirectionalData(freeLink);
  385.                 freeLink = freeLinkData->directionalData[0].nextLinkIndex;
  386.         }
  387.  
  388.         return mem;
  389. }
  390.  
  391. inline size_t CGraphLinkManager::MemoryUsed() const
  392. {
  393.         return MemoryAllocated() - MemoryUnused();
  394. }
  395.  
  396. // NOTE Nov 2, 2009: <pvl> bucket is in use if any of the slots it contains is in use
  397. inline bool CGraphLinkManager::IsBucketInUse(unsigned bucketIndex) const
  398. {
  399.         GraphLinkBidirectionalData* slotData = m_buckets[bucketIndex];
  400.         for (unsigned slot = 0; slot < BUCKET_SIZE; ++slot, ++slotData)
  401.         {
  402.                 if (IsUsed(slotData))
  403.                         return true;
  404.         }
  405.         return false;
  406. }
  407.  
  408. inline void CGraphLinkManager::MarkBucketForDeletion(unsigned bucketIndex)
  409. {
  410.         GraphLinkBidirectionalData* slotData = m_buckets[bucketIndex];
  411.         for (unsigned slot = 0; slot < BUCKET_SIZE; ++slot, ++slotData)
  412.                 MarkToBeDeleted(slotData);
  413. }
  414.  
  415. inline void CGraphLinkManager::CollectGarbage()
  416. {
  417.         std::vector<int> bucketsToDelete;
  418.         bucketsToDelete.reserve(m_buckets.size());
  419.  
  420.         for (int i = 0, count = int(m_buckets.size()); i < count; ++i)
  421.         {
  422.                 if (m_buckets[i] == 0) continue;
  423.  
  424.                 if (!IsBucketInUse(i))
  425.                 {
  426.                         bucketsToDelete.push_back(i);
  427.                         MarkBucketForDeletion(i);
  428.                 }
  429.         }
  430.  
  431.         // NOTE Nov 2, 2009: <pvl> now walk the free list and remove and link data slots
  432.         // from it that live in buckets about to be deleted
  433.         if (m_freeList)
  434.         {
  435.                 // NOTE Nov 2, 2009: <pvl> unfortunately we have to treat 'm_freeList'
  436.                 // as a special case
  437.                 GraphLinkBidirectionalData* data = GetBidirectionalData(m_freeList);
  438.                 while (IsToBeDeleted(data))
  439.                 {
  440.                         m_freeList = data->directionalData[0].nextLinkIndex;
  441.                         if (m_freeList == 0) break;
  442.                         data = GetBidirectionalData(m_freeList);
  443.                 }
  444.  
  445.                 if (m_freeList)
  446.                 {
  447.                         unsigned freeLink = m_freeList;
  448.                         while (freeLink)
  449.                         {
  450.                                 unsigned markedLink = freeLink;
  451.                                 const GraphLinkBidirectionalData* markedLinkData = GetBidirectionalData(markedLink);
  452.                                 do
  453.                                 {
  454.                                         markedLink = markedLinkData->directionalData[0].nextLinkIndex;
  455.                                         if (markedLink == 0) break;
  456.                                         markedLinkData = GetBidirectionalData(markedLink);
  457.                                 }
  458.                                 while (IsToBeDeleted(markedLinkData));
  459.  
  460.                                 GetBidirectionalData(freeLink)->directionalData[0].nextLinkIndex = markedLink;
  461.                                 freeLink = markedLink;
  462.                         }
  463.                 }
  464.         }
  465.  
  466.         for (int i = 0, count = int(bucketsToDelete.size()); i < count; ++i)
  467.         {
  468.                 delete[] m_buckets[bucketsToDelete[i]];
  469.                 m_buckets[bucketsToDelete[i]] = 0;
  470.         }
  471. }
  472.  
  473. #endif //__GRAPHLINKMANAGER_H__
  474.  
downloadGraphLinkManager.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