大世界行军优化：从寻路算法到服务器架构的全面实践#

1
大世界行军系统面临的挑战
2
├── 寻路挑战
3
│   ├── 长距离寻路（跨州郡，路径长度可达数千格）
4
│   ├── 动态阻挡（玩家主城、要塞、公会关系）
5
│   ├── 高并发寻路请求（每秒数千次）
6
│   └── 路径质量 vs 性能的平衡
7
├── 网络同步挑战
8
│   ├── 行军状态同步（位置、速度、方向）
9
│   ├── 视野内海量对象同步
10
│   ├── 带宽限制（移动网络）
11
│   └── 延迟与卡顿处理
12
├── 视野管理挑战
13
│   ├── 视野内对象筛选
14
│   ├── 流量洪峰（视野切换时）
15
│   └── 优先级裁减
16
└── 服务器架构挑战
17
    ├── 单核无法承载
18
    ├── 多线程/多进程拆分
19
    └── 开发效率 vs 性能的平衡

1
六边形网格坐标系统（立方坐标）：
2

3
           (0,-1,+1)  (+1,-1,0)
4
               / \     / \
5
              /   \   /   \
6
    (-1,0,+1) \   / \   / (+1,0,-1)
7
               \ /   \ /
8
    (-1,+1,0) --+-- (0,0,0) --+-- (+1,+1,-1)
9
               / \   / \
10
    (0,+1,-1) \   / \   / (0,-1,+1)
11
               \ /   \ /
12
                +-----+

1
// 客户端计算路径，发送给服务器校验
2
public class ClientPathfinding
3
{
4
    List<HexCell> FindPath(HexCell start, HexCell end)
5
    {
6
        // 使用 A* 在客户端计算
7
        var path = AStarPathfinding.Find(start, end);
8
        // 发送路径给服务器
9
        SendPathToServer(path);
10
        return path;
11
    }
12
}

1
// 服务器计算路径，返回给客户端
2
func (s *PathfindingService) FindPath(req *PathRequest) (*PathResponse, error) {
3
    // 服务器拥有完整静态+动态数据
4
    path := s.engine.FindPath(req.Start, req.End, req.PlayerId)
5
    return &PathResponse{Path: path}, nil
6
}

1
前端寻路（短距离/预览）  +  后端寻路（长距离/权威）
2
         │                        │
3
         ▼                        ▼
4
   客户端展示路径            服务器计算权威路径
5
         │                        │
6
         └────────┬───────────────┘
7
                  ▼
8
         路径校验 + 行军模拟

1
层次结构：
2

3
Level 2 (大区域层): 州 → 郡 → 县
4
    ┌───────┬───────┐
5
    │ 州 A  │ 州 B  │
6
    │   ────┼───    │
7
    │ 州 C  │ 州 D  │
8
    └───────┴───────┘
9

10
Level 1 (关隘层): 区域之间的连接点
11
    州A ──[关隘A]── 州B
12
    州A ──[码头B]── 州C
13

14
Level 0 (地格层): 精细的六边形网格
15
    每个格子是一个节点

1
1. 高层抽象寻路（Level 2）
2
   - 将起点和目标点映射到对应的大区域
3
   - 在大区域图上用 A* 找到区域序列
4
   - 得到：州A → 关隘X → 州B → 码头Y → 州C
5

6
2. 中层关隘寻路（Level 1）
7
   - 在每个区域内部，找到到达关隘的路径
8
   - 区域入口 → 关隘 → 区域出口
9

10
3. 低层精细寻路（Level 0）
11
   - 仅在起点和终点所在的局部区域做精细寻路
12
   - 起点 → 区域出口 （短距离）
13
   - 区域入口 → 终点 （短距离）
14

15
4. 路径拼接
16
   - 将三段路径拼接为完整路径

1
class HierarchicalPathfinder:
2
    def __init__(self, map_data):
3
        self.region_graph = self.build_region_graph()  # 大区域图
4
        self.gateway_graph = self.build_gateway_graph()  # 关隘图
