1
#include <vector>
2
#include <queue>
3
#include <limits>
4

5
// Dijkstra —— 求从 start 到所有节点的最短距离
6
// graph[u] = {{v1, w1}, {v2, w2}, ...}  邻接表
7
std::vector<int> dijkstra(
8
    const std::vector<std::vector<std::pair<int,int>>>& graph, int start)
9
{
10
    int n = graph.size();
11
    std::vector<int> dist(n, std::numeric_limits<int>::max());
12
    // 最小堆: {距离, 节点}
13
    std::priority_queue<std::pair<int,int>,
14
                        std::vector<std::pair<int,int>>,
15
                        std::greater<>> pq;
16

17
    dist[start] = 0;
18
    pq.push({0, start});
19

20
    while (!pq.empty()) {
21
        auto [d, u] = pq.top();
22
        pq.pop();
23

24
        // 关键优化: 如果当前距离已经过时, 跳过
25
        if (d > dist[u]) continue;
26

27
        for (auto [v, w] : graph[u]) {
28
            int new_dist = dist[u] + w;
29
            if (new_dist < dist[v]) {
30
                dist[v] = new_dist;
31
                pq.push({new_dist, v});
32
            }
33
        }
34
    }
35

36
    return dist;  // dist[i] = 起点到 i 的最短距离, INT_MAX = 不可达
37
}

1
图:
2
    S ---4--- A
3
    |         |
4
    2         1
5
    |         |
6
    B ---3--- C ---2--- D
7
    |                   |
8
    1                   5
9
    |                   |
10
    E --------7-------- F
11

12
dist 表变化 (起点 S):
13

14
初始: [S=0, A=∞, B=∞, C=∞, D=∞, E=∞, F=∞]
15

16
取出 S(0): 松弛 A→4, B→2
17
       [S=0, A=4, B=2, C=∞, D=∞, E=∞, F=∞]
18

19
取出 B(2): 松弛 C→5, E→3
20
       [S=0, A=4, B=2, C=5, D=∞, E=3, F=∞]
21

22
取出 E(3): 松弛 F→10
23
       [S=0, A=4, B=2, C=5, D=∞, E=3, F=10]
24

25
取出 A(4): 松弛 C→5(不更新, 5≤5)
26
       [S=0, A=4, B=2, C=5, D=∞, E=3, F=10]
27

28
取出 C(5): 松弛 D→7
29
       [S=0, A=4, B=2, C=5, D=7, E=3, F=10]
30

31
取出 D(7): 松弛 F→12(不更新, 10≤12)
32
       [S=0, A=4, B=2, C=5, D=7, E=3, F=10]
33

34
取出 F(10): 无更新
35
       最终: [S=0, A=4, B=2, C=5, D=7, E=3, F=10]  ✅

1
// Dijkstra 带路径恢复
2
std::pair<std::vector<int>, std::vector<int>> dijkstra_with_path(
3
    const std::vector<std::vector<std::pair<int,int>>>& graph, int start)
4
{
5
    int n = graph.size();
6
    std::vector<int> dist(n, std::numeric_limits<int>::max());
7
    std::vector<int> prev(n, -1);  // 前驱节点
8
    std::priority_queue<std::pair<int,int>,
9
                        std::vector<std::pair<int,int>>,
10
                        std::greater<>> pq;
11

12
    dist[start] = 0;
13
    pq.push({0, start});
14

15
    while (!pq.empty()) {
16
        auto [d, u] = pq.top();
17
        pq.pop();
18

19
        if (d > dist[u]) continue;
20

21
        for (auto [v, w] : graph[u]) {
22
            int new_dist = dist[u] + w;
23
            if (new_dist < dist[v]) {
24
                dist[v] = new_dist;
25
                prev[v] = u;  // 记录: v 的最短路来自 u
26
                pq.push({new_dist, v});
27
            }
28
        }
29
    }
30

31
    return {dist, prev};
32
}
33

34
// 从 prev 数组恢复路径
35
std::vector<int> reconstruct_path(const std::vector<int>& prev, int target) {
36
    std::vector<int> path;
37
    for (int v = target; v != -1; v = prev[v]) {
38
        path.push_back(v);
39
    }
40
    std::reverse(path.begin(), path.end());
41
    return path;
42
}

1
#include <vector>
2
#include <limits>
3

4
struct Edge {
5
    int from, to, weight;
6
};
7

