VC++ A*寻路算法

A*寻路算法是一种常用的路径规划算法，可以用于游戏开发、机器人路径规划等领域。下面是一个简单的VC++实现示例：

#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*寻路算法的内容，可以参考其他资料。