# 前言

最近又重新学习 Cocos 了，发现几年前写过一片关于 A * 算法的 demo，正好复习一下 A * 算法吧～

# 定义

A * 算法是一种路径搜索算法，是广度优先搜索算法（BFS）的一种优化。

# 广度优先搜索算法 (BFS)

BFS 是连通图的一种遍历策略，从原点开始，依次向四周遍历，遍历过的点做个标记，下次不再遍历当前点，从四周遍历点继续往下遍历，直到遍历到目标位置。

作为一种暴力的搜索算法，缺点还是十分明显的，当起始点在左下角，终点在右上角时，BFS 会去搜索全图才能搜索到目标点，这是很低效的一种做法。

# A * 算法

作为 BFS 的一种优化算法，A * 提出了 启发函数 这个概念

F=G+H
F: 预估代价
G: 当前点跟原点的步长 (即从原点到当前点经过了多少次)
H: 当前点与终点的距离

类似于取权重值的一种做法，A * 将 BFS 遍历四周的点改为优先遍历四周中 F 值最低的一个点，再以此点深度取 F 值遍历。

# H 的取值算法

曼哈顿距离
H = 当前点与目标点的 xy 坐标差值的绝对值和

$H=|x_{1}-x_{2}|+|y_{1}-y_{2}|$

欧几里得距离
H = 当前点与目标点的距离

$H=\sqrt{(x_{1}-x_{2})^2+(y_{1}-y_{2})^2}$

# 参考教程

奇乐编程学院

Introduction to the A* Algorithm
文档链接

# 项目示例

项目地址:Cocos_AStar

# 代码说明

MapData: 地图配置，这里用二维数组表示

	export interface MapData {
	row: number, // 地图行数
	column: number, // 地图列数
	map: number[][]
	}

	export enum MapType {
	road = 0, // 地形
	obstacle, // 障碍
	beginPos, // 开始位置
	endPos, // 结束位置
	}

point: 点类，用于记录当前点坐标与前一个寻路点。AStarData: 用于代价预估，标记此点是否走过

	export interface point{
	x:number,
	y:number,
	parentNode:point
	}

	export interface AStarData{
	isCanWalk:boolean; // 这个点是否能走
	pointNode:point, // 当前节点数据
	F:number, // 当前点到终点的代价
	G:number, // 起点到当前点的代价
	H:number // 当前点到终点的预估代价（忽略障碍，计算直线距离的代价值）
	}

initTempMapData: 生成地图数据

	// 根据配置文件生成初始的地图数据数组
	private initTempMapData(data:MapData){
	let row = data.row;
	let col = data.column;
	let map = data.map;
	for(let i=0;i<row;i++){
	if(!this._pathMapsData[i]){
	this._pathMapsData[i] = [];
	}
	for(let j=0;j<col;j++){
	let type = map[i][j];
	let isCanWalk = true;
	if(type == MapType.beginPos){
	this._curPos.x = i;
	this._curPos.y = j;
	this._startPos = this._curPos;
	}else if(type == MapType.endPos){
	this._endPos.x=i;
	this._endPos.y=j;
	}else if(type==MapType.obstacle){
	isCanWalk = false;
	}
	let aStarData:AStarData = {
	isCanWalk:isCanWalk,
	pointNode:{x:i,y:j,parentNode:null},
	F:this._defaultCost,
	G:this._defaultCost,
	H:this._defaultCost
	}
	this._pathMapsData[i][j] = aStarData;
	}
	}
	}

aStarCalculate: 计算当前数据地图对应的最短路径

	// 开启 a * 算法搜索最短路径
	private aStarCalculate(){
	//_openList:open 列表，用于更新每个点的最小代价值，因为一个点可能由周围 4 个点遍历到，所以要拿这个列表用于保存此点的最小代价方向，矫正 parentNode 指向
	//_closeList:close 列表，用于存储每次 while 结束后的搜索到的路径列表

	//1.0 将初始点放入 openList 中
	this._openList.push(this._curPos);
	while(true){
	//2.0 判断 openList 如果为空则搜索失败，如果存在目标点则搜索成功
	let length = this._openList.length;
	if(length<=0) {
	console.error('搜索失败!!!');
	this._isSearchSuccess = false;
	break;
	}
	if(this.checkIsInOpenList(this._endPos.x,this._endPos.y)>=0){
	console.log('搜索成功!!!');
	this._endPos.parentNode = this._curPos;
	this._closeList.push(this._endPos);
	this._isSearchSuccess = true;
	break;
	}
	//3.0 从 openList 中选出 F 值最小的节点作为当前节点，并将其加入到 closeList 中
	let minNode:point = this.getMinFPointFromOpenList();
	let x = minNode.x;
	let y = minNode.y;
	this._curPos = minNode;
	let opIdx = this.checkIsInOpenList(x,y);
	this._openList.splice(opIdx,1);
	this._closeList.push(minNode);

	//4.0 计算当前节点的相邻的所有可到达节点，根据最小代价点重置当前点 parent 指向
	for(let i=0;i<4;i++){
	switch(i){
	case MoveDir.up:{
	this.doCalculateCost(x,y+1);
	break;
	}
	case MoveDir.down:{
	this.doCalculateCost(x,y-1);
	break;
	}
	case MoveDir.left:{
	this.doCalculateCost(x-1,y);
	break;
	}
	case MoveDir.right:{
	this.doCalculateCost(x+1,y);
	break;
	}
	}
	}
	}
	}

doCalculateCost: 计算当前节点代价，根据最小代价点重置当前点 parent 指向

	// 计算代价
	private doCalculateCost(x,y){
	// 如果该节点在 close 列表中，则不检查
	let idx = this.checkIsInCloseList(x,y);
	if(idx>=0){
	return;
	}

	let data = this.getPathMapDataByXY(x,y);
	if(!data) return;
	if(!data.isCanWalk) return;


	// 如果该节点在 open 列表中，则检查其通过当前节点计算得到的 F 值是否更小，如果更小则更新其 F 值，并将其父节点设置为当前节点
	let opIdx = this.checkIsInOpenList(x,y);
	if(opIdx>=0){
	// 监测点的 F 值
	let point:point = this._openList[opIdx];
	let curF = data.F;

	// 当前节点父节点的值
	let pNode = this._curPos.parentNode;
	let pData = this.getPathMapDataByXY(pNode.x,pNode.y);
	let pF = pData.F;

	if(curF<pF){
	this._curPos.parentNode = point;
	}

	}else{
	// 如果该节点不在 open 列表中，则将其加入到 open 列表，并计算 F 值，设置其父节点为当前节点。
	let point:point = {
	x:x,
	y:y,
	parentNode:this._curPos
	}
	// 曼哈顿距离算法，_cost 为移动权重，可为不同方向配置不同权重
	data.G = (Math.abs(this._startPos.x-x)+Math.abs(this._startPos.y-y))*this._cost;
	data.H = (Math.abs(this._endPos.x-x)+Math.abs(this._endPos.y-y))*this._cost;
	data.F = data.G+data.H;
	this._pathMapsData[x][y] = data;
	this._openList.push(point);
	}
	}