VC++ A*寻路算法
时间: 2023-07-10 20:07:35 浏览: 95
A*寻路算法是一种常用的路径规划算法,可以用于游戏开发、机器人路径规划等领域。下面是一个简单的VC++实现示例:
```c++
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
const int INF = 1 << 30;
// 定义节点结构体
struct Node {
int x, y;
int f, g, h;
Node* parent;
Node(int x = -1, int y = -1):x(x), y(y), f(INF), g(INF), h(INF), parent(nullptr) {}
bool operator < (const Node& rhs) const {
return f > rhs.f;
}
};
class AStar {
public:
AStar(int rows, int cols):rows(rows), cols(cols) {
// 初始化地图
map.resize(rows);
for (int i = 0; i < rows; i++) {
map[i].resize(cols, 0);
}
}
// 设置起点和终点
void setStart(int x, int y) {
start = new Node(x, y);
}
void setEnd(int x, int y) {
end = new Node(x, y);
}
// 添加障碍物
void addBlock(int x, int y) {
map[x][y] = 1;
}
// 计算路径
vector<Node*> findPath() {
vector<Node*> path;
priority_queue<Node> openList; // open表,存储待扩展的节点
vector<Node*> closeList; // close表,存储已扩展的节点
// 初始化起点
start->f = start->g = start->h = 0;
openList.push(*start);
while (!openList.empty()) {
// 取出open表中f值最小的节点
Node curr = openList.top();
openList.pop();
// 如果当前节点是终点,则返回路径
if (curr.x == end->x && curr.y == end->y) {
Node* node = &curr;
while (node) {
path.push_back(node);
node = node->parent;
}
reverse(path.begin(), path.end());
break;
}
// 扩展当前节点的四个方向
for (int i = 0; i < 4; i++) {
int nx = curr.x + dx[i];
int ny = curr.y + dy[i];
// 判断是否越界
if (nx < 0 || nx >= rows || ny < 0 || ny >= cols) {
continue;
}
// 判断是否是障碍物或已经扩展过
if (map[nx][ny] == 1 || isContain(closeList, nx, ny)) {
continue;
}
// 计算新节点的g值和h值
Node* newNode = new Node(nx, ny);
newNode->g = curr.g + 1;
newNode->h = calcH(newNode);
newNode->f = newNode->g + newNode->h;
newNode->parent = &curr;
// 将新节点加入open表
openList.push(*newNode);
}
// 将当前节点加入close表
closeList.push_back(new Node(curr.x, curr.y));
}
// 释放内存
for (auto node : closeList) {
delete node;
}
return path;
}
private:
int rows, cols;
vector<vector<int>> map; // 地图
Node* start;
Node* end;
// 两点之间的曼哈顿距离
int calcH(Node* node) {
return abs(node->x - end->x) + abs(node->y - end->y);
}
// 判断close表中是否包含某个节点
bool isContain(vector<Node*>& closeList, int x, int y) {
for (auto node : closeList) {
if (node->x == x && node->y == y) {
return true;
}
}
return false;
}
// 四个方向
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };
};
int main() {
AStar astar(5, 5);
astar.setStart(0, 0);
astar.setEnd(4, 4);
astar.addBlock(2, 2);
astar.addBlock(3, 2);
astar.addBlock(3, 3);
vector<Node*> path = astar.findPath();
for (auto node : path) {
cout << "(" << node->x << "," << node->y << ")" << endl;
}
return 0;
}
```
以上是一个简单的VC++实现示例,如果你想了解更多关于A*寻路算法的内容,可以参考其他资料。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)