游戏 AI / 系统课时
先验证一张可寻路地图
先验证一张可寻路地图
在正式接入 A* 之前,先用一张最小地图验证“节点是否连得起来”更可靠。本节用起点、终点和障碍物构造两个小地图,通过简单连通性检查确认可达与不可达两种结果,避免把地图建模错误误判成寻路算法问题。
学习目标
- 能用最小网格表达起点、终点、可行走格与障碍物
- 能先用基础遍历验证节点连通性,再继续调试 A*
- 能识别由障碍物分割形成的不可达区域
最小地图只保留四类信息
为了验证搜索空间,不需要一开始就放入地形权重、动态障碍、传送点等复杂规则。先保留四种符号即可:S 表示起点,G 表示终点,. 表示可行走格,# 表示障碍物。
验证时最重要的是区分两个问题:终点格本身是不是可走,以及起点所在连通区域能不能真正连接到终点。终点不是障碍物,并不等于它一定可达;一圈墙完全可以把一个合法终点隔离起来。

先用基础遍历检查连通性
在 A* 中,如果最终返回“找不到路径”,可能是算法实现有 bug,也可能是地图本来就不连通。调试时可以先用不依赖启发函数的广度优先搜索做基线检查:如果 BFS 也到不了终点,优先检查地图数据和邻接规则;如果 BFS 能到而 A* 不能到,再检查 A* 的开放列表、关闭列表和代价更新。
下面示例使用四方向移动,分别检查一张可达地图和一张被墙隔断的地图。
import java.util.ArrayDeque;
import java.util.Queue;
public class GridConnectivityCheck {
private static final int[][] DIRS = {
{0, -1}, {1, 0}, {0, 1}, {-1, 0}
};
public static boolean isReachable(char[][] grid) {
int height = grid.length;
int width = grid[0].length;
int sx = -1, sy = -1, gx = -1, gy = -1;
for (int y = 0; y < height; y++) {
for (int x = 0; x < width; x++) {
if (grid[y][x] == 'S') {
sx = x;
sy = y;
} else if (grid[y][x] == 'G') {
gx = x;
gy = y;
}
}
}
if (sx < 0 || gx < 0) {
throw new IllegalArgumentException("map must contain S and G");
}
boolean[][] visited = new boolean[height][width];
Queue<int[]> queue = new ArrayDeque<>();
queue.add(new int[]{sx, sy});
visited[sy][sx] = true;
while (!queue.isEmpty()) {
int[] current = queue.remove();
if (current[0] == gx && current[1] == gy) {
return true;
}
for (int[] d : DIRS) {
int nx = current[0] + d[0];
int ny = current[1] + d[1];
if (ny < 0 || ny >= height || nx < 0 || nx >= width) {
continue;
}
if (visited[ny][nx] || grid[ny][nx] == '#') {
continue;
}
visited[ny][nx] = true;
queue.add(new int[]{nx, ny});
}
}
return false;
}
private static char[][] map(String... rows) {
char[][] grid = new char[rows.length][];
for (int i = 0; i < rows.length; i++) {
grid[i] = rows[i].toCharArray();
}
return grid;
}
public static void main(String[] args) {
char[][] reachable = map(
"S....",
".###.",
"...#.",
".#...",
"....G"
);
char[][] blocked = map(
"S....",
"#####",
"....G",
".....",
"....."
);
System.out.println("reachable map: " + isReachable(reachable));
System.out.println("blocked map: " + isReachable(blocked));
}
}预期输出:
reachable map: true
blocked map: false这个结果只回答“是否存在一条合法路径”,不会判断哪条路最好。它正适合作为 A* 之前的地图基线测试,因为逻辑简单,出现异常时更容易确定问题是在地图还是在 A*。
不可达通常来自三类建模错误
第一类是地图边界或坐标转换错误。例如把 (x, y) 读成 [x][y],而二维数组实际按 [y][x] 存储,会导致障碍物出现在错误位置。第二类是邻接规则与游戏移动规则不一致,例如地图设计默认可以斜走,但验证程序只允许四方向。第三类是障碍物把地图切成多个连通区域,起点和终点恰好落在不同区域中。
把这张小地图当成回归测试
最小地图的价值不只是第一次调试。后续你修改节点结构、加入八方向移动、调整障碍判断或重写 A* 时,都可以保留这两个用例:可达地图必须继续返回可达,不可达地图必须继续返回不可达。
当最小地图稳定通过后,再逐步增加权重地形、斜向移动和更大地图。这样一旦结果出错,你可以快速定位是哪一层规则引入了问题,而不是在复杂关卡里同时猜地图、邻接和 A* 三套逻辑。