手把手教会用C++实现A*算法_c++ a*算法

书接上回，上一篇博客我们介绍了A算法最基本的原理，本篇博客我们来手把手的教会大家A算法的C++实现！原文链接在此，大佬分别用Python、C++、C#进行了算法的实现orz

正文如下：

本文是我对A *的介绍的辅助指南，在此我将解释算法的工作原理。
在此页面上，我将展示如何实现广度优先搜索，Dijkstra的算法，贪婪的最佳优先搜索和A *。 我尝试使代码保持简单。

图搜索有一系列相关算法。算法有很多变体，实现上也有很多变体。将本文展示的代码视为一个起点，而不是适用于所有情况的最终版本。

c++实现

注意：一些示例代码需要 redblobgames/pathfinding/a-star/implementation.cpp才能执行。我使用 C++ 11 编写这些代码，如果你使用的是更老版本的 C++标准，有些代码可能需要更改。

这里的代码仅供教程参考，不具备正式使用质量。本文最后一节会给出一些提示来优化它。

广度优先搜索

让我们在 C++ 中实现广度优先搜索。以下是我们需要用到的组件（与 Python 实现相同）：

• 图（Graph）

  一种数据结构：可以告诉我图中每个位置的相邻位置（参考这篇文章）。加权图还可以告诉我沿着边移动的成本。

• 位置（Locations）

  一个简单值（整数、字符串、元组等），用于标记图中的位置。它们不一定是具体地图上的某些位置。根据解决的问题，它们还可能包含其他信息，例如方向、燃料、库存等。

• 搜索（Search）

  一种算法：它接受一个图、一个起始位置以及一个目标位置（可选），并为图中的某些位置甚至所有位置计算出一些有用的信息（是否可访问，它的父指针，之间的距离等）。

• 队列（Queue）

  搜索算法中用来确定处理图中位置顺序的数据结构。

在之前的介绍文章中，我聚焦在搜索上。在这篇文章中，我会填充余下的细节，来使程序完整。让我们从图（Graph）这个数据结构开始，其中位置（节点）为char类型：

struct SimpleGraph {
   
  std::unordered_map<char, std::vector<char> > edges;

  std::vector<char> neighbors(char id) {
   
    return edges[id];
  }
};
1
2
3
4
5
6
7
8
9

这里是一个例子：

SimpleGraph example_graph {
   {
   
    {
   'A', {
   'B'}},
    {
   'B', {
   'A', 'C', 'D'}},
    {
   'C', {
   'A'}},
    {
   'D', {
   'E', 'A'}},
    {
   'E', {
   'B'}}
  }};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

C++ 标准库中已经包含了队列类，因此，我们现在已经有了图（SimpleGraph）、位置（char）以及队列（std::queue)。那么让我们来尝试一下广度优先搜索：

#include "redblobgames/pathfinding/a-star/implementation.cpp"

void breadth_first_search(SimpleGraph graph, char start) {
   
  std::queue<char> frontier;
  frontier.push(start);

  std::unordered_set<char> reached;
  reached.insert(start);

  while (!frontier.empty()) {
   
    char current = frontier.front();
    frontier.pop();

    std::cout << "Visiting " << current << '\n';
    for (char next : graph.neighbors(current)) {
   
      if (reached.find(next) == reached.end()) {
   
        frontier.push(next);
        reached.insert(next);
      }
    }
  }
}


int main() {
   
  breadth_first_search(example_graph, 'A');
}
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

运行结果：

Visiting A
Visiting B
Visiting C
Visiting D
Visiting E
1
2
3
4
5

栅格/网格（Grid）也可以表示为图。现在，我将定义一个名为 SquareGrid 的图类，其中的位置数据结构为两个整数。在此地图中，图中的位置（“状态”）与游戏地图上的位置相同，但在许多问题中，图中的位置与地图上的位置不同。我将不显式存储边数据，而是使用neighbors函数来计算它们。不过，在其他许多问题中，最好将它们明确存储：

struct GridLocation {
   
  int x, y;
};

namespace std {
   
/* implement hash function so we can put GridLocation into an unordered_set */
template <> struct hash<GridLocation> {
   
  typedef GridLocation argument_type;
  typedef std::size_t result_type;
  std::size_t operator()(const GridLocation& id) const noexcept {
   
    return std::hash<int>()(id.x ^ (id.y << 4));
  }
};
}


struct SquareGrid {
   
  static std::array<GridLocation, 4> DIRS;

  int width, height;
  std::unordered_set<GridLocation> walls;

  SquareGrid(int width_, int height_)
     : width(width_), height(height_) {
   }

  bool in_bounds(GridLocation id) const {
   
    return 0 <= id.x && id.x < width
        && 0 <= id.y && id.y < height;
  }

  bool passable(GridLocation id) const {
   
    return walls.find(id) == walls.end();
  }

  std::vector<GridLocation> neighbors(GridLocation id) const {
   
    std::vector<GridLocation> results;

    for (GridLocation dir : DIRS) {
   
      GridLocation next{
   id.x + dir.x, id.y + dir.y};
      if (in_bounds(next) && passable(next)) {
   
        results.push_back(next);
      }
    }

    if ((id.x + id.y) % 2 == 0) {
   
      // aesthetic improvement on square grids
      std::reverse(results.begin(), results.end());
    }

    return results;
  }
};

std::array<GridLocation, 4> SquareGrid::DIRS =
  {
   GridLocation{
   1, 0}, GridLocation{
   0, -1}, GridLocation{
   -1, 0}, GridLocation{
   0, 1}};
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

在辅助文件implementation.cpp我定义了一个函数来生成网格：

#include "redblobgames/pathfinding/a-star/implementation.cpp"

int main() {
   
  SquareGrid grid = make_diagram1();
  draw_grid(grid, 2);
}
1
2
3
4
5
6
7

运行结果：

. . . . . . . . . . . . . . . . . . . . . ####. . . . . . . 
. . . . . . . . . . . . . . . . . . . . . ####. . . . . . . 
. . . . . . . . . . . . . . . . . . . . . ####. . . . . . . 
. . . ####. . . . . . . . . . . . . . . . ####. . . . . . . 
. . . ####. . . . . . . . ####. . . . . . ####. 
1
2
3
4