BVB Source Codes

CRYENGINE Show AllNodesContainer.h Source code

Return Download CRYENGINE: download AllNodesContainer.h Source code - Download CRYENGINE Source code - Type:.h
  1. // Copyright 2001-2016 Crytek GmbH / Crytek Group. All rights reserved.
  2.  
  3. #ifndef ALLNODESCONTAINER_H
  4. #define ALLNODESCONTAINER_H
  5.  
  6. #if _MSC_VER > 1000
  7.         #pragma once
  8. #endif
  9.  
  10. #include <CryAISystem/IAgent.h>
  11. #include "AILog.h"
  12. #include "HashSpace.h"
  13. #include <CryCore/Containers/VectorSet.h>
  14. #include "GraphNodeManager.h"
  15.  
  16. #include <vector>
  17. #include <algorithm>
  18.  
  19. /// Container for pointers to nodes so that it's quick/convenient to:
  20. /// 1. Insert nodes of any type
  21. /// 2. remove nodes of any type
  22. /// 3. Iterate over all nodes
  23. /// 4. Iterate over all nodes of a particular type
  24. /// 5. Find a node (e.g. for validation)
  25. class CAllNodesContainer
  26. {
  27. public:
  28.         /// Node that this iterator becomes invalid as soon as the container
  29.         /// gets modified
  30.         class Iterator
  31.         {
  32.         public:
  33.                 /// Create an iterator, starting at the beginning
  34.                 Iterator(const CAllNodesContainer& container, IAISystem::tNavCapMask navTypeMask = IAISystem::NAVMASK_ALL);
  35.                 ~Iterator();
  36.                 /// increment and return the current value
  37.                 unsigned Increment();
  38.                 /// just return the current value
  39.                 unsigned GetNode() const;
  40.                 /// Set to the beginning. Note that this can get called by the container if it is modified
  41.                 /// in such a way that we might be invalid.
  42.                 void Reset();
  43.         private:
  44.                 friend class CAllNodesContainer;
  45.                 /// Called by the container destructor
  46.                 void ContainerDeleted() { m_container = 0; }
  47.                 IAISystem::tNavCapMask                            m_navTypeMask;
  48.                 /// Current iterator over the containers types
  49.                 std::map<unsigned, VectorSet<unsigned>>::iterator m_currentAllNodesIt;
  50.                 /// our current iterator over the container's nodes of our current type
  51.                 VectorSet<unsigned>::iterator                     m_it;
  52.                 /// end iterator for the container's nodes of our current type
  53.                 VectorSet<unsigned>::iterator                     m_currentEndIt;
  54.                 /// The container we're associated with - always non-zero unless the container got deleted
  55.                 CAllNodesContainer*                               m_container;
  56.         };
  57.  
  58.         struct SGraphNodeRecord
  59.         {
  60.                 SGraphNodeRecord(unsigned nodeIndex) : nodeIndex(nodeIndex) {}
  61.                 const Vec3& GetPos(CGraphNodeManager& nodeManager) const  { return nodeManager.GetNode(nodeIndex)->GetPos(); }
  62.                 bool        operator==(const SGraphNodeRecord& rhs) const { return rhs.nodeIndex == nodeIndex; }
  63.                 unsigned    nodeIndex;
  64.         };
  65.  
  66.         class GraphNodeHashSpaceTraits
  67.         {
  68.         public:
  69.                 GraphNodeHashSpaceTraits(CGraphNodeManager& nodeManager) : nodeManager(nodeManager) {}
  70.  
  71.                 const Vec3& operator()(const SGraphNodeRecord& item) const { return item.GetPos(nodeManager); }
  72.  
  73.                 CGraphNodeManager& nodeManager;
  74.         };
  75.  
  76.         CAllNodesContainer(CGraphNodeManager& nodeManager);
  77.  
  78.         ~CAllNodesContainer();
  79.  
  80.         /// Add a node to this container - uses the position to store it in a spatial structure
  81.         void AddNode(unsigned nodeIndex);
  82.  
  83.         void Reserve(IAISystem::ENavigationType type, size_t size);
  84.  
  85.         /// Remove a node from this container (invalidates all iterators)
  86.         void RemoveNode(unsigned nodeIndex);
  87.  
  88.         /// Indicates if the node is in this container
  89.         bool DoesNodeExist(unsigned nodeIndex) const;
  90.  
  91.         /// Returns unsorted all nodes of a particular type within range of the position passed in, together
  92.         /// with the squared distance to the node (unsorted)
  93.         void GetAllNodesWithinRange(std::vector<std::pair<float, unsigned>>& nodesOut, const Vec3& pos, float range, IAISystem::tNavCapMask navTypeMask) const;
  94.  
  95.         /// Returns one node within range of the position passed in together with the squared distance
  96.         /// NOTE: it just returns the first node it finds in range, not the closest one
  97.         bool GetNodeWithinRange(std::pair<float, unsigned>& nodeOut, const Vec3& pos, float range, IAISystem::tNavCapMask navTypeMask, CGraph* graph) const;
  98.  
  99.         /// Returns the hash space for other queries
  100.         const CHashSpace<SGraphNodeRecord, GraphNodeHashSpaceTraits>& GetHashSpace() const { return m_hashSpace; }
  101.  
  102.         /// Remove the iterator passed in and get an iterator representing the next
  103.         /// node
  104.         //Iterator Erase(const Iterator& it);
  105.  
  106.         /// Returns the memory usage in bytes
  107.         size_t MemStats() const;
  108.  
  109.         /// For debugging - finds out if our HashSpace is consistent within itself and with AllNodesContainer.
  110.         bool ValidateHashSpace() const;
  111.  
  112.         /// Compact the memory usage
  113.         void Compact();
  114.  
  115. private:
  116.         friend class Iterator;
  117.  
  118.         /// Called by the Iterator ctor
  119.         void AttachIterator(Iterator* pIt) { m_attachedIterators.insert(pIt); }
  120.         /// Called by the Iterator dtor
  121.         void DetachIterator(Iterator* pIt) { m_attachedIterators.erase(pIt); }
  122.  
  123.         void ResetIterators(IAISystem::tNavCapMask m_navTypeMask);
  124.  
  125.         /// A set of nodes that are all of the same type
  126.         /// [MichaelS 29/1/2007] Changed to use VectorSet to save memory. This has slower insertion
  127.         /// time, but faster lookup time. Since insertion only happens at load-time, this should be
  128.         /// fast enough, and save quite a lot of memory.
  129.         typedef VectorSet<unsigned> tNodes;
  130.  
  131.         /// All nodes split into sets all containing the same type
  132.         typedef std::map<unsigned, tNodes> tAllNodes;
  133.         tAllNodes m_allNodes;
  134.  
  135.         /// Our spatial structure
  136.         CHashSpace<SGraphNodeRecord, GraphNodeHashSpaceTraits> m_hashSpace;
  137.  
  138.         struct SNodeCollector
  139.         {
  140.                 SNodeCollector(CGraphNodeManager& nodeManager, std::vector<std::pair<float, unsigned>>& nodes, IAISystem::tNavCapMask navTypeMask)
  141.                         : nodeManager(nodeManager), nodes(nodes), navTypeMask(navTypeMask) {}
  142.                 void operator()(const SGraphNodeRecord& record, float distSq)
  143.                 {
  144.                         GraphNode* pNode = nodeManager.GetNode(record.nodeIndex);
  145.                         if (pNode->navType & navTypeMask)
  146.                                 nodes.push_back(std::make_pair(distSq, record.nodeIndex));
  147.                 }
  148.  
  149.                 CGraphNodeManager&                       nodeManager;
  150.                 std::vector<std::pair<float, unsigned>>& nodes;
  151.                 IAISystem::tNavCapMask                   navTypeMask;
  152.         };
  153.  
  154.         // as the name implies this collector just accepts one element, then returns true
  155.         struct SOneNodeCollector
  156.         {
  157.                 SOneNodeCollector(CGraphNodeManager& nodeManager, CGraph* graph, const Vec3& pos, std::pair<float, unsigned>& inNode, IAISystem::tNavCapMask navTypeMask)
  158.                         : nodeManager(nodeManager), m_Graph(graph), m_Pos(pos), node(inNode), navTypeMask(navTypeMask) {}
  159.  
  160.                 bool operator()(const SGraphNodeRecord& record, float distSq);
  161.  
  162.                 CGraphNodeManager&          nodeManager;
  163.                 std::pair<float, unsigned>& node;
  164.                 IAISystem::tNavCapMask      navTypeMask;
  165.  
  166.                 CGraph*                     m_Graph;
  167.                 Vec3                        m_Pos;
  168.         };
  169.  
  170.         // attached iterators that we invalidate when things change
  171.         std::set<Iterator*> m_attachedIterators;
  172.         CGraphNodeManager&  m_nodeManager;
  173. };
  174.  
  175. //====================================================================
  176. // MemStats
  177. //====================================================================
  178. inline size_t CAllNodesContainer::MemStats() const
  179. {
  180.         size_t result = sizeof(*this);
  181.         size_t nodeSize = sizeof(tNodes::reference) /* + sizeof(void*)*3 + sizeof(int)*/;
  182.         for (tAllNodes::const_iterator it = m_allNodes.begin(); it != m_allNodes.end(); ++it)
  183.         {
  184.                 result += //sizeof(*it) +
  185.                           sizeof(bool) + sizeof(void*) * 3 + sizeof(char) * 2 +
  186.                           sizeof(it->first) + it->second.capacity() * nodeSize;
  187.         }
  188.         result += m_hashSpace.MemStats();
  189.         result += m_attachedIterators.size() * (sizeof(Iterator*));
  190.         return result;
  191. }
  192.  
  193. //====================================================================
  194. // Reset: Moves iterator to point at first node with matching NavType
  195. //====================================================================
  196. inline void CAllNodesContainer::Iterator::Reset()
  197. {
  198.         const unsigned navTypeMask = m_navTypeMask;
  199.  
  200.         for (m_currentAllNodesIt = m_container->m_allNodes.begin();
  201.              m_currentAllNodesIt != m_container->m_allNodes.end();
  202.              ++m_currentAllNodesIt)
  203.         {
  204.                 const unsigned navType = m_currentAllNodesIt->first;
  205.                 tNodes& nodes = m_currentAllNodesIt->second;
  206.  
  207.                 // If navType matches and node(s) exist for NavType
  208.                 if ((navType & navTypeMask) && !nodes.empty())
  209.                 {
  210.                         // Select first node of this NavType
  211.                         m_it = nodes.begin();
  212.                         m_currentEndIt = nodes.end();
  213.                         return;
  214.                 }
  215.         }
  216.         // container will always have an entry for nav mask 0
  217.         m_it = m_container->m_allNodes.begin()->second.begin();
  218.         m_currentEndIt = m_container->m_allNodes.begin()->second.end();
  219.         m_currentAllNodesIt = m_container->m_allNodes.begin();
  220. }
  221.  
  222. //====================================================================
  223. // Iterator
  224. // The const cast is evil... but without it then I have to implement
  225. // a const iterator and that is a pain
  226. //====================================================================
  227. inline CAllNodesContainer::Iterator::Iterator(const CAllNodesContainer& container, IAISystem::tNavCapMask navTypeMask)
  228.         : m_navTypeMask(navTypeMask), m_container(const_cast<CAllNodesContainer*>(&container))
  229. {
  230.         m_container->AttachIterator(this);
  231.         Reset();
  232. }
  233.  
  234. //===================================================================
  235. // Iterator
  236. //===================================================================
  237. inline CAllNodesContainer::Iterator::~Iterator()
  238. {
  239.         if (m_container)
  240.                 m_container->DetachIterator(this);
  241. }
  242.  
  243. //====================================================================
  244. // Increment
  245. //====================================================================
  246. inline unsigned CAllNodesContainer::Iterator::Increment()
  247. {
  248.         AIAssert(m_container);
  249.         unsigned nodeIndex = 0;
  250.  
  251.         if (m_it != m_currentEndIt)
  252.         {
  253.                 nodeIndex = *m_it;
  254.                 // cppcheck-suppress assertWithSideEffect
  255.                 assert(m_container->m_nodeManager.GetNode(nodeIndex)->navType & m_navTypeMask);
  256.                 ++m_it;
  257.         }
  258.  
  259.         if (m_it == m_currentEndIt)
  260.         {
  261.                 if (m_currentAllNodesIt == m_container->m_allNodes.end())
  262.                         return 0;
  263.                 for (++m_currentAllNodesIt; m_currentAllNodesIt != m_container->m_allNodes.end(); ++m_currentAllNodesIt)
  264.                 {
  265.                         if (m_currentAllNodesIt->first & m_navTypeMask)
  266.                         {
  267.                                 tNodes& nodes = m_currentAllNodesIt->second;
  268.                                 if (!nodes.empty())
  269.                                 {
  270.                                         m_it = nodes.begin();
  271.                                         m_currentEndIt = nodes.end();
  272.                                         if (0 == nodeIndex)
  273.                                         {
  274.                                                 nodeIndex = *m_it;
  275.                                                 // cppcheck-suppress assertWithSideEffect
  276.                                                 AIAssert(m_container->m_nodeManager.GetNode(nodeIndex)->navType & m_navTypeMask);
  277.                                                 ++m_it;
  278.                                         }
  279.                                         break;
  280.                                 }
  281.                         }
  282.                 }
  283.         }
  284.         return nodeIndex;
  285. }
  286.  
  287. //====================================================================
  288. // GetNode
  289. //====================================================================
  290. inline unsigned CAllNodesContainer::Iterator::GetNode() const
  291. {
  292.         AIAssert(m_container);
  293.         if (m_it != m_currentEndIt)
  294.         {
  295.                 unsigned nodeIndex = *m_it;
  296.                 AIAssert(m_container->m_nodeManager.GetNode(nodeIndex)->navType & m_navTypeMask);
  297.                 return nodeIndex;
  298.         }
  299.         else
  300.         {
  301.                 return 0;
  302.         }
  303. }
  304.  
  305. //====================================================================
  306. // CAllNodesContainer
  307. //====================================================================
  308. inline CAllNodesContainer::CAllNodesContainer(CGraphNodeManager& nodeManager)
  309.         :
  310.         m_hashSpace(Vec3(7, 7, 7), 8192, GraphNodeHashSpaceTraits(nodeManager)),
  311.         m_nodeManager(nodeManager)
  312. {
  313.         m_allNodes[0];
  314. }
  315.  
  316. //===================================================================
  317. // ~CAllNodesContainer
  318. //===================================================================
  319. inline CAllNodesContainer::~CAllNodesContainer()
  320. {
  321.         for (std::set<Iterator*>::iterator it = m_attachedIterators.begin(); it != m_attachedIterators.end(); ++it)
  322.         {
  323.                 Iterator* pIt = *it;
  324.                 pIt->ContainerDeleted();
  325.         }
  326. }
  327.  
  328. //===================================================================
  329. // ResetIterators
  330. //===================================================================
  331. inline void CAllNodesContainer::ResetIterators(IAISystem::tNavCapMask navTypeMask)
  332. {
  333.         for (std::set<Iterator*>::iterator it = m_attachedIterators.begin(); it != m_attachedIterators.end(); ++it)
  334.         {
  335.                 Iterator* pIt = *it;
  336.                 if (pIt->m_navTypeMask | navTypeMask)
  337.                         pIt->Reset();
  338.         }
  339. }
  340.  
  341. //====================================================================
  342. // AddNode
  343. //====================================================================
  344. inline void CAllNodesContainer::AddNode(unsigned nodeIndex)
  345. {
  346.         GraphNode* pNode = m_nodeManager.GetNode(nodeIndex);
  347.         AIAssert(pNode);
  348.         if (!pNode)
  349.         {
  350.                 AIWarning("CAllNodesContainer: Attempting to add 0 node!");
  351.                 return;
  352.         }
  353.         unsigned type = pNode->navType;
  354.  
  355.         m_allNodes[type].insert(nodeIndex);
  356.  
  357.         m_hashSpace.AddObject(SGraphNodeRecord(nodeIndex));
  358.  
  359.         ResetIterators(type);
  360. }
  361.  
  362. //====================================================================
  363. // Reserve
  364. //====================================================================
  365. inline void CAllNodesContainer::Reserve(IAISystem::ENavigationType type, size_t size)
  366. {
  367.         m_allNodes[type].reserve(size);
  368. }
  369.  
  370. //====================================================================
  371. // RemoveNode
  372. //====================================================================
  373. inline void CAllNodesContainer::RemoveNode(unsigned nodeIndex)
  374. {
  375.         GraphNode* pNode = m_nodeManager.GetNode(nodeIndex);
  376.  
  377.         AIAssert(pNode);
  378.         if (!pNode)
  379.         {
  380.                 AIWarning("CAllNodesContainer: Attempting to remove 0 node!");
  381.                 return;
  382.         }
  383.         unsigned type = pNode->navType;
  384.         tNodes& nodes = m_allNodes[type];
  385.  
  386.         tNodes::iterator it = nodes.find(nodeIndex); // why do I need to cast?!
  387.         if (it == nodes.end())
  388.         {
  389.                 AIWarning("CAllNodesContainer::RemoveNode Could not find node %p", pNode);
  390.                 return;
  391.         }
  392.  
  393.         nodes.erase(it);
  394.  
  395.         m_hashSpace.RemoveObject(SGraphNodeRecord(nodeIndex));
  396.  
  397.         ResetIterators(type);
  398. }
  399.  
  400. //====================================================================
  401. // DoesNodeExist
  402. // careful not to dereference the pointer, at least until we know it's
  403. // valid
  404. //====================================================================
  405. inline bool CAllNodesContainer::DoesNodeExist(unsigned nodeIndex) const
  406. {
  407.         const GraphNode* pNode = m_nodeManager.GetNode(nodeIndex);
  408.         if (!pNode)
  409.         {
  410.                 AIWarning("CAllNodesContainer: Attempting to see if 0 node exists!");
  411.                 return false;
  412.         }
  413.  
  414.         for (tAllNodes::const_iterator it = m_allNodes.begin();
  415.              it != m_allNodes.end();
  416.              ++it)
  417.         {
  418.                 const tNodes& nodes = it->second;
  419.                 tNodes::const_iterator nodeIt = nodes.find(nodeIndex); // why do I need to cast?!
  420.                 if (nodeIt != nodes.end())
  421.                 {
  422.                         return true;
  423.                 }
  424.         }
  425.         return false;
  426. }
  427.  
  428. ////====================================================================
  429. //// Erase
  430. ////====================================================================
  431. //inline CAllNodesContainer::Iterator CAllNodesContainer::Erase(const Iterator& it)
  432. //{
  433. //  if (it.m_container != this)
  434. //  {
  435. //    AIWarning("CAllNodesContainer::Erase Asked to erase an iterator not associated with us");
  436. //    return it;
  437. //  }
  438. //  if (const GraphNode *pNode = it.GetNode())
  439. //  {
  440. //    unsigned type = pNode->navType;
  441. //    ResetIterators(type);
  442. //  }
  443. //  CAllNodesContainer::Iterator result(it);
  444. //  if (result.m_it != result.m_currentEndIt)
  445. //  {
  446. //    m_hashSpace.RemoveObject(SGraphNodeRecord(it.GetNode()));
  447. //              std::set<GraphNode*>::iterator itNext = result.m_it;
  448. //              itNext++;
  449. //              result.m_currentAllNodesIt->second.erase(result.m_it);
  450. //    result.m_it = itNext;
  451. //    if (result.m_it != result.m_currentEndIt)
  452. //      return result;
  453. //  }
  454. //
  455. //  result.Increment();
  456. //  return result;
  457. //}
  458.  
  459. //====================================================================
  460. // GetAllNodesWithinRange
  461. //====================================================================
  462. inline void CAllNodesContainer::GetAllNodesWithinRange(std::vector<std::pair<float, unsigned>>& nodesOut, const Vec3& pos, float range, IAISystem::tNavCapMask navTypeMask) const
  463. {
  464.         FUNCTION_PROFILER(GetISystem(), PROFILE_AI);
  465.         nodesOut.resize(0);
  466.         SNodeCollector collector(m_nodeManager, nodesOut, navTypeMask);
  467.         m_hashSpace.ProcessObjectsWithinRadius(pos, range, collector);
  468. }
  469.  
  470. //====================================================================
  471. // GetNodeWithinRange
  472. //====================================================================
  473. inline bool CAllNodesContainer::GetNodeWithinRange(std::pair<float, unsigned>& nodeOut, const Vec3& pos, float range, IAISystem::tNavCapMask navTypeMask, CGraph* graph) const
  474. {
  475.         FUNCTION_PROFILER(GetISystem(), PROFILE_AI);
  476.  
  477.         SOneNodeCollector collector(m_nodeManager, graph, pos, nodeOut, navTypeMask);
  478.         return m_hashSpace.GetObjectWithinRadius(pos, range, collector);
  479. }
  480.  
  481. #endif
  482.  
downloadAllNodesContainer.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