每日算法 — 使用java实现滚动的天空：三维空间滚动与动态障碍规避

滚动的天空（Rolling Sky）是一款快节奏的三维滚球游戏，玩家控制小球在悬浮于空中的道路上滚动，通过左右滑动躲避障碍。本文用Java实现其核心机制：三维空间中的球体运动学、基于四元数的平滑旋转、AABB碰撞检测与动态障碍生成算法。

核心设计思路

游戏世界可抽象为三个层次：

1. 物理层：小球受重力、离心力与法向力作用，在三维曲面上滚动；
2. 渲染层：将三维坐标投影到屏幕，绘制道路、障碍与球体；
3. 逻辑层：根据球体位置实时检测与障碍的碰撞，生成前方道路。

本文聚焦于物理运动学与碰撞检测的算法实现。

完整Java实现

import java.util.*;

/**
 * 滚动的天空核心引擎
 * 包含：三维球体运动、四元数旋转、AABB碰撞、障碍生成
 */
public class RollingSkyEngine {

    // ==================== 三维向量工具 ====================
    static class Vec3 {
        double x, y, z;
        Vec3(double x, double y, double z) { this.x = x; this.y = y; this.z = z; }
        Vec3 add(Vec3 v) { return new Vec3(x + v.x, y + v.y, z + v.z); }
        Vec3 sub(Vec3 v) { return new Vec3(x - v.x, y - v.y, z - v.z); }
        Vec3 mul(double s) { return new Vec3(x * s, y * s, z * s); }
        double dot(Vec3 v) { return x * v.x + y * v.y + z * v.z; }
        Vec3 cross(Vec3 v) {
            return new Vec3(
                y * v.z - z * v.y,
                z * v.x - x * v.z,
                x * v.y - y * v.x
            );
        }
        double length() { return Math.sqrt(x * x + y * y + z * z); }
        Vec3 normalize() {
            double len = length();
            if (len < 1e-9) return new Vec3(0, 0, 0);
            return new Vec3(x / len, y / len, z / len);
        }
        @Override
        public String toString() {
            return String.format("(%.2f, %.2f, %.2f)", x, y, z);
        }
    }

    // ==================== 四元数：平滑旋转 ====================
    static class Quaternion {
        double w, x, y, z;
        Quaternion(double w, double x, double y, double z) {
            this.w = w; this.x = x; this.y = y; this.z = z;
        }
        // 绕轴旋转angle弧度
        static Quaternion fromAxisAngle(Vec3 axis, double angle) {
            Vec3 a = axis.normalize();
            double half = angle / 2;
            double s = Math.sin(half);
            return new Quaternion(Math.cos(half), a.x * s, a.y * s, a.z * s);
        }
        Quaternion multiply(Quaternion q) {
            return new Quaternion(
                w * q.w - x * q.x - y * q.y - z * q.z,
                w * q.x + x * q.w + y * q.z - z * q.y,
                w * q.y - x * q.z + y * q.w + z * q.x,
                w * q.z + x * q.y - y * q.x + z * q.w
            );
        }
        Quaternion conjugate() { return new Quaternion(w, -x, -y, -z); }
        // 旋转向量
        Vec3 rotate(Vec3 v) {
            Quaternion qv = new Quaternion(0, v.x, v.y, v.z);
            Quaternion result = this.multiply(qv).multiply(this.conjugate());
            return new Vec3(result.x, result.y, result.z);
        }
        // 球面插值Slerp
        static Quaternion slerp(Quaternion a, Quaternion b, double t) {
            double dot = a.w * b.w + a.x * b.x + a.y * b.y + a.z * b.z;
            if (dot < 0) { b = new Quaternion(-b.w, -b.x, -b.y, -b.z); dot = -dot; }
            if (dot > 0.9995) {
                return new Quaternion(
                    a.w + t * (b.w - a.w),
                    a.x + t * (b.x - a.x),
                    a.y + t * (b.y - a.y),
                    a.z + t * (b.z - a.z)
                ).normalize();
            }
            double theta0 = Math.acos(dot);
            double theta = theta0 * t;
            double sinTheta = Math.sin(theta);
            double sinTheta0 = Math.sin(theta0);
            double s0 = Math.cos(theta) - dot * sinTheta / sinTheta0;
            double s1 = sinTheta / sinTheta0;
            return new Quaternion(
                a.w * s0 + b.w * s1,
                a.x * s0 + b.x * s1,
                a.y * s0 + b.y * s1,
                a.z * s0 + b.z * s1
            );
        }
        Quaternion normalize() {
            double len = Math.sqrt(w * w + x * x + y * y + z * z);
            return new Quaternion(w / len, x / len, y / len, z / len);
        }
    }

