数据结构与算法 - JPS

2022-08-12

全文 ≈ 1.8k字 | 预计阅读时长 7分钟

JPS 寻路算法是基于 A*计算过程中查找节点冗余、效率较低等问题优化的一种算法。

背景

A*是比较常见的寻路算法，但存在一个较为明显的问题，当移动到新的节点总是会把相邻节点（4、8）加入到待查找列表。这样带来两个问题

在多条移动路径成本相同时，冗余查找。
待查找节点过多，内存使用率过高。

JPS

JPS 全称“Jump search point”，又称“跳点搜索”、“拐点搜索”，由两位澳大利亚教授 2011 年提出（论文）。

JPS 寻路算法保留 A*的主体逻辑，不一样的是 JPS 只会把感兴趣的节点加入到待查找列表，怎样计算出感兴趣的节点呢？以下 2 个概念眼熟一下

强迫邻居
跳点（拐点）

通过有没有强迫邻居判断当前节点是否跳点，也就是感兴趣的节点。

强迫邻居

强迫邻居的定义：

节点 x 的 8 个邻居中有障碍，且 x 的父节点 p 经过 x 到达 n 的距离代价比不经过 x 到达的 n 的任意路径的距离代价小，则称 n 是 x 的强迫邻居。

允许对角移动的情况下，检索方向强迫邻居节点的方式分为 3 种：对角、垂直、水平。

对角移动

垂直移动

水平移动

绿色是父节点，红色是障碍物，x 是当前节点，n 是强迫邻居。

通俗的解释就是，在指定移动方向上“强迫”当前节点改变移动方向的节点就是当前节点的强迫邻居，同时当前节点也是跳点，跳点和强迫邻居都相邻障碍节点。

跳点（拐点）

知道如果有强迫邻居改变当前节点移动方向，那么当前节点就被视为跳点，这是判断跳点的条件之一。判断当前节点是否跳点的任一条件：

当前节点是起点或终点。
当前节点拥有强迫邻居。
如果移动方向是对角移动，当前节点的垂直、水平方向上的节点满足条件 1 或条件 2，当前节点一样被视为跳点。

条件 3 可能有些难理解，示意图:

黄色网格 1、2、3 都是跳点，网格 1 因为满足“当前节点的垂直、水平方向上的节点满足条件 1 或条件 2，当前节点一样被视为跳点”条件（网格 2 是跳点），所以也是跳点。

寻路思路

把起点放进待查找节点列表。
从待查找节点列表里面取出一个，判断该节点是否是终点，如果不是则查找该节点的相邻节点。
遍历相邻节点，判断节点是否已查找过，否则对相邻节点进行跳点查找并对跳点进行估价，同时把当前节点设为跳点到父节点，如果跳点是终点则返回，否则把跳点加入到待查找节点列表。
对待查找节点列表按 f 值进行排序，取最小值。重复 2、3、4 步骤，直至找到终点坐标（最终的跳点）。

完整的寻路过程：

以上寻路过程，JPS 和 A*寻路过程的区别在于跳点查找：

// 跳点函数
// 判断当前点是否满足跳点条件
func (r *Jps) jump(node, parent *Node) *Node {
	// 是终点，直接返回
	if r.isEnd(node) {
		return node
	}
	x, y := node.X, node.Y
	dx, dy := r.direction(node, parent)
	// 对角移动
	if dx != 0 && dy != 0 {
		// [左|右]不能走 && [左上|左下|右上|右下]能走
		if !r.isWalkable(x-dx, y) && r.isWalkable(x-dx, y+dy) {
			return node
		}
		// [上|下]不能走 && [左上|右上|左下|右下]能走
		if !r.isWalkable(x, y-dy) && r.isWalkable(x+dx, y-dy) {
			return node
		}
		// 递归查找方向[上|下]继续查找
		if r.isWalkable(x+dx, y) && r.jump(r.nodes[x+dx][y], node) != nil {
			return node
		}
		// 递归查找方向[左|右]继续查找
		if r.isWalkable(x, y+dy) && r.jump(r.nodes[x][y+dy], node) != nil {
			return node
		}
	} else if dx == 0 { // 垂直移动
		// 右不能走 && [右下|右上]能走
		if !r.isWalkable(x+1, y) && r.isWalkable(x+1, y+dy) {
			return node
		}
		// 左不能走 && [左上|左下]能走
		if !r.isWalkable(x-1, y) && r.isWalkable(x-1, y+dy) {
			return node
		}
	} else { // 水平移动
		// 下不能走 && [左下|右下]能走
		if !r.isWalkable(x, y+1) && r.isWalkable(x+dx, y+1) {
			return node
		}
		// 上不能走 && [左上|右上]能走
		if !r.isWalkable(x, y-1) && r.isWalkable(x+dx, y-1) {
			return node
		}
	}
	// 递归查找方向[左上|左下|右上|右下]继续查找
	if r.isWalkable(x+dx, y+dy) {
		if next := r.jump(r.nodes[x+dx][y+dy], node); next != nil {
			return next
		}
	}
	// 无强迫邻居（当前节点不是跳点）或到达边界
	return nil
}

