首页 > Python基础教程 >
-
C#教程之C#实现基本的AStar平面寻路算法
1、算法实施模型
在我看来，最简单最基础的寻路环境是：在一片二维网格区域中存在一些围墙（Block），在起始点和终点之间保持连通的前提下寻找一条最佳路径。
2、算法原理
详细介绍有很多，可参考网址：http://www.policyalmanac.org/games/aStarTutorial.htm，浅显易懂，重点是理解“启发式搜索”的概念。下面谈谈我自己的理解，如果是第一次接触A*寻路算法，还是先老老实实看完给出的参考网址吧（当然也可以参考相关的中文介绍资料）。
在一片二维网格中，每个网格可以看作一个节点（Grid），节点有的是可通过的（FlatGround），有的是障碍（Block），有的可能是其他特殊地形（Mountain），以上可以归纳为节点的地形属性（LandAttribute）；寻路完毕后要凸显路径上的节点，归纳为布尔型的路径属性（PathAttribute）。我们要让计算机寻找路径，首先必须要告诉它评价节点是否为路径的标准。这就需要给每个节点加一个标识值，通过比较这个值的高低，来判断最优解。如何计算这个标识值就是算法的核心。
A*算法采用的标准是：F = G + H。G表示当前节点到起点移动的耗费，H表示当前节点到终点可能的移动耗费，两者之和F值越小，我们就认为它越有可能是最短路径上的一个节点。注意G/H表述上的区别，从计算机的角度去思考，从起点寻路到当前的某个节点，移动的耗费是一步步累加而来的，是可以确定的；但我们并不知道从当前节点到目标节点最终会耗费多少，所以只能通过某种方法预估，通常我们会使用曼哈顿街区方法。其实这个名称也只是故弄玄虚，就是计算一下当前节点沿着矩形边移动到目标节点的距离，非常简单，重点是理解背后的思路。在我看来，传统的寻路表述是：先到某大街，再经过某胡同，再到终点；而启发式的寻路表述是：我不知道下一步怎么走，在我这位置目前走胡同最便捷，咱们先试试？前者是人脑思维，后者是计算机思维。
从节点到路径，启发式的搜索需要试错，也就是说只有最后找到目标节点，路径才会确定下来，这也就意味着路径属性的赋值要等到路径确定下来之后。在寻路过程中，如何把路径节点和之前确定的路径关联起来呢？一个很妙的方法是给每个节点加上一个父节点（FatherGrid），这样就把路径节点串成了路径。这也就可以理解：路径属性其实是从终点开始当前节点的父节点是否为空的浅显表达。
这样可以总结出节点应有的属性：坐标属性、地形属性、路径属性以及评估移动耗费的属性，以下为Grid类的设计代码。
class Grid
{
private int x;
internal int X
{
get { return x; }
set { x = value; }
}
private int y;
internal int Y
{
get { return y; }
set { y = value; }
}
private byte landAttribute = 1;
/// <summary>
/// 属性：描述地形,默认为平地，0表示该节点为障碍（不可通行）
/// </summary>
internal byte LandAttribute
{
get { return landAttribute; }
set { landAttribute = value; }
}
private bool pathAttribute = false;
/// <summary>
/// 属性：是否为路径节点，是为true，默认为false
/// </summary>
internal bool PathAttribute
{
get { return pathAttribute; }
set { pathAttribute = value; }
}
private int gCostAttribute;
/// <summary>
/// 属性：当前网格距离起点的移动耗费
/// </summary>
internal int GCostAttribute
{
get { return gCostAttribute; }
set { gCostAttribute = value; }
}
private int hCostAttribute;
/// <summary>
/// 属性：当前网格距离终点的移动耗费
/// </summary>
internal int HCostAttribute
{
get { return hCostAttribute; }
set { hCostAttribute = value; }
}
/// <summary>
/// 字段：当前网格的父节点
/// </summary>
internal Grid fatherGrid;
/// <summary>
/// 方法：获得地形的符号表达
/// </summary>
/// <param name="g">当前节点</param>
/// <returns>String：地形的符号表达</returns>
internal static string Print(Grid g)
{
if (g.PathAttribute) return "☆";
else
{
switch (g.LandAttribute)
{
case 0: return "■";
case 1: return "□";
case 2: return "▲";
default: return "○";
}
}
}
}
/// <summary>
/// 枚举：地形的集合
/// </summary>
enum LandFormEnum
{
Block = 0,
Flatground = 1,
Mountain = 2
}
}
3、代码实现
1)地图生成（Map类）
对于第一次写实现代码的人来说，最简单的地图莫如用二维Byte数组表示了（如下表所示，1表示障碍，0表示可通过）。
更直接一点，既然建立了Grid类，我们何不就使用一个二维Grid数组表达一张地图呢？本质上两者的思路是一致的。
在Map类中，我还增加了起点和终点的两个属性。这里就体现属性较之字段的优点了：属性中的方法可以很方便也很严格地初始化参数，保证了程序运行的安全。这也算是体现代码健壮性的小细节吧？然后，该类还提供了MapGridSet()方法，用于生成各种地形或者障碍。
以下为Map类的设计代码：
class Map
{
/// <summary>
/// 字段：地图长
/// </summary>
internal int LenX;
/// <summary>
/// 字段：地图宽
/// </summary>
internal int LenY;
/// <summary>
/// 字段：用网格节点描述的地图
/// </summary>
internal Grid[,] simplemap;
/// <summary>
/// 构造方法：初始化地图
/// </summary>
/// <param name="x">地图长</param>
/// <param name="y">地图宽</param>
public Map(int x, int y)
{
LenX = x;
LenY = y;
simplemap = new Grid[LenY, LenX];
for (int i = 0; i < LenY; i++)
for (int j = 0; j < LenX; j++)
{
simplemap[i, j] = new Grid() { X = j, Y = i };
}
}
private Grid startGrid;
/// <summary>
/// 属性：地图起点
/// </summary>
internal Grid StartGrid
{
get { return startGrid; }
set
{
if (value.LandAttribute != 0)
{
startGrid = value;
startGrid.GCostAttribute = 0;
startGrid.fatherGrid = null;
startGrid.PathAttribute = true;
simplemap[startGrid.Y, startGrid.X] = startGrid;
}
else startGrid = null;
}
}
private Grid endGrid;
/// <summary>
/// 属性：地图终点
/// </summary>
internal Grid EndGrid
{
get { return endGrid; }
set
{
endGrid = value;
endGrid.PathAttribute = true;
simplemap[endGrid.Y, endGrid.X] = endGrid;
}
}
/// <summary>
/// 方法：对所有网格的地形属性进行初始化设置从而生成一张地图
/// </summary>
/// <param name="grid">当前节点</param>
/// <param name="landform">地形选项</param>
internal void MapGridSet(Grid grid, byte landform)
{
if (landform > landtypes) return;
else grid.LandAttribute = landform;
}
/// <summary>
/// 字段：地形总数
/// </summary>
private int landtypes = Enum.GetValues(typeof(LandFormEnum)).Length - 1;
2)路径生成（Paths类）
这是最核心的代码。
首先要做一些准备：
a、计算G/H值
H值采用之前所说的曼哈顿街区方法，很简单，略过。
我们允许沿着对角线移动。如果把上下左右移动的耗费设为1，那么斜行的移动耗费为√2，近似为1.4。事实上，我们都会将直行移动耗费设为10，斜行移动耗费设为14，因为计算机对于整型的处理速度要高于浮点型，这算是性能上的一个小细节吧。
b、开启/关闭列表
开启列表用于存放路径节点的“候选人”，关闭列表用于存放“已审核过的人员”，这些都是为了提高算法的效率。这里还涉及到了List<T>的使用，对于C#的初学者来说，相关的知识还是很有趣、很重要也很有用的。
其次要理清楚思路：
a、从起点开始，检查九宫格边缘8个节点（CheckAround），除却越界、障碍和上一步已经检查过的节点（在关闭列表中的节点）；
b、对于剩下的节点，如果不在开启列表中（第一次被CheckAround到），则将该边缘节点的父节点设置为九宫格中间的节点（即当前CheckAround时的中心节点），加入开启列表中（列入待检查的点）；
c、如果在开启列表中（之前被检查过，但F值不是最小，所以没有加入路径），需要再判断一次被检查点的G值和父节点。这里单纯用语言描述比较复杂，给出一个最简单的实例。
起点周围3个节点加入开启列表，父节点为起点，A点G值为14，F值34最小，选为下一步的中心节点，B点G值为10，H值30；
接着，A点周围检查B点，此时根据A点G值计算B点的G值为24，大于原来的G值10，不做任何处理（即B点父节点仍为起点，G值仍为10），检查C点，G为28、H为20，父节点为A点，显然B点为下一步的中心节点；
从B点周围检查，起点和A点都在关闭列表中了，直接跳过不必再检查，检查C点时发现此时G值为20，小于原先的28，即实际最佳路径是起点-B-C，所以将C的父节点修改为B点，G值修改为20。（后续过程略）
通过以上的过程，可以看出其实对于人脑来说，A点本来的检查工作是多余的（对人脑来说很明显去C点直线最近嘛），这也就是寻路算法的自我修正所带来的性能损耗。为了寻找最短路径，就需要更多的试错和修正，性能和效率必然会受到影响，所以寻路算法会在性能和结果之间做出权衡。
最后生成Paths类的实现代码：
class Paths
{
List<Grid> openList = new List<Grid>();
List<Grid> closeList = new List<Grid>();
/// <summary>
/// 方法：判断当前节点是否在指定列表中，是则返回true
/// </summary>
/// <param name="x">坐标x</param>
/// <param name="y">坐标y</param>
/// <param name="list">列表</param>
/// <returns>Bool：在指定列表中则返回true</returns>
protected bool IsInList(int x, int y, List<Grid> list)
{
foreach (Grid g in list)
{
if (g.X == x && g.Y == y) return true;
}
return false;
}
/// <summary>
/// 方法：从指定列表里获取指定节点
/// </summary>
/// <param name="grid">节点</param>
/// <param name="list">列表</param>
/// <returns>Grid：返回指定节点</returns>
protected Grid GetGridFromList(Grid grid, List<Grid> list)
{
foreach (Grid g in list)
{
if (g.X == grid.X && g.Y == grid.Y) return g;
}
return null;
}
/// <summary>
/// 方法：计算G耗费
/// </summary>
/// <param name="x">坐标x</param>
/// <param name="y">坐标y</param>
/// <param name="sg">起点</param>
/// <returns>Int：G值</returns>
protected int GetGridCostG(int x, int y, Grid sg)
{
if (sg.fatherGrid != null)
return (sg.X == x || sg.Y == y) ? sg.fatherGrid.GCostAttribute + 10 : sg.fatherGrid.GCostAttribute + 14;
else return 0;
}
/// <summary>
/// 方法：计算H耗费
/// </summary>
/// <param name="x">坐标x</param>
/// <param name="y">坐标y</param>
/// <param name="eg">终点</param>
/// <returns>Int：H值</returns>
protected int GetGridCostH(int x, int y, Grid eg)
{
return Math.Abs(x - eg.X) + Math.Abs(y - eg.Y);
}
/// <summary>
/// 方法：从指定列表中获取F值最小的节点
/// </summary>
/// <param name="list">列表</param>
/// <returns>Grid：F值最小的节点</returns>
protected Grid GetMinFFromList(List<Grid> list)
{
if (list.Count == 0) return null;
int tmpF = list[0].GCostAttribute + list[0].HCostAttribute;
foreach (Grid g in list)
{
if (g.GCostAttribute + g.HCostAttribute < tmpF)
return g;
}
return list[0];
}
/// <summary>
/// 方法：检查当前节点周边的节点
/// </summary>
/// <param name="sg">当前节点</param>
/// <param name="eg">终点</param>
/// <param name="map">Map类的实例</param>
protected void CheckAround(Grid sg, Grid eg, Map map)
{
int gridmapRow = map.LenY;//获取地图的行数
int gridmapCol = map.LenX;//获取地图的列数
Grid[,] gridmap = map.simplemap;
for (int i = sg.X - 1; i < sg.X + 2; i++)
for (int j = sg.Y - 1; j < sg.Y + 2; j++)
{
if (i < 0 || i > gridmapCol - 1 || j < 0 || j > gridmapRow - 1) continue;
if (gridmap[j, i].LandAttribute == 0 || IsInList(i, j, closeList) || (i == sg.X && j == sg.Y)) continue;
gridmap[j, i].HCostAttribute = GetGridCostH(i, j, eg);
if (!IsInList(i, j, openList))
{
gridmap[j, i].fatherGrid = sg;
gridmap[j, i].GCostAttribute = GetGridCostG(i, j, sg);
openList.Add(gridmap[j, i]);
}
else if (gridmap[j, i].GCostAttribute > GetGridCostG(i, j, sg))
{
gridmap[j, i].GCostAttribute = GetGridCostG(i, j, sg);
gridmap[j, i].fatherGrid = sg;
}
}
}
/// <summary>
/// 方法：寻路算法
/// </summary>
/// <param name="sg">起点</param>
/// <param name="eg">终点</param>
/// <param name="map">Map类的实例</param>
internal void Find(Grid sg, Grid eg, Map map)
{
openList.Add(sg);
while (!IsInList(eg.X, eg.Y, openList) || openList.Count == 0)
{
Grid g = GetMinFFromList(openList);
if (g != null)
{
openList.Remove(g);
closeList.Add(g);
CheckAround(g, eg, map);
}
else return;
}
Grid tmpg = GetGridFromList(eg, openList);
Save(tmpg);
}
/// <summary>
/// 方法：保存路径
/// </summary>
/// <param name="g">节点</param>
internal void Save(Grid g)
{
while (g.fatherGrid != null)
{
g.PathAttribute = true;
g = g.fatherGrid;
}
}
}
对于Paths类来说是可以不要实例化的，也就是可以写成静态类。
3)执行（Main函数）
毋须多言，直接实例化就好：
class Program
{
static void Main(string[] args)
{
//初始化地图
Map mapSample = new Map(10, 10);
Grid sg = new Grid() { X = 0, Y = 4 };
mapSample.StartGrid = sg;
Grid eg = new Grid() { X = 9, Y = 5 };
mapSample.EndGrid = eg;
//设置障碍
for (int i = 2; i < 8; i++) mapSample.MapGridSet(mapSample.simplemap[i, 5], 0);
mapSample.MapGridSet(mapSample.simplemap[2, 4], 0);
mapSample.MapGridSet(mapSample.simplemap[7, 4], 0);
//寻路
Paths astarPath = new Paths();
astarPath.Find(mapSample.StartGrid, mapSample.EndGrid, mapSample);
//打印地图和路径
foreach (Grid g in mapSample.simplemap)
{
if (g.X == mapSample.LenY-1)
Console.WriteLine(Grid.Print(g));
else
Console.Write(Grid.Print(g));
}
Console.ReadKey();
}
}
4)结果展示
以上就是我目前的研究进度。当然，A*寻路算法有很多的优化和特例，比如三维A*寻路算法、双向A*算法，比如起点和终点不连通的情形，比如文明5里的六角网格等等。希望能够继续深入，不断将这些消化和总结出来，提升自己。也希望诸位读者不吝赐教！
总之，编程还是很有趣的~
