开始阅读一下recast-crowds相关知识，这个功能是避免怪物在跑动的时候，挤在一块。先从数据结构开始了解。

每个agent都认为其他的agent都会移动；

agent在接近其他agent的时候，速度会变慢，甚至能停止；

当拥挤的时候，将会先尝试自己指向最近的寻路点连线向量$\vec{a}$，是否存在碰撞；

如果有碰撞，先减速，将$\vec{a}$向量±45°做短距离移动；

源码中通过@ingroup来做分类。

1	/// @ingroup crowd

具体工程：

DetourCrowd

初步阅读

概念罗列

名词解释

里面使用了一些概念：

单词	释义	备注
bound	限制
Boundary	边界
convex	凸多边形
volume	卷，大量
avoidance	避免，逃避；废止
Segment	段，部分
Poly	多边形
Corner	角落
Topology	拓扑
purge	清理
steering	导航
corridor	走廊
segment	段

文件清单

DetourCrowd 文件

限定：

为转向决定，提供的最大的相邻对象

class dtCrowd

对外提供对于一组 dtCrowdAgent 管理的类。

成员

int m_maxAgents;// 最大代理数目
dtCrowdAgent* m_agents;// 当前持有的代理
dtCrowdAgent** m_activeAgents;// 激活的代理
dtCrowdAgentAnimation* m_agentAnims;// 代理动画

dtPathQueue m_pathq;// 寻路队列

dtObstacleAvoidanceParams m_obstacleQueryParams[DT_CROWD_MAX_OBSTAVOIDANCE_PARAMS];//阻挡寻路参数
dtObstacleAvoidanceQuery* m_obstacleQuery;//阻挡寻路

dtProximityGrid* m_grid;// 近似单元格

dtPolyRef* m_pathResult;// 寻路面片集合
int m_maxPathResult;// 最大面片数目

float m_agentPlacementHalfExtents[3];

dtQueryFilter m_filters[DT_CROWD_MAX_QUERY_FILTER_TYPE];// 查询过滤器

float m_maxAgentRadius;// 最大的代理对象的半径

int m_velocitySampleCount;// 速度样本数

dtNavMeshQuery* m_navquery;// 导航寻路对象

私有函数：

// 更新拓扑优化
void updateTopologyOptimization(dtCrowdAgent** agents, const int nagents, const float dt);
// 更新移动请求
void updateMoveRequest(const float dt);
// 检查路径的有效性
void checkPathValidity(dtCrowdAgent** agents, const int nagents, const float dt);
// 获取代理的index
inline int getAgentIndex(const dtCrowdAgent* agent) const  { return (int)(agent - m_agents); }
// 请求重新设定移动目标位置
bool requestMoveTargetReplan(const int idx, dtPolyRef ref, const float* pos);
// 清理
void purge();

公用函数：

1
2
3

// 初始化crowd对象，新建一批agent，设置agent的半径，设置寻路对象；
bool init(const int maxAgents, const float maxAgentRadius, dtNavMesh* nav);

struct dtCrowdAgent

被 dtCrowd 管理的单个 agent 对象


/// True if the agent is active, false if the agent is in an unused slot in the agent pool.
bool active;

/// The type of mesh polygon the agent is traversing. (See: #CrowdAgentState)
unsigned char state;

/// True if the agent has valid path (targetState == DT_CROWDAGENT_TARGET_VALID) and the path does not lead to the requested position, else false.
bool partial;

/// The path corridor the agent is using.
dtPathCorridor corridor;

/// The local boundary data for the agent.
dtLocalBoundary boundary;

/// Time since the agent's path corridor was optimized.
float topologyOptTime;

/// The known neighbors of the agent.
dtCrowdNeighbour neis[DT_CROWDAGENT_MAX_NEIGHBOURS];

/// The number of neighbors.
int nneis;

/// The desired speed.
float desiredSpeed;

float npos[3];    ///< The current agent position. [(x, y, z)]
float disp[3];    ///< A temporary value used to accumulate agent displacement during iterative collision resolution. [(x, y, z)]
float dvel[3];    ///< The desired velocity of the agent. Based on the current path, calculated from scratch each frame. [(x, y, z)]
float nvel[3];    ///< The desired velocity adjusted by obstacle avoidance, calculated from scratch each frame. [(x, y, z)]
float vel[3];    ///< The actual velocity of the agent. The change from nvel -> vel is constrained by max acceleration. [(x, y, z)]

/// The agent's configuration parameters.
dtCrowdAgentParams params;

/// The local path corridor corners for the agent. (Staight path.) [(x, y, z) * #ncorners]
float cornerVerts[DT_CROWDAGENT_MAX_CORNERS*3];

