每日算法 — 使用java实现蜈蚣：体节路径队列与空间哈希碰撞检测

街机经典《蜈蚣》看起来只是”一条虫子爬来爬去”，但它的算法内核相当精致：一条由十几个体节组成的蜈蚣，被击中后要从中间断开，断开的两段各自独立蜿蜒下行；同时场上还有蜘蛛、跳蚤、蝎子三种完全不同运动模式的敌人。本文用 Java 实现这套逻辑：用路径队列让体节”踩着前节的脚印”前进、用空间哈希把上百个碰撞检测压进常数时间、用状态机处理断裂后的多段独立寻路。

一、蜈蚣的运动本质：一条共享的路径

新手实现蜈蚣最容易踩的坑是逐节独立计算位置：

// 错误做法：每节自己算方向
for (int i = 0; i < segments.size(); i++) {
    Segment s = segments.get(i);
    s.x += s.dx;  s.y += s.dy;   // 每节都独立判断是否撞墙
}

问题立刻出现：转弯时各节会算出一致的方向，但撞墙判定发生在不同时刻，导致体节互相重叠或拉长。真实蜈蚣的行为是”整条虫像一根绳子一样沿着管道流动”。

正确做法是路径队列（path queue）：头部每走一格，就把新位置塞进队首，整条虫的每一节都从队列里按索引取位置。

public final class Centipede {
    static final int CELL = 24;         // 逻辑格尺寸
    static final int COLS = 30, ROWS = 26;

    /** 体节位置轨迹：index 0 是队首（最新位置），越往后越旧 */
    private final ArrayDeque<Point> path = new ArrayDeque<>();
    private int segmentCount;

    /** 头部移动一格，尾节自动"离开"最旧位置 */
    void step(Predicate<Point> canEnter) {
        Point head = path.peekFirst();
        Point next = headingNext(head);

        if (!canEnter.test(next)) {
            next = turnDown(head);              // 撞墙：向下折返
            if (!canEnter.test(next)) return;    // 竖直也堵住：停在原地
        }
        path.addFirst(next);
        while (path.size() > segmentCount) path.removeLast();
    }
}

为什么 segmentCount 要单独存。 因为队列长度即体节数量，而体节会在被击中时减少——两件事必须解耦：一条虫的”身体长度”会变，”路径记忆”不能丢。保留超长路径对后续被击中后重新生长有用。

headingNext 的蜿蜒逻辑是蜈蚣的标志性行为：沿一个方向走 N 格后向下一行，再反向走 N 格，如此往返，形成”扫掠”轨迹。

Point headingNext(Point head) {
    int nx = head.x + dirX;
    if (nx < 0 || nx >= COLS) {
        dirX = -dirX;
        return new Point(head.x, head.y + 1);   // 到边界 → 下移一行并反向
    }
    return new Point(nx, head.y);
}

注意这里的处理顺序：先判断越界再反向，且下移那一格不消耗横向步数。这符合原版街机的行为——蜈蚣触边后垂直下落一格，然后朝反方向继续。

二、断裂：一条虫变成多条虫

被子弹击中的体节不是消失，而是变成蘑菇障碍，同时虫体在该处断开，形成两条独立的虫。

/** 击中第 hitIndex 节：返回断裂后产生的两条虫 */
List<Centipede> split(int hitIndex) {
    List<Centipede> children = new ArrayList<>();
    if (hitIndex == 0) {
        // 击中头节：整条虫缩短一节，方向不变
        this.segmentCount--;
        return children;
    }
    if (hitIndex >= segmentCount - 1) {
        // 击中尾节：仅缩短
        this.segmentCount--;
        return children;
    }

    // 中间断裂：前半段保留原方向，后半段继承位置但反向
    Centipede front = copyWithSegments(0, hitIndex);
    Centipede back  = copyWithSegments(hitIndex + 1, segmentCount);
    back.dirX = -this.dirX;
    children.add(front);
    children.add(back);
    return children;
}

后半段为什么要反向？因为原版蜈蚣断开后，尾段会独立向下并朝相反方向继续行进，形成两条交错扫掠的虫。这个细节如果照抄”方向不变”，玩家会看到两条虫完全同步撞墙，视觉上像同一只虫——很容易被误认为是 bug。

copyWithSegments 需要按索引切片 path，但 ArrayDeque 不支持随机访问，所以我用 ArrayList 存路径、head 指针标记队首，避免反复转换：

