DFS(node, goal):
if node is goal:
    return path to node
mark node as visited

for each neighbor in neighbors(node):
    if neighbor is not visited:
        path = DFS(neighbor, goal)
        if path is not None:
            return path
return None

BFS(start, goal):
create a queue Q
enqueue start onto Q
mark start as visited

while Q is not empty:
    node = dequeue Q
    if node is goal:
        return path to node
    for each neighbor in neighbors(node):
        if neighbor is not visited:
            mark neighbor as visited
            enqueue neighbor onto Q
return None

Dijkstra(graph, start, goal):
    create a priority queue Q
    for each node in graph:
        dist[node] = infinity
        previous[node] = undefined
    dist[start] = 0
    Q.insert(start, dist[start])

    while Q is not empty:
        node = Q.extract_min()
        if node is goal:
            return reconstruct_path(previous, goal)
        for each neighbor in neighbors(node):
            alt = dist[node] + cost(node, neighbor)
            if alt < dist[neighbor]:
                dist[neighbor] = alt
                previous[neighbor] = node
                Q.decrease_key(neighbor, alt)
    return None

reconstruct_path(previous, goal):
    path = []
    while goal is not undefined:
        path.prepend(goal)
        goal = previous[goal]
    return path

FloydWarshall(graph):
n = number of nodes in graph
dist = array[n][n]

for i from 1 to n:
    for j from 1 to n:
        if i == j:
            dist[i][j] = 0
        else if (i, j) in graph:
            dist[i][j] = weight of edge (i, j)
        else:
            dist[i][j] = infinity

for k from 1 to n:
    for i from 1 to n:
        for j from 1 to n:
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
return dist

BellmanFord(graph, source):
    n = number of nodes in graph
    dist = array[n]
    parent = array[n]
    ## Step 1: Initialize distances from source to all other nodes as infinity
    for i from 1 to n:
        dist[i] = infinity
        parent[i] = undefined
    dist[source] = 0

    ## Step 2: Relax all edges |V| - 1 times
    for i from 1 to n-1:
        for each edge (u, v) in graph:
            if dist[u] + weight(u, v) < dist[v]:
                dist[v] = dist[u] + weight(u, v)
                parent[v] = u

    ## Step 3: Check for negative-weight cycles
    for each edge (u, v) in graph:
        if dist[u] + weight(u, v) < dist[v]:
            print("Graph contains a negative-weight cycle")
            return None
    return dist, parent

reconstruct_path(parent, target):
    path = []
    while target is not undefined:
        path.append(target)
        target = parent[target]
    path.reverse()
    return path

SPFA(graph, source):
n = number of nodes in graph
dist = array[n]
inQueue = array[n]

for i from 1 to n:
    dist[i] = infinity
    inQueue[i] = false
dist[source] = 0
queue = [source]
inQueue[source] = true

while queue is not empty:
    u = queue.pop(0)
    inQueue[u] = false
    for each neighbor v of u:
        if dist[u] + weight(u, v) < dist[v]:
            dist[v] = dist[u] + weight(u, v)
            if not inQueue[v]:
                queue.append(v)
                inQueue[v] = true
return dist

GreedyBestFirstSearch(start, goal, heuristic):
create a priority queue Q
Q.insert(start, heuristic(start, goal))
mark start as visited

while Q is not empty:
    node = Q.extract_min()
    if node is goal:
        return path to node
    for each neighbor in neighbors(node):
        if neighbor is not visited:
            mark neighbor as visited
            Q.insert(neighbor, heuristic(neighbor, goal))
return None

AStar(graph, start, goal, heuristic):
    create an open set (priority queue) Q
    create a closed set
    g_score = {node: infinity for node in graph}
    f_score = {node: infinity for node in graph}
    g_score[start] = 0
    f_score[start] = heuristic(start, goal)
    Q.insert(start, f_score[start])

    while Q is not empty:
        current = Q.extract_min()
        if current is goal:
            return reconstruct_path(came_from, current)
        closed_set.add(current)
        for neighbor in neighbors(current):
            if neighbor in closed_set:
                continue
            tentative_g_score = g_score[current] + cost(current, neighbor)
            if tentative_g_score < g_score[neighbor]:
                came_from[neighbor] = current
                g_score[neighbor] = tentative_g_score
                f_score[neighbor] = g_score[neighbor] + heuristic(neighbor, goal)
                if neighbor not in Q:
                    Q.insert(neighbor, f_score[neighbor])
    return None

