英雄无敌3移动力专题（一） 局部优化

作为一款复杂度极高的游戏，英雄无敌3的理论构建一直是缺失的。本系列主要关注作为英雄无敌3游戏核心的移动力系统以及它与其他系统（如战斗系统与经济系统等）的联系。叙述上主要从一些例子出发，再总结一些相关经验，希望能为真正系统的理论构建提供一些想法和思路。主观因素较多，错误也难以避免，欢迎交流指正。第一篇我们就从最基础的部分讲起，以下正文

将一个问题划分成若干个小部分是一个常见的处理方式，尤其是在移动力规划这么复杂而困难的问题当中。虽然局部移动力利用的优化并不一定带来整体效率的最大化，但是效果往往也不会太差。这篇我们就主要研究如何优化单英雄的移动力消耗。

移动力的获取

单个英雄初始移动力的获取相信大家都很熟悉了，主要的优化方式也很简单，大概就是养步、鞋子这类的宝物等，增加移动力的量也都很容易计算，这里就不详细说明。值得注意的是养步与鞋子、后勤术这类相对比较独立的系统不同，它与战斗系统和经济系统的关系非常密切，因此在后面会专门就此写一个专题。

邻格间的移动

寻找两点间移动力消耗最少的路径可以说是最基础的问题了（这里我们将不考虑飞与跳，因为它们会改变地图的拓扑结构），为此我们先来总结一下邻格移动的基础知识。

游戏冒险地图是由一个个正方形格点构成的，一般的移动有八个可能的方向，可以移到相邻的一个空格中去，多数情况下对角移动消耗移动力都是平移的1.41倍。各种地形上移动力消耗可以总结如下图

一般来讲移动力惩罚百分比只由英雄当前所在格的地形决定，但也有些例外：

从路上到基本地形（就是图中沼泽和它之前的地形）之间的移动，其移动力惩罚由路所覆盖的格子的基本地形决定。

英雄有寻路术、寻路靴或是身上带有游牧民的情况。（飞行与只携带地形优势兵种等可以降低移动力消耗，但并不是降低惩罚百分比）

有时斜向移动消耗并不为直向的1.41倍，一种情况就是我们常说的“偷步”。当 100*基本地形惩罚百分比≤英雄剩余移动力≤141*基本地形惩罚百分比时，这时就只用花费直向的移动力就可以斜向移动了。

几个例子：

两点间的移动优化

有了最基础的知识，我们就可以讨论怎么找到给定两点间移动力消耗最少的路径。已经知道了每一步的移动力消耗，我们就有多种已有的算法来找到最短路径，其中最常用也是英雄无敌3游戏内置的自动寻路算法就是A*算法。具体内容就不详细介绍了，有兴趣可以自己了解。如果你像我一样懒，不想自己去用程序来实现算法，我们可以利用已经做好的程序，那就是游戏本体。

比如这样一种情况，由于中立生物的阻挡，不能直接利用游戏的自动寻路功能找到攻击蓝色英雄的最短路径

我们可以直接自己画一个相同的地形和障碍物设置，把怪物去掉，再利用游戏的寻路功能和一些简单的计算，就知道该走哪条路了。（当然简单情况手算也没问题）

但是有了游戏本身的自动寻路系统这个问题就解决了吗？显然不是的。游戏本身的自动寻路系统是有缺陷的。

1.首先，游戏的自动寻路系统没有充分考虑英雄自身剩余移动力的约束。

还是上面那个例子，自动寻路系统给出的提示是从下面走，我们的红色英雄1560点移动力，第一天从下面走可以走到下图中的位置，第二天还需要花费1082点移动力

但是从上面走，我们发现第二天只需要花费1046点移动力

那么显然上面那条路是更好的。究其原因，我们发现从下面走时第一天溢出了55点移动力，而上面走只溢出了14点移动力，而自动寻路系统并不会考虑移动力溢出的问题。因此造成了实际结果与自动寻路提示的不同，因此要改进游戏的自动寻路算法也很简单，这里就不多说明，有兴趣可以尝试。要注意的就是除了过天之外，上下船，天鹅湖等也会造成移动力的溢出。

2.其次，自动寻路系统没有考虑一些特殊的移动方式，例如回城，“坐飞机”，传送门等，但我们也有比较成熟的解决方案。比如我们可以将城，怪物，传送门等看作一个个的特殊节点，除了一般的邻格移动方式之外，我们再在图中加入一些特殊节点之间的边，比如对应传送门之间的边长就是0，坐飞机也就是从怪物的邻格到占领的城镇间的边长为0的单向的边（这是不考虑具体战斗的情况）。这时熟悉算法的玩家肯定知道怎么处理了，在此不多展开。当然，简单情形也可以手算找到最优路径，方法类似。

多点间的移动优化

解决了两点间的移动优化问题，我们来看多点之间的移动优化问题。比如下图中的典型问题，有很多棵树，我们想从传送门出发，把每一颗树都访问一遍（或许还有回到传送门的要求），问怎样消耗的移动力最少。