如何在Unity中实现AStar寻路算法及地图编辑器

文章目录

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代价值以及是否为可行走区域的标识信息，代码如下：

namespaceSK.Framework.AStar{publicclassNode{publicint x;publicint y;/// <summary>/// 父节点/// </summary>publicNode parent;/// <summary>/// 是否为可行走区域/// </summary>publicbool IsWalkable {get;privateset;}/// <summary>/// 起始节点到当前节点的代价/// </summary>publicint gCost;/// <summary>/// 当前节点到终节点的代价/// </summary>publicint hCost;/// <summary>/// 代价/// </summary>publicint Cost {get{return gCost + hCost;}}publicNode(int x,int y,bool isWalkable){this.x = x;this.y = y;
            IsWalkable = isWalkable;}}}

节点间的估价

每向正上、下、左右方向走一步代价为1，根据勾股定理，每向斜方向走一步代价为

     2
    
   
  
  
   \sqrt{2}
  
 
2​，近似1.414，而为了便于计算、节省性能，我们将正方向移动一步的代价记为10，斜方向移动一步的代价记为14，都取

int

整数。

//计算两节点之间的代价privateintCalculateCost(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~)return14*(deltaX >deltaY ? deltaY : deltaX)+10* delta;}

算法核心

/// <summary>/// 根据起始节点和终节点获取路径/// </summary>/// <param name="startNode">起始节点</param>/// <param name="endNode">终节点</param>/// <returns>路径节点集合</returns>publicList<Node>GetPath(Node startNode,Node endNode){//开放集合List<Node> openCollection =newList<Node>();//封闭集合HashSet<Node> closeCollection =newHashSet<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 =newList<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>publicList<Node>GetNeighbouringNodes(Node node,SearchMode searchMode){List<Node> neighbours =newList<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,outRaycastHit 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(newVector3(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 =newTexture2D(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

中：