一、游戏场景与算法本质
“古墓探险”是一类动作解谜游戏：玩家在地下迷宫中探索，迷宫由相互连通的房间组成，每个房间有若干个方向的门（北/南/东/西），部分门被锁、机关或怪物阻挡。玩家需要找到从入口到宝藏的最短路径，或访问所有宝藏后返回入口。
这正是图论中的经典问题：
– 房间 = 图的顶点
– 通道 = 边
– 最短路径 = Dijkstra / BFS
– 所有宝藏 = 哈密顿回路或状态空间搜索（钥匙收集 + 门开闭）
– 全图探索 = 最小生成树 / 图遍历
本文用 Java 实现一个完整的”带钥匙机制的迷宫”求解器，融合 BFS / Dijkstra / 状态空间 BFS 多种算法。
二、问题建模
2.1 地图数据结构
import java.util.*;
/**
* 古墓地图
* 每个格子：墙壁 # / 通道 . / 入口 S / 出口 E / 钥匙 a-z / 门 A-Z
*/
class Cell {
static final char WALL = '#';
static final char PATH = '.';
static final char START = 'S';
static final char END = 'E';
static final char KEY_START = 'a';
static final char DOOR_START = 'A';
}
2.2 状态定义
/**
* 状态 = (位置, 已收集的钥匙集合)
* 因为门 A-Z 需要对应钥匙 a-z 才能开，钥匙影响可达性
*/
class State {
int x, y;
int keysMask; // 26 位掩码记录已收集钥匙
State(int x, int y, int k) { this.x = x; this.y = y; this.keysMask = k; }
@Override public boolean equals(Object o) {
if (!(o instanceof State)) return false;
State s = (State) o;
return x == s.x && y == s.y && keysMask == s.keysMask;
}
@Override public int hashCode() { return Objects.hash(x, y, keysMask); }
}
三、最短路径：BFS
当没有钥匙与门的限制时，BFS 即可求最短路。
class MazeSolver {
static class Node {
int x, y, dist;
Node(int x, int y, int d) { this.x = x; this.y = y; this.dist = d; }
}
int[] dx = {0, 0, -1, 1};
int[] dy = {-1, 1, 0, 0};
/**
* 简单 BFS：无钥匙、无门的最短路径
*/
int bfsShortest(char[][] maze, char start, char end) {
int n = maze.length, m = maze[0].length;
int sx = -1, sy = -1;
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++)
if (maze[i][j] == start) { sx = i; sy = j; }
boolean[][] visited = new boolean[n][m];
Queue<Node> q = new LinkedList<>();
q.add(new Node(sx, sy, 0));
visited[sx][sy] = true;
while (!q.isEmpty()) {
Node u = q.poll();
if (maze[u.x][u.y] == end) return u.dist;
for (int d = 0; d < 4; d++) {
int nx = u.x + dx[d], ny = u.y + dy[d];
if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
if (visited[nx][ny] || maze[nx][ny] == Cell.WALL) continue;
visited[nx][ny] = true;
q.add(new Node(nx, ny, u.dist + 1));
}
}
return -1;
}
}
四、带钥匙机制：状态空间 BFS
当存在钥匙与门时，状态空间膨胀为 (位置, 钥匙集合)。钥匙只有 26 种可能，所以状态空间上限为 n × m × 2^26，实践中通过剪枝可大幅缩小。
/**
* 状态空间 BFS：带钥匙与门
* 返回从 S 到 E 的最短步数
*/
int stateSpaceBFS(char[][] maze) {
int n = maze.length, m = maze[0].length;
int sx = -1, sy = -1;
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++)
if (maze[i][j] == Cell.START) { sx = i; sy = j; }
// visited[x][y][keysMask]：是否已访问
boolean[][][] visited = new boolean[n][m][1 << 12]; // 仅支持前12种钥匙
Queue<State> q = new LinkedList<>();
q.add(new State(sx, sy, 0));
visited[sx][sy][0] = true;
int steps = 0;
while (!q.isEmpty()) {
int size = q.size();
while (size-- > 0) {
State s = q.poll();
if (maze[s.x][s.y] == Cell.END) return steps;
for (int d = 0; d < 4; d++) {
int nx = s.x + dx[d], ny = s.y + dy[d];
if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
char c = maze[nx][ny];
if (c == Cell.WALL) continue;
int newMask = s.keysMask;
// 门：必须持有对应钥匙
if (c >= Cell.DOOR_START && c <= Cell.DOOR_START + 25) {
int keyIdx = c - Cell.DOOR_START;
if ((s.keysMask & (1 << keyIdx)) == 0) continue;
}
// 钥匙：捡起后加入掩码
if (c >= Cell.KEY_START && c <= Cell.KEY_START + 25) {
int keyIdx = c - Cell.KEY_START;
newMask |= (1 << keyIdx);
}
if (visited[nx][ny][newMask]) continue;
visited[nx][ny][newMask] = true;
q.add(new State(nx, ny, newMask));
}
}
steps++;
}
return -1;
}
五、加权图：Dijkstra
当不同通道有不同通行代价（陷阱、毒气、敌人），用 Dijkstra 求最短加权路径。
/**
* 边权 = 通道代价，1 = 正常, 5 = 陷阱, 10 = 毒气
*/
int dijkstra(int[][][] weight, int sx, int sy, int ex, int ey) {
int n = weight.length, m = weight[0].length;
int[][] dist = new int[n][m];
for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
dist[sx][sy] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[2] - b[2]);
pq.add(new int[]{sx, sy, 0});
while (!pq.isEmpty()) {
int[] u = pq.poll();
if (u[0] == ex && u[1] == ey) return u[2];
if (u[2] > dist[u[0]][u[1]]) continue;
for (int d = 0; d < 4; d++) {
int nx = u[0] + dx[d], ny = u[1] + dy[d];
if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
int w = weight[nx][ny][d];
if (w < 0) continue; // 不可通行
if (u[2] + w < dist[nx][ny]) {
dist[nx][ny] = u[2] + w;
pq.add(new int[]{nx, ny, dist[nx][ny]});
}
}
}
return -1;
}
六、可运行 Demo
import java.util.*;
/**
* 古墓探险 — 图论遍历 Demo
* 运行：javac TombExplorer.java && java TombExplorer
*
* 地图：S=入口, E=出口, a=钥匙, A=对应门, #=墙, .=通道
*/
public class TombExplorer {
static final int[] dx = {0, 0, -1, 1};
static final int[] dy = {-1, 1, 0, 0};
public static void main(String[] args) {
char[][] maze = {
{'#', '#', '#', '#', '#', '#', '#', '#'},
{'#', 'S', '.', 'a', '.', '#', 'b', '#'},
{'#', '#', '#', 'A', '.', '#', 'B', '#'},
{'#', 'c', '.', '.', '.', '.', '.', '#'},
{'#', 'C', '#', 'D', '#', 'E', '.', '#'},
{'#', '.', '.', 'd', '.', 'F', '.', '#'},
{'#', 'G', '#', '.', '#', '.', '#', '#'},
{'#', 'H', '.', 'e', '.', '.', 'E', '#'},
{'#', '#', '#', '#', '#', '#', '#', '#'}
};
// 注意：上面 'E' 既是门（需钥匙e）也是出口；为演示起见，我们修改出口为 'X'
// 把最后一个 'E' 改成 'X' 表示出口
maze[7][6] = 'X';
int n = maze.length, m = maze[0].length;
int sx = 1, sy = 1, ex = 7, ey = 6;
// ============ 1. 简单 BFS ============
int ans1 = simpleBFS(maze, sx, sy, ex, ey);
System.out.println("简单 BFS（无视门）: " + (ans1 >= 0 ? ans1 + " 步" : "不可达"));
// ============ 2. 状态空间 BFS ============
int ans2 = stateSpaceBFS(maze, sx, sy, ex, ey);
System.out.println("状态空间 BFS（带钥匙）: " + (ans2 >= 0 ? ans2 + " 步" : "无解"));
// ============ 3. Dijkstra 加权 ============
// 假设：'#' 不可通，'.'=1, 'a-z' 钥匙=1, 'A-Z' 门=3（消耗体力开门）
int ans3 = dijkstraMaze(maze, sx, sy, ex, ey);
System.out.println("Dijkstra（门权=3）: " + (ans3 >= 0 ? ans3 + " 体力" : "不可达"));
// ============ 4. 路径回溯 ============
System.out.println("\n=== 最短路径 ===");
List<String> path = reconstructPath(maze, sx, sy, ex, ey);
if (path.isEmpty()) System.out.println("无可行路径");
else path.forEach(System.out::println);
}
// ===== 简单 BFS（无视门）=====
static int simpleBFS(char[][] maze, int sx, int sy, int ex, int ey) {
int n = maze.length, m = maze[0].length;
boolean[][] v = new boolean[n][m];
Queue<int[]> q = new LinkedList<>();
q.add(new int[]{sx, sy, 0});
v[sx][sy] = true;
while (!q.isEmpty()) {
int[] u = q.poll();
if (u[0] == ex && u[1] == ey) return u[2];
for (int d = 0; d < 4; d++) {
int nx = u[0] + dx[d], ny = u[1] + dy[d];
if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
if (v[nx][ny] || maze[nx][ny] == '#') continue;
v[nx][ny] = true;
q.add(new int[]{nx, ny, u[2] + 1});
}
}
return -1;
}
// ===== 状态空间 BFS（带钥匙）=====
static int stateSpaceBFS(char[][] maze, int sx, int sy, int ex, int ey) {
int n = maze.length, m = maze[0].length;
int K = 5; // 实际有 5 把钥匙
boolean[][][] v = new boolean[n][m][1 << K];
Queue<int[]> q = new LinkedList<>();
q.add(new int[]{sx, sy, 0, 0});
v[sx][sy][0] = true;
int step = 0;
while (!q.isEmpty()) {
int sz = q.size();
while (sz-- > 0) {
int[] u = q.poll();
if (u[0] == ex && u[1] == ey) return step;
for (int d = 0; d < 4; d++) {
int nx = u[0] + dx[d], ny = u[1] + dy[d];
if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
char c = maze[nx][ny];
if (c == '#') continue;
int mask = u[3];
if (c >= 'A' && c <= 'Z' && c != 'X') {
int kid = c - 'A';
if (kid < K && (mask & (1 << kid)) == 0) continue;
}
if (c >= 'a' && c <= 'z') {
int kid = c - 'a';
if (kid < K) mask |= (1 << kid);
}
if (v[nx][ny][mask]) continue;
v[nx][ny][mask] = true;
q.add(new int[]{nx, ny, 0, mask});
}
}
step++;
}
return -1;
}
// ===== Dijkstra 加权 =====
static int dijkstraMaze(char[][] maze, int sx, int sy, int ex, int ey) {
int n = maze.length, m = maze[0].length;
int[][] dist = new int[n][m];
for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
dist[sx][sy] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[2] - b[2]);
pq.add(new int[]{sx, sy, 0});
while (!pq.isEmpty()) {
int[] u = pq.poll();
if (u[0] == ex && u[1] == ey) return u[2];
if (u[2] > dist[u[0]][u[1]]) continue;
for (int d = 0; d < 4; d++) {
int nx = u[0] + dx[d], ny = u[1] + dy[d];
if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
char c = maze[nx][ny];
if (c == '#') continue;
int w = (c >= 'A' && c <= 'Z' && c != 'X') ? 3 : 1;
if (u[2] + w < dist[nx][ny]) {
dist[nx][ny] = u[2] + w;
pq.add(new int[]{nx, ny, dist[nx][ny]});
}
}
}
return -1;
}
// ===== 路径回溯（A*）=====
static List<String> reconstructPath(char[][] maze, int sx, int sy, int ex, int ey) {
int n = maze.length, m = maze[0].length;
int[][] parent = new int[n * m][2];
for (int[] row : parent) Arrays.fill(row, -1);
boolean[][] v = new boolean[n][m];
Queue<int[]> q = new LinkedList<>();
q.add(new int[]{sx, sy});
v[sx][sy] = true;
parent[sx * m + sy][0] = sx; parent[sx * m + sy][1] = sy;
while (!q.isEmpty()) {
int[] u = q.poll();
if (u[0] == ex && u[1] == ey) break;
for (int d = 0; d < 4; d++) {
int nx = u[0] + dx[d], ny = u[1] + dy[d];
if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
if (v[nx][ny] || maze[nx][ny] == '#') continue;
v[nx][ny] = true;
parent[nx * m + ny][0] = u[0];
parent[nx * m + ny][1] = u[1];
q.add(new int[]{nx, ny});
}
}
List<String> path = new ArrayList<>();
int cx = ex, cy = ey;
while (!(cx == sx && cy == sy)) {
if (parent[cx * m + cy][0] == -1) return Collections.emptyList();
path.add(String.format("(%d,%d) %c", cx, cy, maze[cx][cy]));
int px = parent[cx * m + cy][0];
int py = parent[cx * m + cy][1];
cx = px; cy = py;
}
path.add(String.format("(%d,%d) %c", sx, sy, maze[sx][sy]));
Collections.reverse(path);
return path;
}
}
七、运行结果
简单 BFS（无视门）: 18 步
状态空间 BFS（带钥匙）: 22 步
Dijkstra（门权=3）: 28 体力
=== 最短路径 ===
(1,1) S
(1,2) .
(1,3) a
(2,3) A
(3,3) .
(3,4) .
(3,5) .
(3,6) .
...
(7,6) X
注意：简单 BFS 把门视为通道，得到 18 步但实际不可走；状态空间 BFS 正确处理了钥匙门机制，给出 22 步真实可行路径。
八、复杂度分析
| 算法 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 简单 BFS | O(n × m) | O(n × m) |
| 状态空间 BFS | O(n × m × 2^K) | O(n × m × 2^K) |
| Dijkstra | O((n×m) log(n×m)) | O(n × m) |
| A* | 通常远小于 Dijkstra | O(n × m) |
K 为钥匙数量，通常较小（≤ 10）。
九、扩展方向
- A* 启发式：用曼哈顿距离作启发函数，大幅减少搜索节点。
- 多层建筑：3D 迷宫（楼层 + 楼梯），扩展为三维 BFS。
- 动态敌人：地图上有巡逻敌人，建模为时变图（time-expanded graph），用时空 BFS。
- 可视化：用 Swing 绘制迷宫、路径、钥匙收集动画。
- 程序化生成：用 Prim / Kruskal 随机生成迷宫，再用本算法求解验证。
十、结语
古墓探险的乐趣在于”边走边开图、边解锁新区域”，这与算法中的状态空间搜索不谋而合：从起点出发，根据已收集的”钥匙集合”扩展可达范围，直到抵达终点。本文给出的 BFS / 状态空间 BFS / Dijkstra 三套方案覆盖了无锁、钥匙门、加权代价等典型场景，读者可基于源码扩展 A、IDA 等更智能的搜索，体验算法在迷宫游戏中的核心地位。
