zp1/backend/FLOW_FIELD_NAVIAGTION.md

僵尸流向场寻路系统技术文档

1. 概述

本系统将僵尸的寻路算法从 A* 个体寻路改为基于距离场/流向场的群体寻路算法，显著提升了多僵尸同时寻路的效率和自然性。

1.1 核心优势

特性	A* 算法	流向场算法
计算方式	每个僵尸独立计算	共享流向场，统一计算
多目标支持	需要为每个目标重新计算	自动支持多个玩家目标
性能	O(n) 每僵尸	O(m) 每帧 (m=地图格子数)
动态适应	需要重新寻路	自动适应玩家移动

2. 系统架构

2.1 核心组件

GameWorld
    ├── GameMap
    │   ├── distanceField[][]  (距离场)
    │   ├── flowFieldX[][]     (流向场X分量)
    │   ├── flowFieldY[][]     (流向场Y分量)
    │   └── flowFieldValid     (流向场有效标志)
    │
    └── Zombie[]
        ├── x, y               (当前位置)
        ├── targetX, targetY   (目标网格中心)
        ├── hasTarget          (是否有目标)
        ├── reservedGridX/Y    (预留格子)
        └── hasReservation     (是否有预留)

2.2 数据流

每帧更新流程:
1. GameWorld.updateFlowField()
   └── 收集所有存活玩家位置
   └── 调用 GameMap.updateFlowField()

2. GameMap.updateFlowField()
   └── BFS 扩散计算距离场
   └── 基于距离场计算流向场

3. Zombie.move()
   └── 查询流向场获取移动方向
   └── 检查格子占用/预留
   └── 移动到网格中心
   └── 碰撞分离处理

3. 距离场与流向场

3.1 距离场 (Distance Field)

使用 BFS (广度优先搜索) 算法计算每个格子到最近玩家的距离。

// 初始化：所有玩家位置距离为0，加入队列
for (float[] pos : playerPositions) {
    int px = (int) Math.floor(pos[0]);
    int py = (int) Math.floor(pos[1]);
    distanceField[py][px] = 0;
    queue.add(new int[]{px, py});
}

// BFS 扩散
while (!queue.isEmpty()) {
    int[] current = queue.poll();
    for (int[] dir : dirs) {
        int nx = current[0] + dir[0];
        int ny = current[1] + dir[1];

        // 检查墙壁和角落阻挡
        if (dir[0] != 0 && dir[1] != 0) {
            if (isWall(cx + dir[0], cy) || isWall(cx, cy + dir[1])) {
                continue;
            }
        }

        float moveCost = (dir[0] != 0 && dir[1] != 0) ? 1.414f : 1.0f;
        float newDist = currentDist + moveCost;

        if (newDist < distanceField[ny][nx]) {
            distanceField[ny][nx] = newDist;
            queue.add(new int[]{nx, ny});
        }
    }
}

特性：

• 支持 8 方向移动（对角线代价为 √2）
• 正确处理角落碰撞（斜向移动时检查相邻两格是否都为墙）

3.2 流向场 (Flow Field)

基于距离场计算每个格子的最优流向方向。

// 对于每个非墙格子，找到距离场梯度下降方向
for (int y = 0; y < height; y++) {
    for (int x = 0; x < width; x++) {
        if (isWall(x, y)) continue;

        float bestDist = distanceField[y][x];
        float bestDirX = 0, bestDirY = 0;

        // 检查8个方向邻居
        for (int[] dir : dirs) {
            int nx = x + dir[0];
            int ny = y + dir[1];

            if (distanceField[ny][nx] < bestDist) {
                bestDist = distanceField[ny][nx];
                // 单位化方向向量
                float len = (float) Math.sqrt(dir[0]*dir[0] + dir[1]*dir[1]);
                bestDirX = dir[0] / len;
                bestDirY = dir[1] / len;
            }
        }

        flowFieldX[y][x] = bestDirX;
        flowFieldY[y][x] = bestDirY;
    }
}

4. 僵尸移动逻辑

4.1 网格中心对齐

与 A* 寻路类似，僵尸朝向网格中心点 (gridX + 0.5f, gridY + 0.5f) 移动，避免飘忽不定。