    // ==================== AABB包围盒 ====================
    static class AABB {
        Vec3 min, max;
        AABB(Vec3 min, Vec3 max) { this.min = min; this.max = max; }
        boolean intersects(AABB other) {
            return min.x <= other.max.x && max.x >= other.min.x &&
                   min.y <= other.max.y && max.y >= other.min.y &&
                   min.z <= other.max.z && max.z >= other.min.z;
        }
        // 球体与AABB的最短距离平方
        double distanceSqToPoint(Vec3 p) {
            double dx = Math.max(min.x - p.x, Math.max(0, p.x - max.x));
            double dy = Math.max(min.y - p.y, Math.max(0, p.y - max.y));
            double dz = Math.max(min.z - p.z, Math.max(0, p.z - max.z));
            return dx * dx + dy * dy + dz * dz;
        }
    }

    // ==================== 道路段 ====================
    static class RoadSegment {
        Vec3 center;      // 道路中心点
        Vec3 forward;     // 前进方向（切线）
        Vec3 up;          // 法向（垂直路面向上）
        Vec3 right;       // 右方向（路面宽度方向）
        double width;     // 道路宽度
        double length;    // 段长度

        RoadSegment(Vec3 center, Vec3 forward, Vec3 up, double width, double length) {
            this.center = center;
            this.forward = forward.normalize();
            this.up = up.normalize();
            this.right = forward.cross(up).normalize();
            this.width = width;
            this.length = length;
        }

        // 获取道路表面的世界坐标（横向偏移offset∈[-1,1]）
        Vec3 getSurfacePoint(double offset) {
            return center.add(right.mul(offset * width / 2));
        }
    }

    // ==================== 障碍物 ====================
    static class Obstacle {
        Vec3 position;
        Vec3 size;
        AABB bounds;
        ObstacleType type;

        enum ObstacleType { STATIC, MOVING, ROTATING }

        Obstacle(Vec3 pos, Vec3 size, ObstacleType type) {
            this.position = pos;
            this.size = size;
            this.type = type;
            Vec3 half = size.mul(0.5);
            this.bounds = new AABB(pos.sub(half), pos.add(half));
        }

        void update(double time) {
            if (type == ObstacleType.MOVING) {
                position.x += Math.sin(time * 2) * 0.1;
                Vec3 half = size.mul(0.5);
                bounds = new AABB(position.sub(half), position.add(half));
            }
        }
    }

    // ==================== 球体实体 ====================
    static class Ball {
        Vec3 position = new Vec3(0, 1, 0); // 球心位置（半径1，y=1在地面）
        Vec3 velocity = new Vec3(0, 0, 5); // 初始向前速度
        double radius = 1.0;
        double mass = 1.0;
        Quaternion rotation = new Quaternion(1, 0, 0, 0); // 朝向四元数
        double rollAngle = 0; // 滚动累积角度（用于计算旋转）

        // 碰撞后的无敌帧
        double invincibleTimer = 0;

        void update(double dt, RoadSegment road, List<Obstacle> obstacles, double time) {
            // 1. 输入：左右移动（简化：直接修改横向速度）
            // 实际游戏中通过触摸/键盘输入控制横向速度

            // 2. 将速度投影到道路表面
            Vec3 velOnSurface = projectToSurface(velocity, road.up);

            // 3. 更新位置
            position = position.add(velOnSurface.mul(dt));

            // 4. 重力与法向约束：将y约束在道路表面高度（简化：假设道路在xz平面）
            position.y = radius; // 保持在地面上

            // 5. 横向边界约束
            double lateral = road.right.dot(position.sub(road.center));
            if (Math.abs(lateral) > road.width / 2 - radius) {
                double clamped = Math.signum(lateral) * (road.width / 2 - radius);
                position = road.center.add(road.right.mul(clamped)).add(road.up.mul(radius));
                // 撞墙反弹
                velocity = velocity.sub(road.right.mul(velocity.dot(road.right) * 2));
            }

            // 6. 滚动旋转：球体滚动的角速度 = 线速度 / 半径
            double speed = velOnSurface.length();
            rollAngle += speed * dt / radius;
            Vec3 rollAxis = road.right.cross(road.forward).normalize();
            Quaternion deltaRot = Quaternion.fromAxisAngle(rollAxis, speed * dt / radius);
            rotation = deltaRot.multiply(rotation);

            // 7. 碰撞检测
            if (invincibleTimer > 0) {
                invincibleTimer -= dt;
            } else {
                for (Obstacle obs : obstacles) {
                    obs.update(time);
                    double distSq = obs.bounds.distanceSqToPoint(position);
                    if (distSq < radius * radius) {
                        // 碰撞发生！
                        handleCollision(obs, road);
                        invincibleTimer = 0.5; // 0.5秒无敌
                        break;
                    }
                }
            }
        }

        // 将向量投影到平面（去掉法向分量）
        Vec3 projectToSurface(Vec3 v, Vec3 normal) {
            Vec3 n = normal.normalize();
            return v.sub(n.mul(v.dot(n)));
        }

