游戏 AI / 系统课时

先验证一张可寻路地图

先验证一张可寻路地图

在正式接入 A* 之前,先用一张最小地图验证“节点是否连得起来”更可靠。本节用起点、终点和障碍物构造两个小地图,通过简单连通性检查确认可达与不可达两种结果,避免把地图建模错误误判成寻路算法问题。

学习目标

  • 能用最小网格表达起点、终点、可行走格与障碍物
  • 能先用基础遍历验证节点连通性,再继续调试 A*
  • 能识别由障碍物分割形成的不可达区域

最小地图只保留四类信息

为了验证搜索空间,不需要一开始就放入地形权重、动态障碍、传送点等复杂规则。先保留四种符号即可:S 表示起点,G 表示终点,. 表示可行走格,# 表示障碍物。

验证时最重要的是区分两个问题:终点格本身是不是可走,以及起点所在连通区域能不能真正连接到终点。终点不是障碍物,并不等于它一定可达;一圈墙完全可以把一个合法终点隔离起来。

最小可达地图与不可达地图对比

先用基础遍历检查连通性

在 A* 中,如果最终返回“找不到路径”,可能是算法实现有 bug,也可能是地图本来就不连通。调试时可以先用不依赖启发函数的广度优先搜索做基线检查:如果 BFS 也到不了终点,优先检查地图数据和邻接规则;如果 BFS 能到而 A* 不能到,再检查 A* 的开放列表、关闭列表和代价更新。

下面示例使用四方向移动,分别检查一张可达地图和一张被墙隔断的地图。

java
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));
    }
}

预期输出:

text
reachable map: true
blocked map: false

这个结果只回答“是否存在一条合法路径”,不会判断哪条路最好。它正适合作为 A* 之前的地图基线测试,因为逻辑简单,出现异常时更容易确定问题是在地图还是在 A*。

不可达通常来自三类建模错误

第一类是地图边界或坐标转换错误。例如把 (x, y) 读成 [x][y],而二维数组实际按 [y][x] 存储,会导致障碍物出现在错误位置。第二类是邻接规则与游戏移动规则不一致,例如地图设计默认可以斜走,但验证程序只允许四方向。第三类是障碍物把地图切成多个连通区域,起点和终点恰好落在不同区域中。

把这张小地图当成回归测试

最小地图的价值不只是第一次调试。后续你修改节点结构、加入八方向移动、调整障碍判断或重写 A* 时,都可以保留这两个用例:可达地图必须继续返回可达,不可达地图必须继续返回不可达。

当最小地图稳定通过后,再逐步增加权重地形、斜向移动和更大地图。这样一旦结果出错,你可以快速定位是哪一层规则引入了问题,而不是在复杂关卡里同时猜地图、邻接和 A* 三套逻辑。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

先验证一张可寻路地图

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通