现实世界里，无论人或者动物，通常它们要去某地的话，都会自动选择一条最近的路线。在游戏中也一样，很多RPG游戏都会提供一个功能来让角色自动走到某地。这个功能就是模仿显示世界中的人或者动物的行为，寻找一条最短路径走到目的地。比如国内大部分MMORPG手游都会有一键完成任务的功能，玩家只需要点击一下任务标签，玩家控制的角色就会自动行走到目标NPC附近。那么这个功能是怎么实现的呢?
这个系列的文章将介绍一种基于导航的寻路系统的实现方法。
基于格子（Grid）的寻路
通常提起寻路，人们常常会想起A*寻路，A*算法作为Dijkstra算法的扩展，因其高效性被广泛应用在游戏中，如《星际争霸》中就大量使用。
正如Patrick Wyatt的博客里所述，《星际争霸》是基于魔兽争霸引擎制作的，而早期《魔兽争霸2》的做法就是把地图分成一个个的格子去寻路，如下图所示。
同样的，《星际争霸》虽然是一款斜视角的游戏，但也是用了基于格子的方式来组织地图的寻路信息。不同的是，《星际争霸》划分的格子比《魔兽争霸2》细得多。
到了《魔兽争霸3》时代，该游戏成功将基于格子的寻路应用到了3D场景中。
有了这样的格子作为地图，结合A*算法，寻路算法的实现将会是一件比较容易的事情。详细的A*算法就不再介绍，详细算法可以阅读这篇名为《A* Pathfinding for Beginners》的文章。
基于格子的A*寻路有以下优点：
-
地图构造简单。整个寻路地图都是以相同长宽的正方形格子组合而成。
-
动态阻挡实现简单。每个格子是否可以通行，可以很简单地通过改变其属性的方式来改变同行性。
但是也有一些缺点：
-
寻路地图边缘锯齿太多，边缘不平滑。
-
地图格子数太多。为了使地图边缘不至于太粗糙，很多时候就需要缩小每个格子的面积，同时增加格子数，正如Patrick Wyatt在《星际争霸》里的实践一样。
基于导航（Navigation）的寻路
导航（Navigation）即通常所说的行走层，本质上来说，它还是一个由众多多边形组成的网格模型，所以也称作导航网格（Navigation Mesh）。
导航网格可以很精确的勾勒出地图的可行走区域的形状，只要导航网格能贴合到地面，而且角色能在导航网格面片上行走，就能实现出一套寻路系统。
Unity内置的寻路系统就是基于导航来进行的寻路，但这套工具有个最大的问题就是算法、数据格式不开源，导致了游戏服务端和客户端无法做到同步，因此在实际强联网游戏开发中会采用其他的寻路方案。
Recast Navigation作为一个开源的基于导航的寻路库，具有几乎类似Unity内置寻路系统相同的功能，能自动快速生成导航网格模型，高效的实时运算能让游戏在很短时间内找到一条合理的寻路路径。由于其开源的性质，使得服务器客户端的同步成为了可能，且已经有许多项目成功实践。
但是，即使有Recast Navigation这样成熟的开源项目，我们还是打算在接下来的文章里实现一套轻量级的寻路系统，其意义总结如下。
-
造轮子的过程，同时也是更深入理解导航网格寻路的过程。
-
从原理入手，避免拿来主义。
-
更加灵活，俗话说船小好掉头，可以基于不同项目定制不同的功能。
寻路系统基本功能
-
根据模型数据（例如FBX模型）生成导航网格数据。
-
支持多层导航网格。例如地面和浮空岛分别使两层不同的导航网格。
-
检测导航网格边缘。例如《王者荣耀》的达摩这个英雄就有技能是将人击飞至地图边缘。
-
基于A*的导航网格寻路算法。
-
角色能够站在导航网格上。也就是说根据角色的x和z坐标值，能求出其在行走层上的y值。
-
动态阻挡。比如有些战斗地图会设置阶段的概念，进入下一阶段的地图区域就无法再回到上一区域了，类似有一道隐形的“墙”阻挡住了角色的行走。
后续将会详细讨论以上功能的实现方法。