在游戏开发中，AI的最基本问题之一就是寻路算法或称路径规划算法，在三 年前，我曾实现过 基于“图算法”的最短路径规划算法，然而在游 戏中，我们通常将地图抽象为有单元格构成的矩形，如：
这个微型地图 由3*3的单元格构成，当然，实际游戏中的地图通常比它大很多，这里只是给出 一个示例。
由于游戏地图通常由单元格构成，所以，基于“图算法 ”的路径规划便不再那么适用，我们需要采用基于单元格的路径规划算法 。A*算法是如今游戏所采用的寻路算法中相当常用的一种算法，它可以保证在任 何起点和任何终点之间找到最佳的路径（如果存在的话），而且，A*算法相当有 效。
关于A*算法的原理的详细介绍，可以参考 这篇文章。当你明白A*算 法的原理之后，在来看接下来的A*算法的实现就会比较容易了。
现在， 让我们转入正题，看看如何在C#中实现A*算法。
首先，我们把地图划分 为单元格，如此，一个地图就可以由（M行*N列）个单元格构成。我们使用 AStarNode类来抽象单元格，表示一个节点，而节点的位置用Point表示，其X坐 标表示Column Index，Y坐标表示Line Index。AStarNode的定义如下：
Code
[copy to clipboard]CODE:
/// <summary>
/// AStarNode 用于保存规划到当前节点时的各个 Cost值以及父节点。
/// zhuweisky 2008.10.18
/// </summary>
public class AStarNode
{
#region Ctor
public AStarNode(Point loc, AStarNode previous, int _costG, int _costH)
{
this.location = loc;
this.previousNode = previous;
this.costG = _costG;
this.costH = _costH;
}
#endregion
#region Location
private Point location = new Point(0, 0);
/// <summary>
/// Location 节点所在的位置， 其X值代表ColumnIndex，Y值代表LineIndex
/// </summary>
public Point Location
{
get { return location; }
}
#endregion
#region PreviousNode
private AStarNode previousNode = null;
/// <summary>
/// PreviousNode 父节点，即是由哪个节点导航到当前节点的。
/// </summary>
public AStarNode PreviousNode
{
get { return previousNode; }
}
#endregion
#region CostF
/// <summary>
/// CostF 从起点导航经过本节点然后再到目的节点的估算总代价。
/// </summary>
public int CostF
{
get
{
return this.costG + this.costH;
}
}
#endregion
#region CostG
private int costG = 0;
/// <summary>
/// CostG 从起点导 航到本节点的代价。
/// </summary>
public int CostG
{
get { return costG; }
}
#endregion
#region CostH
private int costH = 0;
/// <summary>
/// CostH 使用启发式方法估算的从本节点到目的节点的代价。
/// </summary>
public int CostH
{
get { return costH; }
}
#endregion
#region ResetPreviousNode
/// <summary>
/// ResetPreviousNode 当从起点到达本节点 有更优的路径时，调用该方法采用更优的路径。
/// </summary>
public void ResetPreviousNode(AStarNode previous, int _costG)
{
this.previousNode = previous;
this.costG = _costG;
}
#endregion
public override string ToString()
{
return this.location.ToString();
}
}