VB.net 2010 视频教程 VB.net 2010 视频教程 python基础视频教程
SQL Server 2008 视频教程 c#入门经典教程 Visual Basic从门到精通视频教程
当前位置:
首页 > Python基础教程 >
  • C#教程之C#实现基本的AStar平面寻路算法

1、算法实施模型

在我看来,最简单最基础的寻路环境是:在一片二维网格区域中存在一些围墙(Block),在起始点和终点之间保持连通的前提下寻找一条最佳路径。

2、算法原理

详细介绍有很多,可参考网址:policyalmanac.org/games,浅显易懂,重点是理解“启发式搜索”的概念。下面谈谈我自己的理解,如果是第一次接触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里的六角网格等等。希望能够继续深入,不断将这些消化和总结出来,提升自己。也希望诸位读者不吝赐教!

总之,编程还是很有趣的~


相关教程