8
// Bellman-Ford —— 支持负权边, 可检测负环
9
// 返回 {dist 数组, 是否存在负环}
10
std::pair<std::vector<int>, bool> bellman_ford(
11
    int n, const std::vector<Edge>& edges, int start)
12
{
13
    std::vector<int> dist(n, std::numeric_limits<int>::max());
14
    dist[start] = 0;
15

16
    // V-1 轮松弛
17
    for (int i = 0; i < n - 1; ++i) {
18
        bool updated = false;
19
        for (const auto& [u, v, w] : edges) {
20
            if (dist[u] != std::numeric_limits<int>::max()
21
                && dist[u] + w < dist[v])
22
            {
23
                dist[v] = dist[u] + w;
24
                updated = true;
25
            }
26
        }
27
        // 优化: 如果本轮没有更新, 提前终止
28
        if (!updated) break;
29
    }
30

31
    // 第 V 轮: 检测负环
32
    bool has_negative_cycle = false;
33
    for (const auto& [u, v, w] : edges) {
34
        if (dist[u] != std::numeric_limits<int>::max()
35
            && dist[u] + w < dist[v])
36
        {
37
            has_negative_cycle = true;
38
            break;
39
        }
40
    }
41

42
    return {dist, has_negative_cycle};
43
}

1
// SPFA —— Bellman-Ford 的队列优化
2
std::vector<int> spfa(
3
    const std::vector<std::vector<std::pair<int,int>>>& graph, int start)
4
{
5
    int n = graph.size();
6
    std::vector<int> dist(n, std::numeric_limits<int>::max());
7
    std::vector<bool> in_queue(n, false);
8
    std::queue<int> q;
9

10
    dist[start] = 0;
11
    q.push(start);
12
    in_queue[start] = true;
13

14
    while (!q.empty()) {
15
        int u = q.front();
16
        q.pop();
17
        in_queue[u] = false;
18

19
        for (auto [v, w] : graph[u]) {
20
            if (dist[u] + w < dist[v]) {
21
                dist[v] = dist[u] + w;
22
                if (!in_queue[v]) {
23
                    q.push(v);
24
                    in_queue[v] = true;
25
                }
26
            }
27
        }
28
    }
29

30
    return dist;
31
}

1
#include <vector>
2
#include <limits>
3

4
// Floyd-Warshall —— 全源最短路径
5
// dist[i][j] = i 到 j 的最短距离
6
void floyd_warshall(std::vector<std::vector<int>>& dist) {
7
    int n = dist.size();
8
    constexpr int INF = std::numeric_limits<int>::max() / 2;  // 防溢出
9

10
    // k = 中转节点
11
    for (int k = 0; k < n; ++k) {
12
        for (int i = 0; i < n; ++i) {
13
            for (int j = 0; j < n; ++j) {
14
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
15
                    dist[i][j] = dist[i][k] + dist[k][j];
16
                }
17
            }
18
        }
19
    }
20
}
21

22
// 使用示例:
23
// 初始化: dist[i][j] = weight(i,j), 无边 = INF, dist[i][i] = 0
24
// 调用后: dist[i][j] = i 到 j 的最短距离

1
初始距离矩阵 (INF=∞):
2
       0    1    2    3
3
  0 [  0    3    ∞    7  ]
4
  1 [  ∞    0    2    ∞  ]
5
  2 [  ∞    ∞    0    1  ]
6
  3 [  ∞    ∞    ∞    0  ]
7

8
k=0 (经过节点 0): 无变化 (0 到 1,3 有边, 但没有新的更短路)
9

10
k=1 (经过节点 1):
11
  dist[0][2] = min(∞, dist[0][1] + dist[1][2]) = min(∞, 3+2) = 5
12
       0    1    2    3
13
  0 [  0    3    5    7  ]
14

15
k=2 (经过节点 2):
16
  dist[0][3] = min(7, dist[0][2] + dist[2][3]) = min(7, 5+1) = 6
17
  dist[1][3] = min(∞, dist[1][2] + dist[2][3]) = min(∞, 2+1) = 3
18
       0    1    2    3
19
  0 [  0    3    5    6  ]
20
  1 [  ∞    0    2    3  ]
21

22
k=3: 无新更新
23

24
最终: dist[0][3] = 6 (路径: 0→1→2→3)  ✅

1
Dijkstra vs A* 的扩展方式:
2

3
Dijkstra (盲目扩展):          A* (启发式引导):
4
    · · · · · · · ·               · · · · · · · ·
