游戏开发者联盟

boost中的A*算法

The Boost Graph Library (BGL)

这是boost的图论算法库,之前没有关注过这个库,今天无意中在它长长的算法列表中,发现了包括A*算法在内的多个最短路径算法:

  1. dijkstra_shortest_paths
  2. dijkstra_shortest_paths_no_color_map
  3. bellman_ford_shortest_paths
  4. dag_shortest_paths
  5. johnson_all_pairs_shortest_paths
  6. floyd_warshall_all_pairs_shortest_paths
  7. r_c_shortest_paths - resource-constrained shortest paths
  8. astar_search (A* search algorithm)

不由自主有了念想,能不能替换自己写过的A*算法呢?值得一试。

预备知识

相比稀疏矩阵来说,这个玩意就复杂了多了,需要先建立图,然后应用astar算法。而我的数据是稀疏矩阵,我希望能直接利用这个矩阵,并且不想再正儿八经建立一个图。先找找资料读读。

  1. 官方文档
  2. C++图常用库boost graph library(一)
  3. 探索 Boost Graph Library
  4. 官方例子:A*算法求解迷宫,这个例子相对比较好,它给了一个除了adjacency_list之外的使用方式,之前找到的文章无一例外都是 adjacency_list。这个例子和我的需求比较契合。
  5. 自定义adjacency_list的存储方式

知识点

  • adjacency_matrix 和 adjacency_list 对比
名称 空间复杂度 遍历的时间复杂度 插入删除时间复杂度 实用场景
adjacency_matrix O(V2) O(V2) 常数 稠密图
adjacency_list O(V + E) O(V + E) 稀疏图

(E is the number of edges)

实现一个图

对于类似迷宫的地图,只需要添加顶点,不需要添加边,也就不需要存储边,相邻关系就是边。所以我需要简化存储。

a*算法对图的要求必须是:必须符合 Incidence Graph或者 Vertex List Graph,这里我选择了Incidence Graph,因为它非常便于得到出向边(我这是无向图,什么边都一样)。
此外,还必须符合Graph的基本定义。

实际上这些要求只是一种traits、特征,并不是基类、接口。所以翻出来他们要求的特征,照着写就行了。

此外,还可以参照它的源码,我参考了相对简单的grid_graph

然后这个图就可以当做参数传递给astar_search,进行路径搜索。

自己实现一个图,有个显著的好处,可以方便的切换各种容器类、或者各种矩阵存储方式。