5
        self.local_grid = map_data  # 精细网格
6

7
    def find_path(self, start, end):
8
        # Step 1: 高层抽象
9
        start_region = self.get_region(start)
10
        end_region = self.get_region(end)
11

12
        if start_region == end_region:
13
            # 同区域，直接精细寻路
14
            return self.local_astar(start, end)
15

16
        region_path = self.region_astar(start_region, end_region)
17

18
        # Step 2: 拼接路径
19
        full_path = []
20
        current_pos = start
21

22
        for i, region in enumerate(region_path):
23
            if i == len(region_path) - 1:
24
                # 最后一个区域，寻路到终点
25
                entry = self.get_region_entry(region, region_path[i-1])
26
                segment = self.local_astar(entry, end)
27
            else:
28
                # 找到去下一个区域的出口
29
                exit_gateway = self.get_gateway(region, region_path[i+1])
30
                segment = self.local_astar(current_pos, exit_gateway)
31
                current_pos = exit_gateway
32

33
            full_path.extend(segment)
34

35
        return full_path

1
// 数据结构设计
2
type MapData struct {
3
    // 静态数据（不变，可以预加载到内存）
4
    StaticObstacles  []HexCoord   // 山、水等永久障碍
5
    GatewayGraph     *GatewayGraph // 关隘、码头等固定连接点
6

7
    // 动态数据（频繁变化）
8
    DynamicObstacles sync.Map     // 玩家建筑等动态阻挡
9
    AllianceRelations map[int64]int64 // 公会关系
10
}
11

12
// 阻挡查询时合并静态和动态数据
13
func (m *MapData) IsBlocked(coord HexCoord, playerID int64) bool {
14
    // 静态阻挡
15
    if m.StaticObstacles.Contains(coord) {
16
        return true
17
    }
18

19
    // 动态阻挡 - 检查是否有玩家建筑
20
    if building, ok := m.DynamicObstacles.Load(coord); ok {
21
        b := building.(*Building)
22
        // 同公会/联盟可通行
23
        if m.AllianceRelations[playerID] == b.AllianceID {
24
            return false
25
        }
26
        return true
27
    }
28

29
    return false
30
}

1
行军途中遇到新建阻挡：
2
┌──────────────────────────────────────────┐
3
│  原路径: A ──→ B ──→ C ──→ D ──→ E      │
4
│                     ↑                    │
5
│              在此处出现新阻挡             │
6
│                                          │
7
│  处理策略：                               │
8
│  1. 从当前位置到 C 的路径不变             │
9
│  2. 从 C 开始重新寻路到终点 E             │
10
│  3. 拼接新路径：A→B→C→F→G→E              │
11
│  4. 通知客户端路径更新                    │
12
└──────────────────────────────────────────┘

1
短距离寻路（< 100 格）: JPS / A*
2
中距离寻路（100-500 格）: 双向 A*
3
长距离寻路（> 500 格）: 分层寻路 + 预计算关键路径

1
// 行军数据结构（服务器端）
2
type MarchEvent struct {
3
    MarchID     int64          // 行军唯一 ID
4
    OwnerID     int64          // 所属玩家
5
    ArmyID      int64          // 关联的部队 ID
6
    Path        []HexCoord     // 完整路径（坐标序列）
7
    StartTime   time.Time      // 出发时间戳
8
    Speed       float64        // 行军速度（格/秒）
9
    TargetType  MarchTargetType // 目标类型：攻击/采集/回城
10
    TargetID    int64          // 目标 ID
11
    CurrentPos  HexCoord       // 当前位置（服务器权威）
12
    State       MarchState     // 行军/战斗/返回/完成
13
}
14

15
// 行军状态
16
type MarchState int
17
const (
18
    MarchMoving   MarchState = iota // 正在行军
19
    MarchFighting                    // 战斗中
20
    MarchReturning                   // 返回中
21
    MarchCompleted                   // 已完成
22
)

1
行军 (March)  ←→  部队 (Army)
2
  轻量对象           重量对象
