---

AStar算法

简介

Unity中提供了NavMesh导航寻路的AI功能，如果项目不涉及服务端它应该能满足大部分需求，但如果涉及服务端且使用状态同步技术，可能需要服务端同时实现寻路功能，这时就需要考虑其它实现思路，而AStar寻路算法则是常使用的一种。

AStar算法是一种静态路网中求解最短路径最有效的直接搜索方法，基于广度优先搜索（BFS）和Dijkstra算法，通过不断维护节点的代价来寻求代价最小的路径，代价的估价公式：F(N)=G(N) + H(N)。

• G：理解为起始节点到当前节点的代价；
• H：理解为当前节点到终节点的代价。

其它概念：

• 开放集合：记录所有被考虑用来寻找最短路径的节点集合；
• 封闭集合：记录不会被考虑用来寻找最短路径的节点集合。

算法思路：

• 将起始节点放入开放集合；
• While循环重复以下步骤，直到结束条件满足：
  • 在开放集合中寻找代价最小的节点，并把寻找到的节点作为Current当前节点；
  • 将获取到的当前节点从开放集合移除放入封闭集合；
  • 若当前节点已经是终节点，寻路结束，跳出While循环，否则继续执行以下操作；
  • 获取当前节点的邻节点，并对每个邻节点执行以下步骤：
    • 若邻节点为不可行走区域(障碍)或者邻节点已经在封闭集合中，不执行任何操作，Continue继续遍历下一个邻节点；
    • 若邻节点不在开放集合中，将其放入开放集合，并将Current当前节点赋值给该邻节点的父节点，计算、记录该邻节点的G、H代价；
    • 若邻节点在开放集合中，判断经Current当前节点到达该邻节点的G值是否小于原来的G值，若小于则将该邻节点的父节点设为当前节点，并重新计算该邻节点的G、H代价。
• 从终节点开始依次获取父节点放入一个列表，最终将列表做倒序操作就是最终寻路的路径。

实现

Node节点

地图网格由x * y个Node节点组成，定义节点类，变量包含节点的x、y索引值、父节点信息、G、H、F代价值以及是否为可行走区域的标识信息，代码如下：

