175452gl6dc3p2e6ibkt2l.jpg
　　NPC寻路也是个老生常谈的话题了，但是一说到NPC寻路，可能就有人迷茫了：哥们儿你说的寻路是什么意思？怎么个寻法？举个例子好不好？寻路这个词是游戏开发中专用的，映射到大家课本上学到的知识点，就是图(数据结构中的图结构)中两点之间的路径。这个路径不是特指最短路径，但它就专门指的就是图中两点之间的路径。

　　1、NPC有聪明也有笨的，聪明的NPC在玩家放大招的冷却时间内会找到一个最短路径直冲玩家去攻击。一个有心计的NPC就门绕到玩家后面去包抄或者偷袭，而胆小的NPC就到处乱跑乱跳了。下面图示表示我能想到的寻路方式。

1753021o1v9xcf2y1aaocc.jpg
　　上面示意图中的图结构，每个网格的十字交叉点是图的节点，连接节点的线就是和节点就是该节点的出度或入度。从上图中可以看出，从A到B，我们给出了四条线。黄线是哪个胆小如鼠的NLC的路线，它左右乱窜，最后终于下定决心去攻击目标。红线和蓝线均是最短路径，同样的速度，NPC可以同时到达目标。绿色的线是那个心机婊，绕到目标后边搞偷袭去了。

　　2、分析。蓝线和红线不用说，是我们根据算法能找到的最短路径，可能找到红线，也可能找到蓝线，根据算法不同而不同，我们总能找到一个最短路径，后边会附上一个最短路径的实现算法，对算法感兴趣的可以参考一下。黄线，是个到处乱攒的路径，到达目标之前一直让这个NPC瞎跑就行了，然后播放对应的动画（胆小的NPC播放瑟瑟发抖，极度聪明的NPC播放故作深沉的动画）。在时间基本上可以了之后，再给这个NPC找个最短路径让它去攻击目标哇。这样看起来这个NPC就有看头了。跑来跑去，有时候还思考，掐指一算，呵呵呵呵呵呵呵呵呵。而绿线就现在是重点了。它是要抽空绕到目标背后的，尽量偷袭目标。算是最聪明的一个NPC。

　　3、分析绿线，这个NPC要绕到目标后面去，我们的寻路系统要做哪些工作。首先，这个NPC能走过的通路要发生变化，普通的NPC是哪里都可以走的，横着 一个格子，竖着一个格子，有格子就能走。但是这个不一样。这个要绕道，不能随便走，要绕到目标后边去。这个NPC的可走的通路并不是想象中的格子，而是下面这样的：

175303fxwecxmmsiii4ns4.jpg
　　比如上面的绿色绕行路线和红色绕行路线。这个时候无视之前我们定义的图的节点的邻接点的组合。把图中出现的这几个点看成相邻节点来找最短路径，这个需要重新为这个NPC定义一个邻接表了。邻接表就是表示相邻两个节点的列表。我们定义几条类似于绿色和红色的可以绕行到目标后面的数个路径，在邻接表表示的图中，这些路径是通的。比如绿色和红色的这条线，包括类似的一些可以绕到目标后面的一些路径。根据需求，邻接表是可以动态修改的，修改后需要重新计算路径。

　　4、实现。热气球来了，马上就能上天！

　　以上寻路设计的基础都是最短路径算法。为什么要最短路径？答：因为不管你怎么走，到最后的目标都是要找到一个目的地，最后一步总是要来个最短路径算法的，所以这个最短路径的算法是基础了。

　　接第三步来的，我们把绕行简化一下有心机的NPC的走法。首先它在一定单位内是走S形状的路线的。

