引言
密室逃脱是一种热门的实景解谜游戏：玩家被困在密室中，需要寻找线索、解开谜题、找到钥匙，最终通过一系列房间到达出口。本文将用Java实现一个密室逃脱自动求解器，核心采用图论建模将房间和通道转化为图结构，并通过状态空间BFS搜索最短逃脱路径。
问题建模
密室逃脱可以建模为状态空间搜索问题：
- 状态：当前所在房间 + 已收集的物品/钥匙集合
- 动作：移动到相邻房间、拾取物品、使用钥匙开门、触发机关
- 目标：到达出口房间
- 约束：某些门需要特定钥匙，某些机关需要特定物品触发
这种建模方式将密室逃脱转化为带约束的最短路径问题。
import java.util.*;
/**
* 密室逃脱求解器：图论建模 + 状态空间BFS
*/
public class EscapeRoomSolver {
// 物品类型
enum Item { RED_KEY, BLUE_KEY, GOLD_KEY, LEVER, NOTE, TORCH }
// 房间
static class Room {
int id;
String name;
Set<Item> items; // 房间内可拾取的物品
boolean isExit; // 是否为出口
Room(int id, String name) {
this.id = id;
this.name = name;
this.items = new HashSet<>();
this.isExit = false;
}
}
// 通道（门）
static class Door {
int from, to; // 连接的房间
Item requiredKey; // 所需钥匙（null表示无需钥匙）
boolean isOneWay; // 是否单向
String puzzle; // 谜题描述（简化处理）
Door(int from, int to, Item key, boolean oneWay) {
this.from = from;
this.to = to;
this.requiredKey = key;
this.isOneWay = oneWay;
}
}
// 游戏状态：位置 + 背包
static class GameState {
int roomId; // 当前房间
Set<Item> inventory; // 已收集物品
List<String> path; // 到达此状态的路径记录
int steps; // 已走步数
GameState(int roomId, Set<Item> inventory, List<String> path, int steps) {
this.roomId = roomId;
this.inventory = new HashSet<>(inventory);
this.path = new ArrayList<>(path);
this.steps = steps;
}
// 状态唯一标识（用于判重）
String getKey() {
List<Item> sorted = new ArrayList<>(inventory);
Collections.sort(sorted, Comparator.comparing(Enum::name));
return roomId + "|" + sorted;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof GameState)) return false;
GameState other = (GameState) o;
return roomId == other.roomId && inventory.equals(other.inventory);
}
@Override
public int hashCode() {
return Objects.hash(roomId, inventory);
}
}
private Map<Integer, Room> rooms;
private Map<Integer, List<Door>> adjacency; // 邻接表
public EscapeRoomSolver() {
rooms = new HashMap<>();
adjacency = new HashMap<>();
}
public void addRoom(Room room) {
rooms.put(room.id, room);
adjacency.putIfAbsent(room.id, new ArrayList<>());
}
public void addDoor(Door door) {
adjacency.get(door.from).add(door);
if (!door.isOneWay) {
// 添加反向通道（如果不需要钥匙，或者钥匙是对称的）
// 简化处理：双向门共用同一把钥匙
adjacency.get(door.to).add(new Door(door.to, door.from, door.requiredKey, false));
}
}
状态空间BFS搜索
/**
* BFS搜索最短逃脱路径
* 核心：将(房间, 背包)作为复合状态，确保找到步数最少的解
* @param startRoom 起始房间ID
* @return 逃脱路径，若无法逃脱返回null
*/
public List<String> solve(int startRoom) {
Queue<GameState> queue = new LinkedList<>();
Set<String> visited = new HashSet<>();
// 初始状态：在起始房间，空背包
GameState initial = new GameState(startRoom, new HashSet<>(),
new ArrayList<>(), 0);
queue.offer(initial);
visited.add(initial.getKey());
while (!queue.isEmpty()) {
GameState current = queue.poll();
Room room = rooms.get(current.roomId);
// 检查是否到达出口
if (room.isExit) {
current.path.add("到达出口! 总步数: " + current.steps);
return current.path;
}
// 动作1：拾取当前房间的所有物品
Set<Item> newInventory = new HashSet<>(current.inventory);
boolean picked = false;
for (Item item : new HashSet<>(room.items)) {
if (!current.inventory.contains(item)) {
newInventory.add(item);
picked = true;
}
}
if (picked) {
GameState pickState = new GameState(current.roomId, newInventory,
current.path, current.steps + 1);
pickState.path.add("在" + room.name + "拾取物品: " +
diffSet(newInventory, current.inventory));
String key = pickState.getKey();
if (!visited.contains(key)) {
visited.add(key);
queue.offer(pickState);
}
}
// 动作2：尝试通过所有可达的门
for (Door door : adjacency.getOrDefault(current.roomId, new ArrayList<>())) {
// 检查是否有钥匙
if (door.requiredKey != null &&
!current.inventory.contains(door.requiredKey)) {
continue; // 缺少钥匙，无法通过
}
GameState nextState = new GameState(door.to, current.inventory,
current.path, current.steps + 1);
Room nextRoom = rooms.get(door.to);
String action = "从" + room.name + "移动到" + nextRoom.name;
if (door.requiredKey != null) {
action += " (使用" + door.requiredKey + ")";
}
nextState.path.add(action);
String key = nextState.getKey();
if (!visited.contains(key)) {
visited.add(key);
queue.offer(nextState);
}
}
}
return null; // 无法逃脱
}
private Set<Item> diffSet(Set<Item> a, Set<Item> b) {
Set<Item> diff = new HashSet<>(a);
diff.removeAll(b);
return diff;
}
A*启发式搜索优化
对于复杂密室，纯BFS可能状态空间爆炸。引入A算法，使用曼哈顿距离+未获取关键物品数*作为启发函数。
/**
* A*搜索：带启发式的最优路径搜索
*/
public List<String> solveAStar(int startRoom) {
// 优先级队列：按 f = g + h 排序
PriorityQueue<AStarNode> pq = new PriorityQueue<>(
Comparator.comparingDouble(n -> n.f));
Set<String> visited = new HashSet<>();
GameState initial = new GameState(startRoom, new HashSet<>(),
new ArrayList<>(), 0);
pq.offer(new AStarNode(initial, heuristic(initial)));
visited.add(initial.getKey());
while (!pq.isEmpty()) {
AStarNode node = pq.poll();
GameState current = node.state;
Room room = rooms.get(current.roomId);
if (room.isExit) {
current.path.add("到达出口! 总步数: " + current.steps);
return current.path;
}
// 生成所有后继状态（同BFS）
List<GameState> successors = generateSuccessors(current);
for (GameState next : successors) {
String key = next.getKey();
if (visited.contains(key)) continue;
visited.add(key);
double h = heuristic(next);
pq.offer(new AStarNode(next, next.steps + h));
}
}
return null;
}
/**
* 启发函数：估计从当前状态到目标的最小代价
* h = 到最近出口的最短路径 + 缺失关键物品数 * 惩罚
*/
private double heuristic(GameState state) {
// 计算到各出口的最短路径（忽略钥匙限制，作为下界）
double minDist = Double.MAX_VALUE;
for (Room room : rooms.values()) {
if (room.isExit) {
double dist = shortestPathDistance(state.roomId, room.id);
minDist = Math.min(minDist, dist);
}
}
// 统计还缺少多少把钥匙（所有门所需的钥匙集合）
Set<Item> neededKeys = new HashSet<>();
for (List<Door> doors : adjacency.values()) {
for (Door door : doors) {
if (door.requiredKey != null) {
neededKeys.add(door.requiredKey);
}
}
}
neededKeys.removeAll(state.inventory);
return minDist + neededKeys.size() * 2; // 每缺少一把钥匙预估需要2步
}
/**
* 忽略钥匙限制的简单最短路径（Dijkstra/BFS）
*/
private double shortestPathDistance(int from, int to) {
Queue<int[]> queue = new LinkedList<>();
Set<Integer> visited = new HashSet<>();
queue.offer(new int[]{from, 0});
visited.add(from);
while (!queue.isEmpty()) {
int[] cur = queue.poll();
if (cur[0] == to) return cur[1];
for (Door door : adjacency.getOrDefault(cur[0], new ArrayList<>())) {
if (!visited.contains(door.to)) {
visited.add(door.to);
queue.offer(new int[]{door.to, cur[1] + 1});
}
}
}
return Double.MAX_VALUE;
}
static class AStarNode {
GameState state;
double f; // f = g + h
AStarNode(GameState state, double f) {
this.state = state;
this.f = f;
}
}
private List<GameState> generateSuccessors(GameState current) {
List<GameState> result = new ArrayList<>();
Room room = rooms.get(current.roomId);
// 拾取物品
Set<Item> newInv = new HashSet<>(current.inventory);
boolean picked = false;
for (Item item : room.items) {
if (!current.inventory.contains(item)) {
newInv.add(item);
picked = true;
}
}
if (picked) {
GameState s = new GameState(current.roomId, newInv, current.path, current.steps + 1);
s.path.add("拾取: " + diffSet(newInv, current.inventory));
result.add(s);
}
// 移动
for (Door door : adjacency.getOrDefault(current.roomId, new ArrayList<>())) {
if (door.requiredKey != null && !current.inventory.contains(door.requiredKey))
continue;
GameState s = new GameState(door.to, current.inventory, current.path, current.steps + 1);
s.path.add("移动至" + rooms.get(door.to).name);
result.add(s);
}
return result;
}
完整测试：三层密室场景
/**
* 构建测试密室场景
* 场景：三层密室，需要收集钥匙逐层解锁
*/
public static EscapeRoomSolver buildTestScenario() {
EscapeRoomSolver solver = new EscapeRoomSolver();
// 创建房间
Room entrance = new Room(0, "入口大厅");
Room library = new Room(1, "图书馆");
Room kitchen = new Room(2, "厨房");
Room garden = new Room(3, "花园");
Room basement = new Room(4, "地下室");
Room lab = new Room(5, "实验室");
Room exit = new Room(6, "出口");
exit.isExit = true;
solver.addRoom(entrance);
solver.addRoom(library);
solver.addRoom(kitchen);
solver.addRoom(garden);
solver.addRoom(basement);
solver.addRoom(lab);
solver.addRoom(exit);
// 放置物品
library.items.add(Item.RED_KEY);
kitchen.items.add(Item.BLUE_KEY);
garden.items.add(Item.TORCH);
basement.items.add(Item.GOLD_KEY);
lab.items.add(Item.NOTE);
// 构建通道
solver.addDoor(new Door(0, 1, null, false)); // 入口 <-> 图书馆
solver.addDoor(new Door(0, 2, null, false)); // 入口 <-> 厨房
solver.addDoor(new Door(1, 3, Item.RED_KEY, false)); // 图书馆 <-> 花园（需红钥匙）
solver.addDoor(new Door(2, 4, Item.BLUE_KEY, false)); // 厨房 <-> 地下室（需蓝钥匙）
solver.addDoor(new Door(3, 5, Item.TORCH, false)); // 花园 <-> 实验室（需火把）
solver.addDoor(new Door(4, 5, Item.GOLD_KEY, false)); // 地下室 <-> 实验室（需金钥匙）
solver.addDoor(new Door(5, 6, null, false)); // 实验室 <-> 出口
return solver;
}
public static void main(String[] args) {
EscapeRoomSolver solver = buildTestScenario();
System.out.println("=== 密室逃脱求解 ===\n");
System.out.println("场景描述：");
System.out.println("入口大厅 -> 图书馆(红钥匙) -> 花园(火把) -> 实验室 -> 出口");
System.out.println("入口大厅 -> 厨房(蓝钥匙) -> 地下室(金钥匙) -> 实验室 -> 出口\n");
// BFS求解
System.out.println("--- BFS最短路径 ---");
List<String> bfsPath = solver.solve(0);
if (bfsPath != null) {
for (String step : bfsPath) {
System.out.println(step);
}
} else {
System.out.println("无法逃脱!");
}
System.out.println("\n--- A*启发式搜索 ---");
List<String> astarPath = solver.solveAStar(0);
if (astarPath != null) {
for (String step : astarPath) {
System.out.println(step);
}
}
}
}
复杂度分析
- 状态空间大小：设 $R$ 为房间数，$I$ 为物品总数，则最大状态数为 $R \cdot 2^I$
- BFS时间复杂度：$O(R \cdot 2^I)$，每个状态处理一次
- BFS空间复杂度：$O(R \cdot 2^I)$，存储访问标记和队列
- A*优化：在启发函数良好的情况下，实际访问的状态数远小于BFS，通常可缩减至 $O(R \cdot 2^{I-k})$，$k$ 为已收集物品数
扩展：带机关触发机制的求解
// 机关类型
static class Mechanism {
int roomId; // 所在房间
Item triggerItem; // 触发所需物品
int unlocksRoom; // 解锁的房间
String description;
Mechanism(int room, Item item, int unlocks, String desc) {
this.roomId = room;
this.triggerItem = item;
this.unlocksRoom = unlocks;
this.description = desc;
}
}
private List<Mechanism> mechanisms = new ArrayList<>();
/**
* 扩展的状态转移：增加机关触发动作
*/
private List<GameState> generateSuccessorsWithMechanisms(GameState current) {
List<GameState> result = generateSuccessors(current);
// 检查当前房间是否有可触发的机关
for (Mechanism mech : mechanisms) {
if (mech.roomId == current.roomId &&
current.inventory.contains(mech.triggerItem)) {
// 机关触发后解锁新通道
// 实际实现中需要动态修改邻接表或记录解锁状态
GameState triggered = new GameState(current.roomId, current.inventory,
current.path, current.steps + 1);
triggered.path.add("触发机关: " + mech.description);
result.add(triggered);
}
}
return result;
}
总结
本文通过Java实现了密室逃脱问题的完整求解框架：
- 图论建模：将房间映射为节点，通道映射为带权边（钥匙约束）
- 状态空间复合：将(位置, 背包)作为搜索状态，保证完备性
- BFS最短路径：确保找到的逃脱方案步数最少
- A*启发优化：利用距离启发函数加速复杂密室求解
读者可以进一步扩展：引入时间压力机制、增加NPC交互、实现多玩家协同逃脱、或构建随机密室生成器。
