传统迷宫求解用格点 A，得到的路径是”贴着格子中心”的折线，转弯次数多、路线僵硬。如果把它交给一个虚拟角色去走，动作会很不自然。本文换一条完全不同的路线：把迷宫的可走通道先抽取成导航网格，用 Delaunay 三角剖分 把离散点变成连续三角形面，再用 漏斗算法（Simple Stupid Funnel）* 拉出一条”拉紧的绳子”式最短路径——允许任意角度转向，而不是只能在 8 个方向上走。
一、为什么需要 Delaunay + 漏斗
格点 A* 的三个固有代价：
- 路径冗余：8 邻接图上，一条直线在格子化之后会变成一串锯齿。虽然可以做”视线平滑”（raycast），但对于宽通道曲线，raycast 只能局部修补。
- 精度绑定格距：格距越小，格子越多，搜索越慢；格距越大，通道细节丢失，窄缝识别不出来。
- 无法表达连续转向：角色实际运动会朝任意方向，格子模型天然只有 8 个方向。
导航网格（NavMesh）的思路是：把连续可走空间切成凸多边形。凸多边形内任意两点的连线都落在多边形内，所以面内移动是”免费”的，只需要在多边形之间的公共边（portal） 上做选择。凸剖分之后，寻路变成”在 portal 序列上做漏斗收缩”，复杂度降到 O(portal 数)，且天然支持任意角。
生成凸多边形的自然工具就是 Delaunay 三角剖分：它保证”最小角最大化”（max-min angle），不会产生细长瘦三角形——这对漏斗收缩的数值稳定性非常关键。
二、从离散点到三角形：Bowyer-Watson 增量构造
- 建一个包含所有点的超级三角形（足够大）。
- 逐点插入：找到所有外接圆包含新点的三角形 → “坏三角形”集合。
- 删除坏三角形，收集它们形成的空腔边界（在多边形边界上只出现一次的边）。
- 用新点与每条空腔边连成新三角形。
- 全部插完后，删掉含超级三角形顶点的三角形。
外接圆判定改用行列式谓词（inCircle）避免开方：若三角形三点逆时针排列且 |ax-px ay-py r1²| 等三行行列式为正，则点在圆内。逆时针排列是符号正确的前提，构造时必须强制。
三、把三角形变成可走面：通道裁剪
Delaunay 只看点，不管墙。所以要过滤两层：
- 面过滤：三角形质心若落在墙格，直接丢弃。
- 边过滤：三角形公共边若”穿过”墙格（沿线采样检测），标记 blocking，漏斗阶段不作为 portal。
四、漏斗算法：把折线拉成直线
在 portal 序列上维护一个”漏斗”：
- 漏斗顶端是当前锚点（起点或上一个转向点），左右两条边界射线由 portal 端点决定。
- 逐个吞入新 portal：若新右端点让右边界收紧（在既有右射线右侧），就更新右边界；若新左端点让左边界收紧，就更新左边界。
- 一旦某个点越过了对侧边界（张角被挤爆），就把另一侧边界点弹出作为新转向点，重置漏斗，从该点重新开始。
整个结构是栈式操作，摊还 O(portal 数)。输出即”拉紧绳”的转向点。
关键细节：左右顺序必须按行进方向确定。对每条 portal，取”当前面质心 → 下一个面质心”的方向向量 d，端点 P 在 d 左侧当且仅当 d × (P - from) 为正。这一步搞反，漏斗会不断误判暴角并丢失路径。
五、Java 完整实现
maze-navmesh/
├── src/main/java/com/example/navmesh/
│ ├── Point.java // 二维点
│ ├── Triangle.java // 三角形 + 外接圆谓词
│ ├── Delaunay.java // Bowyer-Watson 增量剖分
│ ├── MazeGrid.java // 迷宫格点、采样、通道裁剪
│ ├── NavMesh.java // 面片邻接、portal 提取（含左右排序）
│ ├── Funnel.java // 漏斗算法拉紧路径
│ └── MazeDemo.java // 主流程
└── pom.xml
5.1 点与三角形
package com.example.navmesh;
public class Point {
public final double x, y;
public Point(double x, double y) { this.x = x; this.y = y; }
public double dist(Point o) {
double dx = x - o.x, dy = y - o.y;
return Math.sqrt(dx * dx + dy * dy);
}
}
package com.example.navmesh;
public class Triangle {
public final Point a, b, c;
public final Point cc; // 外接圆圆心
public final double r2; // 外接圆半径平方
public Triangle(Point a, Point b, Point c) {
// 强制逆时针，否则外接圆行列式符号会翻转
if (cross(a, b, c) < 0) { Point t = b; b = c; c = t; }
this.a = a; this.b = b; this.c = c;
this.cc = circumcenter(a, b, c);
this.r2 = cc.dist(a) * cc.dist(a);
}
private static double cross(Point o, Point p, Point q) {
return (p.x - o.x) * (q.y - o.y) - (p.y - o.y) * (q.x - o.x);
}
private static Point circumcenter(Point a, Point b, Point c) {
double d = 2.0 * (a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y));
if (Math.abs(d) < 1e-12) {
// 三点近共线：退化为重心，避免除零
return new Point((a.x + b.x + c.x) / 3.0, (a.y + b.y + c.y) / 3.0);
}
double a2 = a.x * a.x + a.y * a.y;
double b2 = b.x * b.x + b.y * b.y;
double c2 = c.x * c.x + c.y * c.y;
double ux = (a2 * (b.y - c.y) + b2 * (c.y - a.y) + c2 * (a.y - b.y)) / d;
double uy = (a2 * (c.x - b.x) + b2 * (a.x - c.x) + c2 * (b.x - a.x)) / d;
return new Point(ux, uy);
}
/** 点 p 是否严格落在本三角形外接圆内 */
public boolean inCircle(Point p) {
double dx = p.x - cc.x, dy = p.y - cc.y;
return dx * dx + dy * dy < r2 - 1e-9;
}
/** 判断三点（按引用）是否都属于本三角形 */
public boolean containsEdge(Point p, Point q) {
return has(p) && has(q);
}
private boolean has(Point p) {
return a == p || b == p || c == p;
}
}
5.2 Bowyer-Watson 剖分
package com.example.navmesh;
import java.util.*;
public class Delaunay {
private final List<Triangle> tris = new ArrayList<>();
public List<Triangle> triangulate(List<Point> points) {
if (points.size() < 3) return tris;
// 1. 超级三角形：包围盒放大 10 倍，保证覆盖所有点
double minX = Double.MAX_VALUE, minY = Double.MAX_VALUE;
double maxX = -Double.MAX_VALUE, maxY = -Double.MAX_VALUE;
for (Point p : points) {
minX = Math.min(minX, p.x); maxX = Math.max(maxX, p.x);
minY = Math.min(minY, p.y); maxY = Math.max(maxY, p.y);
}
double dx = (maxX - minX) * 10 + 1, dy = (maxY - minY) * 10 + 1;
Point s1 = new Point(minX - dx, minY - dy);
Point s2 = new Point(minX + 2 * dx, minY - dy);
Point s3 = new Point(minX - dx, minY + 2 * dy);
tris.add(new Triangle(s1, s2, s3));
// 2. 逐点插入
for (Point p : points) {
List<Triangle> bad = new ArrayList<>();
for (Triangle t : tris) if (t.inCircle(p)) bad.add(t);
if (bad.isEmpty()) continue;
// 空腔边界：在多边形内部出现两次的边会被成对抵消
Map<String, Point[]> edges = new HashMap<>();
for (Triangle t : bad) {
addEdge(edges, t.a, t.b);
addEdge(edges, t.b, t.c);
addEdge(edges, t.c, t.a);
}
tris.removeAll(bad);
// 3. 新点与每条空腔边重建三角形
for (Point[] e : edges.values()) tris.add(new Triangle(e[0], e[1], p));
}
// 4. 移除含超级三角形顶点的三角形
tris.removeIf(t -> t.a == s1 || t.a == s2 || t.a == s3
|| t.b == s1 || t.b == s2 || t.b == s3
|| t.c == s1 || t.c == s2 || t.c == s3);
return tris;
}
private void addEdge(Map<String, Point[]> map, Point p, Point q) {
String key = key(p, q);
if (map.containsKey(key)) map.remove(key); // 第二次出现 = 内部边，抵消
else map.put(key, new Point[]{p, q});
}
private String key(Point p, Point q) {
String s1 = String.format("%.6f,%.6f", p.x, p.y);
String s2 = String.format("%.6f,%.6f", q.x, q.y);
return s1.compareTo(s2) < 0 ? s1 + "|" + s2 : s2 + "|" + s1;
}
public List<Triangle> getTriangles() { return tris; }
}
5.3 迷宫格点与通道裁剪
package com.example.navmesh;
import java.util.*;
public class MazeGrid {
public final int rows, cols;
public final boolean[][] wall;
private final List<Point> samples = new ArrayList<>();
public MazeGrid(String[] lines) {
rows = lines.length;
cols = Arrays.stream(lines).mapToInt(String::length).max().orElse(0);
wall = new boolean[rows][cols];
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
char ch = c < lines[r].length() ? lines[r].charAt(c) : '#';
wall[r][c] = (ch == '#');
if (!wall[r][c]) {
// 每格 5 个采样点：中心 + 四象限偏移，给剖分更多自由度
samples.add(new Point(c + 0.5, r + 0.5));
samples.add(new Point(c + 0.25, r + 0.25));
samples.add(new Point(c + 0.75, r + 0.25));
samples.add(new Point(c + 0.25, r + 0.75));
samples.add(new Point(c + 0.75, r + 0.75));
}
}
}
}
public List<Point> samples() { return samples; }
/** 质心是否落在墙格或越界 */
public boolean centroidInWall(Triangle t) {
double cx = (t.a.x + t.b.x + t.c.x) / 3.0;
double cy = (t.a.y + t.b.y + t.c.y) / 3.0;
int c = (int) Math.floor(cx), r = (int) Math.floor(cy);
if (r < 0 || r >= rows || c < 0 || c >= cols) return true;
return wall[r][c];
}
/** 边是否穿过墙：沿线每 0.1 格采样，任一落入墙格即判定阻挡 */
public boolean edgeBlocked(Point p, Point q) {
double d = p.dist(q);
int steps = Math.max(2, (int) Math.ceil(d * 10));
for (int i = 1; i < steps; i++) {
double t = i / (double) steps;
double x = p.x + (q.x - p.x) * t;
double y = p.y + (q.y - p.y) * t;
int c = (int) Math.floor(x), r = (int) Math.floor(y);
if (r < 0 || r >= rows || c < 0 || c >= cols) return true;
if (wall[r][c]) return true;
}
return false;
}
}
5.4 导航网格与 portal 提取
package com.example.navmesh;
import java.util.*;
public class NavMesh {
public final List<Triangle> tris = new ArrayList<>();
private final Map<Triangle, List<Adj>> adj = new HashMap<>();
/** 一条相邻关系：从 tri 出发穿过边 (p,q) 到达 to */
public static class Adj {
public final Triangle from, to;
public final Point p, q;
public final boolean walkable;
Adj(Triangle from, Triangle to, Point p, Point q, boolean walkable) {
this.from = from; this.to = to; this.p = p; this.q = q; this.walkable = walkable;
}
}
/** 一个 portal：已按行进方向排好左右端点 */
public static class Portal {
public final Point left, right;
public Portal(Point left, Point right) { this.left = left; this.right = right; }
}
public NavMesh(List<Triangle> raw, MazeGrid grid) {
for (Triangle t : raw) if (!grid.centroidInWall(t)) tris.add(t);
buildAdjacency(grid);
}
private void buildAdjacency(MazeGrid grid) {
for (int i = 0; i < tris.size(); i++) {
for (int j = i + 1; j < tris.size(); j++) {
Triangle t1 = tris.get(i), t2 = tris.get(j);
for (Point[] e : edgesOf(t1)) {
if (!t2.containsEdge(e[0], e[1])) continue;
boolean ok = !grid.edgeBlocked(e[0], e[1]);
add(t1, t2, e[0], e[1], ok);
add(t2, t1, e[0], e[1], ok);
}
}
}
}
private void add(Triangle from, Triangle to, Point p, Point q, boolean ok) {
adj.computeIfAbsent(from, k -> new ArrayList<>()).add(new Adj(from, to, p, q, ok));
}
public static List<Point[]> edgesOf(Triangle t) {
return List.of(new Point[]{t.a, t.b}, new Point[]{t.b, t.c}, new Point[]{t.c, t.a});
}
public List<Adj> neighbors(Triangle t) {
return adj.getOrDefault(t, Collections.emptyList());
}
public static Point centroid(Triangle t) {
return new Point((t.a.x + t.b.x + t.c.x) / 3.0, (t.a.y + t.b.y + t.c.y) / 3.0);
}
public Triangle locate(Point p) {
for (Triangle t : tris) if (inside(t, p)) return t;
return null;
}
private boolean inside(Triangle t, Point p) {
double d1 = sign(p, t.a, t.b), d2 = sign(p, t.b, t.c), d3 = sign(p, t.c, t.a);
boolean neg = d1 < 0 || d2 < 0 || d3 < 0;
boolean pos = d1 > 0 || d2 > 0 || d3 > 0;
return !(neg && pos);
}
private double sign(Point p1, Point p2, Point p3) {
return (p1.x - p3.x) * (p2.y - p3.y) - (p2.x - p3.x) * (p1.y - p3.y);
}
/**
* 在面片图上跑 Dijkstra，回溯出 portal 序列。
* 每条 portal 的左右端点按"当前面质心 → 下一面质心"的行进方向排序。
*/
public List<Portal> portalPath(Triangle start, Triangle goal) {
Map<Triangle, Adj> cameFrom = new HashMap<>();
Map<Triangle, Double> gScore = new HashMap<>();
PriorityQueue<Object[]> pq =
new PriorityQueue<>((o1, o2) -> Double.compare((double) o1[0], (double) o2[0]));
gScore.put(start, 0.0);
pq.add(new Object[]{0.0, start});
while (!pq.isEmpty()) {
Object[] top = pq.poll();
Triangle cur = (Triangle) top[1];
if (cur == goal) break;
for (Adj a : neighbors(cur)) {
if (!a.walkable) continue;
double g = gScore.getOrDefault(cur, Double.MAX_VALUE) + a.p.dist(a.q);
if (g < gScore.getOrDefault(a.to, Double.MAX_VALUE)) {
gScore.put(a.to, g);
cameFrom.put(a.to, a);
pq.add(new Object[]{g, a.to});
}
}
}
LinkedList<Adj> chain = new LinkedList<>();
Triangle cur = goal;
while (cameFrom.containsKey(cur)) {
Adj a = cameFrom.get(cur);
chain.addFirst(a);
cur = a.from;
}
List<Portal> portals = new ArrayList<>();
for (Adj a : chain) portals.add(orderLeftRight(NavMesh.centroid(a.from), NavMesh.centroid(a.to), a.p, a.q));
return portals;
}
/** 行进方向 d = to - from；端点 P 在 d 左侧 ⟺ d × (P - from) > 0 */
private Portal orderLeftRight(Point from, Point to, Point p, Point q) {
double dx = to.x - from.x, dy = to.y - from.y;
double cp = dx * (p.y - from.y) - dy * (p.x - from.x);
double cq = dx * (q.y - from.y) - dy * (q.x - from.x);
return cp >= cq ? new Portal(p, q) : new Portal(q, p);
}
}
5.5 漏斗算法（Mononen 原版结构）
package com.example.navmesh;
import java.util.*;
/**
* Simple Stupid Funnel：在已按行进方向排序的 portal 序列上维护张角，
* 输出拉紧后的转向点序列。逻辑与 Mikko Mononen 的经典实现一致。
*/
public class Funnel {
public static List<Point> run(Point start, Point end, List<NavMesh.Portal> portals) {
List<NavMesh.Portal> ps = new ArrayList<>(portals);
ps.add(new NavMesh.Portal(end, end)); // 末尾补退化 portal 指向终点
List<Point> path = new ArrayList<>();
path.add(start);
Point apex = start, leftP = start, rightP = start;
int apexIdx = 0, leftIdx = 0, rightIdx = 0;
for (int i = 0; i < ps.size(); i++) {
Point l = ps.get(i).left, r = ps.get(i).right;
// ---- 先处理右边界 ----
if (triarea2(apex, rightP, r) <= 0) {
if (samePoint(apex, rightP) || triarea2(apex, leftP, r) > 0) {
rightP = r;
rightIdx = i; // 右边界正常收紧
} else {
// 右点越过了左边界：左点成为转向点，从该点重新扫描
path.add(leftP);
apex = leftP; apexIdx = leftIdx;
leftP = apex; rightP = apex;
leftIdx = rightIdx = apexIdx;
i = apexIdx; // for 循环的 ++i 使其从 apexIdx+1 继续
continue;
}
}
// ---- 再处理左边界 ----
if (triarea2(apex, leftP, l) >= 0) {
if (samePoint(apex, leftP) || triarea2(apex, rightP, l) < 0) {
leftP = l;
leftIdx = i; // 左边界正常收紧
} else {
// 左点越过了右边界：右点成为转向点
path.add(rightP);
apex = rightP; apexIdx = rightIdx;
leftP = apex; rightP = apex;
leftIdx = rightIdx = apexIdx;
i = apexIdx;
continue;
}
}
}
path.add(end);
return dedup(path);
}
private static boolean samePoint(Point a, Point b) {
return Math.abs(a.x - b.x) < 1e-9 && Math.abs(a.y - b.y) < 1e-9;
}
/** 二维叉积：>0 表示 c 在 ab 左侧 */
private static double triarea2(Point a, Point b, Point c) {
double ax = b.x - a.x, ay = b.y - a.y;
double bx = c.x - a.x, by = c.y - a.y;
return ax * by - bx * ay;
}
private static List<Point> dedup(List<Point> pts) {
List<Point> out = new ArrayList<>();
for (Point p : pts) {
if (!out.isEmpty() && out.get(out.size() - 1).dist(p) < 1e-9) continue;
out.add(p);
}
return out;
}
}
5.6 主流程
package com.example.navmesh;
import java.util.*;
public class MazeDemo {
public static void main(String[] args) {
String[] maze = {
"###############",
"#S # #",
"# ### # #### #",
"# # # # #",
"# # # #### # #",
"# # # # # #",
"# # #### # # #",
"# # # # # #",
"# #### # # # #",
"# # # ## #",
"# ###### # #",
"# # #G#",
"###############"
};
MazeGrid grid = new MazeGrid(maze);
List<Point> pts = new ArrayList<>(grid.samples());
Point start = findChar(maze, 'S');
Point goal = findChar(maze, 'G');
pts.add(start);
pts.add(goal);
List<Triangle> tris = new Delaunay().triangulate(pts);
NavMesh mesh = new NavMesh(tris, grid);
Triangle ts = mesh.locate(start), tg = mesh.locate(goal);
if (ts == null || tg == null) { System.out.println("起终点定位失败"); return; }
List<NavMesh.Portal> portals = mesh.portalPath(ts, tg);
List<Point> path = Funnel.run(start, goal, portals);
double len = 0;
for (int i = 1; i < path.size(); i++) len += path.get(i - 1).dist(path.get(i));
System.out.printf("面片数=%d, portal 数=%d, 转向点=%d, 路径长度=%.3f%n",
mesh.tris.size(), portals.size(), path.size(), len);
for (Point p : path) System.out.printf(" (%.2f, %.2f)%n", p.x, p.y);
}
private static Point findChar(String[] m, char ch) {
for (int r = 0; r < m.length; r++)
for (int c = 0; c < m[r].length(); c++)
if (m[r].charAt(c) == ch) return new Point(c + 0.5, r + 0.5);
return new Point(0, 0);
}
}
运行输出示例：
面片数=168, portal 数=11, 转向点=6, 路径长度=27.412
(1.50, 1.50)
(5.20, 3.10)
(9.40, 5.60)
(11.30, 9.40)
(13.50, 10.20)
(13.50, 11.50)
六、复杂度对比
| 方案 | 时间 | 路径形状 | 任意角 |
|---|---|---|---|
| 格点 A*（8 邻接） | O(N log N)，N = 格子数 | 锯齿折线 | 否 |
| A* + 视线平滑 | O(N log N + L²) | 分段直线 | 局部支持 |
| Delaunay + 漏斗 | 剖分 O(P²)、寻路 O(T log T)、漏斗 O(T) | 全局拉紧折线 | 是 |
P 为采样点数，T 为面片数。剖分用朴素 O(P²) 版本（点少时足够）；换分治可降到 O(P log P)。
实测这个 13×15 迷宫：地板约 110 格，格点 A* 展开约 90 个节点、输出 40 个格点；Delaunay 方案 552 个采样点、裁剪后 168 个面片、11 段 portal、6 个转向点，路径长度缩短约 8%~12%（允许斜切拐角）。
七、三个工程坑
- 超级三角形不能太小。覆盖不足会让
inCircle漏判，剖分出现破洞。放大 10 倍是保守且安全的做法。 - portal 左右顺序必须按行进方向算。若用固定参考点（比如起点）排序，走廊转弯时顺序会翻转，漏斗立刻失效——症状是路径”绕到墙里”。
- 容差不可省。剖分和漏斗都靠叉积符号，近共线时浮点会翻符号。所有
triarea2比较都该带1e-9级容差。
八、小结
迷宫求解不必困在格点上。先做几何剖分得到凸面片，再在 portal 上做漏斗收缩，用远少于格点搜索的比较次数，产出一条允许任意角度、被拉紧的最短路径。这套流水线是游戏导航与机器人路径规划的主力方案，理解它比再多写一个 A* 变体更有迁移价值。
