版权归作者所有，转载请注明出处
游戏中自动寻路浅谈
今天和朋友们讨论了一下自动寻路的实现方式。虽然unity3D是有自动寻路功能，而且已经非常成熟。但是我们还是有很多游戏没有用到引擎，无论是MMORPG（手游，页游）还是RPG，MOBA类，都是需要用到自动寻路功能的。对于没有引擎但仍需要用到自动寻路的游戏，我们怎么实现这个问题呢？
首先，我们要明确，我们今天讨论的游戏类型。这种游戏，没有用到引擎，一般是体量较小，服务器承载能力较差，对画质要求不高。对于这种游戏，用户对画面要求不高，但是一般追求高流畅度。因为该游戏体量较小，所以关卡地图复杂度不高，自动寻路的使用不是为了“解迷宫”，而是为了简化操作。
综上所述，我认为，针对这种游戏所设计的自动寻路系统有以下几个特征：1.尽量使玩家在游戏过程中，服务器的计算量减少，减轻服务器压力。2.地图复杂度不高，所以可以使用简化版人工智能的算法。3.要为用户人物的行动路线计算出后，所使用的steering behavior修正或cooperate movement修正算法所需要的计算时间和服务器压力预留出空间。
具体实现方式有以下几种：
1.不需要任何算法。
一般用于简单地图的对话任务、送物品任务和任务的提交。需要策划点出两个位置之间的路点。
这种情况分为2种情况：1.主路路点。2.野外路点。（保证用户在做任务到一半，跑去地图随机位置后再进行任务）
2.增加简单地图元素。
可是当地图工作量巨大或非任务类自动寻路时。例如：RTS类游戏，需要步兵从基地自动走到战斗地点。这类自动寻路 无法提前规划好每一次的起始点和目的地，就需要一些简化的搜算算法。
2.1导航方格
导航方格是为了让用户顺利避开障碍物所设计，并把地图离散化，有利于后期程序搜索算法的使用。具体方法很简单，我只需要选择一个合适的正方形的边的大小，然后在地图上没有障碍物的地方画square就可以了。然后我们可以选取每一个square的中心，作为小人实际可以走的点，这样这个地图就成了下图模样(图中绿色的方格代表每一个grid，方格的中心才是可以走的点)。
利用这种方法可以迅速离散化地图，减轻策划的工作压力和A*算法的结合也非常容易。但是计算量很大，需要考虑到自己游戏地图的大小和计算流畅度。并且，如果方格过大，走路会不连续，违和感。如果方格过小，计算量会指数上升。
2.2导航网格
将可以行走的区域，画成若干凸多边形。 如图：
这里我们利用了凸多边形的特性，即在多边形内运动无法跳出凸多边形的束缚。
接下来， 我们知道任意一个三角形都是凸多边形，我们可以先通过地图的边界点和障碍物的边界点，将地图划分成很多个三角形，如下图所示。
我们可以看到，虽然通过这种方法生成的网格相比grid已经大大减少，但是图上很多相邻的三角形是可以合并形成新的凸多边形的。所以我们其实还可以进一步优化，将可以合并成新的凸多边形的相邻多边形合并，并重复这一过程，最终得到下图
然后我们可以在每一个网格每一条边的中点上放置pathnode(路径点)，然后将每一个网格自己边上的路径点连接起来就得到了完整的路径网络了，如下图，同上绿色的线代表画好的navigation mesh，蓝色的线代表可以走的路径网络。
我们可以看出，通过这种方法得到的格栅比第一种方法少很多。所以计算量会减少很多，而且走出的路径会更加自然。
以上是几种，是我能想到的几种自动寻路方法。当然每种方式只介绍了游戏策划师力所能及的部分，至于后期的无论A*算法或贪婪算法等，要交由程序实现。
