扁平化配色方案网站,网站建设开发服务费会计科目,app制作教程电脑流程,传奇在线玩网页版A*#xff08;A-star#xff09;是一种图遍历和寻路算法#xff0c;由于其完整性、最优性和最佳效率#xff0c;它被用于计算机科学的许多领域。给定一个加权图、一个源节点和一个目标节点#xff0c;该算法将找到从源到目标的最短路径#xff08;相对于给定的权重#…A*A-star是一种图遍历和寻路算法由于其完整性、最优性和最佳效率它被用于计算机科学的许多领域。给定一个加权图、一个源节点和一个目标节点该算法将找到从源到目标的最短路径相对于给定的权重。
算法过程遍历方向为从竖直向上沿顺时针方向。
1.首先计算开始节点的G,H,F值将开始节点放入检测列表中。
2.将检测列表中的所有点按到目标所需的成本的估计值F排序选择F最小的节点作为当前节点。
3.将当前点从检测列表中移除加入到已检测列表中。
4.计算当前点周围的八个点G,H,F值将不包含在检测列表中的点加入到检测列表。
5.重复234,直到找到目标点。
注
F g n hn
gn 是从起始节点到 n 的路径的成本hn 是一个启发式函数用于估计从 n 到目标的最便宜路径的成本。
代码实现
改造路径点数据类
public class DataNode
{public Vector2Int pos;public DataNode parent;//A*使用public int gCost 999999999;public int hCost;public int fCost;public DataNode(Vector2Int pos, DataNode parent){this.pos pos;this.parent parent;}//A*使用计算Fpublic void CalculateFCost(){fCost gCost hCost;}
}
算法类
public class AStar : FindPathAlgorithm
{public AStar(int[,] mapData, int xCount, int zCount) : base(mapData, xCount, zCount){}public override ListVector2Int FindPath(Vector2Int startPos, Vector2Int goalPos){DataNode dataNode this.AStarFind(startPos, goalPos);if (dataNode null){Debug.LogError(寻路有误请检查参数是否正确);return null;}return Utils.GetPath(dataNode);}DataNode AStarFind(Vector2Int startPos, Vector2Int goalPos){//存储要检测的点ListDataNode frontier new ListDataNode();//存储已经检测的点ListVector2Int reached new ListVector2Int();DataNode startNode new DataNode(startPos,null);startNode.gCost 0;startNode.hCost CalculateDistanceCost(startPos, goalPos);startNode.CalculateFCost();frontier.Add(startNode);while (frontier.Count 0){DataNode currentNode GetLowestFCostNode(frontier);if (currentNode.pos goalPos){return new DataNode(goalPos, currentNode.parent);}frontier.Remove(currentNode);reached.Add(currentNode.pos);ListDataNode neighbors GetNeighbors(currentNode.pos, reached);foreach (DataNode neighbourNode in neighbors){int tentativeGCost currentNode.gCost CalculateDistanceCost(currentNode.pos, neighbourNode.pos);if (tentativeGCost neighbourNode.gCost){neighbourNode.parent currentNode;neighbourNode.gCost tentativeGCost;neighbourNode.hCost CalculateDistanceCost(neighbourNode.pos, goalPos);neighbourNode.CalculateFCost();if (!frontier.Contains(neighbourNode)){frontier.Add(neighbourNode);}}}}return null;}ListDataNode GetNeighbors(Vector2Int current, ListVector2Int reached){ListDataNode neighbors new ListDataNode();for (int i 0; i Utils.pointDir.Count; i){Vector2Int neighbor current Utils.pointDir[i];if (this.IsCanAdd(neighbor, reached)){neighbors.Add(new DataNode(neighbor,null));}}return neighbors;}bool IsCanAdd(Vector2Int current, ListVector2Int reached){if (reached.Contains(current))return false;if (current.x 0 current.y 0 current.x xCount current.y zCount){//如果是障碍物则不能被Addif (this.mapData[current.y, current.x] 1){return false;}return true;}return false;}private int CalculateDistanceCost(Vector2Int a, Vector2Int b){return Mathf.Abs(a.x - b.x) Mathf.Abs(a.y - b.y);}private DataNode GetLowestFCostNode(ListDataNode pathNodeList){DataNode lowestFCostNode pathNodeList[0];for (int i 1; i pathNodeList.Count; i){if (pathNodeList[i].fCost lowestFCostNode.fCost){lowestFCostNode pathNodeList[i];}}return lowestFCostNode;}
}
结果 参考链接
A* 算法简介 (redblobgames.com)
A* 搜索算法 - 维基百科自由的百科全书 (wikipedia.org)
A* Pathfinding (E01: algorithm explanation) - YouTube
