承接网站网站建设,免费icp备案服务码,玩客云 做网站服务器,黑帽seo教程文章目录AStar算法简介实现Node节点节点间的估价算法核心邻节点的搜索方式地图编辑器简介实现绘制地图网格障碍/可行走区域地图数据存储AStar算法 简介
Unity中提供了NavMesh导航寻路的AI功能#xff0c;如果项目不涉及服务端它应该能满足大部分需求#xff0c;但如果涉及服…
文章目录AStar算法简介实现Node节点节点间的估价算法核心邻节点的搜索方式地图编辑器简介实现绘制地图网格障碍/可行走区域地图数据存储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/// 父节点/// /summarypublic Node parent;/// summary/// 是否为可行走区域/// /summarypublic bool IsWalkable { get; private set; }/// summary/// 起始节点到当前节点的代价/// /summarypublic int gCost;/// summary/// 当前节点到终节点的代价/// /summarypublic int hCost;/// summary/// 代价/// /summarypublic int Cost { get { return gCost hCost; } }public Node(int x, int y, bool isWalkable){this.x x;this.y y;IsWalkable isWalkable;}}
}节点间的估价
每向正上、下、左右方向走一步代价为1根据勾股定理每向斜方向走一步代价为2\sqrt{2}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 namestartNode起始节点/param
/// param nameendNode终节点/param
/// returns路径节点集合/returns
public ListNode GetPath(Node startNode, Node endNode)
{//开放集合ListNode openCollection new ListNode();//封闭集合HashSetNode closeCollection new HashSetNode();//起始节点放入开放集合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;//获取邻节点ListNode 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);}}}//倒序获取父节点ListNode path new ListNode();Node currNode endNode;while (currNode ! startNode){path.Add(currNode);currNode currNode.parent;}//再次倒序后得到完整路径path.Reverse();return path;
}邻节点的搜索方式
搜索邻节点时有两种搜索方式四连通和八连通
四连通又称四邻域是指对应节点的上、下、左、右四个方向为邻节点 八连通又称八邻域是指对应节点的上、下、左、右、左上、右上、左下、右下八个方向为邻节点 /// summary
/// 获取指定节点的邻节点
/// /summary
/// param namenode指定节点/param
/// param namesearchMode搜索方式 四连通/八连通/param
/// returns邻节点列表/returns
public ListNode GetNeighbouringNodes(Node node, SearchMode searchMode)
{ListNode neighbours new ListNode();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 * yGrid 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中