5
    · · · * * · · ·               · · · · · · · ·
6
    · · * * * * · ·               · · · * · · · ·
7
    · * * * S * * ·               · · * * S · · ·
8
    · · * * * * · ·               · · · * * · · ·
9
    · · · * * · · G               · · · · * * · G
10
    · · · · · · · ·               · · · · · * * ·
11
    · · · · · · · ·               · · · · · · · ·
12

13
    S=起点, G=终点, *=已探索节点
14

15
Dijkstra 探索了大量无用方向;  A* 直奔目标, 探索量大幅减少

1
#include <vector>
2
#include <queue>
3
#include <cmath>
4
#include <algorithm>
5

6
struct Node {
7
    int x, y;
8
    int g;        // 起点到当前的实际代价
9
    double f;     // f = g + h, 总估计代价
10
    bool operator>(const Node& other) const { return f > other.f; }
11
};
12

13
// Manhattan 启发函数 (4方向)
14
inline int heuristic(int x1, int y1, int x2, int y2) {
15
    return std::abs(x1 - x2) + std::abs(y1 - y2);
16
}
17

18
// A* 寻路 —— 在网格上找最短路径
19
std::vector<std::pair<int,int>> a_star(
20
    const std::vector<std::vector<int>>& grid,  // 0=可走, 1=障碍
21
    std::pair<int,int> start,
22
    std::pair<int,int> goal)
23
{
24
    int rows = grid.size(), cols = grid[0].size();
25
    auto [sx, sy] = start;
26
    auto [gx, gy] = goal;
27

28
    // dist[x][y] = 起点到 (x,y) 的最短距离
29
    std::vector<std::vector<int>> dist(rows, std::vector<int>(cols, INT_MAX));
30
    // 前驱节点
31
    std::vector<std::vector<std::pair<int,int>>> prev(
32
        rows, std::vector<std::pair<int,int>>(cols, {-1, -1}));
33

34
    // 最小堆, 按 f = g + h 排序
35
    std::priority_queue<Node, std::vector<Node>, std::greater<Node>> open;
36

37
    dist[sx][sy] = 0;
38
    open.push({sx, sy, 0, static_cast<double>(heuristic(sx, sy, gx, gy))});
39

40
    constexpr int dx[] = {0, 0, 1, -1};
41
    constexpr int dy[] = {1, -1, 0, 0};
42

43
    while (!open.empty()) {
44
        auto [x, y, g, f] = open.top();
45
        open.pop();
46

47
        // 到达终点
48
        if (x == gx && y == gy) {
49
            // 回溯路径
50
            std::vector<std::pair<int,int>> path;
51
            auto cur = goal;
52
            while (cur != start) {
53
                path.push_back(cur);
54
                cur = prev[cur.first][cur.second];
55
            }
56
            path.push_back(start);
57
            std::reverse(path.begin(), path.end());
58
            return path;
59
        }
60

61
        // 跳过已过时的节点
62
        if (g > dist[x][y]) continue;
63

64
        // 扩展四个方向
65
        for (int d = 0; d < 4; ++d) {
66
            int nx = x + dx[d], ny = y + dy[d];
67
            if (nx < 0 || nx >= rows || ny < 0 || ny >= cols) continue;
68
            if (grid[nx][ny] == 1) continue;  // 障碍
69

70
            int new_g = g + 1;  // 边权 = 1
71
            if (new_g < dist[nx][ny]) {
72
                dist[nx][ny] = new_g;
73
                prev[nx][ny] = {x, y};
74
                double new_f = new_g + heuristic(nx, ny, gx, gy);
75
                open.push({nx, ny, new_g, new_f});
76
            }
77
        }
78
    }
79

80
    return {};  // 无路可达
81
}

1
int networkDelayTime(std::vector<std::vector<int>>& times, int n, int k) {
2
    // 建图
3
    std::vector<std::vector<std::pair<int,int>>> graph(n + 1);
4
    for (auto& t : times) {
5
        graph[t[0]].push_back({t[1], t[2]});
6
    }
7

8
    // Dijkstra
9
    std::vector<int> dist(n + 1, INT_MAX);
10
    std::priority_queue<std::pair<int,int>,
11
                        std::vector<std::pair<int,int>>,
12
                        std::greater<>> pq;
13

14
    dist[k] = 0;
15
    pq.push({0, k});
16

17
    while (!pq.empty()) {
18
        auto [d, u] = pq.top();
19
        pq.pop();
20

21
        if (d > dist[u]) continue;
22

23
        for (auto [v, w] : graph[u]) {
24
            if (dist[u] + w < dist[v]) {
25
                dist[v] = dist[u] + w;
26
                pq.push({dist[v], v});
27
            }
28
        }
29
    }
30

31
    // 答案 = 所有节点最短距离中的最大值
32
    int ans = 0;
33
    for (int i = 1; i <= n; ++i) {
34
        if (dist[i] == INT_MAX) return -1;  // 有节点不可达
35
        ans = std::max(ans, dist[i]);
36
    }
37
    return ans;
38
}
39
// 时间 O((V+E)logV), 空间 O(V+E)