        void handleCollision(Obstacle obs, RoadSegment road) {
            // 简化碰撞响应：向后弹并减速
            velocity = velocity.mul(0.5);
            velocity = velocity.sub(road.forward.mul(2)); // 向后推
            System.out.println("[碰撞] 球体撞击障碍物！速度降至 " + velocity.length());
        }

        AABB getBounds() {
            Vec3 r = new Vec3(radius, radius, radius);
            return new AABB(position.sub(r), position.add(r));
        }
    }

    // ==================== 关卡生成器 ====================
    static class LevelGenerator {
        List<RoadSegment> roadSegments = new ArrayList<>();
        List<Obstacle> obstacles = new ArrayList<>();
        Random rand = new Random(123);
        double totalLength = 0;

        void generate(int numSegments) {
            Vec3 pos = new Vec3(0, 0, 0);
            Vec3 forward = new Vec3(0, 0, 1);
            Vec3 up = new Vec3(0, 1, 0);

            for (int i = 0; i < numSegments; i++) {
                double segLen = 10 + rand.nextDouble() * 10;
                double width = 8 + rand.nextDouble() * 4;

                // 随机转弯
                double turn = (rand.nextDouble() - 0.5) * 0.3; // 小幅度左右弯
                Vec3 newForward = new Vec3(
                    forward.x * Math.cos(turn) - forward.z * Math.sin(turn),
                    0,
                    forward.x * Math.sin(turn) + forward.z * Math.cos(turn)
                ).normalize();

                RoadSegment seg = new RoadSegment(pos, newForward, up, width, segLen);
                roadSegments.add(seg);

                // 在段上生成障碍物
                int obsCount = rand.nextInt(3);
                for (int j = 0; j < obsCount; j++) {
                    double t = rand.nextDouble();
                    Vec3 obsPos = pos.add(newForward.mul(t * segLen));
                    obsPos = obsPos.add(seg.right.mul((rand.nextDouble() - 0.5) * width * 0.6));
                    obsPos.y = 1.5; // 障碍物高度

                    Vec3 obsSize = new Vec3(2 + rand.nextDouble() * 2, 3, 2 + rand.nextDouble() * 2);
                    Obstacle.ObstacleType type = Obstacle.ObstacleType.values()[rand.nextInt(3)];
                    obstacles.add(new Obstacle(obsPos, obsSize, type));
                }

                pos = pos.add(newForward.mul(segLen));
                forward = newForward;
                totalLength += segLen;
            }
        }

        // 获取球体当前所在的道路段
        RoadSegment getCurrentRoad(Vec3 ballPos) {
            // 简化：返回最近的段中心
            RoadSegment best = roadSegments.get(0);
            double bestDist = Double.MAX_VALUE;
            for (RoadSegment seg : roadSegments) {
                double d = seg.center.sub(ballPos).length();
                if (d < bestDist) {
                    bestDist = d;
                    best = seg;
                }
            }
            return best;
        }
    }

    // ==================== 主模拟循环 ====================
    public static void main(String[] args) {
        System.out.println("=== 滚动的天空引擎启动 ===");

        LevelGenerator level = new LevelGenerator();
        level.generate(50);
        System.out.printf("生成 %d 段道路，%d 个障碍物%n", level.roadSegments.size(), level.obstacles.size());

        Ball ball = new Ball();
        double dt = 1.0 / 60.0;
        double time = 0;

        System.out.println("\n--- 模拟运行（每30帧输出一次）---");
        for (int frame = 0; frame < 1800; frame++) {
            RoadSegment currentRoad = level.getCurrentRoad(ball.position);
            ball.update(dt, currentRoad, level.obstacles, time);
            time += dt;

            if (frame % 30 == 0) {
                System.out.printf("t=%.2fs 位置=%s 速度=%.2f 旋转角=%.2f°%n",
                    time, ball.position, ball.velocity.length(), Math.toDegrees(ball.rollAngle));
            }

            // 终点判定
            if (ball.position.z > level.totalLength) {
                System.out.println("\n到达终点！");
                break;
            }
        }
        System.out.println("\n模拟结束。");
    }
}

复杂度分析

对于50段道路、约100个障碍物的关卡，每帧处理量在微秒级，完全满足60FPS实时需求。

扩展方向

1. 曲面道路：将道路段升级为参数化曲面（如NURBS），实现连续起伏的立体关卡；
2. 物理引擎集成：引入刚体动力学，支持弹跳板、加速带等互动元素；
3. 空间索引：用八叉树或BVH加速碰撞检测，支持千级障碍物同屏；
4. 关卡程序化生成：结合波函数坍缩（WFC）算法，根据音乐节奏自动生成与旋律匹配的道路形状。

滚动的天空将三维几何、物理模拟与音乐节奏融为一体。通过本文的Java实现，读者可以掌握四元数旋转、AABB碰撞检测与动态关卡生成的核心技术，并在此基础上打造更具创意的立体跑酷体验。