3
  - 路径              - 英雄/士兵
4
  - 时间戳            - 属性/装备
5
  - 速度              - 技能
6
  - 状态              - 战斗数据
7

8
到达目的地后，March 对象被删除
9
Army 对象进入战斗/采集状态

1
服务器端逻辑：
2
┌─────────────────────────────────────────────────────┐
3
│ 1. 行军开始时，服务器计算完整路径和时间表           │
4
│    Path: [A, B, C, D, E, F]                        │
5
│    Timeline:                                        │
6
│      t=0s    到达 A (起点)                          │
7
│      t=5s    到达 B                                │
8
│      t=12s   到达 C                                │
9
│      t=18s   到达 D                                │
10
│      t=25s   到达 E                                │
11
│      t=30s   到达 F (终点)                          │
12
│                                                     │
13
│ 2. 服务器只同步：                                    │
14
│    - 当前路径段索引                                 │
15
│    - 段内进度 (0.0 ~ 1.0)                           │
16
│    - 行军速度                                        │
17
│                                                     │
18
│ 3. 客户端根据时间戳推算当前位置：                    │
19
│    currentPos = lerp(path[i], path[i+1], progress)  │
20
└─────────────────────────────────────────────────────┘

1
public class MarchVisualizer : MonoBehaviour
2
{
3
    private MarchData marchData;
4
    private float lastSyncTime;
5

6
    // 服务器同步的数据
7
    public void OnServerSync(int segmentIndex, float segmentProgress, long serverTimestamp)
8
    {
9
        marchData.ServerSegmentIndex = segmentIndex;
10
        marchData.ServerSegmentProgress = segmentProgress;
11
        marchData.ServerTimestamp = serverTimestamp;
12
        lastSyncTime = Time.time;
13
    }
14

15
    // 客户端每帧插值
16
    void Update()
17
    {
18
        // 根据服务器时间戳推算当前应该在哪
19
        float elapsedSinceSync = Time.time - lastSyncTime;
20
        float predictedProgress = marchData.ServerSegmentProgress
21
            + (elapsedSinceSync * marchData.Speed / marchData.SegmentLength);
22

23
        // 平滑插值到预测位置
24
        int currentSegment = marchData.ServerSegmentIndex;
25
        Vector3 targetPos = Vector3.Lerp(
26
            marchData.Path[currentSegment],
27
            marchData.Path[currentSegment + 1],
28
            Mathf.Clamp01(predictedProgress)
29
        );
30

31
        // 平滑移动
32
        transform.position = Vector3.Lerp(
33
            transform.position,
34
            targetPos,
35
            Time.deltaTime * 10f  // 平滑系数
36
        );
37
    }
38
}

1
// 自适应同步频率
2
type SyncStrategy struct {
3
    BaseInterval    time.Duration  // 基础同步间隔（如 2 秒）
4
    MinInterval     time.Duration  // 最小同步间隔（如 0.5 秒）
5
    MaxInterval     time.Duration  // 最大同步间隔（如 5 秒）
6
}
7

8
func (s *SyncStrategy) GetSyncInterval(distance float64, isInView bool) time.Duration {
9
    if !isInView {
10
        // 不在视野内，降低同步频率
11
        return s.MaxInterval
12
    }
13

14
    if distance < 100 {
15
        // 近距离，提高同步频率
16
        return s.MinInterval
17
    }
18

19
    // 距离越远，同步频率越低
20
    return s.BaseInterval * time.Duration(distance/100)
21
}

1
传统同步方式（每个部队每 2 秒）：
2
  FullSync: { marchId, path, speed, position, state, armyData, ... }
3
  大小: ~500 bytes/次
4
  1000 个部队: 500KB/次 × 30次/分钟 = 15MB/分钟
5

6
优化后同步方式：
7
  DeltaSync: { marchId, segmentIndex, progress }
8
  大小: ~20 bytes/次
9
  1000 个部队: 20KB/次 × 30次/分钟 = 600KB/分钟
10

11
带宽节省: 96%

