DetourCrowd.h 18 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460
  1. //
  2. // Copyright (c) 2009-2010 Mikko Mononen memon@inside.org
  3. //
  4. // This software is provided 'as-is', without any express or implied
  5. // warranty. In no event will the authors be held liable for any damages
  6. // arising from the use of this software.
  7. // Permission is granted to anyone to use this software for any purpose,
  8. // including commercial applications, and to alter it and redistribute it
  9. // freely, subject to the following restrictions:
  10. // 1. The origin of this software must not be misrepresented; you must not
  11. // claim that you wrote the original software. If you use this software
  12. // in a product, an acknowledgment in the product documentation would be
  13. // appreciated but is not required.
  14. // 2. Altered source versions must be plainly marked as such, and must not be
  15. // misrepresented as being the original software.
  16. // 3. This notice may not be removed or altered from any source distribution.
  17. //
  18. #ifndef DETOURCROWD_H
  19. #define DETOURCROWD_H
  20. #include "DetourNavMeshQuery.h"
  21. #include "DetourObstacleAvoidance.h"
  22. #include "DetourLocalBoundary.h"
  23. #include "DetourPathCorridor.h"
  24. #include "DetourProximityGrid.h"
  25. #include "DetourPathQueue.h"
  26. /// The maximum number of neighbors that a crowd agent can take into account
  27. /// for steering decisions.
  28. /// @ingroup crowd
  29. static const int DT_CROWDAGENT_MAX_NEIGHBOURS = 6;
  30. /// The maximum number of corners a crowd agent will look ahead in the path.
  31. /// This value is used for sizing the crowd agent corner buffers.
  32. /// Due to the behavior of the crowd manager, the actual number of useful
  33. /// corners will be one less than this number.
  34. /// @ingroup crowd
  35. static const int DT_CROWDAGENT_MAX_CORNERS = 4;
  36. /// The maximum number of crowd avoidance configurations supported by the
  37. /// crowd manager.
  38. /// @ingroup crowd
  39. /// @see dtObstacleAvoidanceParams, dtCrowd::setObstacleAvoidanceParams(), dtCrowd::getObstacleAvoidanceParams(),
  40. /// dtCrowdAgentParams::obstacleAvoidanceType
  41. static const int DT_CROWD_MAX_OBSTAVOIDANCE_PARAMS = 8;
  42. /// The maximum number of query filter types supported by the crowd manager.
  43. /// @ingroup crowd
  44. /// @see dtQueryFilter, dtCrowd::getFilter() dtCrowd::getEditableFilter(),
  45. /// dtCrowdAgentParams::queryFilterType
  46. static const int DT_CROWD_MAX_QUERY_FILTER_TYPE = 16;
  47. /// Provides neighbor data for agents managed by the crowd.
  48. /// @ingroup crowd
  49. /// @see dtCrowdAgent::neis, dtCrowd
  50. struct dtCrowdNeighbour
  51. {
  52. int idx; ///< The index of the neighbor in the crowd.
  53. float dist; ///< The distance between the current agent and the neighbor.
  54. };
  55. /// The type of navigation mesh polygon the agent is currently traversing.
  56. /// @ingroup crowd
  57. enum CrowdAgentState
  58. {
  59. DT_CROWDAGENT_STATE_INVALID, ///< The agent is not in a valid state.
  60. DT_CROWDAGENT_STATE_WALKING, ///< The agent is traversing a normal navigation mesh polygon.
  61. DT_CROWDAGENT_STATE_OFFMESH, ///< The agent is traversing an off-mesh connection.
  62. };
  63. /// Configuration parameters for a crowd agent.
  64. /// @ingroup crowd
  65. struct dtCrowdAgentParams
  66. {
  67. float radius; ///< Agent radius. [Limit: >= 0]
  68. float height; ///< Agent height. [Limit: > 0]
  69. float maxAcceleration; ///< Maximum allowed acceleration. [Limit: >= 0]
  70. float maxSpeed; ///< Maximum allowed speed. [Limit: >= 0]
  71. /// Defines how close a collision element must be before it is considered for steering behaviors. [Limits: > 0]
  72. float collisionQueryRange;
  73. float pathOptimizationRange; ///< The path visibility optimization range. [Limit: > 0]
  74. /// How aggresive the agent manager should be at avoiding collisions with this agent. [Limit: >= 0]
  75. float separationWeight;
  76. /// Flags that impact steering behavior. (See: #UpdateFlags)
  77. unsigned char updateFlags;
  78. /// The index of the avoidance configuration to use for the agent.
  79. /// [Limits: 0 <= value <= #DT_CROWD_MAX_OBSTAVOIDANCE_PARAMS]
  80. unsigned char obstacleAvoidanceType;
  81. /// The index of the query filter used by this agent.
  82. unsigned char queryFilterType;
  83. /// User defined data attached to the agent.
  84. void* userData;
  85. };
  86. enum MoveRequestState
  87. {
  88. DT_CROWDAGENT_TARGET_NONE = 0,
  89. DT_CROWDAGENT_TARGET_FAILED,
  90. DT_CROWDAGENT_TARGET_VALID,
  91. DT_CROWDAGENT_TARGET_REQUESTING,
  92. DT_CROWDAGENT_TARGET_WAITING_FOR_QUEUE,
  93. DT_CROWDAGENT_TARGET_WAITING_FOR_PATH,
  94. DT_CROWDAGENT_TARGET_VELOCITY,
  95. };
  96. /// Represents an agent managed by a #dtCrowd object.
  97. /// @ingroup crowd
  98. struct dtCrowdAgent
  99. {
  100. /// True if the agent is active, false if the agent is in an unused slot in the agent pool.
  101. bool active;
  102. /// The type of mesh polygon the agent is traversing. (See: #CrowdAgentState)
  103. unsigned char state;
  104. /// True if the agent has valid path (targetState == DT_CROWDAGENT_TARGET_VALID) and the path does not lead to the requested position, else false.
  105. bool partial;
  106. /// The path corridor the agent is using.
  107. dtPathCorridor corridor;
  108. /// The local boundary data for the agent.
  109. dtLocalBoundary boundary;
  110. /// Time since the agent's path corridor was optimized.
  111. float topologyOptTime;
  112. /// The known neighbors of the agent.
  113. dtCrowdNeighbour neis[DT_CROWDAGENT_MAX_NEIGHBOURS];
  114. /// The number of neighbors.
  115. int nneis;
  116. /// The desired speed.
  117. float desiredSpeed;
  118. float npos[3]; ///< The current agent position. [(x, y, z)]
  119. float disp[3]; ///< A temporary value used to accumulate agent displacement during iterative collision resolution. [(x, y, z)]
  120. float dvel[3]; ///< The desired velocity of the agent. Based on the current path, calculated from scratch each frame. [(x, y, z)]
  121. float nvel[3]; ///< The desired velocity adjusted by obstacle avoidance, calculated from scratch each frame. [(x, y, z)]
  122. float vel[3]; ///< The actual velocity of the agent. The change from nvel -> vel is constrained by max acceleration. [(x, y, z)]
  123. /// The agent's configuration parameters.
  124. dtCrowdAgentParams params;
  125. /// The local path corridor corners for the agent. (Staight path.) [(x, y, z) * #ncorners]
  126. float cornerVerts[DT_CROWDAGENT_MAX_CORNERS*3];
  127. /// The local path corridor corner flags. (See: #dtStraightPathFlags) [(flags) * #ncorners]
  128. unsigned char cornerFlags[DT_CROWDAGENT_MAX_CORNERS];
  129. /// The reference id of the polygon being entered at the corner. [(polyRef) * #ncorners]
  130. dtPolyRef cornerPolys[DT_CROWDAGENT_MAX_CORNERS];
  131. /// The number of corners.
  132. int ncorners;
  133. unsigned char targetState; ///< State of the movement request.
  134. dtPolyRef targetRef; ///< Target polyref of the movement request.
  135. float targetPos[3]; ///< Target position of the movement request (or velocity in case of DT_CROWDAGENT_TARGET_VELOCITY).
  136. dtPathQueueRef targetPathqRef; ///< Path finder ref.
  137. bool targetReplan; ///< Flag indicating that the current path is being replanned.
  138. float targetReplanTime; /// <Time since the agent's target was replanned.
  139. };
  140. struct dtCrowdAgentAnimation
  141. {
  142. bool active;
  143. float initPos[3], startPos[3], endPos[3];
  144. dtPolyRef polyRef;
  145. float t, tmax;
  146. };
  147. /// Crowd agent update flags.
  148. /// @ingroup crowd
  149. /// @see dtCrowdAgentParams::updateFlags
  150. enum UpdateFlags
  151. {
  152. DT_CROWD_ANTICIPATE_TURNS = 1,
  153. DT_CROWD_OBSTACLE_AVOIDANCE = 2,
  154. DT_CROWD_SEPARATION = 4,
  155. DT_CROWD_OPTIMIZE_VIS = 8, ///< Use #dtPathCorridor::optimizePathVisibility() to optimize the agent path.
  156. DT_CROWD_OPTIMIZE_TOPO = 16, ///< Use dtPathCorridor::optimizePathTopology() to optimize the agent path.
  157. };
  158. struct dtCrowdAgentDebugInfo
  159. {
  160. int idx;
  161. float optStart[3], optEnd[3];
  162. dtObstacleAvoidanceDebugData* vod;
  163. };
  164. /// Provides local steering behaviors for a group of agents.
  165. /// @ingroup crowd
  166. class dtCrowd
  167. {
  168. int m_maxAgents;
  169. dtCrowdAgent* m_agents;
  170. dtCrowdAgent** m_activeAgents;
  171. dtCrowdAgentAnimation* m_agentAnims;
  172. dtPathQueue m_pathq;
  173. dtObstacleAvoidanceParams m_obstacleQueryParams[DT_CROWD_MAX_OBSTAVOIDANCE_PARAMS];
  174. dtObstacleAvoidanceQuery* m_obstacleQuery;
  175. dtProximityGrid* m_grid;
  176. dtPolyRef* m_pathResult;
  177. int m_maxPathResult;
  178. float m_agentPlacementHalfExtents[3];
  179. dtQueryFilter m_filters[DT_CROWD_MAX_QUERY_FILTER_TYPE];
  180. float m_maxAgentRadius;
  181. int m_velocitySampleCount;
  182. dtNavMeshQuery* m_navquery;
  183. void updateTopologyOptimization(dtCrowdAgent** agents, const int nagents, const float dt);
  184. void updateMoveRequest(const float dt);
  185. void checkPathValidity(dtCrowdAgent** agents, const int nagents, const float dt);
  186. inline int getAgentIndex(const dtCrowdAgent* agent) const { return (int)(agent - m_agents); }
  187. bool requestMoveTargetReplan(const int idx, dtPolyRef ref, const float* pos);
  188. void purge();
  189. public:
  190. dtCrowd();
  191. ~dtCrowd();
  192. /// Initializes the crowd.
  193. /// @param[in] maxAgents The maximum number of agents the crowd can manage. [Limit: >= 1]
  194. /// @param[in] maxAgentRadius The maximum radius of any agent that will be added to the crowd. [Limit: > 0]
  195. /// @param[in] nav The navigation mesh to use for planning.
  196. /// @return True if the initialization succeeded.
  197. bool init(const int maxAgents, const float maxAgentRadius, dtNavMesh* nav);
  198. /// Sets the shared avoidance configuration for the specified index.
  199. /// @param[in] idx The index. [Limits: 0 <= value < #DT_CROWD_MAX_OBSTAVOIDANCE_PARAMS]
  200. /// @param[in] params The new configuration.
  201. void setObstacleAvoidanceParams(const int idx, const dtObstacleAvoidanceParams* params);
  202. /// Gets the shared avoidance configuration for the specified index.
  203. /// @param[in] idx The index of the configuration to retreive.
  204. /// [Limits: 0 <= value < #DT_CROWD_MAX_OBSTAVOIDANCE_PARAMS]
  205. /// @return The requested configuration.
  206. const dtObstacleAvoidanceParams* getObstacleAvoidanceParams(const int idx) const;
  207. /// Gets the specified agent from the pool.
  208. /// @param[in] idx The agent index. [Limits: 0 <= value < #getAgentCount()]
  209. /// @return The requested agent.
  210. const dtCrowdAgent* getAgent(const int idx);
  211. /// Gets the specified agent from the pool.
  212. /// @param[in] idx The agent index. [Limits: 0 <= value < #getAgentCount()]
  213. /// @return The requested agent.
  214. dtCrowdAgent* getEditableAgent(const int idx);
  215. /// The maximum number of agents that can be managed by the object.
  216. /// @return The maximum number of agents.
  217. int getAgentCount() const;
  218. /// Adds a new agent to the crowd.
  219. /// @param[in] pos The requested position of the agent. [(x, y, z)]
  220. /// @param[in] params The configutation of the agent.
  221. /// @return The index of the agent in the agent pool. Or -1 if the agent could not be added.
  222. int addAgent(const float* pos, const dtCrowdAgentParams* params);
  223. /// Updates the specified agent's configuration.
  224. /// @param[in] idx The agent index. [Limits: 0 <= value < #getAgentCount()]
  225. /// @param[in] params The new agent configuration.
  226. void updateAgentParameters(const int idx, const dtCrowdAgentParams* params);
  227. /// Removes the agent from the crowd.
  228. /// @param[in] idx The agent index. [Limits: 0 <= value < #getAgentCount()]
  229. void removeAgent(const int idx);
  230. /// Submits a new move request for the specified agent.
  231. /// @param[in] idx The agent index. [Limits: 0 <= value < #getAgentCount()]
  232. /// @param[in] ref The position's polygon reference.
  233. /// @param[in] pos The position within the polygon. [(x, y, z)]
  234. /// @return True if the request was successfully submitted.
  235. bool requestMoveTarget(const int idx, dtPolyRef ref, const float* pos);
  236. /// Submits a new move request for the specified agent.
  237. /// @param[in] idx The agent index. [Limits: 0 <= value < #getAgentCount()]
  238. /// @param[in] vel The movement velocity. [(x, y, z)]
  239. /// @return True if the request was successfully submitted.
  240. bool requestMoveVelocity(const int idx, const float* vel);
  241. /// Resets any request for the specified agent.
  242. /// @param[in] idx The agent index. [Limits: 0 <= value < #getAgentCount()]
  243. /// @return True if the request was successfully reseted.
  244. bool resetMoveTarget(const int idx);
  245. /// Gets the active agents int the agent pool.
  246. /// @param[out] agents An array of agent pointers. [(#dtCrowdAgent *) * maxAgents]
  247. /// @param[in] maxAgents The size of the crowd agent array.
  248. /// @return The number of agents returned in @p agents.
  249. int getActiveAgents(dtCrowdAgent** agents, const int maxAgents);
  250. /// Updates the steering and positions of all agents.
  251. /// @param[in] dt The time, in seconds, to update the simulation. [Limit: > 0]
  252. /// @param[out] debug A debug object to load with debug information. [Opt]
  253. void update(const float dt, dtCrowdAgentDebugInfo* debug);
  254. /// Gets the filter used by the crowd.
  255. /// @return The filter used by the crowd.
  256. inline const dtQueryFilter* getFilter(const int i) const { return (i >= 0 && i < DT_CROWD_MAX_QUERY_FILTER_TYPE) ? &m_filters[i] : 0; }
  257. /// Gets the filter used by the crowd.
  258. /// @return The filter used by the crowd.
  259. inline dtQueryFilter* getEditableFilter(const int i) { return (i >= 0 && i < DT_CROWD_MAX_QUERY_FILTER_TYPE) ? &m_filters[i] : 0; }
  260. /// Gets the search halfExtents [(x, y, z)] used by the crowd for query operations.
  261. /// @return The search halfExtents used by the crowd. [(x, y, z)]
  262. const float* getQueryHalfExtents() const { return m_agentPlacementHalfExtents; }
  263. /// Same as getQueryHalfExtents. Left to maintain backwards compatibility.
  264. /// @return The search halfExtents used by the crowd. [(x, y, z)]
  265. const float* getQueryExtents() const { return m_agentPlacementHalfExtents; }
  266. /// Gets the velocity sample count.
  267. /// @return The velocity sample count.
  268. inline int getVelocitySampleCount() const { return m_velocitySampleCount; }
  269. /// Gets the crowd's proximity grid.
  270. /// @return The crowd's proximity grid.
  271. const dtProximityGrid* getGrid() const { return m_grid; }
  272. /// Gets the crowd's path request queue.
  273. /// @return The crowd's path request queue.
  274. const dtPathQueue* getPathQueue() const { return &m_pathq; }
  275. /// Gets the query object used by the crowd.
  276. const dtNavMeshQuery* getNavMeshQuery() const { return m_navquery; }
  277. private:
  278. // Explicitly disabled copy constructor and copy assignment operator.
  279. dtCrowd(const dtCrowd&);
  280. dtCrowd& operator=(const dtCrowd&);
  281. };
  282. /// Allocates a crowd object using the Detour allocator.
  283. /// @return A crowd object that is ready for initialization, or null on failure.
  284. /// @ingroup crowd
  285. dtCrowd* dtAllocCrowd();
  286. /// Frees the specified crowd object using the Detour allocator.
  287. /// @param[in] ptr A crowd object allocated using #dtAllocCrowd
  288. /// @ingroup crowd
  289. void dtFreeCrowd(dtCrowd* ptr);
  290. #endif // DETOURCROWD_H
  291. ///////////////////////////////////////////////////////////////////////////
  292. // This section contains detailed documentation for members that don't have
  293. // a source file. It reduces clutter in the main section of the header.
  294. /**
  295. @defgroup crowd Crowd
  296. Members in this module implement local steering and dynamic avoidance features.
  297. The crowd is the big beast of the navigation features. It not only handles a
  298. lot of the path management for you, but also local steering and dynamic
  299. avoidance between members of the crowd. I.e. It can keep your agents from
  300. running into each other.
  301. Main class: #dtCrowd
  302. The #dtNavMeshQuery and #dtPathCorridor classes provide perfectly good, easy
  303. to use path planning features. But in the end they only give you points that
  304. your navigation client should be moving toward. When it comes to deciding things
  305. like agent velocity and steering to avoid other agents, that is up to you to
  306. implement. Unless, of course, you decide to use #dtCrowd.
  307. Basically, you add an agent to the crowd, providing various configuration
  308. settings such as maximum speed and acceleration. You also provide a local
  309. target to more toward. The crowd manager then provides, with every update, the
  310. new agent position and velocity for the frame. The movement will be
  311. constrained to the navigation mesh, and steering will be applied to ensure
  312. agents managed by the crowd do not collide with each other.
  313. This is very powerful feature set. But it comes with limitations.
  314. The biggest limitation is that you must give control of the agent's position
  315. completely over to the crowd manager. You can update things like maximum speed
  316. and acceleration. But in order for the crowd manager to do its thing, it can't
  317. allow you to constantly be giving it overrides to position and velocity. So
  318. you give up direct control of the agent's movement. It belongs to the crowd.
  319. The second biggest limitation revolves around the fact that the crowd manager
  320. deals with local planning. So the agent's target should never be more than
  321. 256 polygons aways from its current position. If it is, you risk
  322. your agent failing to reach its target. So you may still need to do long
  323. distance planning and provide the crowd manager with intermediate targets.
  324. Other significant limitations:
  325. - All agents using the crowd manager will use the same #dtQueryFilter.
  326. - Crowd management is relatively expensive. The maximum agents under crowd
  327. management at any one time is between 20 and 30. A good place to start
  328. is a maximum of 25 agents for 0.5ms per frame.
  329. @note This is a summary list of members. Use the index or search
  330. feature to find minor members.
  331. @struct dtCrowdAgentParams
  332. @see dtCrowdAgent, dtCrowd::addAgent(), dtCrowd::updateAgentParameters()
  333. @var dtCrowdAgentParams::obstacleAvoidanceType
  334. @par
  335. #dtCrowd permits agents to use different avoidance configurations. This value
  336. is the index of the #dtObstacleAvoidanceParams within the crowd.
  337. @see dtObstacleAvoidanceParams, dtCrowd::setObstacleAvoidanceParams(),
  338. dtCrowd::getObstacleAvoidanceParams()
  339. @var dtCrowdAgentParams::collisionQueryRange
  340. @par
  341. Collision elements include other agents and navigation mesh boundaries.
  342. This value is often based on the agent radius and/or maximum speed. E.g. radius * 8
  343. @var dtCrowdAgentParams::pathOptimizationRange
  344. @par
  345. Only applicalbe if #updateFlags includes the #DT_CROWD_OPTIMIZE_VIS flag.
  346. This value is often based on the agent radius. E.g. radius * 30
  347. @see dtPathCorridor::optimizePathVisibility()
  348. @var dtCrowdAgentParams::separationWeight
  349. @par
  350. A higher value will result in agents trying to stay farther away from each other at
  351. the cost of more difficult steering in tight spaces.
  352. */