AI 是怎么
在迷雾里抓人的

玩家的目标与回合制

游戏是离散回合制：你按一次方向键或空格等待，就推进一回合。全图的金色数据碎片收集完毕后，出口激活，踏上出口立即获胜——哪怕同回合与机器人重合也不算被捕。时间耗尽或被机器人踩中，则挑战失败。

你的视野是有限的（第 1 关 6 格，逐关增大到 8 格），且视线只能沿行列直线延伸、被墙阻挡——所以"迷雾"不是贴图特效，是视线算法算出来的。你有两件主动资源：EMP（踩青色道具拾取，按 E 释放，击晕 4 格内所有机器人 5 回合）和 撤回（每次尝试 3 次，可反悔一步）。地图上还有金色技能点会实时游走，追上它随机获得护盾、静音或 EMP。

其它机制一览

BFS + Tarjan封锁型 sentinel · 站在你必经的路上

它不追人，只封路。进入警戒态后，封锁型的目标选择分两层：

第一层 · 割点封锁。用 C++ 实现的迭代式 Tarjan 算法实时计算迷宫割点——移除后会把连通区域一分为二的格子，放到地图上就是峡谷隘口、走廊瓶颈。算法维护每个节点的发现序 disc 与回溯可达的最早祖先 low，回溯时 low[child] ≥ disc[parent] 即判定父节点为割点；起点用「DFS 树孩子数 ≥ 2」单独判定，避免漏标误标。割点集合与两张 BFS 距离场（一张以你的 last_known 为源、一张以它自己为源）交叉筛选：在所有「自己不晚于你到达」的格子里，真实割点一票加成，度数 ≥ 3 的路口兜底。

第二层 · 赴约移动。选定驻守点后，用 BFS 最短路走过去。距离场把「每个候选路口跑两次 BFS」优化成「两个源点各建一张场」，第二关约 45 个候选路口的搜索从 ~90 次降到 2 张场 + 少量路径搜索。

A*追击型 hunter · 对确认位置持续施压

看得见就直扑你，看不见就扑最后确认点。追击型的规则最简单也最凶：

CHASE 态（视线确认中）：目标 = 你的实时坐标，A* 沿最低地形代价路径直扑。视线一断，立即降级：状态转入 SEARCH，目标改成 last_known——你的最后确认位置。此后它对你的全部认知就只有这一个格子，直到重新看见你或从声场/队友获得新情报。

实现上它每回合都做一次完整 A*（目标变了自然要重算），搜索核心返回的 path[1] 就是它这回合的落子。地形代价让它的追击"像人"：会绕开刚响过警报的红格（3.0），会顺路蹭隐蔽带（1.7）。

A* + 距离场拦截型 interceptor · 堵你的前方

它不打你，算你。要往哪走，然后提前到那儿等你。拦截型是四台里唯一「面向未来」的：

第一步 · 外推预测。仅在视线确认时（这是读取你方向的唯一合法时机），沿你的朝向逐格外推最多 4 格，遇到墙或关着的门就停——得到一个预测点。

第二步 · 路径级埋伏。真正的杀手锏是 find_ambush_tile：以 last_known 及其相邻格为「你可能的位置」，各建一张 BFS 距离场；再对全图每格查两张表——机器人距离 ≤ 玩家距离（gd ≤ pd，它比你先到）的格子才有资格当埋伏点，从中选「你到它最远、它到它最近」的。这是在算"哪里是你逃不掉的交集"，不是跟在屁股后面跑。

第三步 · A* 赴约。选定埋伏格后同样交给 A* 执行。所有距离场共享同一份回合级缓存，同源点的重复查询零开销。

DFS搜索型 scout · 一寸一寸清剿区域

跟丢你之后，把整片区域犁一遍。搜索型的算法角色最纯粹：

目标设为越界点 (-1,-1)——一个永远"不可达"的目标，DFS 就会系统性地遍历整个连通区域，visited 顺序天然就是真实的搜索推进顺序。它走过的格子记入 search_checked，新一轮搜索周期清空重来，不会在同一片区域无限打转。

多台协同时互异认领：每台搜索者从未检查的前沿格子里选「离自己曼哈顿距离最近」的，且已被队友认领的目标自动排除——分区清剿，而不是挤成一团。搜索倒计时（默认 14 回合）耗尽仍一无所获，就清空记忆强制返航回家。

警戒合围：割点围成的包围圈