reconstruct_path(came_from, current):
    path = []
    while current in came_from:
        path.append(current)
        current = came_from[current]
    path.reverse()
    return path

JPS(start, goal, grid):
   openSet = priority queue
   closedSet = set
   gScore = dictionary with default value infinity
   fScore = dictionary with default value infinity
   parent = dictionary
   gScore[start] = 0
   fScore[start] = heuristic(start, goal)
   openSet.insert(start, fScore[start])

   while openSet is not empty:
       current = openSet.extract_min()
       if current == goal:
           return reconstruct_path(parent, current)
       closedSet.add(current)
       for neighbor in jump_neighbors(current, goal, grid):
           if neighbor in closedSet:
               continue
           tentative_gScore = gScore[current] + distance(current, neighbor)
           if tentative_gScore < gScore[neighbor]:
               gScore[neighbor] = tentative_gScore
               parent[neighbor] = current
               fScore[neighbor] = gScore[neighbor] + heuristic(neighbor, goal)
               if neighbor not in openSet:
                   openSet.insert(neighbor, fScore[neighbor])
   return None

jump_neighbors(current, goal, grid):
   neighbors = []
   for direction in possible_directions:
       jumpPoint = jump(current, direction, goal, grid)
       if jumpPoint is not None:
           neighbors.append(jumpPoint)
   return neighbors

jump(current, direction, goal, grid):
   next = current + direction
   if not in_bounds(next, grid) or is_obstacle(next, grid):
       return None
   if next == goal:
       return next
   if forced_neighbors(next, direction, grid):
       return next
   if direction is diagonal:
       if jump(next, (direction[0], 0), goal, grid) is not None or \\
          jump(next, (0, direction[1]), goal, grid) is not None:
           return next
   return jump(next, direction, goal, grid)

forced_neighbors(node, direction, grid):
   ## Implement detection of forced neighbors
   return True or False

reconstruct_path(parent, current):
   path = []
   while current in parent:
       path.append(current)
       current = parent[current]
   path.reverse()
   return path

JPSPlus(start, goal, grid):
   preprocessed_grid = preprocess_grid(grid)
   openSet = priority queue
   closedSet = set
   gScore = dictionary with default value infinity
   fScore = dictionary with default value infinity
   parent = dictionary
   gScore[start] = 0
   fScore[start] = heuristic(start, goal)
   openSet.insert(start, fScore[start])

   while openSet is not empty:
       current = openSet.extract_min()
       if current == goal:
           return reconstruct_path(parent, current)
       closedSet.add(current)
       for neighbor in jump_neighbors_plus(current, goal, preprocessed_grid):
           if neighbor in closedSet:
               continue
           tentative_gScore = gScore[current] + distance(current, neighbor)
           if tentative_gScore < gScore[neighbor]:
               gScore[neighbor] = tentative_gScore
               parent[neighbor] = current
               fScore[neighbor] = gScore[neighbor] + heuristic(neighbor, goal)
               if neighbor not in openSet:
                   openSet.insert(neighbor, fScore[neighbor])
   return None

preprocess_grid(grid):
   ## Implement preprocessing to compute jump points
   return preprocessed_grid

jump_neighbors_plus(current, goal, preprocessed_grid):
   ## Use precomputed jump points from preprocessed_grid
   neighbors = preprocessed_grid[current]
   return neighbors

reconstruct_path(parent, current):
   path = []
   while current in parent:
       path.append(current)
       current = parent[current]
   path.reverse()
   return path

BStar(graph, start, goal, heuristic):
    openSet = priority queue
    closedSet = set
    gScore = dictionary with default value infinity
    fScore = dictionary with default value infinity
    bScore = dictionary with default value 0
    parent = dictionary
    gScore[start] = 0
    fScore[start] = heuristic(start, goal) + bScore[start]
    openSet.insert(start, fScore[start])
    while openSet is not empty:
        current = openSet.extract_min()
        if current == goal:
            return reconstruct_path(parent, current)
        closedSet.add(current)
        for neighbor in neighbors(current, graph):
            if neighbor in closedSet:
                continue
            tentative_gScore = gScore[current] + distance(current, neighbor)
            tentativeFScore = tentative_gScore + heuristic(neighbor, goal) + bScore[neighbor]
            if tentative_gScore < gScore[neighbor]:
                gScore[neighbor] = tentative_gScore
                fScore[neighbor] = tentativeFScore
                parent[neighbor] = current
                if neighbor not in openSet:
                    openSet.insert(neighbor, fScore[neighbor])
                else:
                    openSet.update(neighbor, fScore[neighbor])
        ## Update the boundary function b(n)
        update_bScore(bScore, current, graph)
    return None

