捉迷藏算法

捉迷藏算法

> 编程

这个算法的目的是找出对手即使移动也无法获得视线的格子。

这个算法通常被称为“捉迷藏”（法语为 Cache-cache），更习惯英语的玩家则叫它“Hide and seek”。

用途

捉迷藏是你最先会用到的走位方法之一，能让你更高效地安排移动。

• 在低等级时，它可以让你的韭葱用剩下的 MP 躲到障碍物后面。

如果你的韭葱躲在障碍物后面，让对手打不到它，对手就只能另寻他法，比如使用能穿过障碍物命中目标的火花，或者 AoE。

• 在高等级时，捉迷藏（或者更好的算法）会变得必不可少，用来尽量减少你受到的伤害。

原理

寻找藏身格子的常用方法要用到可达格子算法。

因此，第一步是获取你的可达格子，从而知道你能移动到哪些格子，也就是可能藏身的格子。 同时还要获取对手（或多个对手）的可达格子，从而知道对手能去哪里，进而找到一个即使对手移动也打不到你的格子。

接下来，要在你的韭葱的可达格子中找出“安全”的格子。 为此，需要逐一检查这些格子，看它们与对手的可达格子之间有没有视线。 如果某个格子与对手的所有可达格子之间都没有视线，那么对手即使移动，也无法瞄准这个格子。

所以，思路是先假设一个格子是“安全”的，再尝试证明它不安全：只要还没有发现视线，就继续逐一检查对手的格子；一旦存在视线，就说明对手能打到这个格子。当然，你还可以进一步细化，为每个候选藏身格子计算一个“危险度”，从中选出最不坏的那个，比如不给对手用 M-激光 直线射击的机会。

绿色格子：你的韭葱 / 红色格子：对手 / 蓝色格子：对手的可达格子 绿线：没有视线 / 红线：有视线