游戏寻路算法：A星算法

A*寻路算法 通常用于使用TileMap形式制作的游戏地图中，TileMap地图是一个二维格子矩阵，每个格子就是地图上的一个单元格子，格子所在的行和列就是格子的二维坐标。每个单元格能够被填充成各种地形地貌，并且可以被标记成可行走区域或不可行走区域。

1.单纯采用BFS：
完备，但算法效率低下，遍历太多无效节点。为了大幅提高搜索效率，引入了启发式搜索
2.启发式搜索：
　利用当前与问题有关的信息作为启发式信息，这些信息是能够提升查找效率以及减少查找次数的。如何使用这些信息，我们定义了一个估价函数h(x)。h(x)是对当前状态x的一个估计，表示x状态到目标状态的距离。
　h(x)的函数值有：1. h(x) >= 0； 2. h(x)越小表示x越接近目标状态；与问题相关的启发式信息都被计算为一定的h(x)的值，引入到搜索过程中。然而，有了启发式信息还不行，如果只有h(x)就相当于一个贪婪优先搜索，每次都是向最靠近目标的状态靠近，但却不一定能找到最优解。
　所以，还需要起始状态到x状态所花的代价，我们称为g(x)。我们的g(x)就是从起点到x位置花的步数，h(x)就是与目标状态的曼哈顿距离或者相差的数目；在最短路径中，我们的g(x)就是到x点的权值，h(x)就是x点到目标结点的最短路或直线距离。

现在，从h(x)和g(x)的定义中不能看出，假如我们搜索依据为 F(x) 函数。

当F(x) = g(x)的时候就是一个等代价搜索，完全是按照花了多少代价去搜索。比如bfs，我们每次都是从离得近的层开始搜索，一层一层搜；等代价搜索虽然具有完备性，能找到最优解，但是效率太低。 当F(x) = h(x)的时候就相当于一个贪婪优先搜索。每次都是向最靠近目标的状态靠近。贪婪优先搜索不具有完备性，不一定能找到解，最坏的情况下类似于dfs。

A算法的核心定义就在F(x) = g(x) + h(x)。并证明了当估价函数满足一定条件，算法一定能找到最优解。估价函数满足一定条件的算法称为A算法。它的限制条件是 F(x) = g(x) + h(x) 。 代价函数g(x) > 0 ；h(x)的值不大于x到目标的实际代价 h*(x) 。即定义的h(x)是可纳的，是乐观的。
　　
给出C++版本的A*实现如下：

#include 
#include 
#include 
#include 

// 定义地图大小
const int rows = 3;
const int cols = 4;

// 定义节点表示
struct Node {
    int x, y;       // 节点的坐标
    int cost;       // 节点的代价（移动成本）
    int f, g, h;    // 估价函数值，已走路径长度，启发式函数值

    Node(int x, int y, int cost) : x(x), y(y), cost(cost), f(0), g(0), h(0) {}

    bool operator<(const Node& other) const {
        return f > other.f; // 优先级队列的比较，F 值越小优先级越高
    }
};

// 判断节点是否在地图范围内
bool isValid(int x, int y) {
    return x >= 0 && x < rows && y >= 0 && y < cols;
}

// A* 算法实现
std::vector<Node> aStar(const std::vector<std::vector<int>>& map, const Node& start, const Node& goal) {
    // 方向：上、下、左、右
    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};

    std::priority_queue<Node> openSet; // 优先级队列，用于存放待扩展的节点
    std::vector<std::vector<bool>> visited(rows, std::vector<bool>(cols, false)); // 记录节点是否被访问过
    std::vector<std::vector<Node>> cameFrom(rows, std::vector<Node>(cols, Node(-1, -1, 0))); // 记录节点的来源

    start.g = 0;
    start.h = abs(start.x - goal.x) + abs(start.y - goal.y);
    start.f = start.g + start.h;
    openSet.push(start);

    while (!openSet.empty()) {
    
        Node current = openSet.top();
        openSet.pop();

        if (current.x == goal.x && current.y == goal.y) {
            std::vector<Node> path;
            while (current.x != -1 && current.y != -1) {
                path.push_back(current);
                current = cameFrom[current.x][current.y];
            }
            return path;
        }

        visited[current.x][current.y] = true;

//四个方向 挑估价函数MIN走（利用了优先级队列）
        for (int i = 0; i < 4; ++i) {
            int newX = current.x + dx[i];
            int newY = current.y + dy[i];

            if (isValid(newX, newY) && !visited[newX][newY] && map[newX][newY] != -1) {
                Node neighbor(newX, newY, map[newX][newY]);

                int tentativeG = current.g + neighbor.cost;
                if (tentativeG < neighbor.g || !visited[neighbor.x][neighbor.y]) {
                    neighbor.g = tentativeG;//累计代价
                    neighbor.h = abs(neighbor.x - goal.x) + abs(neighbor.y - goal.y);//启发函数(曼哈顿距离)
                    neighbor.f = neighbor.g + neighbor.h;//估价函数(代价+启发函数)
                    cameFrom[neighbor.x][neighbor.y] = current;
                    openSet.push(neighbor);
                }
            }
        }
    
    }

    return std::vector<Node>(); // 未找到路径
}

int main() {
    std::vector<std::vector<int>> map = {
        {3, 2, 0, 4},
        {4, -1, 8, 5},
        {1, 6, 7, 0}
    };

    Node start(0, 2, map[0][2]);
    Node goal(2, 3, map[2][3]);

    std::vector<Node> path = aStar(map, start, goal);

    if (path.empty()) {
        std::cout << "Path not found!" << std::endl;
    } else {
        std::cout << "Path found:" << std::endl;
        for (int i = path.size() - 1; i >= 0; --i) {
            std::cout << "(" << path[i].x << ", " << path[i].y << ") ";
        }
        std::cout << std::endl;
    }

    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108