C#: A-Star 诞生
4.92/5 (174投票s)
2003年6月24日
7分钟阅读
594508
8580
使用 C# 理解图和 A* 寻路算法
简介：它应该做什么？
我致力于创建一个 .NET 组件，它允许构建图并对这些结构执行一些操作。特别是，可以运行著名的路径查找算法 A* 来找到两个位置之间的最佳路径。
首先，应该记住，图是由以下内容定义的：
- 节点列表
- 弧线列表
每个节点都使用以下数据定义：
- 空间中的地理位置（坐标 X、Y、Z）
- 出弧集合
- 入弧集合
每条弧线都通过其两个端点节点简单定义。因此，弧线从 _起始节点_ 定向到 _结束节点_。它还具有一个名为“权重”的交叉因子。此值表示从起始节点到达结束节点的难度。因此，通过一条弧线需要付出成本，其基本计算方法如下：
Cost = Distance(StartNode, EndNode) * Weight
您可能会问：“这种结构有什么用处？”。嗯，应用程序可以是多种多样的，从路线图和交通模型到视频游戏中的角色移动。现在的问题是：“人们将如何在图上移动？”。
什么是 A*？
假设您在一个节点上，并且您想到达图上其他位置的另一个位置。然后问：“我将走哪条路，为什么？”。这里要考虑的主要因素是移动的成本。它必须是最小的。成本标准基本上是距离（弧长之和）的函数。但是，它也可以根据其他数据进行调整和变化，例如描述坡度、地面崎岖程度/可行性。您甚至可以模拟交通拥堵。
为了获得最佳路径，有许多算法，它们或多或少有效，具体取决于特定情况。效率不仅取决于计算所需的时间，还取决于结果的可靠性。A* 能够根据可访问性/方向以及弧线成本（如果存在）返回两个节点之间的最佳路径。
在现有算法中，有些算法并不总是实际返回最佳路径，但它们可以优先考虑速度而不是准确性。效率取决于节点的数量及其地理分布。然而，在大多数情况下，A* 被证明是最有效的，因为它结合了优化搜索和启发式方法的使用。
**启发式** 是一个函数，它将一个值与一个节点相关联以对其进行评估。如果最终点以较少的努力（例如更短的距离）达到，则一个节点被认为优于另一个节点。
A* 总是返回最短路径，当且仅当启发式是_可接受的_；也就是说，如果它从不高估。另一方面，如果启发式不可接受，A* 将以更少的时间和更少的内存使用量找到一条路径，但不能绝对保证它是最好的。以下是三个可接受的启发式方法，它们对应于评估节点和目标节点之间的特定距离：
- 欧几里得距离 > Sqrt(Dx²+Dy²+Dz²)
- 曼哈顿距离 > |Dx|+|Dy|+|Dz|
- 最大距离 > Max(|Dx|, |Dy|, |Dz|)
这些函数估算每个可探索节点的剩余距离。因此，搜索可以朝向“最佳”节点。对于给定节点，[当前成本 + 启发式值] 的总和是估计从起始节点经过当前节点到达结束节点的成本。此值用于持续选择最有希望的路径。
实际上，该算法维护两个节点列表，这些列表在搜索过程中被填充和修改：
- 第一个列表，称为
Open，包含通向可探索节点的轨迹。最初，只有起始节点。在每一步，从Open中取出最佳节点。然后，将该节点的最佳后继（根据启发式）作为新轨迹添加到列表中。我们不知道Open中的节点通向何处，因为它们尚未传播。但是，在每个新步骤中都会检查最佳节点。 - 第二个列表，称为
Closed，存储通向已探索节点的轨迹。
该程序基于递归模型。循环持续进行，只要 Open 仍包含一些元素。有关详细信息，请参阅代码（用 C# 编写，足以自行解释）。
public bool SearchPath(Node StartNode, Node EndNode)
{
lock (_Graph)
{
Initialize(StartNode, EndNode);
while ( NextStep() ) {}
return PathFound;
}
}
使用代码：组件的公共接口
Graph 类收集了一组管理其数据的方法，例如：
- 添加/删除节点/弧线
- 从点获取最近/最远的节点/弧线
- 激活/停用整个图
- 清空图
从更实际的角度来看，以下是您可以用于主要类和对象的方法和属性：
public class Graph
{
public Graph()
public IList Nodes { get }
public IList Arcs { get }
public void Clear()
public bool AddNode(Node NewNode)
public Node AddNode(float x, float y, float z)
public bool AddArc(Arc NewArc)
public Arc AddArc(Node StartNode, Node EndNode, float Weight)
public void Add2Arcs(Node Node1, Node Node2, float Weight)
public bool RemoveNode(Node NodeToRemove)
public bool RemoveArc(Arc ArcToRemove)
public void BoundingBox(out double[] MinPt, out double[] MaxPt)
public Node ClosestNode(double X, double Y, double Z, out double Dist,
bool IgnoreFreeWay)
public Arc ClosestArc(double X, double Y, double Z, out double Dist,
bool IgnoreFreeWay)
}
public class Node
{
public Node(double PositionX, double PositionY, double PositionZ)
public IList IncomingArcs { get }
public IList OutgoingArcs { get }
public double X { get }
public double Y { get }
public double Z { get }
public void ChangeXYZ(double PositionX, double PositionY,
double PositionZ)
public bool Passable { get/set }
public Node[] AccessibleNodes { get }
public Node[] AccessingNodes { get }
public void UntieIncomingArcs()
public void UntieOutgoingArcs()
public void Isolate()
public Arc ArcGoingTo(Node N)
public Arc ArcComingFrom(Node N)
public object Clone()
public static void BoundingBox(IList NodesGroup, out double[] MinPt,
out double[] MaxPt)
public static double EuclidianDistance(Node N1, Node N2)
public static double SquareEuclidianDistance(Node N1, Node N2)
public static double ManhattanDistance(Node N1, Node N2)
public static double MaxDistanceAlongAxis(Node N1, Node N2)
public override string ToString()
public override bool Equals(object O)
public override int GetHashCode()
}
public class Arc
{
public Arc(Node Start, Node End)
public Node StartNode { get/set }
public Node EndNode { get/set }
public double Weight { get/set }
public bool Passable { get/set }
virtual public double Cost { get }
public double Length { get }
virtual protected double CalculateLength()
public override string ToString()
public override bool Equals(object O)
public override int GetHashCode()
}
public class AStar
{
public AStar(Graph G)
public bool SearchPath(Node StartNode, Node EndNode)
public void Initialize(Node StartNode, Node EndNode)
public bool NextStep()
public bool Initialized { get }
public int StepCounter { get }
public bool SearchStarted { get }
public bool SearchEnded { get }
public bool PathFound { get }
public Node[] PathByNodes { get }
public Arc[] PathByArcs { get }
public bool ResultInformation(out int NbArcsOfPath, out double CostOfPath)
public double DijkstraHeuristicBalance { get/set }
public Heuristic ChoosenHeuristic { get/set }
public static Heuristic EuclidianHeuristic { get }
public static Heuristic MaxAlongAxisHeuristic { get }
public static Heuristic ManhattanHeuristic { get }
}
节点和弧线可以是_可通行的_，也可以不是。为节点选择这两种状态之一，会将相同的状态传播到出弧和入弧。同样，销毁节点意味着销毁所有直接链接的弧线。此外，弧线必须始终链接到两个节点，而节点可以孤立。
请注意，这些数据重写了 Object.ToString() 和 Object.Equals(Object O)。此外，它们可以序列化。
控制台应用程序的简单用法示例
using System;
using System.Collections;
using System.Text;
using System.IO;
using System.Runtime.Serialization;
using System.Runtime.Serialization.Formatters.Binary;
using EMK.Cartography;
namespace EMK.Tests
{
public class TestAStar
{
public static void Main()
{
try
{
Graph G = new Graph();
Node N1 = G.AddNode(0,0,0);
Node N2 = G.AddNode(5,0,0);
Node N3 = G.AddNode(5,5,0);
Node N4 = G.AddNode(5,5,5);
G.AddArc(N1,N2,1);
G.AddArc(N2,N3,1);
G.AddArc(N3,N4,1);
G.AddArc(N1,N3,1);
Console.WriteLine( ListNodesAndArcs(G) );
Console.WriteLine("Best path to reach "+N4+" from "+N1+" :");
AStar AS = new AStar(G);
if ( AS.SearchPath(N1, N4) )
foreach (Arc A in AS.PathByArcs)
Console.WriteLine( A.ToString() );
else Console.WriteLine( "No result !" );
Console.Write("Serialize and Deserialize. ");
Stream StreamWrite = File.Create("GraphSaved.bin");
BinaryFormatter BinaryWrite = new BinaryFormatter();
BinaryWrite.Serialize(StreamWrite, G);
StreamWrite.Close();
Stream StreamRead = File.OpenRead("GraphSaved.bin");
BinaryFormatter BinaryRead = new BinaryFormatter();
Graph G2 = (Graph) BinaryRead.Deserialize(StreamRead);
StreamRead.Close();
Console.WriteLine( ListNodesAndArcs(G2) );
}
catch(Exception e)
{
Console.Write( "Error :\n\n"+e.ToString() );
}
}
static private string ListNodesAndArcs(Graph GraphToDescribe)
{
StringBuilder SB = new
StringBuilder("Description of the Graph:\n\tNodes> ");
foreach (Node N in GraphToDescribe.Nodes)
SB.Append( N.ToString()+"; " );
SB.Append("\n\tArcs> ");
foreach (Arc A in GraphToDescribe.Arcs)
SB.Append( A.ToString()+"; " );
return SB.ToString();
}
}
}Description of the Graph:
Nodes> {0;0;0}; {5;0;0}; {5;5;0}; {5;5;5}
Arcs> {0;0;0}-->{5;0;0}; {5;0;0}-->{5;5;0};
{5;5;0}-->{5;5;5}; {0;0;0}-->{5;5;0}
Best path to reach {5;5;5} from {0;0;0} :
{0;0;0}-->{5;5;0}
{5;5;0}-->{5;5;5}
Serialize and Deserialize. Description of the Graph:
Nodes> {0;0;0}; {5;0;0}; {5;5;0}; {5;5;5}
Arcs> {0;0;0}-->{5;0;0}; {5;0;0}-->{5;5;0};
{5;5;0}-->{5;5;5}; {0;0;0}-->{5;5;0}
图形环境中的使用示例
图形界面的目的是将组件投入使用，以公平简单地反映其功能。该应用程序允许您绘制、移动、擦除或停用多个节点和弧线。当您的图完成后，您只需单击“A*”图标，然后分别使用鼠标左右键选择起始节点和结束节点。然后您将自动看到最佳路径。如果您修改图，此路径将更新。
如果您想可视化算法的逻辑，请在“A*”图标的子菜单中选择“分步”模式。这样做的目的是让用户清楚地了解发生了什么。
在选项面板（“?”图标）中，您可以更改启发式并设置其影响。最小值（实际上是 0）表示只使用启发式。相反，最大值（实际上是 1）表示搜索将按照 Dijkstra 算法进行。
备注
该程序已通过一系列适应性测试进行验证，这些测试收集了各种场景和交互。尽管如此，它并不旨在成为一个完美的应用程序，而是一个谦虚的程序，它 modest 地声称简单且符合人体工程学。供参考，我之前已经使用 C++（用于 DLL）和 MFC（用于 2D 图形界面）完成了这项工作。我还使用 OpenGL 图形界面在 3D 环境中对其进行了测试。下一步将是使用 Direct3D 9.0 for .NET 或此框架的 OpenGL 解决方案之一来实现 3D 界面。
源代码包含 Point3D 和 Vector3D 等几何工具的轻量级但有趣的实现。它们是 GraphFormer 示例应用程序中图形交互所必需的（线上的投影、向量运算等）。
为了方便和性能，我为 _Closed_ 和 _Open_ 列表使用了 SortableList 类型。优点是，由于列表保持排序状态，最佳轨迹将始终是第一个元素（参见我之前撰写的关于自动排序列表的文章）。尽管如此，将其替换为其他列表类型（例如 ArrayList）也非常容易，前提是您在每一步都查找“最佳”元素（即较低的元素）。
历史
- 2003 年 6 月 22 日：将库代码和注释从法语翻译成英语。
- 2003 年 6 月 24 日：文章提交。
- 2003 年 6 月 26 日：由于 DoubleBuffer 面板样式，不再闪烁。