private final ArrayList<Point> pathList = new ArrayList<>();

Centipede copyWithSegments(int from, int to) {
    Centipede c = new Centipede();
    c.pathList.addAll(pathList.subList(from, to));
    c.segmentCount = to - from;
    c.dirX = this.dirX;
    return c;
}

代价是”队首插入”变成 O(n)，但 n 最多几十节，完全可接受。在体节数量固定的游戏里，用 ArrayList + 指针优于用 Deque——可读性收益远大于常数差异。

三、空间哈希：让碰撞检测不随敌人数量爆炸

场上同时有：1~3 条蜈蚣（最多二十多节）、1 只蜘蛛、若干跳蚤、若干蝎子，再加上几十个蘑菇。朴素实现是”每颗子弹对每个可碰撞对象做 AABB 检测”，量级是 子弹 × 对象，一帧几百次。

但屏幕是格点化的，所有实体都落在 24 像素的网格上——这天然适合空间哈希（spatial hash）：用一个 Map<Long, List<Entity>> 把格子坐标映射到该格内的实体。

final class SpatialHash {
    private final Map<Long, List<Entity>> buckets = new HashMap<>();

    static long key(int cx, int cy) { return ((long) cx << 32) | (cy & 0xffffffffL); }

    void insert(Entity e) {
        long k = key(e.cellX, e.cellY);
        buckets.computeIfAbsent(k, x -> new ArrayList<>(4)).add(e);
    }

    /** 查询某格及相邻 8 格的所有实体 */
    List<Entity> queryNear(int cx, int cy) {
        List<Entity> out = new ArrayList<>(16);
        for (int dx = -1; dx <= 1; dx++)
            for (int dy = -1; dy <= 1; dy++) {
                List<Entity> b = buckets.get(key(cx + dx, cy + dy));
                if (b != null) out.addAll(b);
            }
        return out;
    }
}

几个实现要点：

1. 键的构造必须避免负数溢出。 (long) cx << 32 | (cy & 0xffffffffL) 里 cy 的掩码很关键——如果 cy 为负，直接 | 会污染高位。格点坐标不会为负，但保险起见保留掩码。

2. 每帧重建而非增量维护。 增量维护（插入/删除时更新桶）在实体高速移动时容易漏删，产生”幽灵碰撞”。每帧清空重建的代价是 O(实体数)，远小于增量维护的调试成本。

3. 桶内用 ArrayList 而非 HashSet。 同格内实体通常少于 5 个，线性遍历比哈希更快，且顺序稳定（有利于确定性回放）。

实测效果：60 个实体、每帧 20 颗子弹，朴素检测约 1200 次 AABB；空间哈希后每次查询平均命中 2~4 个对象，总计约 80 次。一个数量级的差距，且随实体数增加而扩大。

四、三种敌人的状态机

《蜈蚣》的敌人各有完全不同的运动规则，用同一个”移动”函数是行不通的。我用一个显式状态机统一管理：

敌人	运动模式	核心决策
蜘蛛	在下方玩家区域内之字形往返	定期检查与玩家的距离，靠近则加速
跳蚤	竖直下落，边落边留蘑菇	若玩家所在列无蘑菇则加速下落
蝎子	横向穿过上半屏，留下毒蘑菇	毒蘑菇会让蜈蚣垂直俯冲

sealed interface Enemy permits Spider, Flea, Scorpion {
    void update(World w);
}

final class Spider implements Enemy {
    int x, y, dx = 1;
    int cooldown = 0;

    @Override public void update(World w) {
        // 之字形：横向移动 + 周期性纵向扰动
        x += dx * 2;
        if (x <= LEFT || x >= RIGHT) dx = -dx;
        if (--cooldown <= 0) {
            y += (w.playerY() > y) ? 1 : -1;   // 朝玩家方向垂直抖动
            cooldown = 8 + RAND.nextInt(10);
        }
        // 距离玩家足够近时提速（原版的"追击"行为）
        if (manhattan(x, y, w.playerX(), w.playerY()) < 6) x += dx * 2;
    }
}

cooldown 的随机化是必须的：如果蜘蛛每帧都朝玩家抖动，它会像制导导弹一样精准，玩家毫无机会。在原版街机里，所有敌人的”智能”都是被刻意打了折扣的——这是游戏设计而非算法缺陷。

蝎子的特殊性在于它会改变其他实体的行为：

