阅读量:7
以下是一种基本的A*寻路算法的实现示例，可以用于C#语言：
using System; using System.Collections.Generic; public class Node { public int X { get; set; } public int Y { get; set; } public bool IsObstacle { get; set; } public int G { get; set; } // G值表示起点到该节点的实际代价 public int H { get; set; } // H值表示该节点到目标节点的估计代价 public int F { get { return G + H; } } // F值表示总代价，F = G + H public Node Parent { get; set; } // 父节点，用于回溯路径 public Node(int x, int y, bool isObstacle = false) { X = x; Y = y; IsObstacle = isObstacle; G = int.MaxValue; H = 0; Parent = null; } } public class AStar { private int[,] _map; // 地图，用二维数组表示 private int _width; // 地图宽度 private int _height; // 地图高度 public AStar(int[,] map) { _map = map; _width = map.GetLength(0); _height = map.GetLength(1); } public List<Node> FindPath(Node startNode, Node targetNode) { List<Node> openList = new List<Node>(); // 开放列表 List<Node> closedList = new List<Node>(); // 关闭列表 startNode.G = 0; startNode.H = CalculateHeuristic(startNode, targetNode); openList.Add(startNode); while (openList.Count > 0) { // 从开放列表中选择F值最小的节点作为当前节点 Node currentNode = FindNodeWithLowestFScore(openList); openList.Remove(currentNode); closedList.Add(currentNode); if (currentNode == targetNode) { // 找到路径，返回路径上的节点 return GeneratePath(startNode, targetNode); } List<Node> neighbors = GetNeighbors(currentNode); foreach (Node neighbor in neighbors) { if (closedList.Contains(neighbor) || neighbor.IsObstacle) { // 跳过已在关闭列表中的节点或障碍节点 continue; } int tentativeG = currentNode.G + 1; // G值暂时设为当前节点的G值加上从当前节点到相邻节点的实际代价 if (!openList.Contains(neighbor) || tentativeG < neighbor.G) { // 若该相邻节点不在开放列表中，或者新的G值更小，则更新G、H和父节点 neighbor.G = tentativeG; neighbor.H = CalculateHeuristic(neighbor, targetNode); neighbor.Parent = currentNode; if (!openList.Contains(neighbor)) { openList.Add(neighbor); } } } } // 无法找到路径，返回空列表 return new List<Node>(); } private int CalculateHeuristic(Node node, Node targetNode) { // 使用曼哈顿距离作为启发函数（估计代价） return Math.Abs(node.X - targetNode.X) + Math.Abs(node.Y - targetNode.Y); } private Node FindNodeWithLowestFScore(List<Node> nodeList) { // 找到F值最小的节点 Node lowestFScoreNode = nodeList[0]; foreach (Node node in nodeList) { if (node.F < lowestFScoreNode.F) { lowestFScoreNode = node; } } return lowestFScoreNode; } private List<Node> GetNeighbors(Node node) { List<Node> neighbors = new List<Node>(); int startX = Math.Max(0, node.X - 1); int endX = Math.Min(_width - 1, node.X + 1); int startY = Math.Max(0, node.Y - 1); int endY = Math.Min(_height - 1, node.Y + 1); for (int x = startX; x <= endX; x++) { for (int y = startY; y <= endY; y++) { if (x == node.X && y == node.Y) { 