欢迎来到奈瑶·映南科技互联网学院
技术教程

c++如何实现A*寻路算法_c++游戏开发常用算法【源码】

穿越時空 次阅读
A*寻路算法是C++游戏开发中最常用、最实用的路径搜索算法，适用于网格地图或图结构，兼顾效率与最优性；核心用优先队列（按f=g+h排序）、哈希表（查重与父节点映射），启发式推荐曼哈顿距离（4向）或对角距离（8向）。

在C++游戏开发中，A*（A-star）寻路算法是最常用、最实用的路径搜索算法之一。它兼顾效率与最优性，适合网格地图（如2D方格、Tile地图）或图结构中的单位移动规划。下面直接给出一个轻量、可读性强、带注释的C++实现，基于标准库，不依赖第三方引擎，可直接集成进你的游戏项目。

核心数据结构设计

要高效运行A*，需三个关键容器：

  • 开放列表（open set）：待评估节点，用std::priority_queue（最小堆），按 f(n) = g(n) + h(n) 排序
  • 关闭列表（closed set）：已处理节点，用std::unordered_set（哈希表）快速查重
  • 父节点映射（came_from）：用std::unordered_map记录每个节点的前驱，用于回溯路径

启发式函数 h(n) 的选择

对网格地图，推荐使用曼哈顿距离（4向移动）或欧几里得距离（8向/斜向移动）。避免用错导致非最优或变慢：

  • 4方向（上下左右）→ 用曼哈顿：abs(x1-x2) + abs(y1-y2)
  • 8方向（含对角线）→ 用对角距离：max(abs(x1-x2), abs(y1-y2))（更准且快）
  • 不建议直接用欧氏距离平方（会失去可容许性），若要用请开根号并确保浮点精度可控

完整可运行示例（控制台版）

以下代码支持 2D 网格（int 类型障碍物标记），输出最短路径坐标序列：

#include 
#include 
#include 
#include 
#include 
#include 
#include 

struct Point {
int x, y;
bool operator==(const Point& o) const { return x == o.x && y == o.y; }
};
// 哈希特化，用于 unordered_set/map
namespace std {
template<> struct hash {
size_t operator()(const Point& p) const {
return hash{}(p.x) ^ (hash{}(p.y) << 1);
}
};
}
// A* 节点（优先队列元素）
struct Node {
Point pos;
float f, g;
bool operator>(const Node& rhs) const { return f > rhs.f; }
};
std::vector astar(const std::vector>& grid,
Point start, Point end) {
if (grid.empty() || grid[0].empty()) return {};
int rows = grid.size(), cols = grid[0].size();
auto in_bounds = [&](int x, int y) {
    return x youjiankuohaophpcn= 0 && x zuojiankuohaophpcn rows && y youjiankuohaophpcn= 0 && y zuojiankuohaophpcn cols;
};
auto is_walkable = [&](int x, int y) {
    return in_bounds(x, y) && grid[x][y] == 0; // 0=空地，1=障碍
};

// 启发式：对角距离（8向）
auto heuristic = [&](Point a, Point b) -youjiankuohaophpcn float {
    int dx = abs(a.x - b.x), dy = abs(a.y - b.y);
    return std::max(dx, dy) + (std::sqrt(2.0f) - 1.0f) * std::min(dx, dy);
};

std::priority_queuezuojiankuohaophpcnNode, std::vectorzuojiankuohaophpcnNodeyoujiankuohaophpcn, std::greaterzuojiankuohaophpcnNodeyoujiankuohaophpcnyoujiankuohaophpcn open;
std::unordered_setzuojiankuohaophpcnPointyoujiankuohaophpcn closed;
std::unordered_mapzuojiankuohaophpcnPoint, Pointyoujiankuohaophpcn came_from;
std::unordered_mapzuojiankuohaophpcnPoint, floatyoujiankuohaophpcn g_score;

open.push({start, heuristic(start, end), 0});
g_score[start] = 0;

const std::vectorzuojiankuohaophpcnstd::pairzuojiankuohaophpcnint,intyoujiankuohaophpcnyoujiankuohaophpcn dirs = {
    {-1,0},{1,0},{0,-1},{0,1}, // 上下左右
    {-1,-1},{-1,1},{1,-1},{1,1} // 对角（可选，注释掉即4向）
};

while (!open.empty()) {
    Node curr = open.top(); open.pop();
    if (curr.pos == end) break;
    if (closed.count(curr.pos)) continue;
    closed.insert(curr.pos);

    for (auto [dx, dy] : dirs) {
        Point next{curr.pos.x + dx, curr.pos.y + dy};
        if (!is_walkable(next.x, next.y)) continue;

        float move_cost = (dx == 0 || dy == 0) ? 1.0f : std::sqrt(2.0f);
        float tentative_g = g_score[curr.pos] + move_cost;

        if (!g_score.count(next) || tentative_g zuojiankuohaophpcn g_score[next]) {
            came_from[next] = curr.pos;
            g_score[next] = tentative_g;
            float f = tentative_g + heuristic(next, end);
            open.push({next, f, tentative_g});
        }
    }
}

// 回溯路径
std::vectorzuojiankuohaophpcnPointyoujiankuohaophpcn path;
for (Point curr = end; curr != start && came_from.count(curr); curr = came_from[curr]) {
    path.push_back(curr);
}
if (!path.empty() && path.back() != start) path.push_back(start);
std::reverse(path.begin(), path.end());
return path;
}


// 示例用法
int main() {
// 0=可通过，1=墙
std::vector<:vector>> map = {
{0,0,0,0,1},
{0,1,0,0,0},
{0,1,0,1,0},
{0,0,0,1,0},
{1,0,0,0,0}
};
auto path = astar(map, {0,0}, {4,4});
std::cout zuojiankuohaophpcnzuojiankuohaophpcn "Path: ";
for (auto p : path) std::cout zuojiankuohaophpcnzuojiankuohaophpcn "(" zuojiankuohaophpcnzuojiankuohaophpcn p.x zuojiankuohaophpcnzuojiankuohaophpcn "," zuojiankuohaophpcnzuojiankuohaophpcn p.y zuojiankuohaophpcnzuojiankuohaophpcn ") ";
std::cout zuojiankuohaophpcnzuojiankuohaophpcn "\n";
}


集成到游戏项目的建议


    

  • 把Point换成你引擎的向量类型（如sf::Vector2i、glm::ivec2），重载==和hash

    • 

  • 将grid参数改为接口抽象（如auto getCell(x,y) -> CellType），支持动态地形或NavMesh采样
    • 

  • 加早停机制：设置最大搜索节点数（防卡死）或时间片（如每帧只算50个节点）
    • 

  • 路径平滑：对返回的折线路径做直线检测+跳点（JPS）或贝塞尔插值，提升视觉自然度
    • 



基本上就这些。A*本身不复杂，但细节（比如启发式选择、移动代价建模、内存管理）容易忽略，影响性能和路径质量。实际项目中常配合路径缓存、分层寻路（Hierarchical A*）或Flow Field做大规模单位调度——那是进阶方向了。






            
 堆 go 进阶 ai 接口 ios 算法 red 特化 auto 最优 cos 数据结构 c++ 最常用 那是 int 标准库 stream node map 上下左右 游戏开发 浮点 曼哈顿 欧几里得

相关文章

按ESC键退出。