/// The local path corridor corner flags. (See: #dtStraightPathFlags) [(flags) * #ncorners]
unsigned char cornerFlags[DT_CROWDAGENT_MAX_CORNERS];

/// The reference id of the polygon being entered at the corner. [(polyRef) * #ncorners]
dtPolyRef cornerPolys[DT_CROWDAGENT_MAX_CORNERS];

/// The number of corners.
int ncorners;

unsigned char targetState;      ///< State of the movement request.
// enum MoveRequestState
// {
//  DT_CROWDAGENT_TARGET_NONE = 0,
//  DT_CROWDAGENT_TARGET_FAILED,
//  DT_CROWDAGENT_TARGET_VALID,
//  DT_CROWDAGENT_TARGET_REQUESTING,
//  DT_CROWDAGENT_TARGET_WAITING_FOR_QUEUE,
//  DT_CROWDAGENT_TARGET_WAITING_FOR_PATH,
//  DT_CROWDAGENT_TARGET_VELOCITY,
//};
dtPolyRef targetRef;        ///< Target polyref of the movement request.
float targetPos[3];          ///< Target position of the movement request (or velocity in case of DT_CROWDAGENT_TARGET_VELOCITY).
dtPathQueueRef targetPathqRef;    ///< Path finder ref.
bool targetReplan;          ///< Flag indicating that the current path is being replanned.
float targetReplanTime;        /// <Time since the agent's target was replanned.

struct dtCrowdAgentParams

dtCrowdAgent 的配置参数。

/// Configuration parameters for a crowd agent.
/// @ingroup crowd
struct dtCrowdAgentParams
{
  float radius;            ///< Agent radius. [Limit: >= 0]
  float height;            ///< Agent height. [Limit: > 0]
  float maxAcceleration;        ///< Maximum allowed acceleration. [Limit: >= 0]
  float maxSpeed;            ///< Maximum allowed speed. [Limit: >= 0]

  /// Defines how close a collision element must be before it is considered for steering behaviors. [Limits: > 0]
  float collisionQueryRange;

  float pathOptimizationRange;    ///< The path visibility optimization range. [Limit: > 0]

  /// How aggresive the agent manager should be at avoiding collisions with this agent. [Limit: >= 0]
  float separationWeight;

  /// Flags that impact steering behavior. (See: #UpdateFlags)
  unsigned char updateFlags;

  /// The index of the avoidance configuration to use for the agent. 
  /// [Limits: 0 <= value <= #DT_CROWD_MAX_OBSTAVOIDANCE_PARAMS]
  unsigned char obstacleAvoidanceType;  

  /// The index of the query filter used by this agent.
  unsigned char queryFilterType;

  /// User defined data attached to the agent.
  void* userData;
};

struct dtCrowdNeighbour

提供 neighbor 数据给 agents 管理。

idx neighor 在 crowd 的index编号。
dist agent neighbor 的距离。

enum CrowdAgentState

/// The type of navigation mesh polygon the agent is currently traversing.
/// @ingroup crowd
enum CrowdAgentState
{
DT_CROWDAGENT_STATE_INVALID, ///< The agent is not in a valid state.
DT_CROWDAGENT_STATE_WALKING, ///< The agent is traversing a normal navigation mesh polygon.
DT_CROWDAGENT_STATE_OFFMESH, ///< The agent is traversing an off-mesh connection.
};

enum MoveRequestState

enum MoveRequestState
{
DT_CROWDAGENT_TARGET_NONE = 0,
DT_CROWDAGENT_TARGET_FAILED,
DT_CROWDAGENT_TARGET_VALID,
DT_CROWDAGENT_TARGET_REQUESTING,
DT_CROWDAGENT_TARGET_WAITING_FOR_QUEUE,
DT_CROWDAGENT_TARGET_WAITING_FOR_PATH,
DT_CROWDAGENT_TARGET_VELOCITY,
};

DetourLocalBoundary 文件

DetourObstacleAvoidance 文件

struct dtObstacleAvoidanceParams

成员：

float velBias;// 运动偏向
float weightDesVel;// 
float weightCurVel;
float weightSide;
float weightToi;// 
float horizTime;// 水平时间
unsigned char gridSize;  ///< grid
unsigned char adaptiveDivs;  ///< adaptive
unsigned char adaptiveRings;  ///< adaptive
unsigned char adaptiveDepth;  ///< adaptive

DetourPathCorridor 文件

DetourPathQueue 文件

class dtPathQueue

寻路队列；

struct PathQuery

