BVB Source Codes

CRYENGINE Show AStarOpenList.h Source code

Return Download CRYENGINE: download AStarOpenList.h Source code - Download CRYENGINE Source code - Type:.h
  1. // Copyright 2001-2016 Crytek GmbH / Crytek Group. All rights reserved.
  2.  
  3. #ifndef ASTAROPENLIST_H
  4. #define ASTAROPENLIST_H
  5.  
  6. #if _MSC_VER > 1000
  7.         #pragma once
  8. #endif
  9.  
  10. #include <CryAISystem/IAgent.h>
  11. #include "GraphStructures.h"
  12. #include <vector>
  13. #include <set>
  14. #include <algorithm>
  15. #include <CryMemory/STLPoolAllocator.h>
  16.  
  17. // If this isn't on the OpenListMonitor isn't even mentioned in AStarOpenList.
  18. //#define MONITOR_OPEN_LIST
  19. /**
  20.  * Useful for gathering info about how A* open list operates.
  21.  *
  22.  * Receives an event for every node that's pushed to the open list and every
  23.  * node that popped from there.  Based on that it computes various statistics.
  24.  *
  25.  * TODO Mai 22, 2007: <pvl> no reasonable way of outputting the gathered stats
  26.  * at the moment.  In fact, mainly intended to be used "manually" under
  27.  * debugger ... :)
  28.  */
  29. class OpenListMonitor
  30. {
  31.         /// Holds any info we care to hold per every node currently on the open list.
  32.         struct NodeInfo
  33.         {
  34.                 CTimeValue m_timestamp;
  35.                 int        m_frame;
  36.                 NodeInfo(const CTimeValue& time, int frame) : m_timestamp(time), m_frame(frame)
  37.                 {}
  38.         };
  39.         /// Uses graph node index as a unique node ID and maps that to corresponding node info.
  40.         typedef std::map<unsigned int, NodeInfo> NodeInfoMap;
  41.         NodeInfoMap m_nodeInfoMap;
  42.  
  43.         /// The actual open list statistics.
  44.         float sMin;
  45.         float sMax;
  46.         float sAvg;
  47.         int   sNumSamples;
  48.         float sMinFrames;
  49.         float sMaxFrames;
  50.         float sAvgFrames;
  51.         /// For each frame that's leaving the open list, this is called with the time
  52.         /// and a number of frames that the node spent on the open list.
  53.         void UpdateStats(float t, int frames)
  54.         {
  55.                 if (t < sMin) sMin = t;
  56.                 if (t > sMax) sMax = t;
  57.                 sAvg = (sAvg * sNumSamples + t) / (sNumSamples + 1);
  58.  
  59.                 if (t < sMinFrames) sMinFrames = (float)frames;
  60.                 if (t > sMaxFrames) sMaxFrames = (float)frames;
  61.                 sAvgFrames = (sAvgFrames * sNumSamples + frames) / (sNumSamples + 1);
  62.  
  63.                 ++sNumSamples;
  64.         }
  65. public:
  66.         OpenListMonitor()
  67.                 : sMin(std::numeric_limits<float>::max())
  68.                 , sMax(std::numeric_limits<float>::min())
  69.                 , sAvg(0.0f)
  70.                 , sNumSamples(0)
  71.                 , sMinFrames(std::numeric_limits<float>::max())
  72.                 , sMaxFrames(std::numeric_limits<float>::min())
  73.                 , sAvgFrames(0.0f)
  74.         {}
  75.         void NodePushed(unsigned int nodeIndex)
  76.         {
  77.                 // NOTE Mai 22, 2007: <pvl> we could filter incoming nodes here if we're
  78.                 // only interested in stats for a certain node class
  79.                 /*
  80.                     GraphNode* nodeptr = nodeManager.GetNode(node);
  81.                     if (nodeptr->navType != IAISystem::NAV_WAYPOINT_HUMAN)
  82.                       return;
  83.                  */
  84.                 CTimeValue now = gEnv->pTimer->GetAsyncTime();
  85.                 int currFrame = gEnv->pRenderer->GetFrameID();
  86.                 m_nodeInfoMap.insert(std::make_pair(nodeIndex, NodeInfo(now, currFrame)));
  87.         }
  88.         void NodePopped(unsigned int nodeIndex)
  89.         {
  90.                 NodeInfoMap::iterator infoIt = m_nodeInfoMap.find(nodeIndex);
  91.                 if (infoIt == m_nodeInfoMap.end())
  92.                 {
  93.                         // NOTE Mai 22, 2007: <pvl> can happen if we filter nodes in NodePushed()
  94.                         return;
  95.                 }
  96.  
  97.                 CTimeValue timeWhenPushed = infoIt->second.m_timestamp;
  98.                 int frameWhenPushed = infoIt->second.m_frame;
  99.  
  100.                 CTimeValue now = gEnv->pTimer->GetAsyncTime();
  101.                 int currFrame = gEnv->pRenderer->GetFrameID();
  102.  
  103.                 float timeSpentInList = (now - timeWhenPushed).GetMilliSeconds();
  104.                 int framesSpentInList = currFrame - frameWhenPushed;
  105.                 UpdateStats(timeSpentInList, framesSpentInList);
  106.         }
  107. };
  108.  
  109. struct AStarSearchNode
  110. {
  111.         float            fCostFromStart;
  112.         float            fEstimatedCostToGoal;
  113.         AStarSearchNode* prevPathNodeIndex;
  114.         GraphNode*       graphNode;
  115.         uint32           nodeIndex : 31;
  116.         bool             tagged    : 1;
  117.  
  118.         AStarSearchNode()
  119.                 : fCostFromStart(fInvalidCost)
  120.                 , fEstimatedCostToGoal(fInvalidCost)
  121.                 , prevPathNodeIndex(0)
  122.                 , graphNode(0)
  123.                 , nodeIndex(0)
  124.                 , tagged(false)
  125.         {
  126.         }
  127.  
  128.         bool IsTagged()
  129.         {
  130.                 return tagged != false;
  131.         }
  132.  
  133.         void Tag()
  134.         {
  135.                 tagged = true;
  136.         }
  137.  
  138.         // Used as a flag for costs that aren't calculated yet
  139.         static const float fInvalidCost;
  140. private:
  141.         friend class CAStarNodeListManager;
  142.  
  143.         AStarSearchNode(uint32 originalNodeIndex)
  144.                 : fCostFromStart(fInvalidCost)
  145.                 , fEstimatedCostToGoal(fInvalidCost)
  146.                 , prevPathNodeIndex(0)
  147.                 , graphNode(0)
  148.                 , nodeIndex(originalNodeIndex)
  149.                 , tagged(false)
  150.         {
  151.         }
  152. };
  153.  
  154. /// Helper class to sort the node lists
  155. struct NodeCompareCost
  156. {
  157.         NodeCompareCost()
  158.         {
  159.         }
  160.  
  161.         bool operator()(const AStarSearchNode* node1, const AStarSearchNode* node2) const
  162.         {
  163.                 return ((node1->fCostFromStart + node1->fEstimatedCostToGoal) > (node2->fCostFromStart + node2->fEstimatedCostToGoal));
  164.         }
  165. };
  166.  
  167. // Helper class to sort the node lists
  168. struct NodeCompareIndex
  169. {
  170.         bool operator()(const AStarSearchNode& node1, const AStarSearchNode& node2) const
  171.         {
  172.                 return node1.nodeIndex < node2.nodeIndex;
  173.         }
  174. };
  175.  
  176. typedef std::vector<AStarSearchNode*> AStarSearchNodeVector;
  177.  
  178. //====================================================================
  179. // CAStarNodeListManager
  180. //====================================================================
  181. class CAStarNodeListManager
  182. {
  183. public:
  184.         CAStarNodeListManager(CGraphNodeManager& nodeManager)
  185.                 : nodeManager(nodeManager)
  186.         {
  187.         }
  188.  
  189.         /// Gets the best node and removes it from the list. Returns 0 if
  190.         /// the list is empty
  191.         AStarSearchNode* PopBestNodeFromOpenList();
  192.  
  193.         /// Adds a node to the list (shouldn't already be in the list)
  194.         void AddNodeToOpenList(AStarSearchNode*);
  195.  
  196.         /// If the node is in the list then its position in the list gets updated.
  197.         /// If not the list isn't changed. Either way the node itself gets
  198.         /// modified
  199.         void UpdateNode(AStarSearchNode* node, float newCost, float newEstimatedCost);
  200.  
  201.         /// Indicates if the list is empty
  202.         bool IsEmpty() const;
  203.  
  204.         /// Empties the list
  205.         void Clear(bool freeMemory = false);
  206.  
  207.         // returns memory usage in bytes
  208.         size_t MemStats();
  209.  
  210.         /// Reserves memory based on an estimated max list size
  211.         void                         ReserveMemory(size_t estimatedMaxSize);
  212.  
  213.         const AStarSearchNodeVector& GetTaggedNodesVector()
  214.         {
  215.                 return taggedNodesVector;
  216.         }
  217.  
  218.         AStarSearchNode* GetAStarNode(uint32 index)
  219.         {
  220.                 std::pair<AStarSearchNodes::iterator, bool> it = currentNodes.insert(AStarSearchNode(index));
  221.                 if (it.second)
  222.                 {
  223.                         AStarSearchNode& node = const_cast<AStarSearchNode&>(*it.first);
  224.                         node.graphNode = nodeManager.GetNode(index);
  225.                 }
  226.  
  227.                 return const_cast<AStarSearchNode*>(&(*it.first));
  228.         }
  229.  
  230. private:
  231.         typedef stl::STLPoolAllocator<AStarSearchNode, stl::PSyncNone>         OpenListAllocator;
  232.         typedef std::set<AStarSearchNode, NodeCompareIndex, OpenListAllocator> AStarSearchNodes;
  233.         AStarSearchNodes currentNodes;
  234.  
  235.         /// the open list
  236.         AStarSearchNodeVector openList;
  237.         CGraphNodeManager&    nodeManager;
  238.         AStarSearchNodeVector taggedNodesVector;
  239.  
  240. #ifdef MONITOR_OPEN_LIST
  241.         OpenListMonitor m_monitor;
  242. #endif // MONITOR_OPEN_LIST
  243. };
  244.  
  245. //====================================================================
  246. // Don't look below here - inline implementation
  247. //====================================================================
  248.  
  249. //====================================================================
  250. // ReserveMemory
  251. //====================================================================
  252. inline void CAStarNodeListManager::ReserveMemory(size_t estimatedMaxSize)
  253. {
  254. }
  255.  
  256. //====================================================================
  257. // MemStats
  258. //====================================================================
  259. inline size_t CAStarNodeListManager::MemStats()
  260. {
  261.         return openList.capacity() * sizeof(unsigned);
  262. }
  263.  
  264. //====================================================================
  265. // IsEmpty
  266. //====================================================================
  267. inline bool CAStarNodeListManager::IsEmpty() const
  268. {
  269.         return openList.empty();
  270. }
  271.  
  272. //====================================================================
  273. // PopBestNode
  274. //====================================================================
  275. inline AStarSearchNode* CAStarNodeListManager::PopBestNodeFromOpenList()
  276. {
  277.         if (IsEmpty())
  278.                 return 0;
  279.  
  280.         AStarSearchNode* node = openList.front();
  281.         // This "forgets about" the last node, and (partially) sorts the rest
  282.         std::pop_heap(openList.begin(), openList.end(), NodeCompareCost());
  283.         // remove the redundant element
  284.         openList.pop_back();
  285.  
  286. #ifdef MONITOR_OPEN_LIST
  287.         m_monitor.NodePopped(node->nodeIndex);
  288. #endif // MONITOR_OPEN_LIST
  289.  
  290.         return node;
  291. }
  292.  
  293. //====================================================================
  294. // AddNode
  295. //====================================================================
  296. inline void CAStarNodeListManager::AddNodeToOpenList(AStarSearchNode* node)
  297. {
  298.         node->Tag();
  299.         taggedNodesVector.push_back(node);
  300.  
  301.         openList.push_back(node);
  302.         std::push_heap(openList.begin(), openList.end(), NodeCompareCost());
  303.  
  304. #ifdef MONITOR_OPEN_LIST
  305.         m_monitor.NodePushed(node->nodeIndex);
  306. #endif // MONITOR_OPEN_LIST
  307. }
  308.  
  309. //====================================================================
  310. // UpdateNode
  311. //====================================================================
  312. inline void CAStarNodeListManager::UpdateNode(AStarSearchNode* node, float newCost, float newEstimatedCost)
  313. {
  314.         const AStarSearchNodeVector::const_iterator end = openList.end();
  315.  
  316.         for (AStarSearchNodeVector::iterator it = openList.begin(); it != end; ++it)
  317.         {
  318.                 if (*it == node)
  319.                 {
  320.                         node->fCostFromStart = newCost;
  321.                         node->fEstimatedCostToGoal = newEstimatedCost;
  322.                         std::push_heap(openList.begin(), it + 1, NodeCompareCost());
  323.  
  324.                         return;
  325.                 }
  326.         }
  327.  
  328.         node->fCostFromStart = newCost;
  329.         node->fEstimatedCostToGoal = newEstimatedCost;
  330. }
  331.  
  332. //====================================================================
  333. // Clear
  334. //====================================================================
  335. inline void CAStarNodeListManager::Clear(bool freeMemory /* = false*/)
  336. {
  337.         if (freeMemory)
  338.         {
  339.                 stl::free_container(openList);
  340.                 currentNodes.clear();
  341.                 stl::free_container(taggedNodesVector);
  342.         }
  343.         else
  344.         {
  345.                 openList.resize(0);
  346.                 currentNodes.clear();
  347.                 taggedNodesVector.resize(0);
  348.         }
  349. }
  350.  
  351. #endif
  352.  
downloadAStarOpenList.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