1
传统九宫格视野管理：
2

3
┌───┬───┬───┐
4
│ 1 │ 2 │ 3 │   玩家在中心格子 5
5
├───┼───┼───┤   同步格子 1-9 内的所有对象
6
│ 4 │ 5 │ 6 │
7
├───┼───┼───┤   问题1: 玩家跨越格子时出现流量洪峰
8
│ 7 │ 8 │ 9 │   问题2: 至少 60% 的同步对象玩家看不到
9
└───┴───┴───┘

1
玩家从 A 移动到 B：
2

3
A 的九宫格: [1,2,3,4,5,6,7,8,9]
4
B 的九宫格: [3,6,9,10,11,12,13,14,15]
5

6
退出视野: 格子 1,2,4,5,7,8  (6个格子)
7
进入视野: 格子 10,11,12,13,14,15 (6个格子)
8

9
瞬间需要处理 12 个格子的对象变化！
10
→ 可能导致客户端卡顿甚至卡死

1
精确视野裁减流程：
2

3
1. 客户端上报真实梯形视野范围
4
        ┌─────────────┐
5
       /│             │\
6
      / │   可见区域   │ \
7
     /  │   (梯形)    │  \
8
    └───┴─────────────┴───┘
9

10
2. 服务器用梯形范围初筛格子
11
   - 计算梯形内包含哪些格子
12
   - 这些格子内的对象 = 潜在可见对象
13

14
3. 精确匹配
15
   - 对每个潜在对象，检查是否在梯形内
16
   - 仅同步真正可见的对象
17

18
效果：
19
- 流量浪费从 60% 降至接近 0%
20
- 所有同步对象都是客户端可见的

1
// 优先级裁减系统
2
type PriorityCulling struct {
3
    MaxObjects int  // 客户端上报的最大承载对象数
4
}
5

6
type ObjectPriority int
7
const (
8
    PriorityCritical  ObjectPriority = 0  // 自身部队、当前目标
9
    PriorityHigh      ObjectPriority = 1  // 友军、附近敌军
10
    PriorityMedium    ObjectPriority = 2  // 视野内其他部队
11
    PriorityLow       ObjectPriority = 3  // 资源点、装饰物
12
    PriorityNone      ObjectPriority = 4  // 可裁剪
13
)
14

15
func (c *PriorityCulling) Cull(objects []*WorldObject, playerID int64) []*WorldObject {
16
    // 1. 计算每个对象的优先级
17
    for _, obj := range objects {
18
        obj.Priority = c.calculatePriority(obj, playerID)
19
    }
20

21
    // 2. 按优先级排序
22
    sort.Slice(objects, func(i, j int) bool {
23
        return objects[i].Priority < objects[j].Priority
24
    })
25

26
    // 3. 裁减超出上限的对象
27
    if len(objects) > c.MaxObjects {
28
        return objects[:c.MaxObjects]
29
    }
30
    return objects
31
}
32

33
func (c *PriorityCulling) calculatePriority(obj *WorldObject, playerID int64) ObjectPriority {
34
    if obj.OwnerID == playerID {
35
        return PriorityCritical  // 自己的部队
36
    }
37
    if obj.TargetID == playerID {
38
        return PriorityCritical  // 正在攻击自己的部队
39
    }
40
    if c.isAllianceMember(obj.OwnerID, playerID) {
41
        return PriorityHigh  // 友军
42
    }
43
    if c.isNearby(obj, playerID, 50) {
44
        return PriorityHigh  // 附近敌军
45
    }
46
    if obj.Type == ObjectTypeArmy {
47
        return PriorityMedium
48
    }
49
    return PriorityLow
50
}

1
无极缩放层级：
2

3
Layer 1 (地表层) ──── 完整数据
4
  ├── 部队位置、兵力、英雄详情
5
  ├── 战斗动画、技能特效
6
  └── 精确坐标
7

8
Layer 2 (战场层) ──── 中等数据
9
  ├── 部队位置、兵力摘要
10
  └── 战斗状态
