年初接手翻新手上游戏的 AI 系统，因而实作了一个只依靠区域性碰撞回避进行移动的
AI 系统。反正当个纪录都好，想想就决定写个一篇文章尝试有系统性地说明。
其实这个名字并不够说明完整厘清这个 AI 能干嘛，但至少有涵盖最重要的主要目的：“
低效能需求”、“区域性”、“碰撞回避”。而在开始解释区域性碰撞回避 AI 之前，不
得不先说明原系统的缺陷，才能够了解实作碰撞区域性碰撞回避 AI 的理由以及对应的优
缺点。

然后因为不知道为什么我现在上传图片到 Imgur 都会传不上去，所以图片是上传巴哈后
的小屋网址 QQ


零、原系统缺陷
原系统基本上是采用 Unity 的 Nav Mesh Agent 为基础在制作的。在几个网络上看到的
影片中都显示 Nav Mesh Agent 可以有杰出的效能表现，就算上千个 Agent 在跑也没问
题。
Nav Mesh Agent 顾名思义就是借由预先或动态更新烤起来的 Nav Mesh 来进行移动的存
在。身为 Nav Mesh Agent 拥有完整的空间资讯，对于位置移动来说可以提供非常高精度
结果，无论是要移动到目标地点的能力，还是途中避免撞到其他物件的能力都会好很多。
这件事情对一般游戏来说是好事，毕竟谁也不想让自己的游戏充满顶着墙壁走路的人物。
本来使用 Nav Mesh Agent 对于关卡结构复杂度高的游戏应该是好事，而我正在开发的游
戏《自动混乱》因为涉及随机生成关卡而容易出现复杂度很高的几何，若是使用 Nav
Mesh Agent 应该可以有很好的结果。
https://i.imgur.com/JhwXkLk.png
（↑随便生成的一个关卡版面，由于空间障碍物的种类繁多，还会有比上图更加难以穿梭
的结构）
坏事呢？
Nav Mesh 能最大化发挥的情境是静态场景。虽然 Nav Mesh 也能进行动态修改，但是相
关的管理就没有办法轻松处理。
虽然让上千个 Nav Mesh Agent 同时跑本身不是个问题，但是前提是这上千个 Nav Mesh
Agent 不会同时要求 CPU 回传路径资讯，也不会需要频繁更新移动目标。

《自动混乱》在设计上是个节奏比较快的游戏，敌我行动能力、击杀速度都相当的快，为
了要挑战玩家，我希望让敌人能相对快速地应对玩家来进行移动。
实际上确实有其他合理的作法，像是降低路径规划请求频率、分散各 AI 请求的时机（参
考：CJ 猫的时域切割 #1OqsJooL ）。
但另一方面这款游戏也涉及关卡随机产生的游戏设计，让维护 Nav Mesh 本身变成相对麻
烦的事情。
由于当时为了要实作方便管理结果的 AI，包含想要用更正规的指令式行动设计包装起来
，因此最后决定来实作完全仰赖区域性碰撞回避执行的 AI。

一、区域性碰撞回避 AI
区域性碰撞回避（Local Collision Avoidance），也就是相对于全域（Global）来说并
不知道关卡全貌而尝试避免碰撞。
我的实作方式基本上是想像成 AI 有 20 个移动方向可以选择，每个 Frame 都会重新确
认一次自己对于各方向的偏好。根据自己的偏好，尽量往该方向转。（这部分可以额外最
佳化，参考：CJ 猫的时间切割 #1Wi9bSCE 与延迟蒐集 #1Wf04-GB ）
例如说 AI 可能不偏好往陷阱和障碍物移动，但是偏好往玩家角色移动。
https://i.imgur.com/FzeyW4p.png
这组 AI 的基本运作逻辑包含：
－避免移动中撞上障碍物
－对各个障碍物有偏好
－偏好维持原本的移动方向
－偏好往指定的目标移动
－与指定的目标保持指定距离

根据上面几件事情，我们可以对这 20 个方向进行加减分并且以绿线表示喜欢、红线表示
不喜欢，以长度表示幅度：
https://i.imgur.com/NbMNkPR.png
接着我们在每个 Frame 都让敌人尽量转向他最喜欢的方向前进。如此一来骨干就算是完
成了，实作出来大概就会长这样，虽然实作上很简单但效果其实很好：
https://twitter.com/RandomDevDK/status/1348143680968818688?s=20

二、物理性行动
在偏好方向上基本概念很简单也很好实作，完成之后 AI 就可以用很低负担的方式持续在
环境中移动而不会撞墙感觉很笨。但要让 AI 的移动上让人有理所当然的感觉就还有待努
力。
其中最重要的就是要让 AI 的物理性质有某种正确性，才能看起来合理，而这个正确性就
源于加减速。
https://i.imgur.com/tkP7tyU.png
加减速应该很好理解，总之要使力速度才会慢慢变快，使力才能让速度慢慢减少。如果
AI 会瞬间以最高速度行动的话看起来就会很滑顺但是有种异样性。这类型的物理性质其
实主要就是：
－移动速度的加减速
－旋转速度的加减速

