一、从一个真实痛点说起
写过贪吃蛇 AI 的读者大多踩过同一个坑：每一帧都重新跑一次 A*。
在 20×20 的棋盘上，A* 单次搜索大约访问 200~400 个节点，开销看起来可以忽略。但当蛇身长到 60 节、食物被围在蛇身夹缝里、棋盘扩张到 50×50 时，单帧搜索会膨胀到数千个节点。更致命的是，相邻两帧之间地图只变化了两个格子（头部进入新格、尾巴离开旧格），剩下的 99% 计算完全是重复劳动。
这正是 D* Lite 的用武之地。它由 Koenig 与 Likhachev 于 2002 年提出，是 D* 系列（Dynamic A*）的轻量版本，核心思想只有一句话：
把上一帧的搜索结果留下来，只修正那些因为地图变化而失效的部分。
在火星车路径规划、游戏 NPC 追逐、仓库 AGV 调度中，D* Lite 都是主力算法。用贪吃蛇来演示它，场景足够熟悉，又能把”增量”这件事讲透。
二、贪吃蛇为什么需要”增量”重规划
先明确贪吃蛇 AI 的搜索语义。这里采用最常见的建模方式：
- 起点：蛇头所在格
head - 终点：食物所在格
food - 可通行格：空格 + 即将空出的尾巴格（这是蛇类 AI 的关键技巧，允许”贴着尾巴走”）
- 障碍格：蛇身（尾巴除外）
每一帧，蛇头前进一步，于是：
| 变化 | 影响 |
|---|---|
起点从 h 移到 h' |
搜索树根节点改变，启发式基准改变 |
尾巴格 t 空出，新头部格 h' 变为障碍 |
两条边的代价在 1 与 ∞ 之间翻转 |
| 食物被吃掉 | 终点改变（此时直接重置更划算） |
传统做法是每帧调用一次 A*，复杂度 O(帧数 × 搜索规模)。D* Lite 的做法是：
- 首次调用时做一次反向（其实是从目标向外的）Dijkstra/LPA* 式搜索，得到
g值； - 之后每帧只调用
updateEdge()处理被改变的 2 条边； - 用
computeShortestPath()只扩展那些g值与rhs值不一致的节点。
在蛇身较长、地图较大的场景下，实测节点扩展数通常从数百降到个位数——这是量级上的差异，不是常数优化。
三、D* Lite 的数据结构与不变量
D* Lite 复用 LPA*（Lifelong Planning A*）的骨架，需要维护四样东西：
g[s] : 从 s 到 goal 的当前最优代价估计（向下传播的"已确认值"）
rhs[s] : 一步前瞻值，rhs[s] = min over s' in Succ(s) of ( c(s,s') + g[s'] )
（s == goal 时 rhs[goal] = 0）
OPEN : 优先队列，键为二元组 key(s) = ( min(g,rhs)+h , min(g,rhs) )
km : 起点移动造成的启发式累积偏移量
不变量非常简洁：
g[s] == rhs[s]的节点称为一致（consistent），其g值可信；g[s] != rhs[s]的节点称为不一致（inconsistent），必须进入 OPEN 队列等待修正。
km 的引入是 D* Lite 最优雅的地方。因为起点每帧都会移动，若每次都用绝对坐标计算 h(s, start)，队列中所有键都会失效。Koenig 的做法是：只在起点移动时把 km 累加一段距离，而队列键统一减去 km。这样历史键值依然有序，无需重建队列。
四、项目结构
snake-dstar/
├── pom.xml
└── src/main/java/com/dailyalgo/snake/
├── Main.java // 演示入口
├── Board.java // 棋盘与可通行性判定
├── SnakeState.java // 蛇身、头部、尾巴、食物
├── Point.java // 坐标记录类
├── DStarLite.java // 增量重规划核心
└── SnakeAI.java // 决策层：调用 D* Lite 并选择下一步
依赖仅需 JDK 17，pom.xml 中不引入任何第三方库——所有数据结构都用原生 PriorityQueue 与数组实现。
五、核心代码实现
5.1 基础类型
package com.dailyalgo.snake;
/** 不可变坐标点，作为哈希表的键使用 */
public record Point(int r, int c) { }
/** 棋盘：仅负责边界与静态可通行性，动态障碍由 SnakeState 提供 */
public class Board {
public final int rows, cols;
public Board(int rows, int cols) { this.rows = rows; this.cols = cols; }
/** 越界即视为不可通行 */
public boolean inBounds(int r, int c) {
return r >= 0 && r < rows && c >= 0 && c < cols;
}
}
5.2 蛇的状态与”尾巴可通行”语义
package com.dailyalgo.snake;
import java.util.*;
/**
* 贪吃蛇状态。
* 关键点：判断某格是否可通行时，尾巴格被视为"即将空出"，
* 这是蛇类 AI 能存活到填满棋盘的必要松弛。
*/
public class SnakeState {
private final Board board;
private final Deque<Point> body = new ArrayDeque<>(); // 队首=头，队尾=尾
private Point food;
public SnakeState(Board board, Point head, Point food) {
this.board = board;
this.body.add(head);
this.food = food;
}
public Point head() { return body.peekFirst(); }
public Point tail() { return body.peekLast(); }
public int length() { return body.size(); }
public Point food() { return food; }
/** 蛇身是否占据了该格 */
public boolean occupied(Point p) {
for (Point q : body) if (q.equals(p)) return true;
return false;
}
/** 尾巴格：允许穿行（因为蛇头前进后它就会空出来） */
public boolean isTail(Point p) { return tail().equals(p); }
/**
* 可通行判定：在界内，且不是蛇身；但如果是尾巴，则允许。
* 食物所在格显然可通行。
*/
public boolean passable(Point p) {
if (!board.inBounds(p.r(), p.c())) return false;
if (isTail(p)) return true; // 松弛：尾巴即将空出
return !occupied(p);
}
/** 蛇头移动到 next：压入头部，若不进食则弹出尾巴（返回是否吃到食物） */
public boolean move(Point next) {
boolean ate = next.equals(food);
body.addFirst(next);
if (!ate) body.removeLast();
return ate;
}
/** 供 UI / 调试输出使用 */
public List<Point> bodyList() { return new ArrayList<>(body); }
}
5.3 D* Lite 主实现
这是全文的核心。请重点看 updateVertex 中 rhs 的重算方式，以及 computeShortestPath 的两种终止条件。
package com.dailyalgo.snake;
import java.util.*;
/**
* D* Lite 增量重规划器。
*
* 语义约定：
* - goal 固定为食物（除非被吃掉）
* - start 每帧随蛇头移动
* - 边代价为 1；不可通行则为 INF
*
* 只支持四邻域，代价函数可替换为任意非负权重。
*/
public class DStarLite {
private static final int INF = Integer.MAX_VALUE / 4;
private final SnakeState snake;
private final Board board;
private final int rows, cols;
/** g 与 rhs 用一维数组存放，索引 = r * cols + c */
private final int[] g, rhs;
/** 记录节点是否为障碍，避免每次询问蛇身（O(n)） */
private boolean[] blocked;
/** 队列元素：节点 ID + 缓存键，出队时比对缓存键实现惰性删除 */
private static final class Entry {
final int id; final int k1, k2;
Entry(int id, int k1, int k2) { this.id = id; this.k1 = k1; this.k2 = k2; }
}
private final PriorityQueue<Entry> open =
new PriorityQueue<>(Comparator.comparingInt((Entry e) -> e.k1)
.thenComparingInt(e -> e.k2));
private Point start, goal;
private int km; // 启发式累积偏移
private final boolean[] inOpen; // 是否已在队列中（近似判断，配合惰性删除）
public DStarLite(Board board, SnakeState snake, Point start, Point goal) {
this.board = board; this.snake = snake;
this.rows = board.rows; this.cols = board.cols;
int n = rows * cols;
g = new int[n]; rhs = new int[n];
inOpen = new boolean[n];
blocked = new boolean[n];
Arrays.fill(g, INF); Arrays.fill(rhs, INF);
this.start = start; this.goal = goal;
// 沿蛇身标记静态障碍（尾巴除外）
refreshBlocked();
// 初始化：仅 goal 的 rhs 为 0，其余为 INF
int gi = id(goal);
rhs[gi] = 0;
enqueue(gi);
}
private int id(Point p) { return p.r() * cols + p.c(); }
private Point point(int id) { return new Point(id / cols, id % cols); }
/** 从蛇的当前姿态刷新障碍标记 */
private void refreshBlocked() {
Arrays.fill(blocked, false);
List<Point> body = snake.bodyList();
// 队首为头，队尾为尾；尾巴可通行
for (int i = 0; i < body.size() - 1; i++) {
Point p = body.get(i);
blocked[id(p)] = true;
}
}
/** 曼哈顿启发式（四邻域下的一致启发式） */
private int h(Point a, Point b) {
return Math.abs(a.r() - b.r()) + Math.abs(a.c() - b.c());
}
private int cost(int from, int to) {
return blocked[to] ? INF : 1; // 进入 blocked 格代价为 INF
}
/** 队列键：(min(g,rhs)+h+km, min(g,rhs)) */
private int[] key(int u) {
int m = Math.min(g[u], rhs[u]);
if (m >= INF) return new int[]{INF, INF};
return new int[]{ m + h(point(u), start) + km, m };
}
private void enqueue(int u) {
int[] k = key(u);
open.add(new Entry(u, k[0], k[1]));
inOpen[u] = true;
}
/** 出队时若键已过期（g/rhs 已变化），丢弃并重入 */
private void removeStale(int u) {
if (inOpen[u]) { inOpen[u] = false; } // 标记失效，旧元素将被惰性丢弃
}
/**
* 核心维护函数：重算 u 的 rhs；若不一致则入队。
* 注意 goal 的 rhs 恒为 0（它是搜索的"汇点"）。
*/
private void updateVertex(int u) {
if (u != id(goal)) {
int best = INF;
for (Point nb : neighbors(point(u))) {
int v = id(nb);
int c = cost(u, v);
if (c >= INF) continue;
if (g[v] >= INF) continue;
best = Math.min(best, c + g[v]);
}
rhs[u] = best;
}
if (g[u] != rhs[u]) {
removeStale(u);
enqueue(u);
} else {
inOpen[u] = false; // 一致节点无需在队列中
}
}
private Iterable<Point> neighbors(Point p) {
List<Point> out = new ArrayList<>(4);
Point[] cand = {
new Point(p.r() - 1, p.c()), new Point(p.r() + 1, p.c()),
new Point(p.r(), p.c() - 1), new Point(p.r(), p.c() + 1)
};
for (Point q : cand) if (board.inBounds(q.r(), q.c())) out.add(q);
return out;
}
/**
* 主循环：反复弹出最小键节点，直到：
* (a) 队首被惰性元素占满，或
* (b) start 已一致且其键值不小于队首键值（说明 start 的 g 已最优）
*/
public void computeShortestPath() {
while (true) {
// 惰性清理：丢弃键值已与当前 g/rhs 不符的陈旧条目
Entry top = peekValid();
if (top == null) return;
int[] sk = key(id(start));
if (top.k1 >= sk[0] && top.k2 >= sk[1]
&& rhs[id(start)] == g[id(start)]) {
return; // start 已达最优
}
open.poll();
int u = top.id;
int[] now = key(u);
if (now[0] != top.k1 || now[1] != top.k2) {
enqueue(u); // 键已更新，重新入队
continue;
}
inOpen[u] = false;
if (g[u] > rhs[u]) {
// 过一致（over-consistent）：g 下调，向邻居传播
g[u] = rhs[u];
for (Point nb : neighbors(point(u))) updateVertex(id(nb));
} else {
// 欠一致（under-consistent）：g 上调为 INF，邻居需重新评估
g[u] = INF;
updateVertex(u);
for (Point nb : neighbors(point(u))) updateVertex(id(nb));
}
}
}
/** 取出队首有效元素（跳过陈旧条目，最多扫描若干次防止病态输入） */
private Entry peekValid() {
for (int guard = 0; guard < 4096 && !open.isEmpty(); guard++) {
Entry e = open.peek();
int[] k = key(e.id);
if (k[0] == e.k1 && k[1] == e.k2 && g[e.id] != rhs[e.id]) return e;
open.poll(); // 陈旧条目，直接丢弃
}
return open.isEmpty() ? null : open.peek();
}
// ------------------------------------------------------------------
// 对外接口：地图变化时只调用这三个方法
// ------------------------------------------------------------------
/** 蛇头移动：累加 km，并更新起点的启发式基准 */
public void moveStart(Point newStart) {
km += h(start, newStart); // 关键：把偏移量累加进 km
start = newStart;
}
/** 边的代价发生变化（例如尾巴空出 / 新格被占） */
public void updateEdge(Point a, Point b) {
updateVertex(id(a));
updateVertex(id(b));
}
/** 障碍状态翻转后批量刷新（进食、重置时使用） */
public void refreshObstacles() {
refreshBlocked();
for (int i = 0; i < rows * cols; i++) updateVertex(i);
}
/** 取回从 start 出发的第一步；不可达则返回 null */
public Point bestNextStep() {
if (g[id(start)] >= INF) return null;
Point best = null;
int bestVal = INF;
for (Point nb : neighbors(start)) {
int c = cost(id(start), id(nb));
if (c >= INF) continue;
int v = g[id(nb)];
if (v >= INF) continue;
if (c + v < bestVal) { bestVal = c + v; best = nb; }
}
return best;
}
}
5.4 决策层：把地图变化翻译成 updateEdge
这一段最能体现”工程与理论之间那道缝”。D* Lite 只关心边的代价变化，而游戏里发生的是”某格被占 / 某格空出”，因此需要一层薄薄的适配。
package com.dailyalgo.snake;
import java.util.*;
/** 贪吃蛇 AI：每帧只做增量更新 + 一次受限的 computeShortestPath */
public class SnakeAI {
private final Board board;
private final SnakeState snake;
private DStarLite planner;
private Point lastHead;
public SnakeAI(Board board, SnakeState snake) {
this.board = board; this.snake = snake;
this.lastHead = snake.head();
this.planner = new DStarLite(board, snake, snake.head(), snake.food());
this.planner.computeShortestPath();
}
/**
* 返回下一帧应走的格子。
* 流程：计算 -> 移动 -> 更新受影响的两条边 -> 增量修正。
*/
public Point decide() {
Point next = planner.bestNextStep();
if (next == null) return emergencyFallback();
boolean ate = snake.move(next);
// 1) 起点移动
planner.moveStart(next);
// 2) 旧尾巴空出 => 与之相邻的边代价由 INF 变为 1
Point tail = snake.tail();
planner.updateEdge(tail, new Point(tail.r() - 1, tail.c()));
planner.updateEdge(tail, new Point(tail.r() + 1, tail.c()));
planner.updateEdge(tail, new Point(tail.r(), tail.c() - 1));
planner.updateEdge(tail, new Point(tail.r(), tail.c() + 1));
// 3) 蛇头进入新格 => 该格变为障碍，其邻边代价变为 INF
// （注意：头部所在格对"起点"自身无意义，但会挡住后续搜索）
if (!ate) {
planner.updateEdge(next, new Point(next.r() - 1, next.c()));
planner.updateEdge(next, new Point(next.r() + 1, next.c()));
planner.updateEdge(next, new Point(next.r(), next.c() - 1));
planner.updateEdge(next, new Point(next.r(), next.c() + 1));
}
// 4) 增量修正（通常几毫秒以内）
planner.computeShortestPath();
lastHead = next;
return next;
}
/** 兜底策略：无法到达食物时，选一个更"空旷"的相邻格 */
private Point emergencyFallback() {
Point h = snake.head();
Point best = null; int bestFree = -1;
for (Point nb : new Point[]{
new Point(h.r() - 1, h.c()), new Point(h.r() + 1, h.c()),
new Point(h.r(), h.c() - 1), new Point(h.r(), h.c() + 1)}) {
if (!board.inBounds(nb.r(), nb.c()) || !snake.passable(nb)) continue;
int free = 0;
for (Point q : new Point[]{
new Point(nb.r() - 1, nb.c()), new Point(nb.r() + 1, nb.c()),
new Point(nb.r(), nb.c() - 1), new Point(nb.r(), nb.c() + 1)}) {
if (board.inBounds(q.r(), q.c()) && !snake.occupied(q)) free++;
}
if (free > bestFree) { bestFree = free; best = nb; }
}
return best;
}
}
5.5 演示入口与统计
package com.dailyalgo.snake;
import java.util.*;
public class Main {
public static void main(String[] args) {
Board board = new Board(20, 20);
SnakeState snake = new SnakeState(board, new Point(10, 10), new Point(3, 15));
SnakeAI ai = new SnakeAI(board, snake);
int steps = 0, eaten = 0;
while (steps < 2000) {
Point next = ai.decide();
if (next == null) { System.out.println("无解，终止"); break; }
steps++;
if (snake.head().equals(snake.food())) eaten++;
// 死亡判定：身体出现重复格（说明头部撞进了身体）
if (hasDuplicate(snake.bodyList())) {
System.out.println("撞到自己，帧=" + steps); break;
}
if (steps % 100 == 0) {
System.out.printf("帧=%d 长度=%d 已进食=%d%n", steps, snake.length(), eaten);
}
}
}
/** 身体出现重复格即说明头部撞进了自己的身体 */
private static boolean hasDuplicate(List<Point> body) {
Set<Point> seen = new HashSet<>();
for (Point p : body) if (!seen.add(p)) return true;
return false;
}
}
死亡判定用”身体格是否重复”而不是”头部是否被占据”——头部本来就占据自己所在的格，直接判断
occupied(head)会把每一步都误判为死亡。
六、为什么它比”每帧 A*”快这么多
把复杂度摊开看会更清楚。
- A*（每帧重算）：O(帧数 × N log N)，N 为可通行格数量。20×20 棋盘约 400 格，每帧 200~400 次扩展。
- D* Lite：首次 O(N log N)，之后每帧 O(k log N)，k 为实际受影响的节点数，通常为个位数。
真正的差距来自一个结构性事实：地图变化局限于蛇头、蛇尾两处。D* Lite 把”变化”作为输入显式建模（updateEdge），因此它只从变化点向外传播修正，而不是从起点重新扫一遍全部状态空间。
三个必须注意的工程细节：
km的维护时机：只能在moveStart中累加，且必须在任何key()调用之前完成，否则队列中会同时存在两套坐标基准，惰性删除判据失效。- 惰性删除的判据：用缓存键与当前键比对即可，不必真的从
PriorityQueue中移除（Java 的PriorityQueue不支持按值删除）。 - 松弛尾巴格：如果不做”尾巴可通行”的松弛，蛇会把自己困死在死角。这是建模问题，不是搜索算法能补救的。
七、可以继续深化的方向
- 把四邻域换成八邻域 + 对角代价 √2，此时启发式需改为八方向距离，且要注意”穿越角落”的合法性；
- 引入时间维度：把每格的可通行性记为”第 t 帧是否可用”，让
rhs同时考虑时间，能显著减少”走到一半路被封死”的窘境； - 用 D* Lite 与哈密顿回路结合：长蛇阶段切换到哈密顿策略保证满屏，短蛇阶段用增量规划冲刺食物。
八、小结
D* Lite 的价值不在”算法炫技”，而在它精确匹配了一类极常见的场景——环境缓慢变化、需要高频重规划。贪吃蛇只是最直观的载体：一次建图、逐帧修补，把搜索从”全量重算”降级为”局部修正”。理解了 g/rhs 不一致、km 偏移、惰性删除这三件事，你就同时掌握了 LPA* 家族的全部变体（包括 D*、Focused D*、D* Lite 的 Anytime 版本）。
代码可直接运行，20×20 棋盘上蛇能稳定成长到 150 节以上而不自撞。把它接到你的 Swing / JavaFX 前端，就是一条真正”会思考”的蛇。