11

12
Layer 3 (国家层) ──── 核心数据
13
  ├── 部队位置（概略）
14
  └── 归属信息

1
// 属性定义时打标签
2
type ArmyAttributes struct {
3
    // +layer1 +layer2 +layer3
4
    Position    HexCoord   `sync:"layer1,layer2,layer3"`
5

6
    // +layer1 +layer2
7
    TroopCount  int32      `sync:"layer1,layer2"`
8

9
    // +layer1
10
    HeroDetails *HeroData  `sync:"layer1"`
11

12
    // +layer1
13
    SkillEffects []*Effect `sync:"layer1"`
14
}
15

16
// 根据当前缩放层级，只同步对应标签的属性
17
func (s *SyncManager) SyncArmy(army *Army, viewerLayer int) {
18
    tags := getLayerTags(viewerLayer)
19
    delta := s.collectDirty(army, tags)  // 只收集对应标签的脏数据
20
    s.sendToClient(viewerID, delta)
21
}

1
玩家从 Layer 3 缩放到 Layer 2：
2
  ❌ 错误做法：同步 Layer 2 的完整数据
3
  ✅ 正确做法：仅同步 Layer 2 特有的数据（客户端已有 Layer 3 数据）
4

5
  客户端数据合并：
6
  Layer3 已有数据 + Layer2 特有增量 = Layer2 完整数据
7
  完全不重复同步！

1
大地图线程拆分架构：
2

3
┌────────────────────────────────────────────┐
4
│                  主线程                      │
5
│  ┌──────────┐  ┌──────────┐  ┌──────────┐  │
6
│  │ 请求处理  │  │ 定时器   │  │ 状态管理  │  │
7
│  └──────────┘  └──────────┘  └──────────┘  │
8
└────────────────────────────────────────────┘
9
         │              │              │
10
         ▼              ▼              ▼
11
┌─────────────┐ ┌─────────────┐ ┌─────────────┐
12
│  视野线程    │ │  寻路线程    │ │  并行定时器  │
13
│  (×1)       │ │  (×4)       │ │  (×N)       │
14
│             │ │             │ │             │
15
│ - 视野裁减  │ │ - 路径计算  │ │ - 战斗计算  │
16
│ - 优先级排序│ │ - 路径校验  │ │ - AI 逻辑   │
17
│ - 事件裁剪  │ │ - 路径重算  │ │ - 结构化并发 │
18
└─────────────┘ └─────────────┘ └─────────────┘

1
// 结构化并发 - 并行定时器
2
type ParallelTimer struct {
3
    Name     string
4
    Tasks    []func()  // 并行阶段的任务
5
    Finalize func()    // 串行收尾
6
}
7

8
func (pt *ParallelTimer) Execute() {
9
    // 阶段 1: 并行执行
10
    var wg sync.WaitGroup
11
    for _, task := range pt.Tasks {
12
        wg.Add(1)
13
        go func(t func()) {
14
            defer wg.Done()
15
            t()
16
        }(task)
17
    }
18
    wg.Wait()
19

20
    // 阶段 2: 串行收尾
21
    pt.Finalize()
22
}
23

24
// 使用示例：战斗结算
25
var battleTimer = ParallelTimer{
26
    Name: "BattleSettlement",
27
    Tasks: []func(){
28
        func() { processPlayerABattles() },  // 并行
29
        func() { processPlayerBBattles() },  // 并行
30
        func() { processPlayerCBattles() },  // 并行
31
    },
32
    Finalize: func() {
33
        // 串行合并战斗结果
34
        mergeBattleResults()
35
        notifyClients()
36
    },
37
}

1
// 将地图划分为 Block
2
type BlockCoord struct {
3
    X, Y int32
4
}
5

6
type BlockManager struct {
7
    // 三个核心映射
8
    Player2Blocks  map[int64]map[BlockCoord]bool  // 玩家 → 视口覆盖的 Block
9
    Block2Players  map[BlockCoord]map[int64]bool  // Block → 关注该 Block 的玩家
10
    Block2Events   map[BlockCoord][]*MarchEvent   // Block → 该 Block 上的行军事件
11
}
12