只要进行上两件事情时都有遵循加减速的性质，AI 的行动就会看起来更煞有其事。

三、实作效果
https://twitter.com/RandomDevDK/status/1436186119666692124?s=20
敌人之间没有碰撞是故意的，但还不错吧？
上图还用到了程序性动画，但这部分就独立发一篇应该比较适合。

四、限制与解法
身为一个不知道整体环境的 AI，对应的限制也就很明确：无法确保他能够移动到指定位
置。
由于《自动混乱》的关卡设计虽然偶尔很复杂，但是基本上不会出现最容易引发局部性碰
撞检测容易卡死的碗型结构：
https://i.imgur.com/hr5Whlw.png
如上图情境，虽然当 AI 远远地靠近这个结构的时候自然而然会绕过去，但如果因为一些
因素意外造成这样的情境发生时，AI 就可能会因此卡死在这个结构内，这方面可以仰赖
偏好方向的权重调整来尽量避免，但就无法完美确保。
https://i.imgur.com/9Jt7Wms.jpg
（↑《Hades》中很具参考性的碗型结构情境，如果站在横跨深渊的位置时，Tiny
Vermin 头目可能会陷在碗型结构出不来，使用远程武器可以轻易无伤打赢。官方某次更
新后 Tiny Vermin 传送离开的频率增加，我认为应该就是为了解决这个问题）

所以在这边提出几个假设实作，可以考虑使用：
（一）LOD AI
这个概念是让各个 AI 有不同级别的实作，某些 AI 使用低精度的区域性碰撞回避，某
些 AI 使用高精度的 Nav Mesh Agent。
区分方式包含根据相对于玩家的距离、敌人类型等等都不错，也可以让低精度 AI 把高精
度 AI 当成一个指标靠近，就有可能借由少量高精度 AI 的协助横跨难以穿梭的空间。
（二）历史纪录与回避
相较于上一个，这个的实用性还待考证。但我的想法是因为 AI 容易出问题的碗型结构，
结果而论会让 AI 不断回去同一个位置，也因此或许可以考虑让 AI 不倾向于前往曾经去
过的位置。根据权重设计也可能反而让敌人更深陷碗里也说不定，就有待测试。
（三）侦错与错误应对
既然可以设计出大致上堪用的 AI，表示这种错误情境相对少见。也因此如果 AI 基本效
果很好的话，就可以让 AI 单纯在特定条件下会“传送”离开原地，让 AI 重新开机判断
逻辑就好。
例如说：
－物理上的传送、跳跃到其他位置
－暂时性放弃现在追踪的目标或甚至偏好往反方向的目标移动

上面两个设计甚至在不需要的情境下执行，还是可以被包装成 AI 在重新审视战况，反而
看起来更煞有其事。

五、结语
AI 的议题大概有无限种的方式可以实作，甚至多个混在一起判断。没有唯一解，只有对
应特定情境适合、好用的解。
例如说上述情境都假设敌人单纯地跟目标保持特定距离，但如果是掩体射击游戏的话，
对 AI 来说保持指定距离就只是间接目标，真正执行的偏好移动地点就得变成邻近的掩体
，并且写一套逻辑去判断哪个掩体的品质比较好
（参考：《看门狗 2》的 AI 战斗逻辑：https://youtu.be/c06DZ81Tbmk）
复杂的关卡会出问题，那么其实也就可以尽量降低场景复杂度。除了减少物件以外，让很
多物件只是装饰品实际上被穿过时会直接被敌人破坏也是种不会让人觉得场景东西很少很
廉价的手法。

但总之这是我现在开发的游戏中使用的 AI 逻辑，写篇文章记录供自己未来备考，也提供
大家做个参考。

未看先推

推 长知识了

图床可以拉到hackmd让他上传试试

你的东西完全可以用NavMesh。问题在如何架构辅助资料结构在这之上。https://www.redblobgames.com/https://theory.stanford.edu/~amitp/GameProgramming/Amit Patel是google的前10位员工，现在是亿万富翁，对游戏有兴趣。他也喜欢动态产生地图，做ai path。https://reurl.cc/43R68D他有各种Group，Cooperative Path finding的连结。好好看一下，你碰到的问题，其他人都碰过。如果你真的不想改，起码考虑一下Heat Map(Influence Map)

推

你的AI大致上是Desire-driven AI，Dijkstra Map(Influence很适合，又简单写，可以变化多很多。https://reurl.cc/EZ7Mnm ，有稍微解释。https://github.com/marukrap/RoguelikeDevResourcesAI连结可看不想用NavMesh就直接铺2d grid