改良 A* + 流场寻路（Flow Field）"混合寻路系统，支持可破坏障碍物

解决什么问题

解决2D游戏ai寻路被障碍物卡住，单位数量密集堵车，会寻路但是不会破坏障碍物的问题。3D游戏需要让ai修改一下，用之前问问ai适不适合自己的项目

适用条件

• 引擎 / 框架：通用
• AI 模型或 Agent：Kimi-k3 deepseek v4f Zcode
• 已验证版本和日期：2026/8/7

使用方法

先让ai判断这个prompt是否适合你的游戏，需不需要修改，然后让它按这个做寻路就行了；

# 角色
你是一名资深游戏 AI / 寻路算法工程师。请为一款 **2D 连续平面**游戏设计并实现
"改良 A* + 流场寻路（Flow Field）"混合寻路系统，支持可破坏障碍物。
输出：架构设计、数据结构、关键伪代码或实现（语言：【在此填写，如 C#/C++/Rust】）、
复杂度分析与测试用例。

# 一、世界模型（严格遵循）

1. 地图为连续二维平面，**不是网格**，单位可在 360° 任意方向沿直线移动，
   转向视为瞬时完成（无转向代价）。
2. 障碍物：
   - **不可破坏障碍**：任意简单多边形，绝对不可穿越；
   - **可破坏障碍**：矩形（含正方形），用 (cx, cy, w, h) 表示，有当前血量 hp。
3. 单位模型：半径为 r 的圆（r =【在此填写，如 0.3】；若 r=0 则为质点），
   攻击距离 attackRange =【在此填写，如 1.5】，每秒伤害 dps。
4. 碰撞处理：对所有障碍物沿法向做半径 r 的 Minkowski 膨胀后再做通行性判断；
   膨胀仅用于碰撞与可见性检查，**不参与第三节的计费**（计费一律用原始矩形）。

# 二、总代价公式

- F(n) = G(n) + H(n)。
- G 沿一条行进线段 seg 的增量：
  **cost(seg) = baseMult × len(seg) + Σ(每个被穿过的可破坏矩形的附加代价)**
  （baseMult 为地形系数，普通地面 = 1.0）

# 三、可破坏矩形计费模型（核心规则，严格按此实现）

1. 行进线段 seg 穿过一个当前血量为 hp 的可破坏矩形时，
   d = **seg 与该原始（未膨胀）矩形的交集长度**，用线段-矩形裁剪
  （Liang–Barsky / slab 法）精确计算，禁止用近似值。附加代价：

   **cost_obstacle = (hp / 10) × d**

2. 校验示例（实现必须全部通过）：
   - 100 血、1×1 正方形，线段正对穿过中心：d = 1 → 附加 = 10，
     即等价于多绕 10 个单位长度的普通路；
   - 同一正方形沿对角线穿过：d = √2 ≈ 1.414 → 附加 ≈ 14.14；
   - 50 血、宽 2 的矩形纵向贯穿：d = 2 → 附加 = (50/10)×2 = 10。
3. 歧义消除：
   - "距离"指线段与矩形区域的**交集几何长度**，不是路径总长、不是矩形边长或直径；
   - 一条线段穿过多个矩形时分别计费后累加；
   - 仅擦边/擦角（d < 1e-6）视为未穿过，不计费；
   - hp = 0 时矩形视为已摧毁，不再计费，也不再阻挡；
   - 所有寻路分支共用同一代价函数与同一实时 hp，禁止第二套权重。
4. 平手规则（确定性）：G 值相等（误差 < 1e-6）时，
   优先"穿过的可破坏矩形数量更少"的路径；仍相同则优先 H 更小者。

# 四、主动攻击拆除行为

1. 路径穿过可破坏矩形时，单位必须**主动攻击拆除**，无需指令，不得原地等待。
2. 行为状态机：
   - `Moving`：沿路径移动；
   - 接近矩形：朝"原始矩形边界上距自身最近的点"移动，
     直到与该点距离 ≤ attackRange；
   - `Attacking`：以 dps 对矩形造成伤害直至 hp = 0；
   - 摧毁后**沿原路径继续前进，不重新寻路**（寻路时已计费，路径仍有效）。
3. 多单位攻击同一矩形时，寻路统一使用实时 hp。

# 五、改良 A*（个体寻路）：基于可见性图

1. 图结构：可见性图（Visibility Graph）。
   - 节点：膨胀后不可破坏多边形的顶点 + 膨胀后可破坏矩形的顶点 + 起点 + 终点
     （起点/终点为查询时动态加入）；
   - 边：两节点间线段不穿过任何"膨胀后不可破坏多边形内部"即可连边；
     穿过膨胀后可破坏矩形的边**允许存在**，按第三节计费（用原始矩形求 d）。
2. 启发函数：H(n) = 欧几里得距离 × 全图最小 baseMult。
   请论证可采纳性：可破坏矩形只使实际代价 ≥ 基础长度代价，故忽略障碍的估计永不高估。
