游戏NPC背后的秘密：MMORPG中AI系统的设计与实现
游戏观察7月30日消息，我们在游戏里面不是只有一种寻路算法，一般来说，首先看直线寻路能不能到达，如果可达就直接返回了，如果失败，再尝试寻找更复杂的一条路径，会依次地去尝试贪心寻路、A*寻路、导航网格寻路等方法，直到找到可以到达目的地的路径。
MMORPG游戏中的AI，不是指广义的人工智能，而是特指在游戏内NPC能够通过环境或者事件的变化进行逻辑判断，从而同玩家产生特定的交互行为。它主要包含三个部分，分别是感知、决策、行动。
感知：是指侦测周围环境变化的能力，如玩家进入视野、受到攻击等;
决策：就是根据环境变化思考做出何种反馈，是整个AI框架主要的构成部分，常见的有状态机、行为树;
行动：即NPC做出的具体反馈，如释放技能、寻路等操作。
MMORPG AI是构建在寻路、移动、技能、视野这4个基础功能之上的，寻路、移动和技能属于行动，而视野更多是一种感知。
AI常见的三种实现方式
01、朴素的AI-Hard Code
举一个游戏中常见的例子，一只野猪在没有人的时候需要自动巡逻;当有人进入视野的时候，它需要去接近这个玩家;当它和玩家的距离达到2米的时候，它要发起一个技能;当它血量低于20%时，它要逃跑。而随着我们游戏开发的深入，NPC越来越多，比如小鹿不会攻击只会逃跑，狼不会逃跑但会释放技能。
这时候问题就出现了，我们如果为每一个NPC单独实现一份AI，一款游戏可能有上千种NPC，工作量会非常巨大，而且非常难以扩展和维护。但朴素AI简单、直接、效率非常高，一般在项目初期应急时使用，即项目上线之初，没有时间、没有能力去做AI的时候，可能简单写一个AI先去做测试使用。
02、有限状态机
状态机可以归纳为三个要素，即现在的状态、事件、动作。当一个事件发生，将会触发一个动作，或者执行一次状态的迁移。
状态机有3个缺点：第一是状态流程图过于复杂，非常难以维护;第二是难以扩展，新加状态的时候需要考虑已有状态间的关系;第三是策划不能充分参与其中，只能由程序员来完成，这会增加程序员的工作量。
03、行为树
行为树里面有一个根节点，有若干子节点。节点主要分为控制节点、条件节点和行为节点，条件节点和行为节点执行都有一个结果，成功、失败或者正在运行中，控制节点会根据返回结果执行下一步动作。
行为树的优点是逻辑直观、一目了然，策划可以借助工具直接配置，不需要程序介入。而缺点则是树分支数量庞大，每次遍历寻找合适节点的过程消耗高。
AI寻路的四种实现方式
01、直线寻路
直线寻路最简单，平时经常用的直线生成算法都可以拿来用，但也最容易失败，因为我们整个地图不都是一个大平原，它可能有各种各样的阻挡。
02、贪心寻路
贪心寻路的策略是每次都朝着距离较近的方向逼近一步，如果某一个方向不能走，就尝试另一个方向。其实它还是不够聪明，当它遇到阻挡的时候，它可能要绕很远，或者要执行很长时间才能真正找到它的路径。
03、A*寻路
A*寻路从任意一点开始的时候，把它四周的几个点放到open表里，然后从open表里取出估价函数最小的点，同时更新open表和close表。其中的close表负责存储考察过的点，open表储存已生成而未考察的点。
估价函数： f(n)=g(n)+h(n)
g(n)就是起点到当前点的代价;
h(n)是当前点到终点的代价。
04、导航网格寻路
大平原地图是由很多小格子组成的，如果寻路时，还需要去遍历每个小格子的话，那么大量的时间会浪费在每个小格子的计算中。
这时，可以让导航网格预处理，把地图大平原切割成一个个凸的多边形。多边形之间，会通过一定的数据结构联合组织起来，在这个多边形中再通过A*去寻路，这样就可以一下子跳过很多格子，一次就找到目的地。
我们在游戏里面不是只有一种寻路算法，一般来说，首先看直线寻路能不能到达，如果可达就直接返回了，如果失败，再尝试寻找更复杂的一条路径，会依次地去尝试贪心寻路、A*寻路、导航网格寻路等方法，直到找到可以到达目的地的路径。