1
int findCheapestPrice(int n, std::vector<std::vector<int>>& flights,
2
                      int src, int dst, int k)
3
{
4
    // Bellman-Ford: 最多 k+1 轮松弛
5
    std::vector<int> dist(n, INT_MAX);
6
    dist[src] = 0;
7

8
    for (int i = 0; i <= k; ++i) {
9
        // 关键: 用上一轮的 dist 来松弛, 防止"链式更新"
10
        std::vector<int> prev_dist = dist;
11

12
        for (auto& f : flights) {
13
            int u = f[0], v = f[1], w = f[2];
14
            if (prev_dist[u] != INT_MAX && prev_dist[u] + w < dist[v]) {
15
                dist[v] = prev_dist[u] + w;
16
            }
17
        }
18
    }
19

20
    return dist[dst] == INT_MAX ? -1 : dist[dst];
21
}
22
// 时间 O(k × E), 空间 O(V)

1
double maxProbability(int n, std::vector<std::vector<int>>& edges,
2
                      std::vector<double>& succProb, int start, int end)
3
{
4
    // 建图
5
    std::vector<std::vector<std::pair<int,double>>> graph(n);
6
    for (int i = 0; i < static_cast<int>(edges.size()); ++i) {
7
        graph[edges[i][0]].push_back({edges[i][1], succProb[i]});
8
        graph[edges[i][1]].push_back({edges[i][0], succProb[i]});
9
    }
10

11
    // "最大"概率 → 最大堆
12
    std::vector<double> prob(n, 0.0);
13
    std::priority_queue<std::pair<double,int>> pq;  // 默认最大堆
14

15
    prob[start] = 1.0;
16
    pq.push({1.0, start});
17

18
    while (!pq.empty()) {
19
        auto [p, u] = pq.top();
20
        pq.pop();
21

22
        if (p < prob[u]) continue;  // 过时节点
23
        if (u == end) return p;     // 提前终止
24

25
        for (auto [v, w] : graph[u]) {
26
            double new_prob = prob[u] * w;  // 概率相乘
27
            if (new_prob > prob[v]) {
28
                prob[v] = new_prob;
29
                pq.push({new_prob, v});
30
            }
31
        }
32
    }
33

34
    return 0.0;  // 不可达
35
}
36
// 时间 O((V+E)logV), 空间 O(V+E)

1
int findTheCity(int n, std::vector<std::vector<int>>& edges, int distanceThreshold) {
2
    constexpr int INF = 1e9;
3
    std::vector<std::vector<int>> dist(n, std::vector<int>(n, INF));
4

5
    // 初始化
6
    for (int i = 0; i < n; ++i) dist[i][i] = 0;
7
    for (auto& e : edges) {
8
        dist[e[0]][e[1]] = e[2];
9
        dist[e[1]][e[0]] = e[2];
10
    }
11

12
    // Floyd-Warshall
13
    for (int k = 0; k < n; ++k)
14
        for (int i = 0; i < n; ++i)
15
            for (int j = 0; j < n; ++j)
16
                dist[i][j] = std::min(dist[i][j], dist[i][k] + dist[k][j]);
17

18
    // 找邻居最少的城市
19
    int result = -1, min_count = n;
20
    for (int i = 0; i < n; ++i) {
21
        int count = 0;
22
        for (int j = 0; j < n; ++j) {
23
            if (i != j && dist[i][j] <= distanceThreshold) ++count;
24
        }
25
        if (count <= min_count) {
26
            min_count = count;
27
            result = i;  // 相同数量取编号最大的
28
        }
29
    }
30
    return result;
31
}
32
// 时间 O(V³), 空间 O(V²)

