《MMO 服务器开发》5.2 A* 与导航网格
上一节让角色会走,这一节让它知道往哪走。本节用 container/heap 从零实现八邻域 A*:对角代价根号二、octile 启发、禁止切角穿墙;再把「格子」换成凸多边形导航网格,用多边形邻接图 A* 求通道,最后用拉绳算法把锯齿路径拉成直线,并实测 200x200 网格的单次寻路开销。
tag
上一节让角色会走,这一节让它知道往哪走。本节用 container/heap 从零实现八邻域 A*:对角代价根号二、octile 启发、禁止切角穿墙;再把「格子」换成凸多边形导航网格,用多边形邻接图 A* 求通道,最后用拉绳算法把锯齿路径拉成直线,并实测 200x200 网格的单次寻路开销。
服务器权威移动是防作弊的地基:位置只能由服务器算,客户端只能提交「我要去哪」。本节从零写 internal/move 包的 Vec2 逻辑坐标与 Mover 状态机,用 20Hz 固定步长推进、到达即吸附不过冲,并只广播真正产生位移的实体,配 go test 验收终点精确与超距请求被拒。
把暴力扫描、九宫格、十字链表三种 AOI 放在同一批 5000 个玩家、同一张地图上实跑基准:九宫格查询约 890ns,十字链表约 4350ns 且移动慢得多,暴力扫描约 37500ns。再把平均兴趣集合 6.21 人换算成每帧出站消息,量化兴趣管理到底省下了多少带宽。
十字链表 AOI 给每个实体同时挂两条有序链表——一条按 X 升序、一条按 Y 升序,查询时两条「带」取交,不需要格边长这个参数。本节从零实现四指针节点、哨兵环链、O(1) 索引、带内取交查询,并与九宫格逐点比对证明语义一致,同时讲清它移动 O(n) 的代价。
九宫格 AOI 把连续地图切成 GridSize=8 的方格,玩家只关心自己所在格与相邻八格。本节用 aegis 的共享坐标类型从零实现格点哈希、O(1) 跨格移动、圆形半径过滤,以及把「谁进入/离开视野」翻译成 CmdAoiAdd 与 CmdAoiRemove 的 Watcher,并附一份 Java 21 对照实现。
同一张地图模板,落地方式却要分三六九等:野外和主城该共享分线,副本要一人一实例。本节从零写 internal/scene 的 LineManager 与 Router:分线按容量塞满一条开下一条,副本每次进入开独立实例,并用统一入口把两种落点收敛到一个 EnterWorld。全部 L1,go test 可直接跑。
地图模板是只读的,真正装玩家的是地图实例。本节从零写 internal/scene 的 InstanceManager:单调递增的 InstanceID、高 16 位实例号加低 48 位序号拼出的 EntityID、Active→Draining→Closed 状态机,以及把空置超时实例回收进对象池复用。L1 全绿,另附池化对照基准。
地图是场景逻辑的地基。本节从零写 internal/scene 的地图数据结构:一张 Width×Height 格网加一张阻挡位图描述静态地图,float64 逻辑坐标 Vec2 与客户端像素解耦,格边长固定 GridSize=8.0,并实现世界坐标与格号互转、可走判定与边界夹取。全部是 L1,go test 可直接跑。
实体散落在多个逻辑线程与场景里,核心问题是「谁有权写它」。本节实现单写者模型下的归属表(正向 + 反向双索引),再把跨运行时搬迁拆成冻结—传输—接管三段,用缓冲重放解决冻结期间在飞的消息,最后用一个 Router 固化分流规则,并用 go test 验证迁移幂等与消息不丢不重。
2.1 的立即 Despawn 不够用:创建要先登记再可见,销毁要先结算再回收。本节把实体生命周期拆成 None/Pending/Active/Dying/Dead 五态,用一张迁移表管住所有合法跳转,再把载荷接进对象池,最后用 go test 验证回收与复用真的发生。
实体、句柄、运行时是三个层次。本节从零定下 EntityID 的高 16 位场景号 + 低 48 位序号位布局,用代际计数解决销毁后序号复用带来的 ABA 问题,再实现一张 O(1) 校验的运行时表,并用 16 个 go test 用例把三种过期引用逐一跑出来。
站内已经有一大批游戏服务器架构文章,卷一又写完了网络内核,那这一卷到底写什么、不写什么?本节把三份内容的分工摊开讲清楚:站内 practice 架构文负责「应该怎么设计」,卷一负责「网络底座怎么写」,本卷负责「玩法系统从零实现并跑出数字」,并把这条边界编码成一张可查询的表。
上一节立了「一个状态只能有一个写者」,但现实里这条原则会被两种方式破坏:写者其实不止一个,以及写者写的是旧数据。它们对应两个最经典的事故——重复发奖与旧数据覆盖。本节先把两个事故的根因拆开,再推出版本单调与幂等键两条守卫,最后用一份能跑的 Go 代码把这两条守卫钉成断言。
卷一讲完网络内核的四层,这一卷换一个视角重新切一遍:从玩法系统的状态归属出发,回答 gateway / logic / scene / data 各自该持有什么状态。本节先把「谁写状态,谁就是那一层」立成第一原则,再把每条命令归到唯一的处理层、把每份状态归到唯一的写入者,最后用一份能跑的 Go 代码把这两条归属规则钉成断言。
审计日志回答的是「谁在什么时候对什么做了什么」,而它本身也是攻击目标。本节把 TaskHub 的审计落成防篡改的哈希链:本机真实跑通写入 3 条记录校验通过,再改写第 2 行结果字段,校验立刻报「第 2 行内容被篡改」;并给出审计与业务日志的分离、保留期与合规映射。
加密的目标是「数据即使被截获或拖库也读不出」。本节把 TaskHub 的传输与存储两条链路都落成可运行代码:用真实握手演示强制 TLS 1.3 如何拒绝只支持 1.2 的客户端,用 AES-GCM 把 32 字节明文加密成 60 字节并验证篡改必然失败,用 bcrypt 演示同口令两次哈希不同、校验正确。
多租户系统里,一个没校验的查询参数就可能让 A 租户读到 B 租户的数据。本节用真实 Postgres 容器跑通两段对照实验:字符串拼接的查询被注入读到 2 行(越权),参数化查询命中 0 行(挡下);再用 html/template 演示输出转义,并给出白名单校验、命令注入与路径穿越的防护清单。
把 TaskAPI 真正部署到服务器:写 systemd 单元托管进程、用软链与健康门控的脚本切换版本、把第 12 章的优雅关闭接到 SIGTERM 上,并实测「发信号后排空在途请求再退出」的完整时序,最后讨论多实例滚动与套接字传递两种零停机思路。
把 TaskAPI 打成最小 Docker 镜像:写多阶段 Dockerfile,构建阶段用 golang:1.27-alpine 编译静态二进制、运行阶段用 alpine 只装产物,配 .dockerignore 与层缓存,用非 root 用户运行,并实测镜像体积、容器日志与端点响应。
把 TaskAPI 编译成能上服务器的产物:用 GOOS/GOARCH 在 Mac 上交叉编译出 Linux 二进制、用 CGO_ENABLED=0 做静态链接、用 -trimpath 与 -ldflags 注入版本号并瘦身,再用 file 与 go version -m 核对产物,最后写成可复用的构建脚本。