C# A* 算法 和 Dijkstra 算法 结合使用

前一篇：路径搜索算法 A* 算法 和 Dijkstra 算法-CSDN博客文章浏览阅读330次，点赞9次，收藏5次。Dijkstra算法使用优先队列来管理待处理的节点，通过不断选择最短距离的节点进行扩展，更新相邻节点的距离值。Dijkstra算法使用一个距离数组来记录起始节点到每个节点的最短距离，通过选择当前距离最小的节点进行扩展，更新与该节点相邻节点的距离值。算法通过估价函数值 f(n) = g(n) + h(n) 来评估节点的优先级，其中 g(n) 是实际移动代价，h(n) 是从当前节点到目标节点的估计代价。请注意，这只是一个简单的示例，实际的路径搜索算法根据具体的场景和需求可能需要更复杂的实现。https://blog.csdn.net/hefeng_aspnet/article/details/135356191

以下是一个示例的C#语言下的A*算法和Dijkstra算法的完整代码：

using System;
using System.Collections.Generic;

public class Node
{
? ? public int x;
? ? public int y;
? ? public bool isWalkable;
? ? public List<Node> neighbors;
? ? public Node parent;
? ? public int gCost; // 从起点到当前节点的实际移动代价
? ? public int hCost; // 从当前节点到目标节点的估算代价

? ? public Node(int x, int y, bool isWalkable)
? ? {
? ? ? ? this.x = x;
? ? ? ? this.y = y;
? ? ? ? this.isWalkable = isWalkable;
? ? ? ? neighbors = new List<Node>();
? ? }

? ? public int fCost { get { return gCost + hCost; } }
}

public class Pathfinding
{
? ? // A*算法寻找路径
? ? public static List<Node> AStar(Node startNode, Node endNode)
? ? {
? ? ? ? List<Node> openSet = new List<Node>();
? ? ? ? HashSet<Node> closedSet = new HashSet<Node>();
? ? ? ? openSet.Add(startNode);

? ? ? ? while (openSet.Count > 0)
? ? ? ? {
? ? ? ? ? ? Node currentNode = openSet[0];
? ? ? ? ? ? for (int i = 1; i < openSet.Count; i++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if (openSet[i].fCost < currentNode.fCost || openSet[i].fCost == currentNode.fCost && openSet[i].hCost < currentNode.hCost)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? currentNode = openSet[i];
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }

? ? ? ? ? ? openSet.Remove(currentNode);
? ? ? ? ? ? closedSet.Add(currentNode);

? ? ? ? ? ? if (currentNode == endNode)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? return GeneratePath(startNode, endNode);
? ? ? ? ? ? }

? ? ? ? ? ? foreach (Node neighbor in currentNode.neighbors)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if (!neighbor.isWalkable || closedSet.Contains(neighbor))
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? continue;
? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? int newCostToNeighbor = currentNode.gCost + GetDistance(currentNode, neighbor);
? ? ? ? ? ? ? ? if (newCostToNeighbor < neighbor.gCost || !openSet.Contains(neighbor))
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? neighbor.gCost = newCostToNeighbor;
? ? ? ? ? ? ? ? ? ? neighbor.hCost = GetDistance(neighbor, endNode);
? ? ? ? ? ? ? ? ? ? neighbor.parent = currentNode;

? ? ? ? ? ? ? ? ? ? if (!openSet.Contains(neighbor))
? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? openSet.Add(neighbor);
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }

? ? ? ? return null;
? ? }

? ? // Dijkstra算法寻找路径
? ? public static List<Node> Dijkstra(Node startNode, Node endNode)
? ? {
? ? ? ? Dictionary<Node, int> distance = new Dictionary<Node, int>();
? ? ? ? Dictionary<Node, Node> previous = new Dictionary<Node, Node>();
? ? ? ? List<Node> unvisited = new List<Node>();

? ? ? ? foreach (Node node in GetAllNodes())
? ? ? ? {
? ? ? ? ? ? distance[node] = int.MaxValue;
? ? ? ? ? ? previous[node] = null;
? ? ? ? ? ? unvisited.Add(node);
? ? ? ? }

? ? ? ? distance[startNode] = 0;

? ? ? ? while (unvisited.Count > 0)
? ? ? ? {
? ? ? ? ? ? Node current = null;

? ? ? ? ? ? foreach (Node node in unvisited)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if (current == null || distance[node] < distance[current])
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? current = node;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }

? ? ? ? ? ? if (current == endNode)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? return GeneratePath(startNode, endNode);
? ? ? ? ? ? }

