Menge
Modular Pedestrian Simulation Framework for Research and Development
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
PathPlanner.h
Go to the documentation of this file.
1 /*
2 
3 License
4 
5 Menge
6 Copyright and trademark 2012-14 University of North Carolina at Chapel Hill.
7 All rights reserved.
8 
9 Permission to use, copy, modify, and distribute this software and its documentation
10 for educational, research, and non-profit purposes, without fee, and without a
11 written agreement is hereby granted, provided that the above copyright notice,
12 this paragraph, and the following four paragraphs appear in all copies.
13 
14 This software program and documentation are copyrighted by the University of North
15 Carolina at Chapel Hill. The software program and documentation are supplied "as is,"
16 without any accompanying services from the University of North Carolina at Chapel
17 Hill or the authors. The University of North Carolina at Chapel Hill and the
18 authors do not warrant that the operation of the program will be uninterrupted
19 or error-free. The end-user understands that the program was developed for research
20 purposes and is advised not to rely exclusively on the program for any reason.
21 
22 IN NO EVENT SHALL THE UNIVERSITY OF NORTH CAROLINA AT CHAPEL HILL OR THE AUTHORS
23 BE LIABLE TO ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL
24 DAMAGES, INCLUDING LOST PROFITS, ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS
25 DOCUMENTATION, EVEN IF THE UNIVERSITY OF NORTH CAROLINA AT CHAPEL HILL OR THE
26 AUTHORS HAVE BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 
28 THE UNIVERSITY OF NORTH CAROLINA AT CHAPEL HILL AND THE AUTHORS SPECIFICALLY
29 DISCLAIM ANY WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
30 OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE AND ANY STATUTORY WARRANTY
31 OF NON-INFRINGEMENT. THE SOFTWARE PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND
32 THE UNIVERSITY OF NORTH CAROLINA AT CHAPEL HILL AND THE AUTHORS HAVE NO OBLIGATIONS
33 TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
34 
35 Any questions or comments should be sent to the authors {menge,geom}@cs.unc.edu
36 
37 */
38 
44 #ifndef __PATH_PLANNER_H__
45 #define __PATH_PLANNER_H__
46 
47 #include "mengeCommon.h"
48 #include "NavMesh.h"
49 #include "ReadersWriterLock.h"
50 #include <map>
51 #include <list>
52 
53 namespace Menge {
54 
58  class MENGE_API PathPlannerException : public virtual MengeException {
59  public:
64 
70  PathPlannerException( const std::string & s ): MengeException(s) {}
71  };
72 
77  public:
82 
89  };
90 
91  // FORWARD DECLARATIONS
92  class PortalRoute;
93  class PathPlanner;
94 
98  typedef size_t RouteKey;
99 
103  typedef std::list< PortalRoute * > PRouteList;
104 
108  typedef PRouteList::iterator PRouteListItr;
109 
113  typedef PRouteList::const_iterator PRouteListCItr;
114 
118  typedef HASH_MAP< RouteKey, PRouteList > PRouteMap;
119 
123  typedef PRouteMap::iterator PRouteMapItr;
124 
128  typedef PRouteMap::const_iterator PRouteMapCItr;
129 
133  class PathPlanner {
134  public:
141  PathPlanner( NavMeshPtr ptr );
142 
146  ~PathPlanner();
147 
160  PortalRoute * getRoute( unsigned int startID, unsigned int endID, float minWidth );
161 
162  protected:
176  PortalRoute * computeRoute( unsigned int startID, unsigned int endID, float minWidth );
177 
187  float computeH( unsigned int node, const Vector2 & goal );
188 
205  PortalRoute * cacheRoute( unsigned int startID, unsigned int endID, PortalRoute * route );
206 
213  PRouteMap _routes;
214 
219 
224 
230  void initHeapMemory( size_t nodeCount );
231 
236  size_t DATA_SIZE;
237 
242  size_t STATE_SIZE;
243 
249  unsigned int * _HEAP;
250 
257  unsigned int * _PATH;
258 
266  float * _DATA;
267 
273  bool * _STATE;
274  };
275 } // namespace Menge
276 
277 #endif // __PATH_PLANNER_H__
PRouteMap _routes
A mapping from RouteKeys (a size_t) to to a list of routes. The list consists of routes between the p...
Definition: PathPlanner.h:213
size_t RouteKey
Definition of the identifier of a Route.
Definition: PathPlanner.h:93
float computeH(unsigned int node, const Vector2 &goal)
Compute's "h" for the A* algorithm. H is the estimate of the cost of a node to a goal point...
Definition: PathPlanner.cpp:263
The core namespace. All elements of Menge are contained in this namespace.
Definition: AgentGenerator.cpp:43
PathPlanner(NavMeshPtr ptr)
Constructor.
Definition: PathPlanner.cpp:81
PRouteMap::iterator PRouteMapItr
An iterator to a PRouteMap.
Definition: PathPlanner.h:123
void initHeapMemory(size_t nodeCount)
Initializes the heap memory.
Definition: PathPlanner.cpp:233
std::list< PortalRoute * > PRouteList
A list of PortalRoute pointers.
Definition: PathPlanner.h:103
Exception class for path planner.
Definition: PathPlanner.h:58
The definition of a readers-writer lock.
Definition: ReadersWriterLock.h:62
PortalRoute * computeRoute(unsigned int startID, unsigned int endID, float minWidth)
Computes a route (and adds it to the cache) between start and end with the minimum clearance given...
Definition: PathPlanner.cpp:123
PathPlannerException()
Default constructor.
Definition: PathPlanner.h:63
size_t STATE_SIZE
The size of a block of data used for STATE in the A* algorithm (2N, N = number of nodes) ...
Definition: PathPlanner.h:242
Class for computing paths through a navigation mesh.
Definition: PathPlanner.h:133
The definition of a route through a navigation mesh from a start to an end node.
Definition: Route.h:60
Base exception class for menge operations.
Definition: MengeException.h:58
bool * _STATE
Block of data for reportin node state (if its in a heap or if its no longer used for calculation...
Definition: PathPlanner.h:273
PortalRoute * getRoute(unsigned int startID, unsigned int endID, float minWidth)
Returns a route between the two specified nodes.
Definition: PathPlanner.cpp:94
~PathPlanner()
Destrutor.
Definition: PathPlanner.cpp:88
PathPlannerFatalException()
Default constructor.
Definition: PathPlanner.h:81
ReadersWriterLock _routeLock
Lock for securing _routes;.
Definition: PathPlanner.h:218
unsigned int * _PATH
The full set of data for reconstructing the path. For any given entry i, the value at i is the index ...
Definition: PathPlanner.h:257
HASH_MAP< RouteKey, PRouteList > PRouteMap
A mapping from RouteKey to PRouteList.
Definition: PathPlanner.h:118
The definition of a readers-writer lock.
Base class for fatal exceptions.
Definition: MengeException.h:99
NavMeshPtr _navMesh
The navigation mesh for planning on.
Definition: PathPlanner.h:223
PRouteList::iterator PRouteListItr
An iterator to a PRouteList.
Definition: PathPlanner.h:108
size_t DATA_SIZE
The size of a block of data used for COST in the A* algorithm (3N, N = number of nodes) ...
Definition: PathPlanner.h:236
PathPlannerException(const std::string &s)
Constructor with message.
Definition: PathPlanner.h:70
PathPlannerFatalException(const std::string &s)
Constructor with message.
Definition: PathPlanner.h:88
PRouteMap::const_iterator PRouteMapCItr
A const iterator to a PRouteMap.
Definition: PathPlanner.h:128
The fatal path planner exception.
Definition: PathPlanner.h:76
Defines the classes which maintain the navigation mesh data.
PRouteList::const_iterator PRouteListCItr
A const iterator to a PRouteList.
Definition: PathPlanner.h:113
unsigned int * _HEAP
The full set of data to serve as the heap There are N entries in a single heap and one heap per threa...
Definition: PathPlanner.h:249
float * _DATA
The block of data for tracking the f, g, and h data for nodes. (This is where DATA_SIZE = 3N comes fr...
Definition: PathPlanner.h:266
PortalRoute * cacheRoute(unsigned int startID, unsigned int endID, PortalRoute *route)
Cache the given route going from start to goal.
Definition: PathPlanner.cpp:270