每日算法 — 使用java实现打企鹅：抛物线物理与最优角度搜索

可莉爸爸 AI算法

一、背景介绍

打企鹅（Yeti Sports）是 2004 年由 InnoGames 开发的 Flash 网页游戏，因其夸张的物理效果与搞笑画风风靡一时。玩家通过控制角色挥棒力度与角度，将企鹅击飞到尽可能远的位置以获得高分。

本游戏的核心算法包括：

  • 抛物线物理模拟：水平速度与垂直速度在重力作用下的分解。
  • 空气阻力与能量衰减：随距离增加阻力逐步累积。
  • 最优角度搜索：在固定力度下枚举角度，找最远飞行距离。
  • 力度滑条控制：玩家拖动滑条决定击球力度。

二、整体设计

游戏采用纯命令行实现，便于读者专注于算法。核心类如下：

  • PhysicsWorld：维护重力、空气阻力、时间步长。
  • Penguin：包含位置、速度、半径、质量。
  • Bat：挥棒动作，根据用户输入返回初速度向量。
  • GameMain：演示最优角度搜索并输出结果。

三、完整代码实现

3.1 物理世界 PhysicsWorld.java

/**
 * 物理世界
 * 实现简单的二维抛体运动模拟：
 *   vx[t+1] = vx[t] - airDrag * vx[t] * dt
 *   vy[t+1] = vy[t] - gravity * dt - airDrag * vy[t] * dt
 *   x[t+1]  = x[t] + vx[t+1] * dt
 *   y[t+1]  = y[t] + vy[t+1] * dt
 */
public class PhysicsWorld {
    public final double gravity;   // 重力加速度（m/s^2），向下为正
    public final double airDrag;   // 空气阻力系数
    public final double dt;        // 仿真时间步长（s）

    public PhysicsWorld(double gravity, double airDrag, double dt) {
        this.gravity = gravity;
        this.airDrag = airDrag;
        this.dt = dt;
    }

    /** 默认世界参数 */
    public static PhysicsWorld defaultWorld() {
        return new PhysicsWorld(9.8, 0.05, 0.016);
    }
}

3.2 企鹅 Penguin.java

/**
 * 企鹅角色
 * 状态包含位置 (x, y) 与速度 (vx, vy)
 * 落地条件：y <= groundY
 */
public class Penguin {
    public double x, y;
    public double vx, vy;
    public final double radius;
    public final double mass;

    public Penguin(double x, double y, double vx, double vy,
                   double radius, double mass) {
        this.x = x; this.y = y;
        this.vx = vx; this.vy = vy;
        this.radius = radius;
        this.mass = mass;
    }

    public static Penguin atRest(double x, double groundY) {
        return new Penguin(x, groundY, 0, 0, 0.3, 1.0);
    }

    /**
     * 推进一个时间步，返回是否仍在飞行
     * 落地后停止更新
     */
    public boolean step(PhysicsWorld world, double groundY) {
        // 应用空气阻力（与速度成正比的指数衰减）
        vx -= world.airDrag * vx * world.dt;
        vy -= world.airDrag * vy * world.dt;
        // 应用重力
        vy -= world.gravity * world.dt;
        // 更新位置
        x += vx * world.dt;
        y += vy * world.dt;
        // 撞地判定
        if (y <= groundY) {
            y = groundY;
            vx = 0; vy = 0;
            return false;
        }
        return true;
    }
}

3.3 球棒 Bat.java

/**
 * 球棒
 * 根据力度 power 和角度 angle（弧度）返回初速度向量
 *   vx = power * cos(angle)
 *   vy = power * sin(angle)
 * 注：y 轴向上为正，因此击球时希望 angle > 0
 */
public class Bat {
    public static double[] hit(double power, double angle) {
        return new double[]{
                power * Math.cos(angle),
                power * Math.sin(angle)
        };
    }
}

3.4 角度搜索器 AngleSearcher.java

/**
 * 最优角度搜索
 * 在固定力度下枚举 0..90 度，找出飞行距离最远的角度
 * 时间复杂度 O(N)，N 为角度采样数
 */
public class AngleSearcher {
    private final PhysicsWorld world;
    private final double power;
    private final double startX;
    private final double groundY;
    private final int samples;

    public AngleSearcher(PhysicsWorld world, double power,
                         double startX, double groundY, int samples) {
        this.world = world;
        this.power = power;
        this.startX = startX;
        this.groundY = groundY;
        this.samples = samples;
    }

    /**
     * 模拟一次击球，返回落地点 x 坐标
     * 最多迭代 5000 步（约 80 秒仿真时间）
     */
    public double simulate(double angle) {
        double[] v = Bat.hit(power, angle);
        Penguin p = new Penguin(startX, groundY, v[0], v[1], 0.3, 1.0);
        int steps = 0;
        while (p.step(world, groundY) && steps < 5000) steps++;
        return p.x;
    }

    /**
     * 网格搜索最优角度
     * 返回 {bestDistance, bestAngleRadians}
     */
    public double[] search() {
        double bestDist = -1;
        double bestAngle = 0;
        for (int i = 1; i < samples; i++) {
            double angle = Math.PI / 2.0 * i / samples;
            double dist = simulate(angle);
            if (dist > bestDist) {
                bestDist = dist;
                bestAngle = angle;
            }
        }
        return new double[]{bestDist, bestAngle};
    }
}

3.5 主程序 GameMain.java

/**
 * 打企鹅游戏主程序
 * 演示三组不同力度下的最优击球角度
 */
public class GameMain {
    public static void main(String[] args) {
        PhysicsWorld world = PhysicsWorld.defaultWorld();
        double groundY = 0;
        double startX = 0;
        double[] powers = {15, 25, 35};
        int samples = 180; // 0.5 度一档

        System.out.println("=== 打企鹅 - 最优角度搜索 ===");
        System.out.printf("%-10s %-15s %-15s%n", "Power", "BestAngle(°)", "Distance(m)");
        for (double power : powers) {
            AngleSearcher searcher = new AngleSearcher(world, power, startX, groundY, samples);
            double[] res = searcher.search();
            double dist = res[0], angle = res[1];
            System.out.printf("%-10.1f %-15.2f %-15.2f%n",
                    power, Math.toDegrees(angle), dist);
        }
    }
}

四、算法分析

4.1 时间复杂度

  • 单次模拟 simulate：每次迭代 O(1)，最多 5000 次迭代，单次模拟 O(K)，K=5000。
  • 角度搜索 search：枚举 samples 个角度，总时间复杂度 O(samples × K)。在 samples=180, K=5000 时约 90 万次运算，毫秒级返回。
  • 二分/三分手优化：可基于单峰性将搜索降至 O(log(samples) × K)。

4.2 物理参数

  • 重力 9.8 m/s²：标准地球重力。
  • 空气阻力 0.05：与速度成正比，决定速度衰减快慢。
  • 时间步长 0.016 s：约 60 FPS。

4.3 物理精度

采用半隐式欧拉法（先更新速度再更新位置），相比显式欧拉在能量守恒上更稳定，仿真长时间飞行时不会爆炸性增长。

五、可扩展方向

  1. 风力场：引入恒定方向风，影响水平速度。
  2. 高度差地形：地面不是平的，不同 x 位置有不同的 groundY。
  3. 碰撞障碍：飞行轨迹上存在建筑物，需要精确碰撞检测。
  4. AI 自动瞄准：以击中最远距离为目标，结合二分搜索 + 模拟给出最优角度。

六、运行说明

将所有 Java 文件放入同一目录，执行 javac *.java && java GameMain，程序会输出三组不同力度下的最优角度与最远距离。

Tagged with: