以下为个人学习笔记整理。总所都周知，做游戏的， A* 寻路是基础，作为一个游戏研发工程🦁，不会 A* 属实说不过去。

在这个英才辈出，手撕红黑的时代，不会 A* 无异于身处食物链的低端。所以！痛定思痛，最终决定还是学习一下（狗头。

# A_star 算法

# 什么是 A* 算法❓

A * 是一种明智的搜索算法，或 “最佳优先” 搜索，意味着它是根据加权图来表示的：从图的特定起始节点开始，它的目的是找到到给定目标节点的路径最小的路径费用（最短路程，最短时间等）。它通过维护始于起始节点的路径树并一次扩展一条路径直到满足其终止标准来做到这一点。——Wikipedia

# 扩展路径

A* 算法通过一次次的扩展路径，直到满足终止标准，最终得到一条最优路线。 A* 算法扩展路径的方式如下：

$f(n) = g(n) + h(n)$

n ：表示路径上的某点。
g(n) ：表示从起点到达该点所需的最小路程成本（最短距离）。
h(n) ：用于估计从该点到达终点的最小路程成本。
- 估计函数的方式有很多，可以是通过两点的直线距离；亦或是使用曼哈顿距离或八卦距离。

# A * 算法核心思想

使用到的数据结构：

「Point」用于表示地图上每个点。
open_map：待遍历点，排除重复待遍历点，点数据和优先队列保持一致。
close_map：已遍历点，用于最终还原路线，记录历史避免重复遍历。
p_queue：优先队列，根据自定义优先级，快速获取下一个遍历点。

算法步骤：

将起点压入优先队列
如果优先队列不为空则弹出优先级最高的点「point」
- 把「point」加入已遍历字典
- 如果「point」是终点，返回最终路线结果（出口 1）
- 获取「point」周围 9 宫格的「round_point」
  - 「round_point」位置必须合法
  - 「round_point」不在「已遍历字典」
  - 「round_point」如果在「待遍历字典」，且 f(n) 效于当前值，则更新待变量字典内的数据，并修改父节点
- 将所有「round_point」加入优先队列和「待遍历字典」
如果无法到达目的地，则退出寻路函数（出口 2）

# 简单测试一下

定义一个 20x20 场景数据，1 表示阻挡物（不可到达），0 表示可以达到。

	scene_map = [[0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
	[0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0],
	[0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0],
	[0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0],
	[0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0],
	[0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0],
	[0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0],
	[0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0],
	[0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0],
	[0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0],
	[0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0],
	[0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0],
	[0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0],
	[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0],
	[0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
	[0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
	[0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0],
	[0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0],
	[0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0],
	[0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0]]

接下来看看最终的效果：

distance: 30.62741699796953, create point: 310

# 通过 `matplotlib` 库可视化结果后效果

# 效果图

灰色方块：可达点
浅蓝色方块：障碍物
绿色方块：起点
红色方块：终点
蓝色方块：待遍历点
黄色方块：已遍历点
黑色方块：最终路线

get_path distance: 35.213203435596434 count: 173

a_star

# 代码链接

A_star

# 参考资料

A* search algorithm - Wikipedia
路径规划之 A* 算法