同时，为了减少查找不必要的节点，查找相邻节点的函数也有优化

// 查找相邻节点位置
func (r *Jps) findNeighbors(node *Node) []*Node {
	neighbors := make([]*Node, 0)
	// 第一次移动
	if node.Parent == nil {
		for _, v := range r.neighborPos {
			x, y := node.X+v[0], node.Y+v[1]
			// 检测节点是否非法
			if !r.isWalkable(x, y) {
				continue
			}
			neighbors = append(neighbors, r.nodes[x][y])
		}
	} else {
		// 计算当前节点位于父节点的方向：水平、垂直和对角方向
		x, y := node.X, node.Y
		dx, dy := r.direction(node, node.Parent)
		// 移动方向上的下一个
		if r.isWalkable(x+dx, y+dy) {
			neighbors = append(neighbors, r.nodes[x+dx][y+dy])
		}
		// 对角移动
		if dx != 0 && dy != 0 {
			// [左|右]能走
			if r.isWalkable(x+dx, y) {
				neighbors = append(neighbors, r.nodes[x+dx][y])
			}
			// [上|下]能走
			if r.isWalkable(x, y+dy) {
				neighbors = append(neighbors, r.nodes[x][y+dy])
			}
			// [左|右]不能走 && [左上|左下|右上|右下]能走
			if !r.isWalkable(x-dx, y) && r.isWalkable(x-dx, y+dy) {
				neighbors = append(neighbors, r.nodes[x-dx][y+dy])
			}
			// [上|下]不能走 && [左上|右上|左下|右下]能走
			if !r.isWalkable(x, y-dy) && r.isWalkable(x+dx, y-dy) {
				neighbors = append(neighbors, r.nodes[x+dx][y-dy])
			}
		} else if dx == 0 { // 垂直移动
			// 右不能走 && [右下|右上]能走
			if !r.isWalkable(x+1, y) && r.isWalkable(x+1, y+dy) {
				neighbors = append(neighbors, r.nodes[x+1][y+dy])
			}
			// 左不能走 && [左上|左下]能走
			if !r.isWalkable(x-1, y) && r.isWalkable(x-1, y+dy) {
				neighbors = append(neighbors, r.nodes[x-1][y+dy])
			}
		} else { // 水平移动
			// 下不能走 && [左下|右下]能走
			if !r.isWalkable(x, y+1) && r.isWalkable(x+dx, y+1) {
				neighbors = append(neighbors, r.nodes[x+dx][y+1])
			}
			// 上不能走 && [左上|右上]能走
			if !r.isWalkable(x, y-1) && r.isWalkable(x+dx, y-1) {
				neighbors = append(neighbors, r.nodes[x+dx][y-1])
			}
		}
	}
	return neighbors
}

完整代码：jps

关于其他优化点

有很多值得优化的细节，

因为是网格寻路，客户端角色走路会出现拐直角的表现（平滑路径，比如：弗洛伊德算法）。
待查找节点列表可以用二叉堆实现，插入和弹出效率都很高。
地图节点使用数组存储，检索效率较高。