什么是营销型网站建设,短网址生成器app,福清网络营销,软件开发公司架构本实验寻路算法均基于网格实现#xff0c;整体称呼为Grid#xff0c;单个瓦片称之为Tile
考虑程序处理的简洁性#xff0c;所有算法使用同一种Tile#xff0c;且权值点#xff0c;A*所需的记录数值也全部放在Tile中记录
前排贴上代码仓库链接#xff1a;
GitHub - Sir…本实验寻路算法均基于网格实现整体称呼为Grid单个瓦片称之为Tile
考虑程序处理的简洁性所有算法使用同一种Tile且权值点A*所需的记录数值也全部放在Tile中记录
前排贴上代码仓库链接
GitHub - Sirokus/Unity-Pathfinding-Project: 内置了BFSDFSGBFSDijkstraA*有权A*无权的寻路函数以及一个能够控制大小障碍物起始点和终点的网格系统仅供个人了解原理使用 数据结构
首先是Tile的数据结构
已剪除不必要的代码保证逻辑清晰
public class Tile : MonoBehaviour
{public bool walkable;public bool visited;public Tile pre;public float cost 1;//A*所需public float G;public float H;public float F G H;public void setWalkable(bool canWalk){walkable canWalk;}public int GetManhattanDistance(Tile tile){Vector2Int aCoord Grid.getCoordByTile(this);Vector2Int bCoord Grid.getCoordByTile(tile);return Mathf.Abs(aCoord.x - bCoord.x) Mathf.Abs(aCoord.y - bCoord.y);}
}
接着是Grid
鉴于Grid中集中了大量业务代码此处只贴出部分有用的函数内容
Grid中存储着所有的格子并提供格子和索引之间的转换以下是具体方式
public static Vector2Int getCoordByTile(Tile tile)
{return new Vector2Int((int)tile.transform.localPosition.x, (int)tile.transform.localPosition.y);
}
public static Tile getTileByCoord(Vector2Int coord)
{if (coord.x 0 || coord.y 0 || coord.x Grid.ins.gridSize.x || coord.y Grid.ins.gridSize.y)return null;return Grid.ins.tiles[coord.x][coord.y];
} 接着是关键的寻路代码
BFS寻路算法
以下是BFS代码为了能够运行时观看寻路过程因此所有寻路代码皆使用协程实现
BFS的基本思想是从出发点开始向四周所有可以行走的节点进行访问并在碰到目标值后停止
BFS是不考虑权值的
IEnumerator BfsPathFindingTask()
{QueueTile queue new QueueTile(); //遍历队列DictionaryTile, Tile came_from new DictionaryTile, Tile(); //前驱队列queue.Enqueue(start);came_from[start] null;while(queue.Count 0){//访问当前TileTile cur queue.Dequeue();Vector2Int curCoord getCoordByTile(cur);//依次访问其四个邻居若可行走且未被访问过则入队foreach(var d in dir){//获取邻居坐标Vector2Int tmp curCoord d;//按坐标获取邻居Tile neighbor getTileByCoord(tmp);//确保邻居可访问且没有前驱没有访问过if (neighbor neighbor.walkable !came_from.ContainsKey(neighbor)){if(neighbor ! end){neighbor.setColor(Color.black, VisitedColorBlendLerp);}//入队该邻居标记已访问记录其父tilequeue.Enqueue(neighbor);came_from[neighbor] cur;//终止条件if(CheckFindPathComplete(neighbor, came_from))yield break;}}if(ShowProcess)yield return new WaitForSeconds(0.001f / (0.001f * speedMultiple));}
} DFS寻路算法
我写的这个就是纯搞笑的算法它会向一个方向一直探测转向直到走无可走再从下一个相邻点进行行走
也就是说这个不是一个启发式算法目标肯定是可以找到的但中间要走多少个弯就只有天知道了
不过review一下发现写的还挺长的
IEnumerator DfsPathFindingTask(Tile tile, System.Action isDone)
{if(end.visited || !tile){isDone();yield break;}tile.visited true;Vector2Int cur getCoordByTile(tile);Tile neighbor null;float minDis float.MaxValue;foreach(var d in dir){Vector2Int tmp cur d;Tile tmpTile getTileByCoord(tmp);if(tmpTile tmpTile.walkable !tmpTile.visited){float dis Vector2.Distance(tmp, endCoord);if(dis minDis){neighbor tmpTile;minDis dis;}}} if(neighbor){if(neighbor ! end){neighbor.setColor(Color.black, VisitedColorBlendLerp);}neighbor.visited true;neighbor.pre tile;if(neighbor end){float costCount neighbor.cost;neighbor neighbor.pre;ListTile path new ListTile();while(neighbor ! start){costCount neighbor.cost;path.Add(neighbor);neighbor neighbor.pre;}costCount start.cost;Debug.Log(costCount);path.Reverse();foreach(Tile t in path){t.setColor(Color.green, 0.5f);yield return new WaitForSeconds(0.02f);}yield break;}if(ShowProcess)yield return new WaitForSeconds(0.01f / (0.01f * speedMultiple));bool isdone false;coroutines.Add(StartCoroutine(DfsPathFindingTask(neighbor, () { isdone true; })));yield return new WaitUntil(() isdone);}else{bool isdone false;coroutines.Add(StartCoroutine(DfsPathFindingTask(tile.pre, () { isdone true; })));yield return new WaitUntil(() isdone);}isDone();
}
GBFS寻路算法
GBFS是在BFS基础上进行改进的算法G代表Greedy贪心这是一个启发式算法这意味着其知道终点的位置并且会一直向理论最靠近终点的位置靠近
这也代表如果其和目标中间有个墙角其也会先深入墙角再沿着墙走出来找到目标因为其不考虑已付出代价 IEnumerator GBfsPathFindingTask(){SortedDictionaryfloat, LinkedListTile queue new SortedDictionaryfloat, LinkedListTile(){{0, new LinkedListTile()}};DictionaryTile, Tile came_from new DictionaryTile, Tile();queue[0].AddLast(start);came_from[start] null;Vector2Int endCoord getCoordByTile(end);while(queue.Count 0){//访问当前TileTile cur queue.First().Value.First();//当前Tile出队if(queue.First().Value.Count 1)queue.First().Value.RemoveFirst();elsequeue.Remove(queue.First().Key);//获取当前Tile坐标Vector2Int curCoord getCoordByTile(cur);//依次访问其四个邻居若可行走且未被访问过则入队foreach(var d in dir){//计算邻居坐标Vector2Int tmp curCoord d;//按坐标获取邻居Tile neighbor getTileByCoord(tmp);//确保邻居可访问if (neighbor neighbor.walkable !came_from.ContainsKey(neighbor)){//计算优先级float priority Vector2Int.Distance(tmp, endCoord);//入队if(!queue.ContainsKey(priority))queue.Add(priority, new LinkedListTile());queue[priority].AddLast(neighbor);//设置前驱came_from[neighbor] cur;//终止条件if(CheckFindPathComplete(neighbor, came_from))yield break;}}if(ShowProcess)yield return new WaitForSeconds(0.01f / (0.01f * speedMultiple));}}
Dijkstra寻路算法
该算法不是一个启发式算法但该算法能够根据不同权值找到最优路径一定最优其几乎相当于一个广度优先的有权版本其会评估路上每一个的已付出代价并选择付出代价最小的节点进行扩展当找到一个已访问结点的更优路径时还会修改其前驱
IEnumerator DijkstraPathFindingTask()
{SortedDictionaryfloat, LinkedListTile queue new SortedDictionaryfloat, LinkedListTile(){{0, new LinkedListTile()}};DictionaryTile, Tile came_from new DictionaryTile, Tile();DictionaryTile, float cost_so_far new DictionaryTile, float();queue[0].AddLast(start);came_from[start] null;cost_so_far[start] 0;while(queue.Count 0){//访问当前TileTile cur queue.First().Value.First();//当前Tile出队if(queue.First().Value.Count 1)queue.First().Value.RemoveFirst();elsequeue.Remove(queue.First().Key);//获取当前Tile坐标Vector2Int curCoord getCoordByTile(cur);//依次访问其四个邻居若可行走且未被访问过则入队foreach(var d in dir){//计算邻居坐标Vector2Int tmp curCoord d;//按坐标获取邻居Tile neighbor getTileByCoord(tmp);if(!neighbor)continue;//计算costfloat new_cost cost_so_far[cur] neighbor.cost;//可行走且第一次走或者此为更优路线if (neighbor.walkable (!cost_so_far.ContainsKey(neighbor) || new_cost cost_so_far[neighbor])){if(neighbor ! end){neighbor.setColor(Color.black, VisitedColorBlendLerp);}//入队if(!queue.ContainsKey(new_cost))queue.Add(new_cost, new LinkedListTile());queue[new_cost].AddLast(neighbor);//设置前驱came_from[neighbor] cur;//更新costcost_so_far[neighbor] new_cost;//终止条件if(CheckFindPathComplete(neighbor, came_from))yield break;}}if(ShowProcess)yield return new WaitForSeconds(0.001f / (0.001f * speedMultiple));}
}
A*寻路算法
A*寻路算法是非常著名的寻路算法其相当于一个混合算法其存在一个启发函数
即 F G H C
G 已经付出的代价类似Dijkstra
H 预估到达目标代价类似GBFS
C 用户自定义算法可用于实现一些A*寻路的特殊偏好如减少拐点等
A*的H计算可以计算欧式距离或者曼哈顿距离通常使用后者因为计算机计算起来比需要平方根的欧氏距离更快方便大量计算
Tips我在算法中还额外使用了向量的叉乘使得寻路时会更倾向于扩展朝向目标的点而非扩展更远的点
IEnumerator AStarPathFindingTask()
{SortedDictionaryfloat, LinkedListTile openQueue new SortedDictionaryfloat, LinkedListTile(){{0, new LinkedListTile()}};DictionaryTile, Tile preDic new DictionaryTile, Tile();DictionaryTile, float costDic new DictionaryTile, float();//用start初始化容器openQueue[0].AddLast(start);preDic[start] null;costDic[start] 0;Vector2Int endCoord getCoordByTile(end);bool wait;while(openQueue.Count 0){wait false;//访问当前TileTile cur openQueue.First().Value.First();//当前Tile出队if(openQueue.First().Value.Count 1)openQueue.First().Value.RemoveFirst();elseopenQueue.Remove(openQueue.First().Key);//获取当前Tile坐标Vector2Int curCoord getCoordByTile(cur);//依次访问其四个邻居若可行走且未被访问过则入队foreach(var d in dir){//计算邻居坐标Vector2Int tmp curCoord d;//按坐标获取邻居Tile neighbor getTileByCoord(tmp);if(!neighbor)continue;//计算邻居的Costfloat new_cost costDic[cur] neighbor.cost;//可行走且第一次走或者此为更优路线if (neighbor.walkable (!costDic.ContainsKey(neighbor) || new_cost costDic[neighbor])){if(neighbor ! end){neighbor.setColor(Color.black, VisitedColorBlendLerp);}//更新costG)costDic[neighbor] new_cost;//F GHswitch中主要是不同的H的计算方式switch(AStarType){case 0:new_cost Vector2Int.Distance(tmp, endCoord);break;case 1:float dx Mathf.Abs(tmp.x - endCoord.x);float dy Mathf.Abs(tmp.y - endCoord.y);new_cost dx dy (Mathf.Sqrt(2) - 2) * Mathf.Min(dx, dy);break;case 2:float dx1 Mathf.Abs(tmp.x - endCoord.x);float dy1 Mathf.Abs(tmp.y - endCoord.y);float dx2 Mathf.Abs(startCoord.x - endCoord.x);float dy2 Mathf.Abs(startCoord.y - endCoord.y);float cross dx1 * dy2 - dx2 * dy1;new_cost neighbor.GetManhattanDistance(end) (cross 0 ? (cross 1) * -2 : cross) * AstarCrossMultiple;break;}//入队if(!openQueue.ContainsKey(new_cost))openQueue.Add(new_cost, new LinkedListTile());openQueue[new_cost].AddLast(neighbor);//记录前驱preDic[neighbor] cur;//终止条件if(CheckFindPathComplete(neighbor, preDic))yield break;wait true;}}if(wait ShowProcess)yield return new WaitForSeconds(0.001f / (0.001f * speedMultiple));}
}
