# Arrow Out 自动求解研发文档（Java，输入为图片）

## 1. 目标与范围

- 输入：一张关卡截图（包含 UI、背景、彩色箭头线条与箭头头部）。
- 输出：
  - `List<Arrow>`：每个箭头的 `id`、离散坐标 `(gx, gy)`、方向 `dir(8方向)`。
  - `List<Integer>`：一条可消除序列（按 `id` 返回）。
- 不在范围：
  - 自动点击/自动操作游戏。
  - 复杂的通用 OCR/UI 识别；本方案仅提取箭头（位置+方向）。

## 2. 规则抽象（用于建模与求解）

### 2.1 箭头属性

每个箭头只保留两类信息：

- 位置：`(x, y)`（工程上最终用离散坐标 `(gx, gy)`）。
- 朝向：8 方向之一（`N, NE, E, SE, S, SW, W, NW`）。

> 颜色、线条粗细、形状风格不影响解题，忽略。

### 2.2 “可消除”判定

对任意箭头 `A`：

- 从 `A` 的箭头尖端（tip）沿其朝向作射线。
- 若该射线上存在任意其他箭头（不论颜色与距离），则 `A` **不可消除**。
- 若该射线直到边界都没有遇到任何箭头，则 `A` **可消除**。

消除后会改变其他箭头的判定，因为阻挡关系会变化。

## 3. 总体架构

分两层：

- `Vision`（识别层）：图片 → 箭头列表（像素坐标 tip + 方向）→ 离散化网格坐标 `(gx, gy)`。
- `Solver`（求解层）：箭头列表 `(gx,gy,dir)` → 消除序列。

接口建议：

- `VisionExtractor.extract(Mat screenshot) -> List<Arrow>`
- `ArrowOutSolver.solve(List<Arrow> arrows) -> List<Integer>`
- `solveFromImage(String imagePath) -> List<Integer>`（端到端封装）

## 4. Vision：从图片提取 `(x,y,dir)`（OpenCV Java）

### 4.1 坐标系约定

- OpenCV 图像坐标：`x` 向右增大，`y` 向下增大。
- 求解模型可以沿用该坐标系，也可以转换为数学坐标系（`y` 向上增大）。
- **要求：方向枚举与坐标系必须一致**。

建议：内部统一用 OpenCV 坐标系，方向定义也按“y 向下”为正。

### 4.2 预处理：裁剪棋盘 ROI（去 UI）

目的：减少误检（顶部文字/按钮/底部工具栏等）。

推荐方案（鲁棒）：利用“彩色线条像素”的饱和度/亮度特征定位主区域。

1) 转 HSV：`cvtColor(bgr, hsv, COLOR_BGR2HSV)`
2) 前景掩码：`mask = (S > s0) && (V > v0)`（只抓彩色高饱和区域）
3) 形态学：`close` 填洞、`open` 去噪
4) 找最大连通区域或最大外接矩形 contour，取其外接矩形为 `boardRoi`

输出：`Mat board`（棋盘区域图像）。

### 4.3 二值化：生成箭头像素掩码

目标：得到只包含箭头线条/箭头头部的 `arrowMask`。

- 在 `board` 上按 HSV 阈值生成二值图（仍然只依赖 S/V）：
  - `arrowMask = (S > s0) && (V > v0)`
- 对 `arrowMask` 做 `morphology close/open`，让箭头头部轮廓更连续。

输出：`Mat arrowMask`（0/255）。

### 4.4 检测箭头头部：定位 tip 与方向

核心思想：箭头头部通常呈“尖角三角形/箭头尖”，几何特征稳定；方向可由“尖点指向”得到。

步骤：

1) `findContours(arrowMask, ...)` 获取轮廓集合
2) 对每个 contour 过滤：
   - 面积在 `[amin, amax]`（避免把长线条当头部，或把噪声当头部）
   - `approxPolyDP` 多边形近似
3) 取 tip（尖点）
   - 对多边形各顶点计算内角，选择 **内角最小** 的顶点作为 `tip`
4) 取中心 `center`
   - 用 `moments` 计算轮廓质心
5) 方向向量
   - `vec = tip - center`
   - `angle = atan2(vec.y, vec.x)`（按 OpenCV 坐标系）
6) 角度量化到 8 方向
   - 每 45° 一档；误差超过 22.5° 的标记为“不确定”进入兜底
7) 去重/聚类
   - 按 `tip` 的欧式距离把相近候选聚成一簇（阈值 5~15 像素）
   - 每簇保留面积最大的候选

输出（像素级）：`List<ArrowPixel>{ tipX, tipY, dir }`。

### 4.5 离散化：从像素坐标到网格坐标 `(gx, gy)`

求解层需要稳定的“同一行/列/对角线”关系，建议把像素 tip 坐标离散化到网格。

推荐做法：对 `x` 与 `y` 分别做 1D 容差聚类。

