131907kc64493qy43bq402.jpg
　　文/苯萘蒽菲@indienova

　　引言

　　许多游戏开发的过程中会涉及到自动寻路，而深度优先搜索则是一种实用的、能够处理自动寻路的算法。本文将会对深度优先搜索实现寻路的过程进行解析，并对更深层次的一些内容进行探究。本文介绍算法时将采用伪代码，不使用某一特定的编程语言。本文默认读者已经对深度优先搜索等算法有了一些了解。

　　关于深度优先搜索

　　深度优先搜索（DFS）是用于遍历或搜索树或图形数据结构的算法。一个从根节点开始（在图的情况下选择一些任意节点作为根节点）并且在回溯之前尽可能地沿着每个分支探索。——翻译自维基百科Depth-first search

　　用通俗一点的语言来描述就是：沿着一条路一直走，当无路可走时返回至上一个岔路口走另一条路，直到走完整个图，期间应避免去走已经走过的路。

　　应用到寻路算法中

　　为了更好地展现深度优先搜索算法，我设计了一个基于网格的图：它有着一定的宽度和高度（设定中均为20），除了边缘的节点，每个节点在左、上、右、下四个方向上都与其他节点接壤，其中可以通行的节点为白色，不可通行的节点为深灰色，出发点所在的节点为绿色，终点节点为红色（如图1）。

1319073zvnvnutzo3tho96.jpg
　　根据深度优先搜索算法的描述，该模型的寻路算法用伪代码可表述如下：

 

  1. 起点入栈
  2.  
  3. 循环（栈不为空时）
  4.  
  5. 取栈顶节点作为当前节点并出栈
  6.  
  7. 将当前节点标记为已搜索
  8.  
  9. 若（当前节点是终点）
  10.  
  11. 跳出循环
  12.  
  13. 对于该节点左、上、右、下四个方向（如果处在边缘则舍掉相应的方向）进行遍历
  14.  
  15. 取当前方向前一个节点为下一节点
  16.  
  17. 若（下一节点“深度”为-1 或 当前节点“深度”+ 1 < 下一节点“深度”）
  18.  
  19. 下一节点“深度”设置为 当前节点“深度”+ 1
  20.  
  21. 将下一节点标记为未搜索
  22.  
  23. 将下一节点的父节点设置为当前节点
  24.  
  25. 结束遍历
  26.  
  27. 遍历四个方向
  28.  
  29. 取当前方向前一个节点为下一节点
  30.  
  31. 若（下一节点未搜索）
  32.  
  33. 若（可通行）
  34.  
  35. 下一节点入栈
  36.  
  37. 遍历结束
  38.  
  39. 循环结束

　　更进一步的探究

　　在各种各样的游戏（尤其是策略角色扮演游戏）中，往往会有着地形因素对角色移动的影响。而在上述的例子（包括了模型与算法）中，只有通行与不可通行的设定，而无更加细致的地形因素的设定。

　　对此，我们必须进行一些必要的改动：

　　第一，地图的设定不能再是通行与不可通行了，取而代之的则是每个节点移动时的“耗费”。也就是说，原先的布尔型数组（记录地图的通行与不可通行）将要变为整型数组（记录地图格点移动时的“耗费”）。在本文的模型中，我设置了4种“耗费”（0、1、2和-1，其中-1用来标记不可通行的格点）。这是对模型的更改（如图3）。

131908ztn64m6k2fh62np6.jpg
　　第二，算法中也要体现出地形因素的考虑。在之前的算法中，能对节点“深度”造成影响的只有从起点到某节点的路程：每沿着节点往下搜索一点、“深度”就累加1。而如果要考虑所谓的地形因素（在本模型中即是“耗费”），就应该累加相应的“耗费”。也就是说，之前提到的条件【当前节点“深度”+ 1 < 下一节点“深度”】相应地变更为【当前节点“深度”+ “耗费” < 下一节点“深度”】。这是对算法的更改。

　　这样一来，算法就变成了这样：

 

  1. 将各个节点的“深度”标记为-1，起点的“深度”标记为0
    •  
    • 起点入栈
      •  
      • 循环（栈不为空时）
        •  
        • 取栈顶节点作为当前节点并出栈
          •  
          • 将当前节点标记为已搜索
            •  
            • 若（当前节点是终点）
              •  
              • 跳出循环
                •  
                • 对于该节点左、上、右、下四个方向（如果处在边缘则舍掉相应的方向）进行遍历
                  •  
                  • 取当前方向前一个节点为下一节点
                    •  
                    • 若（下一节点“深度”为-1 或 当前节点“深度”+ “耗费” < 下一节点“深度”）
                      •  
                      • 下一节点“深度”设置为 当前节点“深度”+ “耗费”
                        •  
                        • 将下一节点标记为未搜索
                          •  
                          • 将下一节点的父节点设置为当前节点
                            •  
                            • 结束遍历
                              •  
                              • 遍历四个方向
                                •  
                                • 取当前方向前一个节点为下一节点
                                  •  
                                  • 若（下一节点未搜索）
                                    •  
                                    • 若（可通行）
                                      •  
                                      • 下一节点入栈
                                        •  
                                        • 遍历结束
                                          •  
                                          • 循环结束

　　延伸

　　除了本文提到的网格模型（正方形密铺），其他的模型（比如正六边形密铺）乃至普通的图，均适用深度优先搜索算法，以实现寻路效果，这里不作展开。

　　图5展现了正六边形密铺时深度优先搜索算法实现的寻路效果（在拓扑学中，图中的正方形密铺等价于正六边形密铺，使用正方形只是为了方便）。

1319081v55a5hzr9hiro5q.jpg
via：indienova
相关阅读：游戏中常用的寻路算法（5）预先计算好的路径的所用空间
锐亚教育

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