最近开始做一款新的游戏了。这次要做的是一款横版跳跃类的 mmo 。前段时间客户端遇到一个问题，策划想要做传统 mmo 里的自动寻路（这个中国特色 mmo 的传统也是醉了）。
本来传统 mmo 的寻路还是很好处理的，无论是 2d 平面的场景还是 3d 起伏的场景，把场景拆分成不同的格子，都可以退化成一个 A* 寻路问题，平坦 2d 游戏一般用规整的矩形格子来拟合场景， 3d 起伏场景一般用不规则的多边形去贴合，最后把格子的关系抽象成 A* 能够使用的数据结构，然后问题就退化成了一个 A* 寻路问题。
但这次我们做的是一个类似超级玛丽似的横版游戏，角色可以像马里奥大叔一样跳跃，场景中存在若干平台，可供玩家跳跃上去。这很难抽象成一个 A* 的寻路问题，但我还是在网上找到有同学是这么干的https://www.darkstar.cn/archives/1506。但这么干性能低下不说还有很多限制，甚至会限制美术的设计，所以我不太想这么做。
如果不用 A* ，那么我们该如何寻路呢？
首先，横版游戏跟传统 mmo 在位移上是存在区别的，传统俯视场景的 mmo ，角色在场景里移动，一般来说是无向性的，角色可以朝四面八方任意行走，这也是为什么需要 A* 这种启发式算法去寻路的原因。而对于横版游戏，其实角色只能进行左右位移，以及跳跃这么三种操作。
上图中，假设我们的马里奥大叔想要去到最上方的 ？ 处，那么一种可行的路径是从最下一层，跳跃到头顶上的砖块之上，然后再继续向上跳跃至 ？ 处。
仔细思考一下会发现，在横版游戏的任意平台上做移动是不需要复杂寻路的，比如马里奥大叔在第一层的平台上左右移动，只需要判断是否达到平台边缘或者是否触碰到障碍即可，其他情况直接直线移动过去就可以了。那什么地方需要用到寻路呢？只有当马里奥大叔需要跳跃的时候。换句话说我们做寻路其实就是在寻找跳跃的点。
我们先把寻路会用到的跳跃点记录下来。
图中指出的是能够通过跳跃到达别的平台的点，比如 t1 , t2 可以通过跳跃去到上面那个单砖块的平台， t3 , t4 可以去到两单位砖块的平台， f1 , f4 可以回到地面， f2 可以去到地面、右边、上方三个平台， f3 可以去到地面，左边两个平台， m1 可以回到地面， m2 可以去到下方单砖块平台（为了简化问题暂时不考虑超级玛丽中跳跃后在空中还可以位移的操作）。
有了这些信息，我们做寻路就变成了寻找一条由跳跃点串起来的路径，路径上任意两个相连的跳跃点如果分属于不同平台，就是通过一次跳跃完成连接的，如果属于同一平台，就是通过直线位移完成连接的。比如上面提到的马里奥大叔去到 ？ 处的路径，就可以表达成： t1 -> f1 -> f2 -> m2 。
怎么找到这条跳跃点连接起来的路径呢？我们只需要反向来寻找，先从 ？ 处出发，寻找能够到达 ？ 处的相邻跳跃点 m1 , m2 ，然后再分别寻找能够到达 m1 和 m2 的相邻跳跃点，结果发现 m1 没有跳跃点可以到达， m2 有 f2 可以到达，按照这个方法继续向前寻找，如果遇到没有跳跃点可以到达的情况就抛弃，直到找到和我们出发点相邻的跳跃点就结束。这样一条可达的路径就出现了。
按照这个方法，我为马里奥大叔找到了几条可达路径：
m2 -> f2 -> f1 -> t1
m2 -> f2 -> t2 -> t1
m2 -> f2 -> f3 -> t3 -> t2 -> t1
m2 -> f2 -> f3 -> f4 -> t4 -> t3 -> t2 -> t1
细心的朋友可能会注意到了，按照这个算法，其实能够找到的路径并不止上面几条，甚至还可能在查找中陷入死循环而无法进行下去，比如在回到地面 t3 点的时候，相邻 t3 的除了 t2 还有 t4 ，如果走 t4 路径，就会再回到 f4 ，从而陷入死循环。那么我们有什么办法能够避免出现这种情况呢？
我们先看看我们是如何描述这个问题的，首先我们找出了每个平台的跳跃点，然后记录下他们，不妨给平台编上号，这样方便我们分析问题，请忽略我拙劣的截图工具使用技巧：
平台编号 s0 - s3 ，我们可以把平台间的关系表示如下：
s0 -> s1 : t1 , t2
s0 -> s2 : t3 , t4
s1 -> s0 : f1 , f2
s1 -> s2 : f2
s1 -> s3 : f2
s2 -> s0 : f3 , f4
s2 -> s1 : f3
s3 -> s0 : m1
s3 -> s1 : m2
这样上面的图就变成了这样一串关系式。冒号前面表示从哪个平台到哪个平台，冒号后面表示能够满足条件的跳跃点。这些关系式有什么特点呢？熟悉图论的同学可能已经看出蹊跷了（这里特别感谢 子熏同学 一眼就帮我找出了规律）。这不就是一张图吗？我们来画一下这个关系图：
有了这个图，一切都豁然开朗了。寻路，其实就是在这个图中找到两个节点之间的路径，如果不考虑跳跃的成本，这个图就是一个传统的有向无权图，有向无权图中两个节点的最短路径直接用 bfs 就可以得到了。然后我们只需要针对每张场景图，事先生成一个这样的关系图就可以了，在寻路的时候直接用这个图来寻路。至于两个节点间有多个跳跃点的情况，我们可以使用一个评估函数来挑选一个跳跃点，比如就用离当前位置更近这么一个评估函数，那么我们就很容易得到一个唯一的路径。至此，我们的寻路算法基本就算完成了。
这个算法不限制平台的形状，在单个平台的内的移动不需要寻路，所以可以采用各种表现方式，即使平台不是平面，比如是一个斜面也可以很好的让前端去表现，这个算法的性能一般来说也比上面提到的 A* 算法要高效的多，因为场景的平台数量一般来说是比划分格子要少的多的，而且平台数量其实是一个策划可控的变量，但场景的大小一般来说是无法妥协的。当然，这个算法也有问题，首先，它忽略了在节点内的移动距离，这就导致它求出来的路径不一定是最短移动距离的路径，只能说是最短经过节点数的路径，想要求得真实最短移动距离路径，恐怕还是需要找到所有的可达路径，然后计算每条路径移动的距离。不过我觉得作为自动寻路来说，找出一条可达路径已经足够，至于是否是最短距离路径，我个人觉得并不重要。
后来比较有意思的地方是，我们的策划给角色加了一个叫跳跃力的概念，这样就导致了不同的角色能够跳跃的高度是不同的，想象一下上图中马里奥大叔能够一次就从 s0 跳上 s3 ，这样该如何处理呢？一种比较直接的办法是在需要寻路时根据角色当前的跳跃力，生成上面的节点关系图，但这是非常耗费性能的，仔细思考一下，就会发现，策划所谓的跳跃力虽然看上去是一个连续的量，但实际上对我们节点关系图的影响却是离散的。什么意思呢？假设我们把策划设定的跳跃力范围定为 [1 , 2.5] ，我们把跳跃力为 1 的跳跃距离叫单位跃距，那么我们可以把策划设定的跳跃力分为 2 段，一段是跳跃力在 [1 , 2.0) ，这一段跳跃力只能让角色一次移动到离自己所在平台一个跃距的平台，或横向或向上；第二段是 [2.0 , 2.5] ，这一段跳跃力能够让角色一次移动两跃距的平台。然后在事先生成节点关系图的时候生成 2 张图，一张是 1 跃距图，一张是 2 跃距图，当需要寻路时，按照角色的当前跳跃力属于哪个范围来决定使用哪一张图。其实在实际使用中，我们完全可以全部用 1 跃距图来寻路，因为跳跃力更高只会增多能够到达的平台，但这并不改变 1 跃距图的连接关系。
我们前端是用 js 实现的，所以我 用 js 写了一份实现 ，感兴趣的朋友可以看看。
网友评论