1753032enuz5v55pp992v6.jpg
　　对角线是绿色的线。每一步走一个对角，但是每一个对角有分成了三个小步，这三小步怎么走就随意了，现在我们求这个绿色的对角线连接起来的路径。算法的原理是最短路径算法，地杰斯特拉最短路径。在定义邻接表时候，斜对角为日字的定义为相邻连通节点即可。具体算法如下，可以找这条绿色的通往目标的路径。然后再补充两个绿色节点之间的路径就可以啦！代码如下：

 

  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5.  
  6.  
  7. namespace ShortPathTest
  8. {
  9. class GenShortPath
  10. {
  11. public int GenTargetPath(int tableWidth, int x1, int y1, int x2, int y2)
  12. {
  13. if (tableWidth <= 0) return -1;
  14.  
  15. int retValue = -1;
  16. //初始化一个图
  17. Element[,] map = new Element[tableWidth, tableWidth];
  18. int[,] distance = new int[tableWidth * tableWidth, tableWidth * tableWidth];
  19. List<Element> pointsInMap = new List<Element>();
  20. for (int i = 0; i < tableWidth; i++)
  21. {
  22. for (int j = 0; j < tableWidth; j++)
  23. {
  24. Element e = new Element() { posX = i, posY = j };
  25. map[i, j] = e;
  26. pointsInMap.Add(e);
  27. }
  28. }
  29.  
  30. for (int i = 0; i < tableWidth * tableWidth; i++)
  31. {
  32. for (int j = 0; j < tableWidth * tableWidth; j++)
  33. {
  34. if (i == j)
  35. {
  36. distance[i, j] = 0;
  37. }
  38. else
  39. {
  40. int posX_1 = pointsInMap.posX;
  41. int posY_1 = pointsInMap.posY;
  42.  
  43. int posX_2 = pointsInMap[j].posX;
  44. int posY_2 = pointsInMap[j].posY;
  45.  
  46. //判断两个点的相对位置
  47. if (Math.Abs(posX_1 - posX_2) == 1 Math.Abs(posY_1 - posY_2) == 2)
  48. {
  49. distance[i, j] = 1;
  50. }
  51. else if (Math.Abs(posX_1 - posX_2) == 2 Math.Abs(posY_1 - posY_2) == 1)
  52. {
  53. distance[i, j] = 1;
  54. }
  55. else
  56. {
  57. distance[i, j] = int.MaxValue;
  58. }
  59. }
  60. }
  61. }
  62.  
  63. //寻找路点
  64. int pointStartIndex = tableWidth * x1 + y1;
  65. Dictionary<int, int> dist = new Dictionary<int,int>();
  66. Dictionary<int, List<Element>> path = new Dictionary<int, List<Element>>();
  67. for (int i = 0; i < tableWidth * tableWidth; i++)
  68. {
  69. path = new List<Element>();
  70. dist= distance[i,pointStartIndex];
  71. if (dist < int.MaxValue)
  72. {
  73. path.Add(pointsInMap[pointStartIndex]);
  74. path.Add(pointsInMap);
  75. }
  76. }
  77.  
  78. List<Element> s = new List<Element>();
  79. s.Add(pointsInMap[pointStartIndex]);
  80.  
  81. for (int t = 0; t <= tableWidth *tableWidth - 1; t++)
  82. {
  83. int min = int.MaxValue;
  84. int k = -1;
  85. for (int i = 0; i < tableWidth * tableWidth; i++)
  86. {
  87. if (!s.Contains(pointsInMap) dist < min) {
  88. k = i;
  89. min = dist;
  90. }
  91. }
  92.  
  93. if (min == int.MaxValue) break;
  94.  
  95. s.Add(pointsInMap[k]);
  96.  
  97. for (int i = 0; i < tableWidth * tableWidth; i++)
  98. {
  99. if (!s.Contains(pointsInMap) distance[k, i] != int.MaxValue (dist[k] + distance[k, i]) < dist)
  100. {
  101. dist = dist[k] + distance[k, i];
  102. path = new List<Element>(path[k]);
  103. path.Add(pointsInMap);
  104. }
  105. }
  106. }
  107. foreach (int k in path.Keys)
  108. {
  109. List<Element> curPath = path[k];
  110. Element ele = curPath[curPath.Count - 1];
  111.  
  112. if (ele.posX == x2 ele.posY == y2)
  113. {
  114. string str = Path to::========>>> + curPath[curPath.Count - 1].ToString() + \n;
  115. for (int i = 0; i < curPath.Count; i++)
  116. {
  117. str += curPath.ToString() + -->;
  118. }
  119. Console.WriteLine(str);
  120. }
  121. }
  122.  
  123. return retValue;
  124. }
  125. }
  126. }
复制代码
　　方便又实用，代码也短，可以轻松移植成任意语言。

via：游戏蛮牛

相关阅读：游戏中常用的寻路算法（5）预先计算好的路径的所用空间

锐亚教育

锐亚教育，游戏开发论坛|游戏制作人|游戏策划|游戏开发|独立游戏|游戏产业|游戏研发|游戏运营| unity|unity3d|unity3d官网|unity3d 教程|金融帝国3|8k8k8k|mcafee8.5i|游戏蛮牛|蛮牛 unity|蛮牛