13
// 行军创建时：挂载到途经的所有 Block
14
func (bm *BlockManager) RegisterMarch(march *MarchEvent) {
15
    for _, coord := range march.Path {
16
        block := bm.coordToBlock(coord)
17
        bm.Block2Events[block] = append(bm.Block2Events[block], march)
18
    }
19
}
20

21
// 玩家视口变化时：通知相关 Block
22
func (bm *BlockManager) OnPlayerViewChange(playerID int64, newBlocks []BlockCoord) {
23
    oldBlocks := bm.Player2Blocks[playerID]
24

25
    // 进入新 Block
26
    for _, block := range newBlocks {
27
        if !oldBlocks[block] {
28
            bm.Block2Players[block][playerID] = true
29
            // 推送该 Block 的现有行军事件
30
            bm.pushEvents(playerID, bm.Block2Events[block])
31
        }
32
    }
33

34
    // 离开旧 Block
35
    for block := range oldBlocks {
36
        if !contains(newBlocks, block) {
37
            delete(bm.Block2Players[block], playerID)
38
        }
39
    }
40

41
    bm.Player2Blocks[playerID] = newBlocks
42
}

1
public enum MarchLODLevel
2
{
3
    High,    // 近距离：完整模型 + 动画
4
    Medium,  // 中距离：简化模型 + 简化动画
5
    Low,     // 远距离：图标 + 行军线
6
    Culled   // 视野外：不渲染
7
}
8

9
public class MarchLODManager : MonoBehaviour
10
{
11
    public float HighDistance = 50f;
12
    public float MediumDistance = 200f;
13
    public float LowDistance = 500f;
14

15
    void Update()
16
    {
17
        foreach (var march in activeMarches)
18
        {
19
            float distance = Vector3.Distance(Camera.main.transform.position, march.Position);
20
            MarchLODLevel level = CalculateLOD(distance);
21

22
            switch (level)
23
            {
24
                case MarchLODLevel.High:
25
                    march.ShowFullModel();
26
                    march.ShowDetailedAnimation();
27
                    break;
28
                case MarchLODLevel.Medium:
29
                    march.ShowSimplifiedModel();
30
                    march.ShowBasicAnimation();
31
                    break;
32
                case MarchLODLevel.Low:
33
                    march.ShowIcon();
34
                    march.ShowMarchLine();
35
                    break;
36
                case MarchLODLevel.Culled:
37
                    march.Hide();
38
                    break;
39
            }
40
        }
41
    }
42
}

1
public class MarchObjectPool : MonoBehaviour
2
{
3
    private Queue<MarchVisual> pool = new Queue<MarchVisual>();
4
    private MarchVisual prefab;
5

6
    public MarchVisual Get()
7
    {
8
        MarchVisual obj;
9
        if (pool.Count > 0)
10
        {
11
            obj = pool.Dequeue();
12
            obj.gameObject.SetActive(true);
13
        }
14
        else
15
        {
16
            obj = Instantiate(prefab);
17
        }
18
        return obj;
19
    }
20

21
    public void Return(MarchVisual obj)
22
    {
23
        obj.gameObject.SetActive(false);
24
        obj.Reset();
25
        pool.Enqueue(obj);
26
    }
27
}

1
行军线渲染优化：
2

3
1. 合并绘制：将多条行军线合并为一次 Draw Call
4
   - 使用 LineRenderer 的 GPU Instancing
5
   - 或使用自定义 Shader + ComputeBuffer
6

7
2. 距离裁剪：超过一定距离不渲染行军线
8
   - 近距离（< 100m）：显示完整行军线
9
   - 中距离（100-500m）：只显示已走过的线段
10
   - 远距离（> 500m）：不显示行军线
11

12
3. 简化路径点：远距离时减少行军线的顶点数
13
   - 原始路径可能有 1000 个点
14
   - 远距离时简化为 20 个点即可