1
int shortestPathBinaryMatrix(std::vector<std::vector<int>>& grid) {
2
    int n = grid.size();
3
    if (grid[0][0] == 1 || grid[n-1][n-1] == 1) return -1;
4

5
    std::queue<std::pair<int,int>> q;
6
    q.push({0, 0});
7
    grid[0][0] = 1;  // 标记已访问
8
    int steps = 1;
9

10
    // 8方向
11
    int dx[] = {0,0,1,-1,1,1,-1,-1};
12
    int dy[] = {1,-1,0,0,1,-1,1,-1};
13

14
    while (!q.empty()) {
15
        int size = q.size();
16
        for (int i = 0; i < size; ++i) {
17
            auto [x, y] = q.front();
18
            q.pop();
19

20
            if (x == n-1 && y == n-1) return steps;
21

22
            for (int d = 0; d < 8; ++d) {
23
                int nx = x + dx[d], ny = y + dy[d];
24
                if (nx >= 0 && nx < n && ny >= 0 && ny < n && grid[nx][ny] == 0) {
25
                    grid[nx][ny] = 1;
26
                    q.push({nx, ny});
27
                }
28
            }
29
        }
30
        ++steps;
31
    }
32

33
    return -1;
34
}
35
// 时间 O(n²), 空间 O(n²)

1
#include <vector>
2
#include <queue>
3
#include <unordered_set>
4
#include <cmath>
5
#include <algorithm>
6

7
// 坐标编码: (x, y) → x * cols + y
8
struct PathNode {
9
    int pos;      // 编码后的坐标
10
    int g;        // 实际代价
11
    double f;     // f = g + h
12

13
    bool operator>(const PathNode& o) const { return f > o.f; }
14
};
15

16
class GamePathfinder {
17
    int _rows, _cols;
18
    const std::vector<std::vector<int>>& _terrain;
19

20
    // 8方向移动, 对角线代价 14 (≈√2×10), 直线代价 10
21
    static constexpr int dx[] = {0, 0, 1, -1, 1, 1, -1, -1};
22
    static constexpr int dy[] = {1, -1, 0, 0, 1, -1, 1, -1};
23
    static constexpr int cost[] = {10, 10, 10, 10, 14, 14, 14, 14};
24

25
    int _encode(int x, int y) const { return x * _cols + y; }
26
    std::pair<int,int> _decode(int pos) const { return {pos / _cols, pos % _cols}; }
27

28
    // Octile 距离 (最紧凑的 8方向启发函数)
29
    double _heuristic(int x1, int y1, int x2, int y2) const {
30
        int dx = std::abs(x1 - x2), dy = std::abs(y1 - y2);
31
        return 10.0 * std::max(dx, dy) + 4.0 * std::min(dx, dy);
32
        // 直线代价 10, 对角线额外代价 ≈ 14 - 10 = 4
33
    }
34

35
    bool _walkable(int x, int y) const {
36
        return x >= 0 && x < _rows && y >= 0 && y < _cols
37
            && _terrain[x][y] == 0;
38
    }
39

40
    // 对角线移动需要检查"肩膀"是否被卡住
41
    bool _diagonal_allowed(int x, int y, int d) const {
42
        if (d < 4) return true;  // 直线移动不需要检查
43

44
        // 例如右下移动 (1,1): 需要 (x+1,y) 和 (x,y+1) 至少一个可通行
45
        // 否则角色会"穿墙"
46
        int nx1 = x + dx[d], ny1 = y;  // 水平分量
47
        int nx2 = x, ny2 = y + dy[d];  // 垂直分量
48
        return _walkable(nx1, ny1) || _walkable(nx2, ny2);
49
    }
50

51
public:
52
    GamePathfinder(const std::vector<std::vector<int>>& terrain)
53
        : _rows(terrain.size()), _cols(terrain[0].size()), _terrain(terrain) {}
54

55
    // A* 寻路: 返回坐标路径
56
    std::vector<std::pair<int,int>> find_path(
57
        std::pair<int,int> start, std::pair<int,int> goal)
58
    {
59
        int total = _rows * _cols;
60
        std::vector<int> g_score(total, INT_MAX);
61
        std::vector<int> prev(total, -1);
62
        std::priority_queue<PathNode, std::vector<PathNode>,
63
                            std::greater<PathNode>> open;
64

65
        auto [sx, sy] = start;
66
        auto [gx, gy] = goal;
67
        int start_pos = _encode(sx, sy);
68
        int goal_pos = _encode(gx, gy);
69

70
        g_score[start_pos] = 0;
71
        open.push({start_pos, 0, _heuristic(sx, sy, gx, gy)});
72

73
        while (!open.empty()) {
74
            auto [pos, g, f] = open.top();
75
            open.pop();
76

77
            if (pos == goal_pos) {
78
                // 回溯路径
79
                std::vector<std::pair<int,int>> path;
80
                for (int p = goal_pos; p != -1; p = prev[p]) {
81
                    path.push_back(_decode(p));
82
                }
83
                std::reverse(path.begin(), path.end());
84
                return path;
85
            }
86

87
            if (g > g_score[pos]) continue;  // 跳过过时节点
88

89
            auto [x, y] = _decode(pos);
90

91
            for (int d = 0; d < 8; ++d) {
92
                int nx = x + dx[d], ny = y + dy[d];
93
                if (!_walkable(nx, ny)) continue;
94
                if (!_diagonal_allowed(x, y, d)) continue;
95

96
                int new_g = g + cost[d];
97
                int npos = _encode(nx, ny);
98

99
                if (new_g < g_score[npos]) {
100
                    g_score[npos] = new_g;
101
                    prev[npos] = pos;
102
                    double new_f = new_g + _heuristic(nx, ny, gx, gy);
103
                    open.push({npos, new_g, new_f});
104
                }
105
            }
106
        }
107

108
        return {};  // 不可达
109
    }
110
};
111