3. 改良点（至少实现并说明收益）：
   - 二叉堆/配对堆 OpenList；版本号标记数组替代 ClosedList 哈希表；
   - Tie-breaking：F 相同时优先 G 更大者；
   - 路径平滑：连续平面 LOS 拉直（可见性检查基于膨胀后障碍；
     可破坏矩形视为"可拉直穿过但保留附加代价"）；
   - 可选：起点/终点邻接边做空间索引加速、节点内存池。
4. 输出：路径点列、总代价 G、路径穿过的可破坏矩形及各自穿过区段（供攻击模块）。

# 六、流场寻路（群体寻路）

1. 适用：≥ N 个单位（默认 5，可配置）共享同一目标时启用。
2. 实现方式（消除歧义，按此执行）：
   - 连续平面无法直接存储方向场，因此流场内部使用**采样网格**
     （分辨率 s =【在此填写，如 0.5 单位】），它纯粹是加速结构，
     与"游戏逻辑非网格"不冲突，单位移动仍是连续的；
   - **Integration Field**：从目标所在采样格出发做 Dijkstra 泛洪，
     每步代价 = 步长 × baseMult + 步进落在可破坏矩形内部的长度 × (hp/10)，
     与第三节公式严格同源；膨胀后不可破坏多边形覆盖的采样格不可通过；
   - **Direction Field**：每格存指向 Integration 值最小邻居的连续单位向量；
     单位取方向时按所在位置双线性插值。
3. 缓存与失效：按"目标 + 代价版本号"缓存；
   矩形被摧毁 / 新增障碍 / hp 变化超 20%（可配置）触发重算，可增量或分帧；
   性能目标：200×200 采样全场重算 ≤ 5ms。
4. 群体攻击：方向场引导单位进入可破坏矩形时，
   到达矩形附近的单位自动进入第四节的 Attacking 行为。

# 七、A* 与流场的融合调度（PathManager）

1. 统一入口 `RequestPath(unit, target)`：
   共享目标单位数 ≥ N → 流场分支；否则 → 可见性图 A* 分支。
2. 两分支共用**同一个代价函数模块**，禁止"A* 决定拆、流场决定绕"的分歧。
3. 兜底：目标被不可破坏多边形完全隔离时，
   返回"通往离目标最近的可破坏矩形的攻击路径"；不存在则返回失败并说明原因。

# 八、实现步骤（按此顺序展开）

1. 几何模块：线段-矩形裁剪（求 d）、点/线段与多边形相交、Minkowski 膨胀；
   先用第三节全部数值示例做单元测试。
2. 代价函数模块 `SegmentCost(p1, p2)`（含矩形附加），供两个寻路分支共用。
3. 可见性图构建（静态预计算 + 起终点动态连边）与改良 A*。
4. 采样网格流场：Integration Field（Dijkstra）→ Direction Field → 双线性插值取值
   → 缓存与版本失效。
5. PathManager：分支调度、事件总线、兜底策略。
6. 移动 + 攻击 FSM：与寻路层解耦，由 PathResult 的矩形区段列表驱动。
7. 性能测试：1000 单位同时寻路的帧耗；流场重算耗时。
8. 测试用例（必须全部通过）：
   a. 唯一通道被 100 血 1×1 正方形封死（正穿 d=1，附加 10），
      绕行需多走 25 → 期望：直接拆。
   b. 同上但绕行仅多走 8 → 期望：绕行。
   c. 对角斜穿 1×1 正方形（附加 10√2 ≈ 14.14），
      存在只需多走 12 的绕行 → 期望：绕行（12 < 14.14）。
   d. 等代价双路径 → 平手规则选矩形更少者。
   e. 50 单位同一目标 → 走流场分支，且个体"拆/绕"决策与 A* 一致。
   f. 矩形在移动途中被摧毁 → A* 单位不重寻路直接通过；流场事件后正确更新。
   g. 目标被不可破坏多边形围死 → 验证兜底攻击路径或失败返回。
   h. 随机地图 1000 次采样验证 H 永不高估真实最小代价。
   i. 线段仅擦矩形边/角（d < 1e-6）→ 不计附加代价。
   j. 宽度 < 2r 的缝隙 → 验证不可通过（膨胀生效），且该判定不影响矩形计费数值。

# 九、交付物

1. 系统架构图（模块划分与数据流）。
2. 数据结构与可见性图构建方案（含复杂度）。
3. 关键算法伪代码或可运行实现：矩形裁剪计费、改良 A*、流场、FSM、PathManager。
4. 时间与空间复杂度分析。
5. 第八节全部测试用例的设计与预期结果表。
6. 已知局限与可调参数清单（N、s、hp 重算阈值、attackRange、r 等）。

如对某些规则存在多种合理解释，请先列出你的理解并向我确认，再开始实现。

如何验证结果

在星尘战线的防卫作战模式中同时刷出20个以上敌人不卡墙不堵车

已知限制与风险

3D游戏需对prompt内容进行修改，可交给ai完成修改

来源与致谢

Kimi-k3生成