DetourProximityGrid 文件

主流程梳理

dwCrowd::update

细读update函数：

// 每一帧都在调用的函数。
void dtCrowd::update(const float dt, dtCrowdAgentDebugInfo* debug)

  // 先将本组全部的 agent 获取出来。
  int dtCrowd::getActiveAgents(dtCrowdAgent** agents, const int maxAgents){...}

  // 检查全部的 agent 还有合法的寻路路点；
  void dtCrowd::checkPathValidity(dtCrowdAgent** agents, const int nagents, const float dt){...}

  // 更新同步移动请求和寻路对象
  void dtCrowd::updateMoveRequest(const float ){...}

  // 优化拓扑
  void dtCrowd::updateTopologyOptimization(dtCrowdAgent** agents, const int nagents, const float dt){...}
  
  // 将agents注册到 proximity grid 
  // 其实就是获取当前的agent对象的pos，radius，计算一个正方形，添加到 proximity grid 中。
  // 可以理解成栅格化；
    dtProximityGrid::addItem
  
  // 获取全部 agent 靠近的 navmesh segments，其实也会将 agent 的 neighbours 都重新生成
  // Get nearby navmesh segments and agents to collide with.
    // 检查 agent 状态需要是 DT_CROWDAGENT_STATE_WALKING
    if (ag->state != DT_CROWDAGENT_STATE_WALKING)
    // 当 agent collision boundary 无效了或者确定距离通过了，将更新 collision boundary。
    // 先计算一个标准量，读取 agent collisionQueryRange
    const float updateThr = ag->params.collisionQueryRange*0.25f;
    // 计算自己位置是否超出了 boundary 的区间
    dtVdist2DSqr(ag->npos, ag->boundary.getCenter()) > dtSqr(updateThr)
    // 检查 boundary 是否还合法
    !ag->boundary.isValid(m_navquery, &m_filters[ag->params.queryFilterType])
      // 检测 Boundary 是否合法
      bool dtLocalBoundary::isValid(dtNavMeshQuery* navquery, const dtQueryFilter* filter)
      // 更新 boundary.update
      ag->boundary.update
    // 获取 agent 的 neighbour agents
    static int getNeighbours()
      // 从 dtProximityGrid::queryItems()
      // 通过近似格子获取附近的agents对象。
      // 循环全部的附近 agent
      // 检查高度是否相差太大
      // 检查距离是否太远
      // static int addNeighbour()
      // 写入 agent.neis 数组中
  // 循环全部的 agent 可以到 corner
  // Find next corner to steer to.
    // 检查 agent.state 是否 DT_CROWDAGENT_STATE_WALKING
    // 检查 agent.targetState 为 DT_CROWDAGENT_TARGET_NONE DT_CROWDAGENT_TARGET_VELOCITY

    // int dtPathCorridor::findCorners
    // 类似 dtNavMeshQuery::findStraightPath 函数
    int findCorners(float* cornerVerts, unsigned char* cornerFlags, dtPolyRef* cornerPolys, const int maxCorners, dtNavMeshQuery* navquery, const dtQueryFilter* filter)
    // 最多收集4步

  // 根据配置，检查是否开启了优化，将会直接将下一个 corner 裁剪掉。
  // Find next corner to steer to.
    void optimizePathVisibility(const float* next, const float pathOptimizationRange, dtNavMeshQuery* navquery, const dtQueryFilter* filter)

    // 后续将会为输出日志，拷贝一些数据。
    // 将导航路径开始位置，结束位置写入debug对象中。
  
  // 循环全部的 agent 触发跳跃点连接，直接将 mesh 连接到一块。
  // Trigger off-mesh connections (depends on corners).
    // 触发器的 2.25f 范围
    bool overOffmeshConnection(const dtCrowdAgent* ag, const float radius)
      // 跳跃点

  // 计算转向
  // Calculate steering.
    // 如果无需转向就全速前进
    if (ag->targetState == DT_CROWDAGENT_TARGET_VELOCITY)
    // 否则
      // 检查是否开启了 Anticipate Turns ，预判转弯
        // 进行更加圆滑的转弯
        void calcSmoothSteerDirection(const dtCrowdAgent* ag, float* dir)
      // 否则
        // 直接转弯
        void calcStraightSteerDirection(const dtCrowdAgent* ag, float* dir)
      // 如果快到终点（2倍于自己的半径）的时候，将会让 agent 减速；

  // 计算速度
  // Velocity planning.	

  // 循环全部的 agent 计算转向。

总结

多阅读别人的代码，学会如何程序如何去做框架。

Abel'Blog

RecastCrowd