数据结构与算法 - AStar(A*)

2022-08-01

全文 ≈ 2.1k字 | 预计阅读时长 8分钟

寻路算法是游戏比较重要的组成部分之一，尤其在国内游戏很常见的自动寻路系统，比如操纵角色从 A 点到 B 点的移动。计算最短路径有很多不同的算法，比如：Dijkstra、AStar（A*）、NavMesh（多边形算法）、RVO 动态避障等等

A*寻路算法

寻路算法的移动路径核心有 2 点：最短、可移动。

所以首先需要确定起点坐标的相邻节点（4 方向、8 方向），然后通过计算最靠近终点坐标的相邻坐标（不考虑障碍物）确认检索方向，再去计算“相邻坐标”移动的下一个坐标（距离终点坐标最近 & 可移动），重复计算这个过程直至找到终点坐标，这就是 A*算法

A*算法是一类基于网格的寻路算法，也就是把地图看作一个由网格组成的矩阵，每个坐标就是一个网格。

一张 3x3 地图

启发函数

从起点移动到终点坐标可能会产生多条移动路径，所以还需要计算出哪条移动路径最短，不然越走越远就演变成《论述如何帮助玩家刷微信步数》的尴尬情况。

在网格地图中肯定是经过越少的网格路径就越短，但我们不可能把每条可能的路径都走一遍再选出哪条路径最短，所以需要进行评估接下来走哪个网格最近。

假设我们把网格直线（水平、垂直）移动成本设为 1、对角移动成本设为：1.4。然后把移动路径上的坐标的成本进行相加取出最小值即可能是当前最佳移动路径。

这也叫启发式算法，即优先检索可能是成本最低的网格。

估价公式

我们不可能把每条可能的路径都走一遍，所以通过估价公式：f = g + h，来评估接下来走哪一个网格。

从起点坐标移动到当前坐标的移动成本（网格数）

从当前坐标移动到终点坐标的移动成本

当前坐标的移动成本

通过这样一个网格移动成本的评估公式，可以大概计算出从起点网格移动至终点网格的路径中，下一步走哪一个网格可能路径最短。

移动成本

怎么计算移动成本？使用距离算法作为估价函数对网格进行估价。比如以下的距离算法（不仅限于）：

欧氏距离
曼哈顿距离
切比雪夫距离
45 度角计算（Octile）

不同的距离算法在不同的场景上表现不一，比如说在静态网格地图场景中

欧氏距离

优点：

计算直线距离，移动路径最短。

缺点：

计算过程中伴随着平方与开根号运算，并且需要使用浮点数，性能差。

因为是网格所以基本不能按照直线进行移动，精确度不够。

曼哈顿距离

优点：

计算过程不存在浮点数，性能较高。

缺点：

只可以垂直或者水平移动。

所以在对 4 方向、8 方向又或者 6 方向上的算法选择是不一样的。比如 4 方向移动上下左右使用曼哈顿距离来进行估价就完全足够，但如果是 8 方向移动就不可以（可以对角移动）。

所以，如果是 8 方向移动的场景通常会采用曼哈顿+对角计算的距离算法。

寻路思路

示例：3x3 & 无障碍的地图

绿色是起点，蓝色是终点

把起点放进待查找节点列表。
从待查找节点列表里面取出一个，判断该节点是否是终点，如果不是则查找该节点的相邻节点，找到 3 个节点分别是右、右下、下。
遍历相邻节点，判断节点是否已查找过，否则对 3 个相邻节点的进行估价（因为使用曼哈顿算法所以把浮点数放大10倍），并把绿色节点设为 3 个相邻节点的父节点，如果某一相邻节点是终点则返回，否则把相邻节点加入到待查找节点列表。

1. 右
    起点距离该节点水平移动一个网格，所以g = 10。该节点到终点对角移动一个网格，所以h = 14。最终该节点的移动成本：14（f = g + h ）。
2. 右下
    起点距离该节点对角移动一个网格，所以g = 14。该节点到终点垂直移动一个网格，所以h = 10。最终该节点的移动成本：14（f = g + h ）。