def update_bScore(bScore, current, graph):
    ## Implement the logic to update bScore based on current node and graph
    pass

def reconstruct_path(parent, current):
    path = []
    while current in parent:
        path.append(current)
        current = parent[current]
    path.reverse()
    return path

ThetaStar(graph, start, goal, heuristic):
   openSet = priority queue
   closedSet = set
   gScore = dictionary with default value infinity
   fScore = dictionary with default value infinity
   parent = dictionary
   gScore[start] = 0
   fScore[start] = heuristic(start, goal)
   openSet.insert(start, fScore[start])
   while openSet is not empty:
       current = openSet.extract_min()
       if current == goal:
           return reconstruct_path(parent, current)
       closedSet.add(current)
       for neighbor in neighbors(current):
           if neighbor in closedSet:
               continue
           tentative_gScore = gScore[current] + distance(current, neighbor)
           if has_line_of_sight(parent[current], neighbor):
               new_gScore = gScore[parent[current]] + distance(parent[current], neighbor)
               if new_gScore < gScore[neighbor]:
                   gScore[neighbor] = new_gScore
                   parent[neighbor] = parent[current]
                   fScore[neighbor] = gScore[neighbor] + heuristic(neighbor, goal)
                   if neighbor not in openSet:
                       openSet.insert(neighbor, fScore[neighbor])
           else:
               if tentative_gScore < gScore[neighbor]:
                   gScore[neighbor] = tentative_gScore
                   parent[neighbor] = current
                   fScore[neighbor] = gScore[neighbor] + heuristic(neighbor, goal)
                   if neighbor not in openSet:
                       openSet.insert(neighbor, fScore[neighbor])
   return None

reconstruct_path(parent, current):
   path = []
   while current in parent:
       path.append(current)
       current = parent[current]
   path.reverse()
   return path

has_line_of_sight(node1, node2):
   ## Implement line-of-sight check
   return True or False

根据输入几何边界确定栅格体素格网的大小。
rcCalcGridSize

对输入几何体素化
rcAllocHeightfield
rcCreateHeightfield rcCreateHeight字段
rcMarkWalkableTriangles
rcRasterizeTriangles

清理体素数据并过滤掉不适合步行的区域。
rcFilterLowHangingWalkableObstacles
rcFilterLedgeSpans
rcFilterWalkableLowHeightSpans

将体素数据合并为更紧凑的表示形式
rcAllocCompactHeightfield
rcAllocCompactHeight字段
rcBuildCompactHeightfield
rcBuildCompactHeight字段

进一步优化体素表示
rcErodeWalkableArea
rcBuildDistanceField
rcBuildRegions rcBuild区域

根据体素数据对导航网格面进行三角测量
rcAllocContourSet
rcBuildContours
rcAllocPolyMesh
rcBuildPolyMesh

使用在运行时有用的其他元数据打包网格。
rcAllocPolyMeshDetail
rcBuildPolyMeshDetail

rcFreeHeightField
rcFreeCompactHeightfield rcFreeCompactHeight字段
rcFreeContourSet

* 在recastdemo右侧栏目中，有着控制各个阶段的参数信息

struct rcConfig
{
    int width; // 场景中x向的cell个数
    int height; // 场景中z向的cell个数
    int tileSize; // tile正方形的边长
    int borderSize; // 指定距离四周边界多远的区域不用生成导航数据，缩小需要生成的区域
    float cs; // cell size
    float ch; // cell height
    float bmin[3]; // 场景包围盒坐标
    float bmax[3]; // 场景包围盒坐标
    float walkableSlopeAngle; // 最大可行走坡度
    int walkableHeight; // 最小可行走通过的高度
    int walkableClimb; // 最大的可攀爬高度
    int walkableRadius; // agent的半径
    int maxEdgeLen; // 最终导航网格中多边形周长的最大值，限定多边形的大小
    float maxSimplificationError; // 最终导航网格中多边形周长的最大值，限定多边形的大小    
    int minRegionArea; // 独立岛屿region的最小cell数目
    int mergeRegionArea; // span数目小于此值的region都将被合并
    int maxVertsPerPoly; // 多边形的最多顶点数目
};

const float* verts;///输入的顶点集合
const int* tris;///输入的三角形集合
int ntris;///输入的三角形个数

///三角形在xz平面投影的包围盒
struct BoundsItem
{
    float bmin[2];
    float bmax[2];
    int i;///由于会对包围盒按坐标排序，id记录了这个包围盒对应的输入三角形的id
};