112
// 使用示例:
113
// GamePathfinder pf(terrain_map);
114
// auto path = pf.find_path({0, 0}, {99, 99});
115
// for (auto [x, y] : path) { move_character_to(x, y); }

1
1. Jump Point Search (JPS)
2
   在均匀网格上, 跳过不必要的中间节点
3
   加速 10-30 倍 (无障碍区域效果最好)
4

5
2. 分层寻路 (Hierarchical Pathfinding)
6
   大地图: 先在"区域图"上 A* 找粗略路径
7
   再在每个区域内 A* 找精确路径
8
   MMO 大世界必备
9

10
3. Navigation Mesh (NavMesh)
11
   不用网格, 用三角形/多边形覆盖地图
12
   节点数大幅减少 → A* 更快
13
   Unity/Unreal 引擎标配
14

15
4. 流场寻路 (Flow Field)
16
   大量单位移向同一目标 (RTS 游戏)
17
   一次计算, 所有单位共享 → O(n) 优于 n 次 A*
18

19
5. 路径平滑 (Path Smoothing)
20
   A* 输出的路径是锯齿状的
21
   用 String-Pulling / Funnel 算法平滑
22
   视觉效果: 角色沿弧线走而非折线走

1
// 真实游戏中, 不同地形有不同移动代价
2
enum Terrain {
3
    ROAD    = 1,   // 道路: 代价 1
4
    GRASS   = 3,   // 草地: 代价 3
5
    FOREST  = 5,   // 森林: 代价 5
6
    SWAMP   = 8,   // 沼泽: 代价 8
7
    WALL    = -1,  // 墙壁: 不可通行
8
};
9

10
// 修改 A* 中的移动代价:
11
// int move_cost = base_cost[d] * terrain_cost[grid[nx][ny]];
12
// 而非固定的 cost[d]
13

14
// 这使得 A* 自动倾向于走道路而非翻山越岭
15
// 玩家看到的效果: NPC 会走大路, 除非绕路代价太高

1
// 游戏中障碍物是动态的 (其他角色、可破坏物体、门)
2
// 方案一: 局部重规划 (Replanning)
3
//   检测到路径被阻断 → 从当前位置重新 A*
4
//   适合: 偶尔的障碍变化
5

6
// 方案二: D* Lite (Dynamic A*)
7
//   增量式更新: 只重新计算受影响的节点
8
//   适合: 频繁的障碍变化 (RTS 战争迷雾)
9

10
// 方案三: 避障层 (Steering + Pathfinding 分离)
11
//   A* 负责全局路径
12
//   Steering Behavior 负责局部避障 (绕过移动中的NPC)
13
//   现代游戏最常用的架构
14

15
// 伪代码:
16
// global_path = a_star(current_pos, target);
17
// while (not_arrived) {
18
//     if (path_blocked(global_path)) {
19
//         global_path = a_star(current_pos, target);  // 重规划
20
//     }
21
//     next_waypoint = global_path.next();
22
//     steer_towards(next_waypoint, avoid_nearby_units());
23
// }