请帮我写一篇简单完整的A星算法,C#语言带有中文注释
时间: 2023-12-26 17:06:58 浏览: 28
好的,下面是一份简单完整的A星算法,C#语言带有中文注释:
```csharp
using System.Collections.Generic;
public class AStarAlgorithm
{
// 定义节点类,包含坐标和当前节点的总代价
public class Node
{
public int x;
public int y;
public int cost;
public Node(int x, int y, int cost)
{
this.x = x;
this.y = y;
this.cost = cost;
}
}
// 定义地图类,包含地图大小和障碍物位置
public class Map
{
public int width;
public int height;
public bool[,] obstacle;
public Map(int width, int height, bool[,] obstacle)
{
this.width = width;
this.height = height;
this.obstacle = obstacle;
}
// 判断指定位置是否为障碍物
public bool IsObstacle(int x, int y)
{
if (x < 0 || x >= width || y < 0 || y >= height)
{
// 超出地图范围的位置视为障碍物
return true;
}
return obstacle[x, y];
}
}
// 计算两个节点之间的代价
public static int CalculateCost(Node a, Node b)
{
// 横向或纵向移动的代价为1,斜向移动的代价为1.4
int dx = Mathf.Abs(a.x - b.x);
int dy = Mathf.Abs(a.y - b.y);
return (int)(10 * (dx + dy) + 4 * (2 - 2 * Mathf.Sqrt(2)) * Mathf.Min(dx, dy));
}
// 寻找从起点到终点的最短路径
public static List<Node> FindPath(Map map, Node start, Node end)
{
List<Node> openList = new List<Node>();
List<Node> closedList = new List<Node>();
// 将起点加入开启列表
openList.Add(start);
while (openList.Count > 0)
{
// 在开启列表中寻找代价最小的节点
Node current = openList[0];
for (int i = 1; i < openList.Count; i++)
{
if (openList[i].cost < current.cost)
{
current = openList[i];
}
}
// 将当前节点从开启列表中移除,并加入关闭列表
openList.Remove(current);
closedList.Add(current);
// 如果当前节点为终点,则返回路径
if (current.x == end.x && current.y == end.y)
{
List<Node> path = new List<Node>();
path.Add(current);
while (current.x != start.x || current.y != start.y)
{
current = current.parent;
path.Insert(0, current);
}
return path;
}
// 遍历当前节点的相邻节点
for (int dx = -1; dx <= 1; dx++)
{
for (int dy = -1; dy <= 1; dy++)
{
if (dx == 0 && dy == 0)
{
// 当前节点不需要再次计算
continue;
}
int x = current.x + dx;
int y = current.y + dy;
if (map.IsObstacle(x, y))
{
// 相邻节点为障碍物,跳过
continue;
}
Node neighbor = new Node(x, y, current.cost + CalculateCost(current, new Node(x, y, 0)));
if (closedList.Contains(neighbor))
{
// 相邻节点已经在关闭列表中,跳过
continue;
}
if (!openList.Contains(neighbor))
{
// 相邻节点不在开启列表中,加入开启列表
neighbor.parent = current;
openList.Add(neighbor);
}
else
{
// 相邻节点已经在开启列表中,更新其代价
int index = openList.IndexOf(neighbor);
if (neighbor.cost < openList[index].cost)
{
openList[index].parent = current;
openList[index].cost = neighbor.cost;
}
}
}
}
}
// 找不到路径,返回空列表
return new List<Node>();
}
}
```
使用方法示例:
```csharp
// 定义地图大小和障碍物位置
int width = 10;
int height = 10;
bool[,] obstacle = new bool[width, height];
obstacle[1, 2] = true;
obstacle[2, 2] = true;
obstacle[3, 2] = true;
obstacle[4, 2] = true;
obstacle[5, 2] = true;
obstacle[6, 2] = true;
obstacle[7, 2] = true;
obstacle[8, 2] = true;
obstacle[9, 2] = true;
// 创建地图对象
AStarAlgorithm.Map map = new AStarAlgorithm.Map(width, height, obstacle);
// 定义起点和终点
AStarAlgorithm.Node start = new AStarAlgorithm.Node(0, 0, 0);
AStarAlgorithm.Node end = new AStarAlgorithm.Node(9, 9, 0);
// 寻找最短路径
List<AStarAlgorithm.Node> path = AStarAlgorithm.FindPath(map, start, end);
// 输出路径
foreach (AStarAlgorithm.Node node in path)
{
Debug.Log(node.x + "," + node.y);
}
```