///BVH的节点
struct rcChunkyTriMeshNode
{
    float bmin[2];///包含区域内所有三角形的包围盒
    float bmax[2];
    int i;///i为正表示是叶子节点；i为负表示是非叶子节点，大小等于在数组内的覆盖范围
    int n;///节点内包含的三角形个数
};

///一棵BVH树
struct rcChunkyTriMesh
{
    rcChunkyTriMeshNode* nodes;///根节点
    int nnodes;///节点个数
    int* tris;///按区域划分排序后的三角形集合
    int ntris;///三角形个数
    int maxTrisPerChunk;///叶子节点最多包含的三角形数
}

void rcMarkWalkableTriangles(rcContext* ctx, const float walkableSlopeAngle,
                             const float* verts, int nv,
                             const int* tris, int nt,
                             unsigned char* areas)
{
    rcIgnoreUnused(ctx);
    rcIgnoreUnused(nv);
    const float walkableThr = cosf(walkableSlopeAngle/180.0f*RC_PI);
    float norm[3];
    for (int i = 0; i < nt; ++i)
    {
        const int* tri = &tris[i*3];
        calcTriNormal(&verts[tri[0]*3], &verts[tri[1]*3], &verts[tri[2]*3], norm);
        // Check if the face is walkable.
        if (norm[1] > walkableThr)
            areas[i] = RC_WALKABLE_AREA;
    }
}

struct rcSpan
{
    unsigned int smin : RC_SPAN_HEIGHT_BITS; ///< The lower limit of the span. [Limit: < #smax]
    unsigned int smax : RC_SPAN_HEIGHT_BITS; ///< The upper limit of the span. [Limit: <= #RC_SPAN_MAX_HEIGHT]
    unsigned int area : 6;                   ///< The area id assigned to the span.
    rcSpan* next;                            ///< The next span higher up in column.
};

struct rcHeightfield
{
    rcHeightfield();
    ~rcHeightfield();

    int width;          ///< The width of the heightfield. (Along the x-axis in cell units.)
    int height;         ///< The height of the heightfield. (Along the z-axis in cell units.)
    float bmin[3];      ///< The minimum bounds in world space. [(x, y, z)]
    float bmax[3];      ///< The maximum bounds in world space. [(x, y, z)]
    float cs;           ///< The size of each cell. (On the xz-plane.)
    float ch;           ///< The height of each cell. (The minimum increment along the y-axis.)
    rcSpan** spans;     ///< Heightfield of spans (width*height).
    rcSpanPool* pools;  ///< Linked list of span pools.
    rcSpan* freelist;   ///< The next free span.

private:
    // Explicitly-disabled copy constructor and copy assignment operator.
    rcHeightfield(const rcHeightfield&);
    rcHeightfield& operator=(const rcHeightfield&);
};

/// Represents a span of unobstructed space within a compact heightfield.
struct rcCompactSpan
{
    unsigned short y;            ///< The lower extent of the span. (Measured from the heightfield's base.)
    unsigned short reg;            ///< The id of the region the span belongs to. (Or zero if not in a region.)
    unsigned int con : 24;        ///< Packed neighbor connection data.    与 Neighbor Span 的连通性，这里 24bit，每 6 bit 一个方向（）
    unsigned int h : 8;            ///< The height of the span.  (Measured from #y.)
};

/// A compact, static heightfield representing unobstructed space.
/// @ingroup recast
struct rcCompactHeightfield
{
    // some define 
    float bmin[3];                ///< The minimum bounds in world space. [(x, y, z)]
    float bmax[3];                ///< The maximum bounds in world space. [(x, y, z)]
    float cs;                    ///< The size of each cell. (On the xz-plane.)
    float ch;                    ///< The height of each cell. (The minimum increment along the y-axis.)
    rcCompactCell* cells;        ///< Array of cells. [Size: #width*#height]                          Cell 的合集，这里采用一维数组表示
    rcCompactSpan* spans;        ///< Array of spans. [Size: #spanCount]                                 所有数组的合集，这里采用一维数组表示
    unsigned short* dist;        ///< Array containing border distance data. [Size: #spanCount]       记录距离场
    unsigned char* areas;        ///< Array containing area id data. [Size: #spanCount]               记录区域是否可行走，或者草地山地等情况
};

/// Provides information on the content of a cell column in a compact heightfield. 
struct rcCompactCell
{
    unsigned int index : 24;    ///< Index to the first span in the column. XZ 平面下的坐标，参考右图                     
    unsigned int count : 8;        ///< Number of spans in the column. 8 位，理论上不会超过 256 个 Span                          
};