namespace SK.Framework.AStar
{public class Node{public int x;public int y;/// <summary>/// 父节点/// </summary>public Node parent;/// <summary>/// 是否为可行走区域/// </summary>public bool IsWalkable { get; private set; }/// <summary>/// 起始节点到当前节点的代价/// </summary>public int gCost;/// <summary>/// 当前节点到终节点的代价/// </summary>public int hCost;/// <summary>/// 代价/// </summary>public int Cost { get { return gCost + hCost; } }public Node(int x, int y, bool isWalkable){this.x = x;this.y = y;IsWalkable = isWalkable;}}
}

节点间的估价

每向正上、下、左右方向走一步代价为1，根据勾股定理，每向斜方向走一步代价为$\sqrt{2}$，近似1.414，而为了便于计算、节省性能，我们将正方向移动一步的代价记为10，斜方向移动一步的代价记为14，都取int整数。

//计算两节点之间的代价
private int CalculateCost(Node n1, Node n2)
{//绝对值int deltaX = n1.x - n2.x;if (deltaX < 0) deltaX = -deltaX;int deltaY = n1.y - n2.y;if (deltaY < 0) deltaY = -deltaY;int delta = deltaX - deltaY;if (delta < 0) delta = -delta;//每向正上、下、左、右方向走一步代价增加10//每斜向走一步代价增加14(勾股定理，精确来说是近似14.14~)return 14 * (deltaX > deltaY ? deltaY : deltaX) + 10 * delta;
}

算法核心

/// <summary>
/// 根据起始节点和终节点获取路径
/// </summary>
/// <param name="startNode">起始节点</param>
/// <param name="endNode">终节点</param>
/// <returns>路径节点集合</returns>
public List<Node> GetPath(Node startNode, Node endNode)
{//开放集合List<Node> openCollection = new List<Node>();//封闭集合HashSet<Node> closeCollection = new HashSet<Node>();//起始节点放入开放集合openCollection.Add(startNode);//开放集合中数量为0时 寻路结束while (openCollection.Count > 0){//当前节点Node currentNode = openCollection[0];//遍历查找是否有代价更小的节点//若代价相同，选择移动到终点代价更小的节点for (int i = 1; i < openCollection.Count; i++){currentNode = (currentNode.Cost > openCollection[i].Cost|| (currentNode.Cost == openCollection[i].Cost&& currentNode.hCost > openCollection[i].hCost))? openCollection[i] : currentNode;}//将获取到的当前节点从开放集合移除放入封闭集合openCollection.Remove(currentNode);closeCollection.Add(currentNode);//当前节点已经是终节点 寻路结束if (currentNode == endNode)break;//获取邻节点List<Node> neighbourNodes = GetNeighbouringNodes(currentNode, SearchMode.Link8);//在当前节点向邻节点继续搜索for (int i = 0; i < neighbourNodes.Count; i++){Node neighbourNode = neighbourNodes[i];//判断邻节点是否为不可行走区域(障碍)或者邻节点已经在封闭集合中if (!neighbourNode.IsWalkable || closeCollection.Contains(neighbourNode))continue;//经当前节点到达该邻节点的G值是否小于原来的G值//或者该邻节点还没有放入开放集合，将其放入开放集合int cost = currentNode.gCost + CalculateCost(currentNode, neighbourNode);if (cost < neighbourNode.gCost || !openCollection.Contains(neighbourNode)){neighbourNode.gCost = cost;neighbourNode.hCost = CalculateCost(neighbourNode, endNode);neighbourNode.parent = currentNode;if (!openCollection.Contains(neighbourNode))openCollection.Add(neighbourNode);}}}//倒序获取父节点List<Node> path = new List<Node>();Node currNode = endNode;while (currNode != startNode){path.Add(currNode);currNode = currNode.parent;}//再次倒序后得到完整路径path.Reverse();return path;
}

邻节点的搜索方式

搜索邻节点时有两种搜索方式，四连通和八连通：

• 四连通：又称四邻域，是指对应节点的上、下、左、右四个方向为邻节点：

• 八连通：又称八邻域，是指对应节点的上、下、左、右、左上、右上、左下、右下八个方向为邻节点：

/// <summary>
/// 获取指定节点的邻节点
/// </summary>
/// <param name="node">指定节点</param>
/// <param name="searchMode">搜索方式 四连通/八连通</param>
/// <returns>邻节点列表</returns>
public List<Node> GetNeighbouringNodes(Node node, SearchMode searchMode)
{List<Node> neighbours = new List<Node>();switch (searchMode){case SearchMode.Link4:for (int i = -1; i <= 1; i++){if (i == 0) continue;int x = node.x + i;if (x >= 0 && x < this.x)neighbours.Add(nodesDic[x * this.x + node.y]);int y = node.y + i;if (y >= 0 && y < this.y)neighbours.Add(nodesDic[node.x * this.x + y]);}break;case SearchMode.Link8:for (int i = -1; i <= 1; i++){for (int j = -1; j <= 1; j++){if (i == 0 && j == 0) continue;int x = node.x + i;int y = node.y + j;if (x >= 0 && x < this.x && y >= 0 && y < this.y)neighbours.Add(nodesDic[x * this.x + y]);}}break;}return neighbours;
}

地图编辑器

简介

按住Ctrl + 鼠标左键绘制地图障碍区域（如图所示，红色框区域即为障碍区域）：

按住Alt + 鼠标左键绘制地图可行走区域（清除障碍区域）：

实现

绘制地图网格

• Grid X、Y组成地图网格（x * y）；
• Grid Size指定每个网格(节点)的大小：

//绘制地图网格
Handles.color = Color.cyan;
for (int i = 0; i <= x; i++)
{Vector3 start = i * size * Vector3.right;Vector3 end = start + y * size * Vector3.forward;Handles.DrawLine(start, end);
}
for (int i = 0; i <= y; i++)
{Vector3 start = i * size * Vector3.forward;Vector3 end = start + x * size * Vector3.right;Handles.DrawLine(start, end);
}

障碍/可行走区域

使用二维数组bool[,] map存储各节点网格是否为可行走区域

• Ctrl + 鼠标左键 标识障碍区域；
• Alt + 鼠标左键 标识可行走区域：

HandleUtility.AddDefaultControl(GUIUtility.GetControlID(FocusType.Passive));
//Ctrl + 鼠标左键 绘制障碍区域
//Alt + 鼠标左键 绘制可行走区域
var e = Event.current;
if (e != null && (e.control || e.alt) && (e.type == EventType.MouseDown || e.type == EventType.MouseDrag) && e.button == 0)
{Ray ray = HandleUtility.GUIPointToWorldRay(e.mousePosition);if (Physics.Raycast(ray, out RaycastHit hit)){int targetX = Mathf.CeilToInt(hit.point.x / size);int targetY = Mathf.CeilToInt(hit.point.z / size);if (targetX <= x && targetX > 0 && targetY <= y && targetY > 0){map[targetX - 1, targetY - 1] = !e.control;}}e.Use();
}//红色框绘制障碍区域
Handles.color = Color.red;
for (int m = 0; m < x; m++)
{for (int n = 0; n < y; n++){if (!map[m, n])Handles.DrawWireCube(new Vector3(m * size, 0f, n * size) + .5f * size * (Vector3.forward + Vector3.right), .9f * size * (Vector3.forward + Vector3.right));}
}

地图数据存储

由于地图数据存储于bool[,] map二维数组中，不支持序列化，因此将其转化为存储于Texture2D类型资产中，实现方式如下：

//生成地图
if (GUILayout.Button("Generate Map Data"))
{//选择保存路径string filePath = EditorUtility.SaveFilePanel("Save Map Data", Application.dataPath, "New Map Data", "asset");if (!string.IsNullOrEmpty(filePath)){//转化为Asset路径filePath = filePath.Substring(filePath.IndexOf("Assets"));//创建地图TexTexture2D bitmap = new Texture2D(x, y, TextureFormat.Alpha8, false);byte[] bytes = bitmap.GetRawTextureData();//默认全部为可行走区域for (int i = 0; i < bytes.Length; i++)bytes[i] = 0;for (int m = 0; m < x; m++){for (int n = 0; n < y; n++){//黑色存储障碍区域 白色存储可行走区域bytes[m * x + n] = (byte)(map[m, n] ? 255 : 0);}}bitmap.LoadRawTextureData(bytes);//创建、保存资产AssetDatabase.CreateAsset(bitmap, filePath);AssetDatabase.SaveAssets();AssetDatabase.Refresh();//选中EditorGUIUtility.PingObject(bitmap);}
}

源码以上传至SKFramework框架Package Manager中：