电脑如何做网站空间,河南建设监理协会官方网站,图书馆管理系统,可视化网站模板编辑软件A星寻路算法简介 A星寻路算法#xff08;A* Search Algorithm#xff09;是一种启发式搜索算法#xff0c;它在图形平面上进行搜索#xff0c;寻找从起始点到终点的最短路径。A星算法结合了广度优先搜索#xff08;BFS#xff09;和最佳优先搜索#xff08;Best-First S…A星寻路算法简介 A星寻路算法A* Search Algorithm是一种启发式搜索算法它在图形平面上进行搜索寻找从起始点到终点的最短路径。A星算法结合了广度优先搜索BFS和最佳优先搜索Best-First Search的特点通过使用启发式函数评估节点的重要性优先选择最有希望达到目标节点的节点进行扩展从而有效地缩小搜索范围。 A星寻路算法的核心概念
节点Node在图形平面上每个可移动的点都可以被视为一个节点。节点可以是地图上的障碍物、可移动的实体等。边Edge节点之间的连接称为边。在路径搜索中边通常表示可移动的路径或移动方向。代价函数Cost FunctionFGH,用于评估从起始节点到当前节点的代价。在A星算法中代价函数通常由两个部分组成实际代价Actual Cost和启发式代价Heuristic Cost。父节点Parent Node在搜索过程中每个节点都有一个指向其父节点的指针表示该节点是如何从父节点扩展而来的。开放列表Open List包含所有正在被考虑的节点。这些节点尚未被扩展且具有最小的实际代价启发式代价。关闭列表Closed List包含所有已经扩展过的节点。这些节点不再被考虑。
A星寻路算法的步骤
初始化设置起始节点和目标节点将起始节点添加到开放列表中。循环执行以下步骤直到开放列表为空或找到目标点 a. 从开放列表中选择具有最小代价的节点n并将其从开放列表中移除。 b. 将节点n添加到关闭列表中并遍历其所有相邻节点。对于每个相邻节点m
如果m不在关闭列表中计算从起始节点到m的实际代价g(m)g(m) g(nn到m的代价和启发式代价h(m)。如果m的代价小于其之前的代价或者m尚未设置父节点则将m的父节点设置为n并更新m的代价g(m)。将m添加到开放列表中。如果节点m是目标节点则找到了最短路径结束算法。
如果开放列表为空而未找到最短路径则说明存在无法达到目标的路径或目标不可达结束算法。输出最短路径从目标节点回溯到起始节点按照父节点指针依次访问节点得到最短路径。
代码实现
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using UnityEngine;//节点
public class AstarNode:IComparableAstarNode //继承接口实现重载排序方式
{public int x;//x坐标public int y;//y坐标public Vector2Int pos;//x,y坐标public int G;//起点到该点的距离public int H;//该点到终点的曼哈顿距离public int F;//F G Fpublic AstarNode() //无参构造函数{}public AstarNode(Vector2Int pos) //有参构造函数{this.pos pos;this.x pos.x;this.y pos.y;}public int CompareTo(AstarNode other) //排序方式{return this.F-other.F; //F小排在前}
}//A星
public class AStar
{bool result false;//单例模式public static AStar instance;public static AStar Instance{get{if(instancenull){instance new AStar();}return instance;}}//上右下左四个方向private Vector2Int[] directions new Vector2Int[]{new Vector2Int(1,0),new Vector2Int(0,1),new Vector2Int(-1,0),new Vector2Int(0,-1)};//上右下左//开放表private ListAstarNode openList new ListAstarNode();//关闭表但这里没用到用cameFrom代替了它的作用//private HashSetVector2Int closeList new HashSetVector2Int();//路径字典用来存储路径以及作为关闭表来判断该点是否已经走过private DictionaryVector2Int,Vector2Int cameFrom new DictionaryVector2Int, Vector2Int();//记录最终路径作为返回值private ListVector2Int path new ListVector2Int();//寻路方法public ListVector2Int FindPath(ListListTransform map,Vector2Int startP,Vector2Int targetP)//地图起点终点{Debug.Log(开始寻路);//计算起点G,H,F将起点加入开放表AstarNode rNode new AstarNode(startP);rNode.G 0;rNode.H Manhattan(rNode.pos,targetP);rNode.F rNode.GrNode.H;openList.Add(rNode);cameFrom[startP] new Vector2Int(-1,-1); //记录路径当前点坐标作为key上一个点的坐标作为value表示从上一个点坐标到达该点//循环直到找到路径或者开放表没有节点while(openList.Count0!result){//开放表以F为标准排序F小在前openList.Sort(); //取出开放表中F最小的节点AstarNode curNode openList[0];//取出的节点要从开放表中移除加入到关闭表openList.RemoveAt(0);//遍历这个点周围的四个方向foreach(Vector2Int dir in directions){Vector2Int newP curNode.posdir;//判断边界有没有超出地图范围if(newP.x0||newP.xmap.Count||newP.y0||newP.ymap[0].Count) //边界点判断{continue;}//判断是否在关闭表if(cameFrom.ContainsValue(newP)){continue;}//判断该点是否是障碍物if(!map[newP.x][newP.y].gameObject.GetComponentTile().CheckObstacle()){continue;}//查看是否在开放表AstarNode node openList.FirstOrDefault(p p.pos newP);//linq查询openlist中是否有该点的节点//不在开放表就计算G,H,F,加入开放表边的代价默认为1if(nodenull){//Debug.Log(添加);AstarNode newNode new AstarNode();newNode.pos newP;newNode.G curNode.G1;newNode.H Manhattan(newNode.pos,targetP);newNode.F newNode.GnewNode.H;cameFrom[newNode.pos] curNode.pos; //记录路径openList.Add(newNode);}else //在开放表判断当前路径代价是否更小是否要更新代价{//如果当前路径代价更小更新代价和路径if(node.G curNode.G1) {node.G curNode.G1;node.F node.Gnode.H;cameFrom[node.pos] curNode.pos;}}//如果当前点就是目标点则停止寻路if(curNode.pos targetP){result true;break;}}}//如果找到路径通过终点与cameFrom从后往前找到整条路径。if(result){//通过栈把路径节点转成从起点到终点StackVector2Int path_stack new StackVector2Int();Vector2Int pos targetP;path_stack.Push(targetP);//将节点压入栈内while(pos!startP){Vector2Int newP cameFrom[pos];pos newP;path_stack.Push(pos);}//将栈内节点弹出while(path_stack.Count0){pos path_stack.Pop();path.Add(pos);//Debug.Log(pos);}}else{Debug.Log(没找到);}return path;}public int Manhattan(Vector2Int a,Vector2Int b) //获取两点曼哈顿距离{return Mathf.Abs(a.x -b.x)Mathf.Abs(a.y-b.y);}}
这段代码通过传递地图网格地点和终点实现了简单的A星寻路算法。首先构建一个新的Astar节点设置为起点节点。起点的G为0H采用曼哈顿距离F G H。将起点节点加入到开放表。要取到开放表中F最小的节点因为数据量较小这里在每次从开放表取节点前都以F进行一次排序得到F最小节点用优先队列会更好。通过该节点访问其上右下左的四个点并判断这些点是否能够加入开放表坐标超出网格范围节点在关闭表节点是障碍点。都不能加入开放表关闭表使用字典存储在实现关闭表的同时还记录了节点之间的路径信息。最后判断坐标点是否在开放表不在开放表的点构建节点并加入开放表这里默认两点间的代价为1在开放表中的则判断新的路径中代价是否更小更小则更新代价和路径信息否则不做处理。最后判断坐标点是否为目标坐标如果是目标坐标即停止寻路。最后通过存储的路径信息找到完整路径。 A星寻路算法的优化技巧
合理选择启发式函数启发式函数用于估计从当前节点到目标节点的代价。选择合适的启发式函数能够提高算法的性能和准确性。常见的启发式函数有曼哈顿距离、欧几里得距离等。权重调整根据实际应用场景和需求可以对边的权重进行调整以优化搜索效率和找到更符合特定要求的路径。动态调整开放列表的大小在搜索过程中可以根据需要动态调整开放列表的大小以平衡搜索效率和内存消耗。利用优先队列进行节点排序将开放列表中的节点按照代价从小到大排序可以利用优先队列数据结构实现高效的排序操作从而提高算法性能。预处理和缓存在某些情况下可以对地图进行预处理或使用缓存机制来提高搜索效率。例如可以将一些已知的信息存储起来以便快速访问或者预先计算某些节点的代价等。多线程并行处理在多核处理器环境下可以利用多线程技术对不同区域或方向的搜索进行并行处理以提高算法的整体性能。局部搜索和回溯策略在搜索过程中可以结合局部搜索和回溯策略来优化路径选择和调整方向。当遇到局部最优解时可以通过回溯或尝试其他方向来寻找更好的解。增量式更新地图对于动态变化的地图环境可以采用增量式更新地图的方法来提高算法的适应性。当地图发生变化时只对变化区域进行重新搜索和处理而保持其他区域的搜索
A星寻路算法的应用 A星寻路算法广泛应用于游戏开发、机器人导航、路径规划等领域。以下是一些具体的应用场景
游戏开发在角色扮演游戏、策略游戏等类型中A星算法常被用于实现智能角色的寻路和移动。通过找到最短路径玩家可以更流畅地控制角色提高游戏的可玩性和体验。机器人导航在机器人领域A星算法用于指导机器人从起点到目标点的路径规划。这种算法能够帮助机器人避开障碍物选择最佳路径从而实现高效、安全的导航。路径规划在交通、物流等领域A星算法用于规划最短或最优路径。例如在物流配送中通过使用A星算法可以找到从起点到目的地的最短路径从而提高配送效率。图形编辑和可视化在处理复杂的图形数据时A星算法可以帮助找到从一个节点到另一个节点的最短路径从而进行高效的编辑和可视化操作。
总结 A星寻路算法是一种高效、实用的路径搜索算法它结合了广度优先搜索和最佳优先搜索的特点通过启发式函数评估节点的重要性从而快速找到最短路径。通过合理的优化技巧A星算法能够适多种应用场景提高性能和准确性。
