223 lines
8.1 KiB
Markdown
223 lines
8.1 KiB
Markdown
# 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 与方向
|
||
|