final class Scorpion implements Enemy {
    @Override public void update(World w) {
        x += dx * 3;
        if (w.isPassable(x, y) && w.mushroomAt(x, y) == null) {
            w.placeMushroom(x, y, Mushroom.POISONED);   // 留下毒蘑菇
        }
    }
}

而蜈蚣在进入毒蘑菇格时必须改变策略——从”水平扫掠”切换为”垂直俯冲”：

/** 蜈蚣头部移动时检查脚下是否为毒蘑菇 */
Point resolveNext(World w, Point head) {
    if (w.mushroomAt(head.x, head.y) == Mushroom.POISONED) {
        poisonedDive = true;   // 进入俯冲模式，持续到离开该列
    }
    if (poisonedDive) {
        Point down = new Point(head.x, head.y + 1);
        if (w.isPassable(down)) return down;
        poisonedDive = false;
        return headingNext(head);
    }
    return headingNext(head);
}

poisonedDive 是一段持续状态而非单帧判断：头部进入毒格后要一直往下冲到出界或撞墙，中间不能被下一帧的普通逻辑覆盖。这个”粘滞状态”（sticky state）模式在状态机实现里很常见——忘了它，蜈蚣就会在毒格上反复横跳。

五、蘑菇图与移动合法性

蘑菇不只是障碍，它构成了一张可通行图。每帧不重建图（太贵），而是把蘑菇存在一个扁平 byte[] 数组里，取值 0=空、1=普通、2=毒：

final byte[] mushroom = new byte[COLS * ROWS];

boolean isPassable(int x, int y) {
    if (x < 0 || x >= COLS || y < 0 || y >= ROWS) return false;
    return true;   // 蘑菇不阻挡移动，只提供"可下落支撑"，见下
}

/** 关键：蜈蚣只能沿着"有蘑菇"或"边界"的行向下折返 */
boolean canDescend(int x, int y) {
    if (y + 1 >= ROWS) return false;
    return mushroom[(y + 1) * COLS + x] != 0;   // 下方有蘑菇才有落点
}

这里体现了一个原版的核心机制：蜈蚣不能自由下落，只有下方有蘑菇时才能”踩”上去。这使得玩家的清蘑菇行为直接影响蜈蚣路径——清空某列蘑菇会让蜈蚣在该列跳过这一层。这个耦合正是游戏策略的来源。

canDescend 的判定顺序也很重要：先判断出界，再查蘑菇。反过来写会在最后一层产生越界访问。

六、复杂度与帧预算

假设场上有 S 条蜈蚣段（总计 ≤ 25 节）、E 个敌人（≤ 8）、M 个蘑菇（≤ 60）、B 颗子弹（≤ 20）。

操作	朴素复杂度	本实现
蜈蚣移动	O(S)	O(S)，每节 O(1) 查队列
子弹碰撞	O(B × (S+E))	O(B × 4)，空间哈希近邻查询
蘑菇查询	O(M) 线性扫	O(1) 数组索引
分裂处理	O(S²) 复制	O(S)，子列表切片

一帧总操作量在 200 次以内，60 FPS 下 CPU 占用可以忽略。真正的性能陷阱是路径队列的内存增长——如果忘记 while (path.size() > segmentCount) removeLast()，队列会无限增长，几小时后内存泄漏。这是这类”轨迹回放”式实现最常见的 bug。

七、小结

蜈蚣这个游戏能提炼出三个通用模式：

路径队列驱动的链条运动：任何”跟随”型实体（贪吃蛇、俄罗斯方块的下落预览、粒子拖尾）都可以用”头部写入 + 尾部淘汰”的队列实现，比逐节独立计算稳定得多。
空间哈希替代两两检测：当实体都在格点上时，一次 Map 查询就能把 O(n²) 降到 O(n)。每帧重建比增量维护更可靠。
粘滞状态机：游戏里大量行为是”进入某状态后持续若干帧”，用布尔标志位表达比用单帧条件判断更不容易出 bug。

最后一句值得记住：原版街机游戏里的敌人 AI 普遍被故意削弱——蜘蛛的随机抖动、跳蚤的条件加速，都是在”看起来聪明”和”可被击败”之间取的平衡点。做游戏算法时，追求最优解往往不如追求可被玩家理解的行为规律。

Tagged with: Centipede 状态机碰撞检测空间哈希蜈蚣街机游戏路径队列链式运动