游戏 AI / 系统课时

邻接节点怎样决定能否拐弯

邻接节点怎样决定能否拐弯

把地图离散成网格后,寻路并不是“想往哪走就往哪走”,而是由邻接规则决定每个节点能扩展到哪些位置。本节比较四方向与八方向移动,并重点处理斜向移动时最容易被忽略的“穿墙切角”问题。

学习目标

  • 理解四方向、八方向邻接规则对路线形状和可达性的影响
  • 正确判断斜向移动,并阻止角色从两个障碍物夹角中穿过
  • 能为自己的移动模型选择与游戏规则一致的邻接集合

邻接规则就是搜索空间的边

在网格地图中,每个可行走格子可以看作一个节点,能够一步到达的格子就是它的邻接节点。四方向规则只允许上、下、左、右移动,因此每个节点最多有 4 条边;八方向规则额外允许四个对角方向,因此最多有 8 条边。

四方向更适合棋盘式、方格战棋或明确禁止斜走的地图。八方向更接近连续空间中的角色移动,但它会引入两个额外问题:斜向一步的代价通常不应与直线一步完全相同,而且必须判断斜线是否穿过障碍物角点。

四方向与八方向邻接以及切角关系

斜向移动为什么不能直接放行

假设角色位于 (x, y),准备走到 (x + 1, y - 1)。如果只检查目标格是否为空,那么即使右侧 (x + 1, y) 和上侧 (x, y - 1) 都是墙,程序仍可能允许角色从夹角穿过去。

常见做法是:执行斜向移动时,同时检查与这条斜线相邻的两个正交格。若采用严格防切角规则,只要其中任意一个正交格被阻挡,就禁止这次斜移。这样生成的路径会更符合有体积角色在网格中的实际运动约束。

用代码生成合法邻居

下面的 Java 示例同时支持四方向和八方向,并在八方向模式下启用严格防切角。地图中 true 表示障碍物。

java
import java.util.ArrayList;
import java.util.List;

public class GridNeighbors {
    private static final int[][] FOUR_DIRS = {
        {0, -1}, {1, 0}, {0, 1}, {-1, 0}
    };

    private static final int[][] EIGHT_DIRS = {
        {0, -1}, {1, 0}, {0, 1}, {-1, 0},
        {1, -1}, {1, 1}, {-1, 1}, {-1, -1}
    };

    public static List<String> neighbors(
            boolean[][] blocked, int x, int y, boolean allowDiagonal) {
        int[][] dirs = allowDiagonal ? EIGHT_DIRS : FOUR_DIRS;
        List<String> result = new ArrayList<>();

        for (int[] d : dirs) {
            int nx = x + d[0];
            int ny = y + d[1];

            if (!walkable(blocked, nx, ny)) {
                continue;
            }

            boolean diagonal = d[0] != 0 && d[1] != 0;
            if (diagonal) {
                // 严格防切角:斜线两侧的正交格必须都可通行。
                if (!walkable(blocked, x + d[0], y)
                        || !walkable(blocked, x, y + d[1])) {
                    continue;
                }
            }

            result.add("(" + nx + "," + ny + ")");
        }

        return result;
    }

    private static boolean walkable(boolean[][] blocked, int x, int y) {
        return y >= 0 && y < blocked.length
                && x >= 0 && x < blocked[0].length
                && !blocked[y][x];
    }

    public static void main(String[] args) {
        boolean[][] blocked = new boolean[4][4];
        blocked[0][1] = true; // 起点上方
        blocked[1][2] = true; // 起点右侧

        System.out.println("4-dir: " + neighbors(blocked, 1, 1, false));
        System.out.println("8-dir: " + neighbors(blocked, 1, 1, true));
    }
}

预期输出:

text
4-dir: [(1,2), (0,1)]
8-dir: [(1,2), (0,1), (0,2)]

右上 (2,0)、左上 (0,0) 和右下 (2,2) 虽然部分目标格本身没有障碍,但它们对应的斜线至少贴着一个被阻挡的正交格,因此被严格防切角规则过滤掉。左下 (0,2) 两侧都可通行,所以保留。

移动代价也要跟邻接规则一致

如果后续 A* 把直线一步的代价设为 1,八方向中的斜向一步通常可设为 sqrt(2) 的近似值,例如 1.414。否则斜向移动会被错误地当成与横向移动同样便宜,路径代价与实际距离不一致。

四方向地图通常配合曼哈顿距离启发式;允许八方向且斜线代价为 sqrt(2) 时,更适合使用八方向距离或欧氏距离。邻接规则、移动代价和启发函数三者要描述同一种移动模型,否则 A* 仍可能运行,但路径质量和最优性会偏离预期。

什么时候该选四方向或八方向

若角色只能按格移动,或玩法要求路线具有明显直角转折,选四方向最简单,也最容易验证。若角色在平面中可以自然斜走,八方向通常更合适,但必须把斜向代价和切角规则一起设计。

真正决定“能否拐弯”的不是 A* 本身,而是你向搜索器暴露了哪些邻接边。只要邻接规则与实际角色移动约束保持一致,后续开放列表、代价计算和启发式才是在正确的搜索空间上工作。

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

目录与阅读设置

阅读设置

17

记录一个想法

邻接节点怎样决定能否拐弯

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

登录哪都通