1) 收集全部 `tipX`，排序
2) 从左到右扫描：相邻差值 < `tx` 的归为同一簇
3) 每簇中心取均值 `cx`，簇序号即 `gx`
4) 对 `tipY` 同理得到 `gy`

参数建议：

- `tx/ty` 可取“箭头头部平均宽度”的 0.5~1 倍。
- 或先验经验值（需按分辨率调参）：10~25 像素。

输出：`List<Arrow>{ id, gx, gy, dir }`。

### 4.6 识别质量校验（必须做）

- 方向置信度：量化前角度与目标方向夹角 > 22.5° 视为不可信。
- 唯一性：同一 `(gx,gy)` 不应出现多个箭头（出现则说明去重/聚类失败）。
- Debug 可视化：在 `board` 上画 tip 点与方向短线，输出调试图，便于快速调参。

### 4.7 兜底方案（可选增强）

若几何检测不稳：

- 模板匹配：8 个方向头部模板，匹配得到方向与 tip。
- 轻量检测模型：训练在 Python，推理可用 ONNXRuntime Java 或 OpenCV DNN。

## 5. Solver：由 `(gx,gy,dir)` 求消除序列

### 5.1 blocker/blockedBy 核心结构

对每个箭头 `i` 维护：

- `blocker[i]`：沿自身方向最近的箭头 id；若不存在为 `-1`。
- `blockedBy[i]`：所有当前把 `i` 当作 blocker 的箭头集合（反向索引，用于增量更新）。
- `ready`：所有 `blocker == -1` 且未删除的箭头队列。

流程：不断从 `ready` 取出可消除箭头删除，并只更新受影响的箭头（即 `blockedBy[removed]`）。

### 5.2 最近阻挡者查询（4 类直线索引）

8 方向只会落在 4 类直线：

- 行：`y = const`，按 `x` 排序
- 列：`x = const`，按 `y` 排序
- 主对角线：`x - y = const`，按 `x` 排序
- 副对角线：`x + y = const`，按 `x` 排序

建议索引结构：

- `Map<Integer, TreeMap<Integer, Integer>> rows;      // y -> (x -> id)`
- `Map<Integer, TreeMap<Integer, Integer>> cols;      // x -> (y -> id)`
- `Map<Integer, TreeMap<Integer, Integer>> diags;     // (x-y) -> (x -> id)`
- `Map<Integer, TreeMap<Integer, Integer>> antiDiags; // (x+y) -> (x -> id)`

`computeBlocker(i)`：

1) 根据 `dir` 选择索引与外层 key
2) 使用 `TreeMap.higherEntry(index)` 或 `lowerEntry(index)` 找最近邻
3) 找到则返回其 id，否则返回 `-1`

删除箭头时同步从 4 套索引中移除，确保后续查询不会返回已删除对象。

### 5.3 多候选时的选择策略

- 优先消除 `blockedBy[u].size()` 最大的箭头（更可能解锁更多箭头）。
- 或用简单队列先做一版；若出现卡死再引入回溯（见 6）。

## 6. 无解与回溯（增强项）

纯“可消除就删”的贪心可能在某些关卡卡死（`ready` 为空但仍有剩余）。

可选策略：

- `A（先落地）`：贪心卡死即返回“无解/需回溯”。
- `B（增强）`：在 `ready` 多候选时做 DFS 回溯；需实现状态回滚（操作日志优于全量拷贝）。
- `C（启发式）`：结合入度优先等启发式减少回溯概率。

## 7. Java 类型与接口建议

### 7.1 数据结构

- `enum Direction { N, NE, E, SE, S, SW, W, NW }`
- `class Arrow { int id; int gx, gy; Direction dir; boolean removed; }`

### 7.2 核心类

- `class VisionExtractor { List<Arrow> extract(Mat screenshot); }`
- `class ArrowOutSolver { List<Integer> solve(List<Arrow> arrows); }`
- `class Pipeline { List<Integer> solveFromImage(String path); }`

## 8. 测试与验收标准

### 8.1 Vision 层

- 能从给定截图中输出合理数量的箭头（不漏检、不明显误检）。
- 输出的 `(gx,gy)` 唯一且稳定（同一箭头在同一位置）。
- 输出方向 `dir` 与肉眼一致（允许少量不确定，但需可追踪）。

### 8.2 Solver 层

- 对构造的小规模数据集：`solve` 输出序列长度等于箭头数量。
- 删除序列合法：每一步删除的箭头在当步满足 `blocker == -1`。
- 若卡死：能明确返回失败（或触发回溯策略）。

## 9. 调参建议（研发流程）

1) 先固定 ROI（或实现自动 ROI）
2) 调 `s0/v0` 使 `arrowMask` 只保留彩色线条
3) 调形态学核大小使箭头头部轮廓连续
4) 调 `amin/amax` 让头部候选稳定
5) 调 `tx/ty` 让网格离散化不抖动
6) 用 debug 图逐轮验证 tip 与方向