游戏 AI / 系统课时
邻接节点怎样决定能否拐弯
邻接节点怎样决定能否拐弯
把地图离散成网格后,寻路并不是“想往哪走就往哪走”,而是由邻接规则决定每个节点能扩展到哪些位置。本节比较四方向与八方向移动,并重点处理斜向移动时最容易被忽略的“穿墙切角”问题。
学习目标
- 理解四方向、八方向邻接规则对路线形状和可达性的影响
- 正确判断斜向移动,并阻止角色从两个障碍物夹角中穿过
- 能为自己的移动模型选择与游戏规则一致的邻接集合
邻接规则就是搜索空间的边
在网格地图中,每个可行走格子可以看作一个节点,能够一步到达的格子就是它的邻接节点。四方向规则只允许上、下、左、右移动,因此每个节点最多有 4 条边;八方向规则额外允许四个对角方向,因此最多有 8 条边。
四方向更适合棋盘式、方格战棋或明确禁止斜走的地图。八方向更接近连续空间中的角色移动,但它会引入两个额外问题:斜向一步的代价通常不应与直线一步完全相同,而且必须判断斜线是否穿过障碍物角点。

斜向移动为什么不能直接放行
假设角色位于 (x, y),准备走到 (x + 1, y - 1)。如果只检查目标格是否为空,那么即使右侧 (x + 1, y) 和上侧 (x, y - 1) 都是墙,程序仍可能允许角色从夹角穿过去。
常见做法是:执行斜向移动时,同时检查与这条斜线相邻的两个正交格。若采用严格防切角规则,只要其中任意一个正交格被阻挡,就禁止这次斜移。这样生成的路径会更符合有体积角色在网格中的实际运动约束。
用代码生成合法邻居
下面的 Java 示例同时支持四方向和八方向,并在八方向模式下启用严格防切角。地图中 true 表示障碍物。
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));
}
}预期输出:
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* 本身,而是你向搜索器暴露了哪些邻接边。只要邻接规则与实际角色移动约束保持一致,后续开放列表、代价计算和启发式才是在正确的搜索空间上工作。