那里做网站好,注册网站云空间,wordpress调用函数,小兔自助建站戴克斯特拉算法#xff08;英语#xff1a;Dijkstras algorithm#xff09;#xff0c;又称迪杰斯特拉算法、Dijkstra算法#xff0c;是由荷兰计算机科学家艾兹赫尔戴克斯特拉在1956年发现的算法。
算法过程#xff1a;
1.首先设置开始节点的成本值为0#xff0c;并将…戴克斯特拉算法英语Dijkstras algorithm又称迪杰斯特拉算法、Dijkstra算法是由荷兰计算机科学家艾兹赫尔·戴克斯特拉在1956年发现的算法。
算法过程
1.首先设置开始节点的成本值为0并将开始节点放入检测列表中。
2.将检测列表中的所有点按到目标点所需的成本值排序选择成本最小的节点作为当前节点并将其移出检测列表。
3.将当前点周围的点中不包含在检测列表中的点加入到检测列表将周围点加入到已检测列表中。
4.更新检测列表中的节点到当前节点的成本值。
5.重复234直到找到目标点。
代码实现
public class Dijkstra : FindPathAlgorithm
{public Dijkstra(int[,] mapData, int xCount, int zCount) : base(mapData, xCount, zCount){}public override ListVector2Int FindPath(Vector2Int startPos, Vector2Int goalPos){DataNode dataNode this.DijkstraFind(startPos, goalPos);if (dataNode null){Debug.LogError(寻路有误请检查参数是否正确);return null;}return Utils.GetPath(dataNode);}DataNode DijkstraFind(Vector2Int startPos, Vector2Int goalPos){//存储要检测的点ListDataNode frontier new ListDataNode();//存储已经检测的点ListVector2Int reached new ListVector2Int();DataNode startNode new DataNode(startPos, null);startNode.gCost 0;frontier.Add(startNode);reached.Add(startPos);while (frontier.Count 0){DataNode currentNode GetLowestgCostNode(frontier);frontier.Remove(currentNode);if (currentNode.pos goalPos){Debug.Log(完成);return new DataNode(goalPos, currentNode.parent);}ListDataNode neighbors GetNeighbors(currentNode.pos, reached);foreach (DataNode neighbourNode in neighbors){if (!frontier.Contains(neighbourNode)){neighbourNode.parent currentNode;frontier.Add(neighbourNode);}reached.Add(neighbourNode.pos);}this.UpdateCost(frontier, currentNode);}return null;}//更新成本值void UpdateCost(ListDataNode nodes, DataNode currentNode){for (int i 0; i nodes.Count; i){int newCost currentNode.gCost CalculateDistanceCost(nodes[i].pos, currentNode.pos);if (nodes[i].gCost newCost){nodes[i].gCost newCost;}}}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 MapData.m_MapData.GetLength(1) current.y MapData.m_MapData.GetLength(0)){//如果是障碍物则不能被Addif (MapData.m_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 GetLowestgCostNode(ListDataNode pathNodeList){DataNode lowestFCostNode pathNodeList[0];for (int i 1; i pathNodeList.Count; i){if (pathNodeList[i].gCost lowestFCostNode.gCost){lowestFCostNode pathNodeList[i];}}return lowestFCostNode;}
}
结果 参考链接
Pathfinding in Unity - Part3: Dijkstra Algorithm Theory (youtube.com)
Pathfinding in Unity - Part4: Dijkstra Algorithm Implementation (youtube.com)
How Dijkstras Algorithm Works (youtube.com)
戴克斯特拉算法 - 维基百科自由的百科全书 (wikipedia.org)
