捉迷藏是最古老的博弈游戏之一，躲藏者需要利用环境遮蔽，寻找者需要通过推理和搜索定位躲藏者。本文用Java实现捉迷藏的AI决策系统，重点讲解射线投射视线检测、状态空间搜索与贝叶斯推断在环境探索中的应用。
问题建模
将游戏场地建模为二维网格地图，每个格子有明确的遮挡属性：
– 空地标（.）：可通行，不遮挡视线
– 障碍物（#）：不可通行，完全遮挡视线
– 躲藏者（H）：需避开寻找者的视线范围
– 寻找者（S）：通过移动和观察缩小躲藏者可能位置集合
视线规则：寻找者只能看到同一行或列中、中间无障碍物相连的格子。对角线不可见。
核心算法
1. 射线投射视线检测（Ray Casting）
从寻找者位置向四个正方向发射射线，遇到障碍物即停止，标记所有可见格子。
2. 贝叶斯状态推断
寻找者维护一个概率分布，表示躲藏者在每个格子的概率。每次观察到某区域”无人”时，将该区域概率归零并重新归一化。
3. 最优搜索策略
寻找者选择能最大化信息增益（期望消除概率质量）的移动方向。
完整Java实现
import java.util.*;
/**
* 捉迷藏 — 视线追踪与状态空间搜索策略
* 包含射线投射、贝叶斯推断、信息增益最优搜索
*/
public class HideAndSeekGame {
private final int rows;
private final int cols;
private final char[][] map;
// 四个正方向
private static final int[][] DIRS = {{-1,0}, {1,0}, {0,-1}, {0,1}};
public HideAndSeekGame(char[][] map) {
this.map = map;
this.rows = map.length;
this.cols = map[0].length;
}
/**
* 射线投射：计算从(sr, sc)位置能看到的所有格子
* 向四个方向发射射线，遇到障碍物停止
*/
public boolean[][] computeVisibility(int sr, int sc) {
boolean[][] visible = new boolean[rows][cols];
if (!inBounds(sr, sc) || map[sr][sc] == '#') return visible;
// 自身位置总是可见的
visible[sr][sc] = true;
// 四个方向射线投射
for (int[] d : DIRS) {
int r = sr + d[0];
int c = sc + d[1];
while (inBounds(r, c) && map[r][c] != '#') {
visible[r][c] = true;
r += d[0];
c += d[1];
}
}
return visible;
}
/**
* 计算视线被遮挡的格子（从该位置不可见的格子）
*/
public boolean[][] computeHiddenZones(int sr, int sc) {
boolean[][] visible = computeVisibility(sr, sc);
boolean[][] hidden = new boolean[rows][cols];
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
hidden[r][c] = inBounds(r, c) && map[r][c] != '#' && !visible[r][c];
}
}
return hidden;
}
/**
* 贝叶斯状态推断：维护躲藏者的位置概率分布
*/
public static class BeliefState {
double[][] prob; // 每个格子的概率
int rows, cols;
public BeliefState(int rows, int cols) {
this.rows = rows;
this.cols = cols;
this.prob = new double[rows][cols];
}
/**
* 均匀初始化：所有空地等概率
*/
public void uniformInit(char[][] map) {
int emptyCount = 0;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (map[r][c] != '#') emptyCount++;
}
}
double p = 1.0 / emptyCount;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
prob[r][c] = (map[r][c] != '#') ? p : 0;
}
}
}
/**
* 更新：观察到某区域"无人"，将该区域概率归零并重新归一化
*/
public void updateObservation(boolean[][] observed, boolean foundNothing) {
double total = 0;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (observed[r][c] && foundNothing) {
prob[r][c] = 0; // 观察到无人，概率归零
}
total += prob[r][c];
}
}
// 重新归一化
if (total > 0) {
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
prob[r][c] /= total;
}
}
}
}
/**
* 获取概率最高的位置
*/
public int[] getMostLikelyPosition() {
double maxP = -1;
int[] best = null;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (prob[r][c] > maxP) {
maxP = prob[r][c];
best = new int[]{r, c};
}
}
}
return best;
}
/**
* 计算熵（不确定性度量）
*/
public double entropy() {
double e = 0;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (prob[r][c] > 0) {
e -= prob[r][c] * Math.log(prob[r][c]) / Math.log(2);
}
}
}
return e;
}
}
/**
* 寻找者最优移动策略：选择能最大化期望信息增益的方向
* 信息增益 = 当前熵 - 期望观察后的熵
*/
public int[] selectBestMove(int sr, int sc, BeliefState belief) {
int[] bestMove = null;
double maxInfoGain = -1;
for (int[] d : DIRS) {
int nr = sr + d[0];
int nc = sc + d[1];
if (!inBounds(nr, nc) || map[nr][nc] == '#') continue;
// 模拟移动到(nr, nc)后的观察
boolean[][] visible = computeVisibility(nr, nc);
// 计算期望信息增益
double infoGain = computeExpectedInfoGain(belief, visible);
// 额外奖励：如果高概率区域在视野内
int[] likelyPos = belief.getMostLikelyPosition();
if (likelyPos != null && visible[likelyPos[0]][likelyPos[1]]) {
infoGain += 0.5;
}
if (infoGain > maxInfoGain) {
maxInfoGain = infoGain;
bestMove = new int[]{nr, nc};
}
}
return bestMove != null ? bestMove : new int[]{sr, sc};
}
/**
* 计算期望信息增益
* E[IG] = P(发现) × IG(发现) + P(未发现) × IG(未发现)
*/
private double computeExpectedInfoGain(BeliefState belief, boolean[][] visible) {
double currentEntropy = belief.entropy();
// 计算在可见区域内发现躲藏者的概率
double pFound = 0;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (visible[r][c]) {
pFound += belief.prob[r][c];
}
}
}
// 场景1：发现了（概率pFound）
// 此时熵变为0（确定位置），但具体哪个位置不确定，需要条件期望
double entropyIfFound = 0;
if (pFound > 0) {
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (visible[r][c] && belief.prob[r][c] > 0) {
double condProb = belief.prob[r][c] / pFound;
entropyIfFound -= condProb * Math.log(condProb) / Math.log(2);
}
}
}
}
// 场景2：没发现（概率1-pFound）
// 躲藏者在不可见区域，重新归一化后的熵
double entropyIfNotFound = currentEntropy; // 简化为当前熵（上界估计）
double expectedEntropy = pFound * entropyIfFound + (1 - pFound) * entropyIfNotFound;
return currentEntropy - expectedEntropy;
}
/**
* 躲藏者最优移动策略：移动到最不可见的区域
*/
public int[] selectBestHideMove(int hr, int hc, int sr, int sc) {
int[] bestMove = null;
double bestScore = Double.NEGATIVE_INFINITY;
// 评估每个可能移动到的位置
for (int[] d : DIRS) {
int nr = hr + d[0];
int nc = hc + d[1];
if (!inBounds(nr, nc) || map[nr][nc] == '#') continue;
// 计算从寻找者视角，该位置是否可见
boolean[][] visible = computeVisibility(sr, sc);
boolean isVisible = visible[nr][nc];
// 计算该位置被多少其他位置看到（"暴露度"）
int exposure = computeExposure(nr, nc);
// 评分：不可见 + 暴露度低 + 远离寻找者
int distToSeeker = Math.abs(nr - sr) + Math.abs(nc - sc);
double score = (isVisible ? -10 : 5) - exposure * 0.3 + distToSeeker * 0.1;
if (score > bestScore) {
bestScore = score;
bestMove = new int[]{nr, nc};
}
}
return bestMove != null ? bestMove : new int[]{hr, hc};
}
/**
* 计算某位置的"暴露度"：从多少个其他空位能看到该位置
*/
private int computeExposure(int r, int c) {
int exposure = 0;
for (int sr = 0; sr < rows; sr++) {
for (int sc = 0; sc < cols; sc++) {
if (map[sr][sc] == '#') continue;
boolean[][] visible = computeVisibility(sr, sc);
if (visible[r][c]) exposure++;
}
}
return exposure;
}
/**
* BFS最短路径：寻找者移动到目标位置的最短路径
*/
public List<int[]> bfsPath(int sr, int sc, int tr, int tc) {
boolean[][] visited = new boolean[rows][cols];
Map<String, String> parent = new HashMap<>();
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{sr, sc});
visited[sr][sc] = true;
while (!queue.isEmpty()) {
int[] cur = queue.poll();
if (cur[0] == tr && cur[1] == tc) {
return reconstructPath(parent, sr, sc, tr, tc);
}
for (int[] d : DIRS) {
int nr = cur[0] + d[0];
int nc = cur[1] + d[1];
if (!inBounds(nr, nc) || visited[nr][nc] || map[nr][nc] == '#') continue;
visited[nr][nc] = true;
parent.put(key(nr, nc), key(cur[0], cur[1]));
queue.add(new int[]{nr, nc});
}
}
return Collections.emptyList();
}
private List<int[]> reconstructPath(Map<String, String> parent,
int sr, int sc, int tr, int tc) {
LinkedList<int[]> path = new LinkedList<>();
String cur = key(tr, tc);
String start = key(sr, sc);
while (!cur.equals(start)) {
String[] p = cur.split(",");
path.addFirst(new int[]{Integer.parseInt(p[0]), Integer.parseInt(p[1])});
cur = parent.get(cur);
if (cur == null) return Collections.emptyList();
}
path.addFirst(new int[]{sr, sc});
return path;
}
/**
* 完整游戏模拟
*/
public void simulateGame(int[] seekerStart, int[] hiderStart, int maxTurns) {
int[] seeker = seekerStart.clone();
int[] hider = hiderStart.clone();
BeliefState belief = new BeliefState(rows, cols);
belief.uniformInit(map);
System.out.println("===== 捉迷藏模拟 =====");
System.out.println("S=寻找者 H=躲藏者 #=障碍物 .=空地");
for (int turn = 1; turn <= maxTurns; turn++) {
// 寻找者观察
boolean[][] visible = computeVisibility(seeker[0], seeker[1]);
boolean found = visible[hider[0]][hider[1]];
if (found) {
System.out.println("\n第" + turn + "回合：寻找者发现了躲藏者！");
System.out.println("躲藏者位置: (" + hider[0] + "," + hider[1] + ")");
printState(seeker, hider);
return;
}
// 更新信念状态
belief.updateObservation(visible, true);
// 寻找者移动
int[] seekerMove = selectBestMove(seeker[0], seeker[1], belief);
if (seekerMove != null) {
seeker[0] = seekerMove[0];
seeker[1] = seekerMove[1];
}
// 躲藏者移动（若未被看到）
int[] hiderMove = selectBestHideMove(hider[0], hider[1], seeker[0], seeker[1]);
hider[0] = hiderMove[0];
hider[1] = hiderMove[1];
System.out.println("\n第" + turn + "回合");
System.out.println("寻找者: (" + seeker[0] + "," + seeker[1] + ")");
System.out.println("躲藏者: (" + hider[0] + "," + hider[1] + ")");
System.out.println("信念熵: " + String.format("%.3f", belief.entropy()));
int[] likely = belief.getMostLikelyPosition();
System.out.println("最可能位置: (" + likely[0] + "," + likely[1] + ")" +
" 概率=" + String.format("%.3f", belief.prob[likely[0]][likely[1]]));
}
System.out.println("\n游戏结束，未能在" + maxTurns + "回合内找到躲藏者");
}
private void printState(int[] seeker, int[] hider) {
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (r == seeker[0] && c == seeker[1]) {
System.out.print('S');
} else if (r == hider[0] && c == hider[1]) {
System.out.print('H');
} else {
System.out.print(map[r][c]);
}
}
System.out.println();
}
}
private boolean inBounds(int r, int c) {
return r >= 0 && r < rows && c >= 0 && c < cols;
}
private String key(int r, int c) {
return r + "," + c;
}
public static void main(String[] args) {
char[][] map = {
"#############".toCharArray(),
"#...........#".toCharArray(),
"#.#.#####.#.#".toCharArray(),
"#.#.......#.#".toCharArray(),
"#...#...#...#".toCharArray(),
"###.#.#.#.###".toCharArray(),
"#...#...#...#".toCharArray(),
"#.#.......#.#".toCharArray(),
"#.#.#####.#.#".toCharArray(),
"#...........#".toCharArray(),
"#############".toCharArray()
};
HideAndSeekGame game = new HideAndSeekGame(map);
game.simulateGame(new int[]{1, 1}, new int[]{9, 11}, 30);
}
}
算法核心要点
射线投射视线检测
本实现采用四方向射线投射而非全方向扫描，基于经典捉迷藏的”直线视野”规则。相比360度扇形扫描，这种设计更符合实际游戏直觉，且计算复杂度从O(360×r)降至O(4×r)。
贝叶斯信念更新
寻找者通过不断排除”已观察且无人”的区域来缩小搜索空间。每次观察后的概率重归一化是贝叶斯推断的核心步骤，确保信念分布始终满足概率公理。
信息增益驱动搜索
寻找者不再盲目追逐最可能位置，而是选择能”最大程度消除不确定性”的移动方向。这种基于信息论的决策策略在机器人搜索与救援、雷达追踪等领域有广泛应用。
复杂度分析
| 模块 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 射线投射 | O(max(rows, cols)) | O(rows×cols) |
| 信念更新 | O(rows×cols) | O(rows×cols) |
| 最优移动选择 | O(4 × (射线代价 + 熵计算)) | O(rows×cols) |
| 暴露度预计算 | O((rows×cols)²) | O(rows×cols) |
| 完整BFS路径 | O(rows×cols) | O(rows×cols) |
扩展方向
- 多躲藏者场景：维护联合概率分布或使用独立假设近似
- 动态障碍物：引入时间维度，处理移动障碍
- 声音线索：扩展观测模型，加入”脚步声”等不完美信息
- 学习对手模式：用马尔可夫链建模躲藏者的移动偏好
总结
捉迷藏AI将经典的”搜索-隐藏”对抗转化为信息论问题。通过射线投射实现精确的视线判定、贝叶斯推断更新信念状态、信息增益指导探索策略，我们构建了一个能自主推理的寻找者AI。这种”感知-推断-决策”的闭环框架是智能体设计的核心范式，广泛应用于自动驾驶感知、军事目标追踪和机器人探索任务。