// 一条轮廓线段
struct rcContour
{
    int* verts;            //简化后轮廓顶点数组
    int nverts;        //简化后顶点数目
    int* rverts;        //原始顶点数组
    int nrverts;        //原始顶点数目
    unsigned short reg;    //拾取轮廓的起始CompactSpan对应Region
    unsigned char area;//拾取轮廓的起始CompactSpan对应area
};

struct rcContourSet
{
    rcContour* conts;    //轮廓数组
    int nconts;        //轮廓数组
    float maxError;    //简化时的最大距离
};

struct rcPolyMesh
{
    unsigned short* verts;    // 所有的多边形顶点信息
        int nvp;        // 一个多边形中的最多顶点个数
    unsigned short* regs;    // 每个多边形对应的region id
    unsigned char* areas;    // 每个多边形对应的area
    int nverts;        // 顶点总数
    int npolys;        // 多边形总数
    int maxpolys;        // 耳割后的初始的三角形个数
    unsigned short* polys;    // 多边形顶点index及邻居多边形index. [Length: #maxpolys * 2 * #nvp]
};

struct dtMeshTile
{
    unsigned int salt;            // 标记当前Tile是否有变更
    dtMeshHeader* header;            // 继续Tile的整体信息
    dtPoly* polys;                // 所有的多边形信息
    float* verts;                // 所有的顶点信息
    dtLink* links;                // 多边形间的连接信息数组，每个多边形对应一个dtLink*，dtLink*是一个单向链表，存储了该多边形的所有连接信息
    dtPolyDetail* detailMeshes;        // 细节网格数据
    float* detailVerts;                    // 细节网格顶点
    unsigned char* detailTris;            // 细节网格三角形
    dtBVNode* bvTree;                       // 多边形对应的BV树
    dtMeshTile* next;                // 下一个tile
};

struct dtPoly
{
    unsigned int firstLink;
    unsigned short verts[DT_VERTS_PER_POLYGON]; //多边形节点索引 从dtMeshTile::verts中取元素
    unsigned short neis[DT_VERTS_PER_POLYGON]; //每条边对应的邻居
    unsigned short flags; // 用户定义标记，不同类型flag对应不同的寻路成本
    unsigned char vertCount; // 多边形数量
    unsigned char areaAndtype; // 对应type和area 高2bit表示type 低6bit表示area
};

* dtBVNode：叶子节点的i表示poly id,而非叶子节点则表示右边子节点的跨度。

struct dtBVNode
{
    unsigned short bmin[3];            // 该节点包含的多边形的AABB包围盒下边界
    unsigned short bmax[3];            // 该节点包含的多边形的AABB包围盒上边界
    int i;                    // 表示Poly id或者右边子节点的跨度
};

struct dtNode
{
    float pos[3];                                ///< Position of the node.
    float cost;                                    ///< Cost from previous node to current node.
    float total;                                ///< Cost up to the node.
    unsigned int pidx : DT_NODE_PARENT_BITS;    ///< Index to parent node.
    unsigned int state : DT_NODE_STATE_BITS;    ///< extra state information. A polyRef can have multiple nodes with different extra info. see DT_MAX_STATES_PER_NODE
    unsigned int flags : 3;                        ///< Node flags. A combination of dtNodeFlags.
    dtPolyRef id;                                ///< Polygon ref the node corresponds to.
};

//TempObstacles的大致运作流程
Preprocess
for each tile
- rasterize static triangles
- find walkable cells
- mark areas
- store compressed heighfield

At Run Time
for a changed tile
- uncompressed heighfield
- mark obstacles
- build regions
- build contours
- build poly mesh
- build detail mesh
- store navmesh

// 创建 DetourCrowd 对象
dtCrowd* crowd = dtAllocCrowd();
// 初始化 DetourCrowd
crowd->init(maxAgents, maxAgentRadius, navMesh);
// 配置代理参数
dtCrowdAgentParams ap;
memset(&ap, 0, sizeof(ap));
ap.radius = agentRadius;
ap.height = agentHeight;
ap.maxAcceleration = maxAcceleration;
ap.maxSpeed = maxSpeed;
// 添加代理到 DetourCrowd
int agentId = crowd->addAgent(startPosition, &ap);
// 设置代理目标
crowd->requestMoveTarget(agentId, targetPosition);
// 在每帧更新代理位置和速度
crowd->update(deltaTime, nullptr);