目前大多数使用的寻路算法有哪些？
目前市面上大部分游戏的寻路算法是A*，或者B*。
A*通常所说的是最优算法也就是寻找最短路径。
B*碰撞式算法也就是，也就是不断的去碰撞能走就走，不管是不是绕路。
当然以上都是我的理解。
我这里只描述一下A*算法的一部分。
通常A*算法分为四方向和八方向计算。
现目前的游戏方式来看不管是2D还是2.5D，还是3D，几乎都采用8方向方式，也有游戏是采用360°点位方式。
本文重点剖析8方向的。
先来看一个效果图
图中你看到的图案表示非阻挡地区，其余是阻挡地区。
绿色的线是表示寻路走过路线。
寻路步骤
1. 从起点A开始, 把它作为待处理的方格存入一个"开启列表", 开启列表就是一个等待检查方格的列表.
2. 寻找起点A周围可以到达的方格, 将它们放入"开启列表", 并设置它们的"父方格"为A.
3. 从"开启列表"中删除起点 A, 并将起点 A 加入"关闭列表", "关闭列表"中存放的都是不需要再次检查的方格
原谅我盗用了园友的图。
图中浅绿色描边的方块表示已经加入 "开启列表" 等待检查. 淡蓝色描边的起点 A 表示已经放入 "关闭列表" , 它不需要再执行检查.
从 "开启列表" 中找出相对最靠谱的方块, 什么是最靠谱? 它们通过公式 F=G+H 来计算.
废话不多说了，直接来源码
源码来之园友，但是稍作修改。
修改1，原本算法不支持复杂地形图。
修改2，原本算法foreach List列表，改为for循环，倒入循环。因为每一次的寻路下一个节点的时候8方向都是上一个节点。
修改3，修改单例模式。
来一张大图看看目前我的地形图
源码
1 public class FindWayManager 2 { 3 static readonly FindWayManager instance = new FindWayManager(); 4 public static FindWayManager Instance { get { return instance; } } 5 6 /// <summary> 7 /// 阻挡点配置，， 8 /// </summary> 9 public int BlockConst = 1; 10 11 //从开启列表查找F值最小的节点 12 private Point GetMinFFromOpenList(List<Point> Open_List) 13 { 14 Point Pmin = null; 15 16 int count = Open_List.Count; 17 for (int i = count - 1; i >= 0; i--) 18 { 19 if (Pmin == null || Pmin.G + Pmin.H > Open_List[i].G + Open_List[i].H) 20 Pmin = Open_List[i]; 21 } 22 return Pmin; 23 } 24 25 //判断关闭列表是否包含一个坐标的点 26 private bool IsInCloseList(int x, int y, List<Point> Close_List) 27 { 28 if (Close_List == null || Close_List.Count == 0) 29 { 30 return false; 31 } 32 33 int count = Close_List.Count; 34 for (int i = count - 1; i >= 0; i--) 35 { 36 if (Close_List[i].X == x && Close_List[i].Y == y) 37 return true; 38 } 39 return false; 40 } 41 //从关闭列表返回对应坐标的点 42 private Point GetPointFromCloseList(int x, int y, List<Point> Close_List) 43 { 44 int count = Close_List.Count; 45 for (int i = count - 1; i >= 0; i--) 46 { 47 if (Close_List[i].X == x && Close_List[i].Y == y) 48 return Close_List[i]; 49 } 50 return null; 51 } 52 53 //判断开启列表是否包含一个坐标的点 54 private bool IsInOpenList(int x, int y, List<Point> Open_List) 55 { 56 int count = Open_List.Count; 57 for (int i = count - 1; i >= 0; i--) 58 { 59 if (Open_List[i].X == x && Open_List[i].Y == y) 60 return true; 61 } 62 return false; 63 } 64 //从开启列表返回对应坐标的点 65 private Point GetPointFromOpenList(int x, int y, List<Point> Open_List) 66 { 67 int count = Open_List.Count; 68 for (int i = count - 1; i >= 0; i--) 69 { 70 if (Open_List[i].X == x && Open_List[i].Y == y) 71 return Open_List[i]; 72 } 73 return null; 74 } 75 76 //计算某个点的G值 77 private int GetG(Point p) 78 { 79 if (p.Next == null) return 0; 80 if (p.X == p.Next.X || p.Y == p.Next.Y) return p.Next.G + 10; 81 else return p.Next.G + 14; 82 } 83 84 //计算某个点的H值 85 private int GetH(Point p, Point pb) 86 { 87 return Math.Abs(p.X - pb.X) + Math.Abs(p.Y - pb.Y); 88 } 89 90 //检查当前节点附近的节点 91 private void CheckP8(Point p0, byte[,] map, Point pa, Point pb, List<Point> Open_List, List<Point> Close_List) 92 { 93 //这里的循环其实就是8方向判断 94 for (int xt = p0.X - 1; xt <= p0.X + 1; xt++) 95 { 96 for (int yt = p0.Y - 1; yt <= p0.Y + 1; yt++) 97 { 98 //排除超过边界和等于自身的点 99 if ((xt >= 0 && xt < map.GetLongLength(1) && yt >= 0 && yt < map.GetLongLength(0)) && !(xt == p0.X && yt == p0.Y)) 100 { 101 //排除障碍点和关闭列表中的点 102 if (map[yt, xt] != BlockConst && !IsInCloseList(xt, yt, Close_List)) 103 { 104 Point pt = GetPointFromOpenList(xt, yt, Open_List); 105 if (pt != null) 106 { 107 //如果节点在开启列表中更新带价值 108 int G_new = 0; 109 if (p0.X == pt.X || p0.Y == pt.Y) G_new = p0.G + 10; 110 else G_new = p0.G + 14; 111 if (G_new < pt.G) 112 { 113 //Open_List.Remove(pt); 114 pt.Next = p0; 115 pt.G = G_new; 116 //Open_List.Add(pt); 117 } 118 } 119 else 120 { 121 //不在开启列表中,如果不存在创建添加到开启列表中 122 pt = new Point(); 123 pt.X = xt; 124 pt.Y = yt; 125 pt.Next = p0; 126 pt.G = GetG(pt); 127 pt.H = GetH(pt, pb); 128 Open_List.Add(pt); 129 } 130 } 131 } 132 } 133 } 134 } 135 136 public Point FindWay(byte[,] r, int sx, int sz, int ex, int ez) 137 { 138 //定义出发位置 139 Point pa = new Point(); 140 pa.X = sx; 141 pa.Y = sz; 142 //定义目的地 143 Point pb = new Point(); 144 pb.X = ex; 145 pb.Y = ez; 146 //如果点超出范围，或者是阻挡点 147 if (0 < pb.X && pb.X < r.GetLength(1) 148 && 0 < pa.X && pa.X < r.GetLength(1) 149 && 0 < pb.Y && pb.Y < r.GetLength(0) 150 && 0 < pa.Y && pa.Y < r.GetLength(0) 151 && !CheckBlocking(r, pa) 152 && !CheckBlocking(r, pb)) 153 { 154 //开启列表 155 List<Point> Open_List = new List<Point>(); 156 //关闭列表 157 List<Point> Close_List = new List<Point>(); 158 159 Open_List.Add(pa); 160 while (!(IsInOpenList(pb.X, pb.Y, Open_List) || Open_List.Count == 0)) 161 { 162 Point p0 = GetMinFFromOpenList(Open_List); 163 if (p0 == null) return null; 164 Open_List.Remove(p0); 165 Close_List.Add(p0); 166 CheckP8(p0, r, pa, pb, Open_List, Close_List); 167 } 168 Point p = GetPointFromOpenList(pb.X, pb.Y, Open_List); 169 return Reverse(p); 170 } 171 return null; 172 } 173 174 Point Reverse(Point point) 175 { 176 //新节点 177 Point newNode = null; 178 //当前节点 179 Point current = point; 180 while (current != null) 181 { 182 //取当前节点的下一个，放入临时节点中 183 Point temp = current.Next; 184 //将当前节点的下一个设置为新节点 185 //(第一次将设置为null，也对着呢，因为第一个节点将作为尾节点) 186 current.Next = newNode; 187 //把当前节点给新节点 188 newNode = current; 189 //把临时节点给当前节点（就是取当前节点的下一个而已） 190 current = temp; 191 } 192 //将最后的新节点给头节点 193 return newNode; 194 } 195 196 public bool CheckBlocking(byte[,] r, Point point) 197 { 198 return CheckBlocking(r, point.X, point.Y); 199 } 200 201 public bool CheckBlocking(byte[,] r, int x, int y) 202 { 203 return r[y, x] == BlockConst; 204 } 205 206 public void PrintMap(byte[,] r) 207 { 208 Console.Clear(); 209 Console.ForegroundColor = ConsoleColor.Gray; 210 for (int y = 0; y < r.GetLongLength(0); y++)//Y轴 211 { 212 for (int x = 0; x < r.GetLongLength(1); x++)//X轴 213 { 214 Console.Write(r[y, x]); 215 } 216 Console.Write("\n"); 217 } 218 219 } 220 221 public void PrintWay(byte[,] r, Point way) 222 { 223 Console.ForegroundColor = ConsoleColor.Green; 224 while (way != null) 225 { 226 Console.CursorLeft = way.X; 227 Console.CursorTop = way.Y; 228 Console.Write("4"); 229 System.Threading.Thread.Sleep(50); 230 way = way.Next; 231 } 232 Console.ForegroundColor = ConsoleColor.Gray; 233 } 234 235 bool check(int x, int y, Point way) 236 { 237 Point f = way; 238 while (f != null) 239 { 240 if (f.X == x && f.Y == y) 241 { 242 return true; 243 } 244 f = f.Next; 245 } 246 return false; 247 } 248 } 249 250 public class Point 251 { 252 //坐标点 253 public int Y { get; set; } 254 //坐标点 255 public int X { get; set; } 256 //从起点到当前点的代价 257 public int G { get; set; } 258 //从终点到当前点的代价 259 public int H { get; set; } 260 261 public Point() 262 { 263 } 264 265 public Point Next { get; set; } 266 }
由于地图阻挡点配置是由工具决定的，所以我根据我这里的方式来创建测试代码
1 using System; 2 using System.Collections.Generic; 3 using System.Linq; 4 using System.Text; 5 using System.Threading.Tasks; 6 using System.Xml.Serialization; 7 8 namespace ConsoleApplication1 9 { 10 [XmlRootAttribute("SceneInfo_Server")] 11 [Serializable] 12 public class MapBlockConfig 13 { 14 public MapBlockConfig() 15 { 16 17 } 18 [XmlAttribute("MapID")] 19 public int MapID { get; set; } 20 21 [XmlElement("WalkSetting")] 22 public WalkSetting Walk { get; set; } 23 24 [Serializable] 25 public class WalkSetting 26 { 27 public WalkSetting() 28 { 29 30 } 31 [XmlAttribute("RZLEN")] 32 public int Rzlen { get; set; } 33 34 35 [XmlAttribute("RXLEN")] 36 public int Rxlen { get; set; } 37 38 39 [XmlAttribute("STARTX")] 40 public int Startx { get; set; } 41 42 43 [XmlAttribute("STARTY")] 44 public int Starty { get; set; } 45 46 47 [XmlAttribute("STARTZ")] 48 public int Startz { get; set; } 49 50 51 [XmlAttribute("BLOCKINFO")] 52 public String Blockinfo { get; set; } 53 } 54 55 } 56 }
阻挡配置
<?xml version="1.0" encoding="utf-8"?> <SceneInfo_Server xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xsd="http://www.w3.org/2001/XMLSchema" MapID="3501"> <WalkSetting RZLEN="120" RXLEN="120" STARTX="0" STARTY="200" STARTZ="0" BLOCKINFO="111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000011111111111111111111111111111111111111111111111111111111111111111111111111110000000000011111111111111111111110000000000001111111111111111111111111111111111111111100000000001111111111111111111111000000000000001111111111111111111100000000000000011111111111111111111111111111111111111000000000000111111111111111111110000000000000000111111111111111111000000000000000011111111111111111111111111111111111100000000000000011111111111111111110000000000000000111111111111111110000000000000000011111111111111111111111111111111111000000000000000001111111111111111100000000000000000011111111111111100000000000000000011111111111111111111111111111111110000000000000000000111111111111111100000000000000000011111111111111000000000000000000011111111111111111111111111111111100000000000000000000001111111111111100000000000000000001111111111111100000000000000000011111111111111111111111111111111100000000000000000000000111111111111100000000000000000001111111111111110000000000000000011111111111111111111111111111111100000000000000000000000011111111111110000000000000000001111111111111100000000000000000111111111111111111111111111111111100000000000000000000000001111111111110000000000000000001111111111110000000000000000000111111111111111111111111111111111100000000000000000000000001111111000000000000000000000001111111111100000000000000000001111111111111111111111111111111111100000000000000000000000000000000000000000000000000000001111111110000000000000000000011111111111111111111111111111111111100000000000000000000000000000000000000000000000000000001111111100000000000000000000111111111111111111111111111111111111100000000000000000000000000000000000000000000000000000000000000000000000000000000011111111111111111111111111111111111111100000000000000000000000000000000000000000000000000000000000000000000000000000000111111111111111111111111111111111111111100000000000000000000000001111111000000000000000000000000000000000000000000000011111111111111111111111111111111111111111100000000000000000000000001111111000000000000000000000000000000000000000000000111111111111111111111111111111111111111111100000000000000000000000001111111000000000000000000000000000000000000000000011111111111111111111111111111111111111111111111100000000000000011111111111111100000000000000000000000000000000000000000111111111111111111111111111111111111111111111111100000000000000011111111111111111000000000000000000000000000000000000011111111111111111111111111111111111111111111111111100000000000000111111111111111111100000000000000000000010000000000000111111111111111111111111111111111111111111111111111100000000000000111111111111111111111000000000000000000111000000000001111111111111111111111111111111111111111111111111111100000000000001111111111111111111111100000000000000001111100000000001111111111111111111111111111111111111111111111111111100000000000001111111111111111111111111000000000000011111100000000001111111111111111111111111111111111111111111111111111100000000000001111111111111111111111111111111111100111111100000000001111111111111111111111111111111111111111111111111111100000000000111111111111111111111111111111111111111111111100000000001111111111111111111111111111111111111111111111111111000000000000111111111111111111111111111111111111111111111110000000001111111111111111111111111111111111111111111111111111000000000000111111111111111111111111111111111111111111111110000000001111111111111111111111111111111111111111111111111111000000000000111111111111111111111111111111111111111111111111000000001111111111111111111111111111111111111111111111111111000000000000111111111111111111111111111111111111111111111110000000001111111111111111111111111111111111111111111111111111000000000000111111111111111111111111111111111111111111111110000000001111111111111111111111111111111111111111111111111111000000000000111111111111111111111111111111111111111111111110000000001111111111111111111111111111111111111111111111111111000000000000011111111111111111111111111111111111111111111110000000001111111111111111111111111111111111111111111111111111000000000000011111111111111111111111111111111111111111111111000000000111111111111111111111111111111111111111111111111111000000000000011111111111111100001111111111111111111111111111000000000001111111111111111111111111111111111111111111111111000000000000011111111111111000000000000000001111111111111111100000000000011111111111111111111111111111111111111111111111000000000000011111111111110000000000000000000000000011111111110000000000000011111111111111111111111111111111111111111111000000000000011111111111000000000000000000000000000001111111111100000000000000111111111111111111111111111111111111111111000000000000011111111110000000000000000000000000000001111111111100000000000000001111111111111111111111111111111111111111100000000000011111111100000000000000000000000000000000111111111100000000000000000011111111111111111111111111111111111111100000000000011111110000000000000000000000000000000000111111111100000000000000000000111111111111111111111111111111111111100000000000011111110000000000000000000000000000000000111111111100000000000000000000001111111111111111111111111111111111100000000000011111100000000000000000000000000000000000111111111100000000000000000000000011111111111111111111111111111111100000000000011111100000000000000000000000000000000000111111111100000000000000000000000000111111111111111111111111111111100000000000011111100000011000000000000000000000000000111111111100000000000000000000000000111111111111111111111111111111100000000000011111100000111110000000000000000000000000111111111100000000000000000000000000111111111111111111111111111111100000000000011111100000111111000000000000000000000000111111111100000000000000000000000000011111111111111111111111111111100000000000111111100000001111000000000000000000000000111111111100000000000000000000000000011111111111111111111111111111100000000000111111000000000001000000000000000000000000111111111100000000000000000000000000001111111111111111111111111111100000000000111111000000000000000000000000000000000000111111111100000000000000000000000000001111111111111111111111111111100000000000111111000000000000000000000000000000000000111111111100000000000000000000000000000111111111111000000000000111100000000000111111000000000000000000000000000000010001111111111100000000000000000000000000000111111111111000000000000111100000000000111111000000000010000000000000000000111111111111111100000000000000000000000000000011111111111000000000000111100000000001111111000001111111111111111111111111111111111111111100000000000000000000000000000011111111111000000000000111100000000001111110000000111111111111111111111111111111111111111100000000000000000000000000000011111111111000000000000111100000000001111111000000111111111111111111111111111111111100000000000000000000000000000000000001111111111000000000011111100000000001111111000000111111111111111111111111111111111000000000000000000000000000000000000001111111111000000000011111100000000001111111000000111111111111111111111111111111111000000000000000011100000000000000000001111111111000000000011111110000000001111111100000111111111111111111111111111111111000000000000000111111100000000000000001111111111000000000011111110000000000111111100000111111111111111111111111111111111000000000000000111111111100000000000001111111111000000000011111110000000000111111100000011111111111111111111111111111110000000000000000111111111100000000000001111111111000000000111111110000000000111111110000001111111111111111111111111111110000000000000001111111111100000000000001111111111000000000111111110000000000011111110000000111111111111111111111111111110000000000000001111111111000000000000001111111111000000001111111110000000000011111110000000011111111111111111111111111100000000000000011111111111000000000000001111111111000000001111111111000000000111111110000000001111111111111111111111111100000000000000011111111111000000000000001111111111000000000111111111000000000111111111000000000111111111111111111111111100000000000000011111111110000000000000001111111111000000000111111111000000000011111111000000000111111111111111111111111000000000000000111111111110000000000000001111111111000000000111111111000000000011111111000000000011111111111111111111111000000000000000111111111110000000000000001111111111000000000111111111000000000011111111100000000011111111111111111111111000000000000000111111111100000000000000001111111111000000000111111111000000000001111111100000000011111111111111111111110000000000000001111111111100000000000000001111111111000000000111111111000000000001111111100000000011111111111111111111000000000000000001111111111100000000000000001111111111000000000111111111000000000001111111110000000011111111111111111100000000000000000001111111111000000000000000001111111111000000000111111111000000000000011111110000000011111111111111110000000000000000000011111111111000000000000000001111111111000000000111111111000000000000011111110000000011111111111111000000000000000000000011111111110000000000000000001111111111000000000111111111000000000000001111111000000011111111111100000000000000000000000011111111110000000000000000001111111111000000000111111111000000000000000111111000000000000000000000000000000000000000000011111111110000000000000000001111111111000000000111111111000000000000000111111000000000000000000000000000000000000000000001111111111000000000000000001111111111000000000111111111000000000000000111111000000000000000000000000000000000000000000001111111111000000000000000001111111111000000000111111111000000000000000111111000000000000000000000000000000000000000000000111111111000000000000000011111111111000000000111111111000000000000000111111000000000000000000000000000000000000000000000111111111100000000000000111111111111000000000111111111000000000000000111110000000000000000000000000000000000000000000000111111111100000000000001111111111111000000000111111111000000000000000111110000000000000000000000000000000000000000000000011111111100000000000001111111111111000000000111111111000000000000000111110000000000000000000000000000000000000000000000011111111110000001111111111111111111000000000111111111000000000000000111110000000000000000000000000000000000000000000000001111111110000001111111111111111111000000000111111111000000000000000111110000000000000000000000000000000000000000000000001111111111000001111111111111111111000000000111111111100000000000001111110000000000000000000000000000000000000000000000001111111111111111111111111111111111000000000011111110000000000000111111100000000000000000000000000000000000100000000000000111111111111111111111111111111111000000000001111100000000000001111111100000000000000000000000000000000001111000000000000111111111111111111111111111111111000000000001110000000000000001111111100000000000000000000000000000000111111111000000000111111111111111111111111111111111000000000000100000000000000001111111100000000000000000000000000000001111111111110000000111111111111111111111111111111111000000000000000000000010000111111111100000000000000000000000000000011111111111111110000111111111111111111111111111111111000000000000000000000111111111111111111111110000000000000000000000111111111111111111111111111111111111111111111111111111000000000000000000001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111" /> </SceneInfo_Server>
测试代码
1 ConsoleApplication1.MapBlockConfig block = new ConsoleApplication1.MapBlockConfig(); 2 System.Xml.Serialization.XmlSerializer xml = new System.Xml.Serialization.XmlSerializer(block.GetType()); 3 System.IO.FileStream fs = new System.IO.FileStream("3501.block.xml", System.IO.FileMode.Open); 4 block = (ConsoleApplication1.MapBlockConfig)xml.Deserialize(fs); 5 fs.Dispose(); 6 7 R = new byte[block.Walk.Rzlen, block.Walk.Rxlen]; 8 9 for (int z = 0; z < block.Walk.Rzlen; z++) 10 { 11 for (int x = 0; x < block.Walk.Rxlen; x++) 12 { 13 char item = block.Walk.Blockinfo[block.Walk.Rxlen * z + x]; 14 R[z, x] = Convert.ToByte(item + ""); 15 } 16 } 17 18 List<int[]> ss = new List<int[]>();//{ { 7, 60, 55, 55 } }; 19 ss.Add(new int[] { 7, 60, 55, 55 }); 20 ss.Add(new int[] { 9, 80, 113, 60 }); 21 ss.Add(new int[] { 9, 80, 55, 90 }); 22 Random ran = new Random(); 23 Console.ReadLine(); 24 FindWayManager.Instance.PrintMap(R); 25 Console.ReadLine(); 26 while (true) 27 { 28 FindWayManager.Instance.PrintMap(R); 29 Point way = null; 30 System.Diagnostics.Stopwatch watch = new System.Diagnostics.Stopwatch(); 31 watch.Start(); 32 int index = ran.Next(ss.Count); 33 int[] points = ss[index]; 34 way = FindWayManager.Instance.FindWay(R, points[0], points[1], points[2], points[3]); 35 watch.Stop(); 36 Console.Title = "寻路用时：" + (watch.ElapsedMilliseconds); 37 FindWayManager.Instance.PrintWay(R, way); 38 System.Threading.Thread.Sleep(1000); 39 } 40 Console.ReadLine();
效果图请参考上面的。
特别声明：
感谢园友提供的思路和源码。我只是稍作修改。
看几张性能分析图
原本的对园友的代码优化和修改，就是基于这个性能分析结果得来。
再一次的测试发现如果把关闭列表用 Dictionary<string, Point> Close_List = new Dictionary<string, Point>();
性能还能再次提升。
但是如果把openlist也改为 Dictionary<string, Point> 性能却不如从前了。
以上四张图都是程序运行一段时间稳定后截图。
期待大神，有更优化的算法~！
