温馨提示×

C#中Astar寻路算法怎么实现

c#
小亿
105
2023-09-21 22:53:05
栏目: 编程语言

以下是一种基本的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)
{

0