// 选择下一个目标网格
if (!hasTarget || centerDist < 0.15f) {
    float[] flowDir = map.getFlowDirection(x, y);
    int nextGridX = currentGridX + (int) Math.round(dirX);
    int nextGridY = currentGridY + (int) Math.round(dirY);

    // 目标 = 网格中心
    targetX = nextGridX + 0.5f;
    targetY = nextGridY + 0.5f;
    hasTarget = true;
}

4.2 格子预留机制

防止多个僵尸同时选择同一格子导致死锁。

// 预留目标格子
reservedGridX = nextGridX;
reservedGridY = nextGridY;
hasReservation = true;

// 检查格子是否被占用或预留
private boolean isGridOccupiedOrReserved(int gridX, int gridY, Collection<Zombie> others) {
    for (Zombie other : others) {
        // 检查当前占用
        if (otherGridX == gridX && otherGridY == gridY) return true;

        // 检查预留
        if (other.hasReservation() &&
            other.getReservedGridX() == gridX &&
            other.getReservedGridY() == gridY) {
            return true;
        }
    }
    return false;
}

4.3 替代路径选择

当首选格子被占用时，寻找最接近目标方向的替代路径。

private int[] findAlternativeDirection(...) {
    // 收集所有可行方向
    for (int[] dir : allDirs) {
        if (isGridOccupiedOrReserved(nx, ny, others)) continue;

        float dotProduct = dir[0] * dirX + dir[1] * dirY;
        candidates.add(new int[]{nx, ny, (int) (dotProduct * 1000)});
    }

    // 按点积排序（最接近原始方向优先）
    candidates.sort((a, b) -> b[2] - a[2]);
    return candidates.isEmpty() ? null : candidates.get(0);
}

4.4 碰撞分离

移动后处理僵尸之间的物理分离，避免重叠。

float minSeparationDist = Constants.ZOMBIE_SIZE;  // 0.8f

for (Zombie other : others) {
    float sepDist = distanceTo(other);

    if (sepDist < minSeparationDist && sepDist > 0.01f) {
        float overlap = minSeparationDist - sepDist;
        float pushX = (sepDx / sepDist) * overlap * 0.5f;
        float pushY = (sepDy / sepDist) * overlap * 0.5f;

        // 尝试推开
        if (map.isWalkable(x + pushX, y + pushY, ZOMBIE_SIZE)) {
            x += pushX;
            y += pushY;
        }
    }
}

4.5 斜向移动防卡墙

处理僵尸斜向移动时碰到墙角卡住的问题。

// 检测是否斜向穿过墙角
if (checkX != checkCurrentX && checkY != checkCurrentY) {
    boolean wallInX = map.isWall(checkX, checkCurrentY);
    boolean wallInY = map.isWall(checkCurrentX, checkY);

    if (wallInX || wallInY) {
        // 尝试沿单轴滑动
        if (!wallInX && canMoveX) {
            x = newX;
        } else if (!wallInY && canMoveY) {
            y = newY;
        }
    }
}

5. 移动顺序

僵尸按 ID 顺序移动，确保低 ID 僵尸优先选择路径。

// GameWorld.updateZombies()
List<Zombie> sortedZombies = new ArrayList<>(zombies.values());
sortedZombies.sort((a, b) -> Integer.compare(a.getId(), b.getId()));

for (Zombie z : sortedZombies) {
    z.move(map, dt, zombies.values());
}

6. 关键常量

常量	值	说明
GRID_SIZE	32	地图尺寸 32×32 格
ZOMBIE_SIZE	0.8f	僵尸碰撞半径
网格中心阈值	0.15f	到达网格中心后重新选择方向
分离距离	ZOMBIE_SIZE	僵尸开始分离的距离
分离推力	0.5f	每次分离移动的比例

7. 潜在问题与解决方案

7.1 僵尸聚集在门口

原因: 流向场在门口处汇聚。

解决方案: 可在距离场中加入惩罚项，让僵尸分散。

7.2 低帧率下移动不稳定

原因: 流向场每帧更新，帧率低时变化剧烈。

解决方案: 考虑增加流向场更新间隔或使用插值平滑。

8. 性能考虑

• 流向场计算: O(width × height × 8) ≈ O(8000) 每帧
• 单僵尸移动: O(1) 查询流向场
• 总复杂度: O(m) + O(n)，其中 m=格子数，n=僵尸数

相比 A* 每帧 O(n × 路径长度)，大幅提升性能。