四台机器人的协同藏在 assign_blockade_roles 里：你被看见后，所有非封锁型的警戒机器人围绕你的 last_known 做合围驻守——候选驻点优先取该连通区的真实割点（必经瓶颈），再补距你 2~4 格的环带格，且每个驻点全局互异（被认领的格子他人不再选择）。候选耗尽时退化为按距离环带分配，仍保证互不重叠。

这不是"围着圆圈站"：割点驻守意味着包围圈卡在你真实的逃逸瓶颈上。配合封锁型的割点封锁，一张围猎网就合拢了。每回合全队共享一次割点集合与距离场缓存（键 ("ap", origin) / ("df", origin)），单回合搜索调用保持在常数级。

感知层：机器人怎么「看见」和「听见」你

视线是几何判定——同排或同列、距离不超过视野半径、中间没有墙，三个条件缺一不可。斜向永远看不见，拐角天然挡视线：

隐蔽带改写视野半径——这是绿格规则 ① 的实现位置，感知入口处一个三元表达式：

声音是 BFS 圈——你每走一步，脚步声以脚下为源点、按可通行连通图逐格传播（墙和关着的门阻隔），产生一张「哪格几回合能听到」的声场。绿格规则 ② 和红格规则都作用在这张场的半径上：

机器人收到声音时拿到的只是整张声场——声源要靠它自己反推（取声场中距离最小的格子）。红格警报之所以"穿墙传信"，是因为声场沿可通行图传播不到的地方，半径 +5 的警报圈早已覆盖全图；而你在绿格里减半后的声场，边缘机器人根本收不到任何格子有声音。

代价层：规则变成 A*/BFS 眼里的「贵与贱」

搜索算法不懂"危险"，只懂代价。绿格与红格的第二条实现路径是地形代价函数——每条搜索边的通行成本：

注意一个不对称：代价函数只影响机器人——玩家走绿格红格不扣分不受罚，规则对你的惩罚全部由感知层执行（被发现、被听到）。这让"红格放必经路口"成为真正的策略考验：算法不想走，但防守空缺的路只有它。

门与重规划：一张随时间呼吸的图

动态门按 period 回合周期开闭（开 open_ticks 回合），开闭状态由当前 tick 与相位决定。算法实现的关键决定是：门不做成动态图，做成每回合重建的静态快照——

每回合建一次、四台机器人共用；下一回合 tick 变了、门的状态变了，快照重建，所有机器人的路径自然重算。重规划不是特殊逻辑，是流水线的副产品。语义上还有一条精确规则：实体可以从本回合刚关闭的门格起步离开，但其他实体不能进入该格——这条边界在 Python、DLL、WASM 三端保持一致。

为什么是 C++，怎么保持三端一致

全队机器人每回合都要做多次完整搜索，纯 Python 会成为瓶颈，也满足不了课程的语言要求。搜索核心编译为 mist_search.dll（桌面 ctypes 调用）与 search_core.wasm（浏览器经 window.mistSearch 调用），另有纯 Python 参考实现用于差分测试与故障回退。

一致性是设计出来的：邻居始终按右、下、左、上顺序生成（可观察契约）；A* 相同 f 值用单调递增 serial 保持插入序；松弛用严格 <、等代价不换父节点。三条规矩保证同一局面下 DLL、WASM、Python 三端给出逐字节相同的路径、访问序与代价——差分测试对四关真实地图、多个门 tick 精确对拍。

A* 在本作中的形态

追击与拦截的执行引擎。评分与教科书一致：f(n) = g(n) + h(n)——g 是累计进入地形的真实代价，h 是曼哈顿距离 × 全图最小进入代价 1.0。四向网格下曼哈顿距离是步数下界，再乘最小代价保证绝不高估（可采纳），于是加权地形下最优性依然成立。h 恒为 0 会退化成 Dijkstra——慢但一样准；h 越准剪枝越狠——这就是它敢直扑你的底气。

同一格可能以不同代价多次入堆（先绕远、后找到近路），本实现不做 decrease-key，出堆时发现记录过期就丢弃——小网格上更快，代码更不易错。整套搜索只返回"下一步"是不够的：完整 path、真实 visited 顺序和 cost 都要返回，因为算法可视化和搜索型机器人的区域分配吃的都是这份数据。

算法与机器人的对应关系

HUD 里每台机器人头上的中文意图（封锁割点 / 合围驻守 / 追击 / 拦截前方 / 分区搜索 / 返航）就是上表状态的实时翻译——游戏开启"算法视图"（V 键）后，你还能直接看到每台机器人的搜索路径线、访问过的格子和当前目标环。

成绩单