? ? ? ? ? ? unvisited.Remove(current);

? ? ? ? ? ? foreach (Node neighbor in current.neighbors)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? int altDistance = distance[current] + GetDistance(current, neighbor);

? ? ? ? ? ? ? ? if (altDistance < distance[neighbor])
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? distance[neighbor] = altDistance;
? ? ? ? ? ? ? ? ? ? previous[neighbor] = current;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }

? ? ? ? return null;
? ? }

? ? // 计算两个节点之间的距离
? ? public static int GetDistance(Node nodeA, Node nodeB)
? ? {
? ? ? ? int distanceX = Math.Abs(nodeA.x - nodeB.x);
? ? ? ? int distanceY = Math.Abs(nodeA.y - nodeB.y);

? ? ? ? return distanceX + distanceY;
? ? }

? ? // 生成路径
? ? public static List<Node> GeneratePath(Node startNode, Node endNode)
? ? {
? ? ? ? List<Node> path = new List<Node>();
? ? ? ? Node currentNode = endNode;

? ? ? ? while (currentNode != startNode)
? ? ? ? {
? ? ? ? ? ? path.Add(currentNode);
? ? ? ? ? ? currentNode = currentNode.parent;
? ? ? ? }

? ? ? ? path.Reverse();
? ? ? ? return path;
? ? }

? ? // 获取所有节点
? ? public static List<Node> GetAllNodes()
? ? {
? ? ? ? List<Node> allNodes = new List<Node>();

? ? ? ? // 在这里根据实际场景生成所有节点并设置邻居节点

? ? ? ? return allNodes;
? ? }
}

class Program
{
? ? static void Main(string[] args)
? ? {
? ? ? ? Node startNode = new Node(0, 0, true); // 起始节点
? ? ? ? Node endNode = new Node(9, 9, true); ?// 目标节点

? ? ? ? // 使用A*算法寻找路径
? ? ? ? List<Node> aStarPath = Pathfinding.AStar(startNode, endNode);

? ? ? ? if (aStarPath != null)
? ? ? ? {
? ? ? ? ? ? Console.WriteLine("A* Algorithm - Path Found:");
? ? ? ? ? ? foreach (Node node in aStarPath)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? Console.WriteLine("(" + node.x + ", " + node.y + ")");
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? else
? ? ? ? {
? ? ? ? ? ? Console.WriteLine("A* Algorithm - No Path Found.");
? ? ? ? }

? ? ? ? // 使用Dijkstra算法寻找路径
? ? ? ? List<Node> dijkstraPath = Pathfinding.Dijkstra(startNode, endNode);

? ? ? ? if (dijkstraPath != null)
? ? ? ? {
? ? ? ? ? ? Console.WriteLine("Dijkstra Algorithm - Path Found:");
? ? ? ? ? ? foreach (Node node in dijkstraPath)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? Console.WriteLine("(" + node.x + ", " + node.y + ")");
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? else
? ? ? ? {
? ? ? ? ? ? Console.WriteLine("Dijkstra Algorithm - No Path Found.");
? ? ? ? }
? ? }
}
????????在示例代码中，我们定义了一个 Node 类来表示节点对象，该类包含节点的坐标、是否可行走、邻居节点等信息。然后，我们在 Pathfinding 类中实现了 A*算法和 Dijkstra 算法来寻找路径。GetDistance 函数用于计算两个节点之间的距离，GeneratePath 函数用于生成路径，GetAllNodes 函数用于获取所有节点。

????????在 Main 函数中，我们创建了起始节点和目标节点，并使用 A*算法和 Dijkstra 算法分别寻找路径。最后，将路径打印出来。

????????请注意，示例代码中只包含了算法的实现逻辑，您需要根据实际情况创建地图、设置节点可行走状态、设置邻居节点等操作。