C#教程之C#实现基本的AStar平面寻路算法|C#教程

金沙澳门官网网址:www.js333com

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

本站最新发布   C#从入门到精通
试听地址  
/eschool/CSharp奥门金沙网址/

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里的六角网格等等。希望能够继续深入,不断将这些消化和总结出来,提升自己。也希望诸位读者不吝赐教!

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

相关教程
        
Baidu
sogou