5.2 A* 与导航网格
5.1 的 Mover 解决了「怎么走」，但它只会朝一个点直线前进。一旦玩家点向地图另一端、中间隔着城墙与河道，服务器就得先算出一条绕开障碍的路径，再把它拆成 Mover 能消费的目标点序列。这就是寻路。
寻路有两种主流表达。一种是网格 A*：把地图切成方格，不可走的格子标成阻挡，在格子上求最短路径。它实现简单、天然支持动态障碍（关一扇门就是改一个 bool），缺点是路径贴着格子走，锯齿感明显，斜向移动还不许切角。另一种是导航网格（navmesh）：把可行走区域拼成一张由凸多边形组成的图，先在多边形图上找通道，再用拉绳算法把通道拉成直线。它生成的路径短而自然，代价是建图复杂、动态障碍难处理。本节两条都从零写一遍，全部是 L1。
网格 A*：一个能跑的最短路径
A* 的骨架是「开放集 + 代价表」。开放集里按 f = g + h 排序，g 是从起点走过来的实际代价，h 是到终点的估计代价（启发函数）。每一轮弹出 f 最小的格子，若它就是终点则回溯出路径，否则把它的邻居压进开放集。两处细节决定它是否可用：
- 启发函数必须可采纳：
h不能高估真实代价，否则会丢最优解。八邻域下用 octile 距离（直走 1、斜走 √2），比欧氏距离更紧、比曼哈顿距离更准。 - 对角移动禁止切角：从
(x,y)斜穿到(x+1,y+1)，必须先确认(x+1,y)与(x,y+1)两个正交格都可行走，否则角色会从两堵墙的夹角里「切」过去。
下面这段是 L1，go test ./internal/move/ 可以直接跑：
// file: internal/move/astar.go
// tier: L1
// verify: go test ./internal/move/
package move
import (
"container/heap"
"math"
)
// Grid 是寻路用的可行走网格：Blocked[y*W+x] 为 true 表示该格不可通行。
// 网格坐标的格边长就是 GridSize，与 AOI 口径一致。
type Grid struct {
W, H int
Blocked []bool
}
// NewGrid 创建全可行走的 w×h 网格。
func NewGrid(w, h int) *Grid {
return &Grid{W: w, H: h, Blocked: make([]bool, w*h)}
}
func (g *Grid) In(x, y int) bool { return x >= 0 && y >= 0 && x < g.W && y < g.H }
// Walkable 报告格 (x,y) 是否可通行；越界一律视为不可走。
func (g *Grid) Walkable(x, y int) bool {
return g.In(x, y) && !g.Blocked[y*g.W+x]
}
// SetBlocked 设置格的阻挡状态（障碍、地形、动态物件都写这里）。
func (g *Grid) SetBlocked(x, y int, b bool) {
if g.In(x, y) {
g.Blocked[y*g.W+x] = b
}
}
// dirs8 是八邻域方向。
var dirs8 = [8][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}}
// octile 是八邻域的启发距离：直走代价 1、斜走代价 √2，可采纳且比欧氏更紧。
func octile(a, b [2]int) float64 {
dx := math.Abs(float64(a[0] - b[0]))
dy := math.Abs(float64(a[1] - b[1]))
return (dx + dy) + (math.Sqrt2-2)*math.Min(dx, dy)
}
// item 是 A* 开放集里的一个格子。
type item struct {
x, y int
f float64
}
// pq 是按 f 值排序的最小堆。
type pq []*item
func (p pq) Len() int { return len(p) }
func (p pq) Less(i, j int) bool { return p[i].f < p[j].f }
func (p pq) Swap(i, j int) { p[i], p[j] = p[j], p[i] }
func (p *pq) Push(v any) { *p = append(*p, v.(*item)) }
func (p *pq) Pop() any {
old := *p
n := len(old)
it := old[n-1]
old[n-1] = nil
*p = old[:n-1]
return it
}
// FindPath 用 A* 在网格上求一条从 start 到 goal 的格子路径（含两端）。
// 8 邻域移动、对角代价 √2、启发函数用 octile，保证找到的是最短路径。
func (g *Grid) FindPath(start, goal [2]int) [][2]int {
if !g.Walkable(start[0], start[1]) || !g.Walkable(goal[0], goal[1]) {
return nil
}
gScore := map[[2]int]float64{start: 0}
came := make(map[[2]int][2]int)
closed := make(map[[2]int]bool)
open := &pq{}
heap.Init(open)
heap.Push(open, &item{start[0], start[1], octile(start, goal)})
for open.Len() > 0 {
cur := heap.Pop(open).(*item)
c := [2]int{cur.x, cur.y}
if c == goal {
return reconstruct(came, c)
}
if closed[c] {
continue
}
closed[c] = true
for _, d := range dirs8 {
nx, ny := cur.x+d[0], cur.y+d[1]
if !g.Walkable(nx, ny) {
continue
}
// 对角穿越要求两侧正交格都可行走，否则角色会「切角」穿墙。
if d[0] != 0 && d[1] != 0 &&
(!g.Walkable(cur.x+d[0], cur.y) || !g.Walkable(cur.x, cur.y+d[1])) {
continue
}
n := [2]int{nx, ny}
step := 1.0
if d[0] != 0 && d[1] != 0 {
step = math.Sqrt2
}
tentative := gScore[c] + step
if old, ok := gScore[n]; ok && tentative >= old {
continue
}
gScore[n] = tentative
came[n] = c
heap.Push(open, &item{nx, ny, tentative + octile(n, goal)})
}
}
return nil
}
// reconstruct 从 came 表回溯出路径。
func reconstruct(came map[[2]int][2]int, cur [2]int) [][2]int {
path := [][2]int{cur}
for {
prev, ok := came[cur]
if !ok {
break
}
path = append(path, prev)
cur = prev
}
// 反转成 start→goal。
for i, j := 0, len(path)-1; i < j; i, j = i+1, j-1 {
path[i], path[j] = path[j], path[i]
}
return path
}
gScore/came/closed 用 map 是为了代码短；代价是每次寻路都要重新分配，200×200 的图上一次寻路就有上万次分配。生产实现会把它们换成按格子索引的切片（gScore[y*W+x]），配合「访问版本号」数组避免每次清零。这一点在下面的基准里看得很清楚。
导航网格：把格子换成凸多边形
网格 A* 的路径贴着格子走，看着别扭；要它自然，就得用导航网格。做法是把可行走区域拆成一堆凸多边形，多边形之间共享边即相邻。寻路分两步：先在「多边形邻接图」上跑 A* 求出要穿过哪些多边形（结构与格子 A* 完全一样，只是节点从格子换成了多边形，启发函数用两个多边形中心的直线距离），再用拉绳算法（simple stupid funnel）把这条通道拉成直线段序列。真正有含金量的是拉绳：它维护一个「漏斗」，左右边界从起点出发逐个门（共享边）收紧；只要漏斗没被压反就说明能走直线，一旦某个门把它压反，就从对面那个顶点拐一下，把它作为路径点吐出来。
navmesh.go 里 Portals 负责把多边形路径翻译成一串门、Funnel 负责拉绳。下面是这两个函数的片段（完整文件在同一个已跑通的 internal/move 包里）：
// snippet: internal/move/navmesh.go（摘录：门与拉绳）
// Portal 是相邻两个多边形共享的一条边（两个端点）。
type Portal struct{ Left, Right Vec2 }
// Portals 把多边形路径翻译成一串「门」：每一对相邻多边形找共享边，
// 并按行进方向把两端分成左、右。朝向错了漏斗会算出反向路径。
func (m *NavMesh) Portals(polyPath []int) []Portal {
var out []Portal
for i := 0; i+1 < len(polyPath); i++ {
a, b := m.Polys[polyPath[i]], m.Polys[polyPath[i+1]]
p, ok := sharedEdge(a, b)
if !ok {
continue
}
// 行进方向 = a 中心 → b 中心；据此决定哪端在左。
dir := b.Center.Sub(a.Center)
if cross(dir, p.Left.Sub(a.Center)) > 0 {
out = append(out, p)
} else {
out = append(out, Portal{Left: p.Right, Right: p.Left})
}
}
return out
}
// triArea 是三角形 abc 的有向面积，正为逆时针（左转）。
func triArea(a, b, c Vec2) float64 {
return (b.X-a.X)*(c.Y-a.Y) - (c.X-a.X)*(b.Y-a.Y)
}
// Funnel 是「拉绳」算法：把穿门折线拉成绕过拐角的直线段序列。
// 它把 A* 的「贴着格子走」的锯齿路径变成角色真正会走的直线。
func Funnel(start Vec2, portals []Portal, goal Vec2) []Vec2 {
apex, left, right := start, start, start
apexIdx, leftIdx, rightIdx := 0, 0, 0
path := []Vec2{start} // 结果含起点
at := func(i int) (Vec2, Vec2) {
if i < len(portals) {
return portals[i].Left, portals[i].Right
}
return goal, goal
}
for i := 0; i <= len(portals); i++ {
l, r := at(i)
// 收紧右边界。
if triArea(apex, right, r) <= 0 {
if apex == right || triArea(apex, left, r) > 0 {
right = r
rightIdx = i
} else {
path = append(path, left)
apex, right = left, left
apexIdx = leftIdx
leftIdx, rightIdx = apexIdx, apexIdx
i = apexIdx
continue
}
}
// 收紧左边界。
if triArea(apex, left, l) >= 0 {
if apex == left || triArea(apex, right, l) < 0 {
left = l
leftIdx = i
} else {
path = append(path, right)
apex, left = right, right
apexIdx = rightIdx
leftIdx, rightIdx = apexIdx, apexIdx
i = apexIdx
continue
}
}
}
path = append(path, goal)
return path
}
拉绳的核心是两次「收紧」：右边界被某个门的右端点收窄时，如果收窄后越过了左边界（triArea(apex, left, r) <= 0 且不构成合法三角），说明直线走不通，必须从 left 拐一下；左边界对称。path 初始化时就放入起点，最后补上终点，所以结果天然包含两端。测试里用一条直走廊验证「中间拐点被全部消掉、只剩起终点」，再用一个 L 形走廊验证拐角确实被拉出来。
基准：一次寻路要花多少
寻路是 CPU 密集操作，玩家点一下就得算一次，必须知道它有多贵。下面这段是 B 级基准，go test -bench 直接跑：
// file: internal/move/path_bench_test.go
// tier: B
// verify: go test -bench . ./internal/move/
package move
import (
"math/rand"
"testing"
)
func benchGrid() *Grid {
rng := rand.New(rand.NewSource(42))
g := NewGrid(200, 200)
for i := 0; i < g.W*g.H/5; i++ { // 20% 随机阻挡
g.SetBlocked(rng.Intn(g.W), rng.Intn(g.H), true)
}
g.SetBlocked(0, 0, false) // 保证起终点可走
g.SetBlocked(199, 199, false)
return g
}
func BenchmarkFindPath(b *testing.B) {
g := benchGrid()
b.ReportAllocs()
for i := 0; i < b.N; i++ {
if p := g.FindPath([2]int{0, 0}, [2]int{199, 199}); len(p) == 0 {
b.Fatal("未找到路径")
}
}
}
func BenchmarkStepAll(b *testing.B) {
w := NewWorld()
for i := 0; i < 10000; i++ {
m := NewMover(Vec2{float64(i), 0}, 5)
_ = m.Request(Vec2{float64(i) + 100, 0})
w.Movers[uint64(i)] = m
}
b.ReportAllocs()
b.ResetTimer()
for i := 0; i < b.N; i++ {
w.StepAll(TickSeconds)
}
}
func BenchmarkLineOfSight(b *testing.B) {
g := NewGrid(200, 200)
for y := 0; y < 200; y++ {
g.SetBlocked(100, y, true)
}
a := CellCenter(50, 50)
c := CellCenter(52, 52)
b.ReportAllocs()
b.ResetTimer()
for i := 0; i < b.N; i++ {
LineOfSight(g, a, c)
}
}
本节小结 / 实测结论
本机（Go 1.26.0，Apple M1 Pro）实跑结果：
$ go test ./internal/move/ -bench BenchmarkFindPath -benchtime=200x -run '^$'
BenchmarkFindPath-10 200 7289897 ns/op 3502165 B/op 17507 allocs/op
200×200、20% 随机阻挡的图上，跨图寻路单次约 7.3 毫秒、分配 3.5 MB。单次看着能接受，但如果有几百个怪物同时寻路，一帧就能把 CPU 打满——这就是为什么生产实现要用切片替掉 map、限制寻路频率、把长路径拆到多帧摊销。以上数字是同机相对量级，绝对数值不可移植。下一节回到 5.1 的 Mover：当客户端发来的落点本身不可信时，怎么把它拦下来。
阅读导航：上一节：5.1 服务器权威移动 · 下一节：5.3 移动校验与防穿墙 。
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。