3. 下
    起点距离该节点垂直移动一个网格，所以g = 10。该节点到终点水平移动两个网格，所以h = 20。最终该节点的移动成本：30（f = g + h ）。

对待查找节点列表按 f 值进行排序，取最小值。重复 2、3、4 步骤，直至找到终点坐标。

代码实现（附上完整代码）

首先最基础的是把地图进行网格化。

/*
地图从左上角开始，水平x 垂直y
  y
x 0,0 1,0 2,0
  0,1 1,1 2,1
  0,2 1,2 2,2
*/
// 0是可移动节点、1是障碍节点
mapData := [][]int{
    {0, 0, 1, 1, 0, 0, 0, 0},
    {0, 0, 0, 0, 1, 0, 0, 0},
    {0, 0, 0, 1, 1, 0, 0, 0},
    {0, 0, 0, 0, 1, 0, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0},
}

每个节点（网格）对应一个坐标，因为估价需要同时每个节点还存储着 f、g、h 值。

// 节点
type Node struct {
	// 坐标
	X int
	Y int
	// 成本
	F int
	G int
	H int
	// 父节点
	Parent *Node
	// 类型
	Type int
	// 状态
	State int
}

有了节点，那么还需要定义每个节点有哪些邻居（这里是 8 方向）

// 如果不允许对角移动，去除对角坐标
neighborPos = [][]int{
    {0, -1},  // 上
    {1, -1},  // 右上
    {1, 0},   // 右
    {1, 1},   // 右下
    {0, 1},   // 下
    {-1, 1},  // 左下
    {-1, 0},  // 左
    {-1, -1}, // 左上
}

并不是所有节点都需要查找，所以还需要定义待查找节点列表、已查找节点列表（已查找过的节点会被忽略）。

1	var openList, closeList []*Node

最后，查找节点的逻辑（这里偷懒，直接贴上封装过的逻辑）

type AStar struct {
	// 启发算法
	Heuristic func(node, end *Node) int
	// 地图大小
	Rows int // y
	Cols int // x
	// 地图节点
	nodes [][]*Node
	start *Node
	end   *Node
	// 开放、关闭列表
	openList  []*Node
	closeList []*Node
	// 相邻节点坐标
	neighborPos [][]int
}

func (r *AStar) FindPath(start, end *Node) *Node {
	r.start = r.nodes[start.X][start.Y]
	r.end = r.nodes[end.X][end.Y]
	// 如果起止点是障碍物
	if !r.start.isWalkable() || !r.end.isWalkable() {
		fmt.Println("障碍物不可移动")
		return nil
	}
	// 先把开始节点放进开放列表
	r.openListAppend(start)
	for len(r.openList) > 0 {
		node := r.openListPop()
		// 判断当前节点是否是终点
		if r.isEnd(node) {
			return node
		}
		// 找开放列表的第一个节点的相邻节点
		neighbors := r.findNeighbors(node)
		for _, neighbor := range neighbors {
			// 是否在关闭列表
			if neighbor.isClosed() {
				continue
			}
			// 开始节点移动至当前节点的成本
			// 相邻节点的坐标x,y
			// 开始节点移动至相邻节点的成本
			g, x, y := node.G, neighbor.X, neighbor.Y
			// 判断移动方式是水平（或垂直）、对角，计算成本
			if x == node.X || y == node.Y {
				g += COST_STRAIGHT
			} else {
				g += COST_DIAGONAL
			}
			if !neighbor.isOpened() || g < neighbor.G {
				neighbor.G = g
				neighbor.H = r.Heuristic(neighbor, end)
				neighbor.F = neighbor.G + neighbor.H
				neighbor.Parent = node
				// 优化逻辑，相邻节点是否是终点
				// if r.isEnd(neighbor) {
				// 	return neighbor
				// }
				if !neighbor.isOpened() {
					r.openListAppend(neighbor)
				}
			}
		}
		// 当前节点放进关闭列表
		r.closeListAppend(node)
		// 更新开放列表顺序
		r.openListSort()
	}
	return nil
}

为什么要给节点定义父节点？

这里使用链表记录移动路径，即通过终点节点不断迭代父节点打印出完整路径。

完整代码：astar