愤怒的小鸟（Angry Birds）是全球现象级的物理弹射游戏，玩家拖动弹弓发射小鸟，利用抛物线轨迹撞击猪与木结构，以消灭所有敌方目标。其内核并非简单的动画播放，而是刚体物理引擎、碰撞检测与蒙特卡洛优化搜索的有机结合。本文将用Java从零构建一个可运行的简化版物理引擎，并讲解如何用蒙特卡洛模拟寻找最优发射角度与初速度。
一、场景建模与物理实体定义
1.1 为什么需要统一实体基类
游戏世界中的小鸟、猪、木块都具备位置、速度、质量、尺寸等属性，且参与相同的物理更新与碰撞检测流程。通过抽象基类统一接口，可大幅简化碰撞遍历与受力计算。
/**
* 二维向量，用于位置、速度、加速度表示
* 支持加减、数乘、点乘与模长计算
*/
class Vec2 {
double x, y;
Vec2(double x, double y) {
this.x = x;
this.y = y;
}
Vec2 add(Vec2 v) { return new Vec2(x + v.x, y + v.y); }
Vec2 sub(Vec2 v) { return new Vec2(x - v.x, y - v.y); }
Vec2 mul(double s) { return new Vec2(x * s, y * s); }
double dot(Vec2 v) { return x * v.x + y * v.y; }
double length() { return Math.sqrt(x * x + y * y); }
@Override
public String toString() {
return String.format("(%.2f, %.2f)", x, y);
}
}
/**
* 物理实体基类
* 所有参与碰撞与运动的游戏对象（鸟、猪、方块）都继承此类
*/
abstract class Entity {
// 中心位置（单位：米）
Vec2 position;
// 速度向量（单位：米/秒）
Vec2 velocity;
// 加速度（通常仅受重力影响）
Vec2 acceleration;
// 质量（千克），质量越大惯性越大
double mass;
// 尺寸：半宽与半高（用于AABB碰撞盒）
double halfWidth, halfHeight;
// 是否已被销毁（生命值归零）
boolean destroyed;
// 实体类型标识
enum Type { BIRD, PIG, WOOD_BLOCK }
final Type type;
Entity(Type type, Vec2 pos, Vec2 vel, double mass, double hw, double hh) {
this.type = type;
this.position = pos;
this.velocity = vel;
this.acceleration = new Vec2(0, 0);
this.mass = mass;
this.halfWidth = hw;
this.halfHeight = hh;
this.destroyed = false;
}
/**
* 获取轴对齐包围盒（AABB）的上下左右边界
* AABB是碰撞检测中最快的粗判手段
*/
double minX() { return position.x - halfWidth; }
double maxX() { return position.x + halfWidth; }
double minY() { return position.y - halfHeight; }
double maxY() { return position.y + halfHeight; }
/**
* 承受冲击并计算伤害
* @param impulse 冲击力大小
*/
abstract void takeDamage(double impulse);
}
1.2 具体实体实现
/**
* 小鸟实体
* 小鸟的特点：质量轻、可被玩家发射、撞击后造成动能伤害
*/
class Bird extends Entity {
// 生命值，小鸟撞击坚硬物体后也会消失
double hp;
Bird(Vec2 pos, double mass, double radius) {
super(Type.BIRD, pos, new Vec2(0, 0), mass, radius, radius);
this.hp = 10.0;
}
@Override
void takeDamage(double impulse) {
// 小鸟承受撞击时，按冲击力扣血
hp -= impulse * 0.5;
if (hp <= 0) destroyed = true;
}
/**
* 从弹弓发射
* @param angle 发射角度（弧度，0表示水平向右，正方向向上）
* @param speed 初速度大小
*/
void launch(double angle, double speed) {
this.velocity = new Vec2(Math.cos(angle) * speed, Math.sin(angle) * speed);
}
}
/**
* 猪实体
* 猪是目标单位，被击倒即视为消灭
*/
class Pig extends Entity {
double hp;
Pig(Vec2 pos, double mass, double radius) {
super(Type.PIG, pos, new Vec2(0, 0), mass, radius, radius);
this.hp = 15.0;
}
@Override
void takeDamage(double impulse) {
hp -= impulse;
if (hp <= 0) destroyed = true;
}
}
/**
* 木块障碍物
* 木块用于搭建防御工事，受撞击后可能碎裂
*/
class WoodBlock extends Entity {
double hp;
// 木块材质强度系数
static final double STRENGTH = 2.0;
WoodBlock(Vec2 pos, double mass, double hw, double hh) {
super(Type.WOOD_BLOCK, pos, new Vec2(0, 0), mass, hw, hh);
this.hp = 30.0;
}
@Override
void takeDamage(double impulse) {
hp -= impulse / STRENGTH;
if (hp <= 0) destroyed = true;
}
}
二、抛物线运动模拟
2.1 物理更新核心
游戏采用显式欧拉积分进行离散时间步进。每帧执行：
- 速度更新：
v = v + a * dt - 位置更新：
p = p + v * dt
重力加速度固定为 g = 9.8 m/s²，方向竖直向下。为简化计算，世界坐标系以弹弓位置为原点，X轴向右，Y轴向上。
/**
* 物理世界管理器
* 负责所有实体的重力施加、运动积分、碰撞检测与响应
*/
class PhysicsWorld {
// 重力加速度（向下为负Y方向）
static final Vec2 GRAVITY = new Vec2(0, -9.8);
// 时间步长（秒），越小模拟越精确但计算量越大
static final double DT = 0.016; // 约60FPS
// 地面高度，实体落到地面以下即视为出界
static final double GROUND_Y = 0.0;
private final List<Entity> entities;
PhysicsWorld() {
this.entities = new ArrayList<>();
}
void addEntity(Entity e) {
entities.add(e);
}
List<Entity> getEntities() {
return entities;
}
/**
* 单步物理模拟
* 1. 对所有存活实体施加重力并更新速度与位置
* 2. 执行碰撞检测与响应
* 3. 移除已被销毁的实体
*/
void step() {
// 阶段一：积分运动
for (Entity e : entities) {
if (e.destroyed) continue;
// 施加重力（仅对空中的鸟和飞起的碎片有效，猪和木块默认静止）
if (e.type == Entity.Type.BIRD || e.velocity.length() > 0.1) {
e.acceleration = GRAVITY;
e.velocity = e.velocity.add(GRAVITY.mul(DT));
e.position = e.position.add(e.velocity.mul(DT));
}
// 地面碰撞简单处理：落地点以下停止
if (e.position.y - e.halfHeight < GROUND_Y) {
e.position.y = GROUND_Y + e.halfHeight;
e.velocity.y = Math.max(e.velocity.y, 0);
// 地面摩擦减速
e.velocity.x *= 0.9;
}
}
// 阶段二：碰撞检测与响应（O(n^2) 暴力遍历，小规模场景足够）
for (int i = 0; i < entities.size(); i++) {
for (int j = i + 1; j < entities.size(); j++) {
Entity a = entities.get(i);
Entity b = entities.get(j);
if (a.destroyed || b.destroyed) continue;
resolveCollision(a, b);
}
}
// 阶段三：清理已销毁实体
entities.removeIf(e -> e.destroyed);
}
2.2 碰撞响应模型
当两个实体发生AABB重叠时，我们采用简化冲量模型：根据相对速度的法向分量计算冲击力，并按质量比例分配速度变化。冲击力同时作为伤害输入。
/**
* AABB碰撞检测 + 冲量响应
* @return 若发生碰撞返回true
*/
boolean resolveCollision(Entity a, Entity b) {
// AABB粗判：检查X轴与Y轴投影是否均重叠
boolean overlapX = a.maxX() > b.minX() && a.minX() < b.maxX();
boolean overlapY = a.maxY() > b.minY() && a.minY() < b.maxY();
if (!overlapX || !overlapY) return false;
// 计算碰撞法线（从a指向b的最短分离方向）
Vec2 normal;
double overlapLeft = a.maxX() - b.minX();
double overlapRight = b.maxX() - a.minX();
double overlapTop = a.maxY() - b.minY();
double overlapBottom = b.maxY() - a.minY();
double minOverlap = Math.min(Math.min(overlapLeft, overlapRight),
Math.min(overlapTop, overlapBottom));
if (minOverlap == overlapLeft) normal = new Vec2(-1, 0);
else if (minOverlap == overlapRight) normal = new Vec2(1, 0);
else if (minOverlap == overlapTop) normal = new Vec2(0, 1);
else normal = new Vec2(0, -1);
// 相对速度
Vec2 relVel = a.velocity.sub(b.velocity);
double velAlongNormal = relVel.dot(normal);
// 若物体正在分离，不处理
if (velAlongNormal > 0) return false;
// 弹性系数（0为完全非弹性，1为完全弹性）
double restitution = 0.4;
double impulseScalar = -(1 + restitution) * velAlongNormal;
impulseScalar /= (1.0 / a.mass + 1.0 / b.mass);
Vec2 impulse = normal.mul(impulseScalar);
a.velocity = a.velocity.add(impulse.mul(1.0 / a.mass));
b.velocity = b.velocity.sub(impulse.mul(1.0 / b.mass));
// 位置分离，防止粘连
double percent = 0.8; // penetration percentage to correct
Vec2 correction = normal.mul(minOverlap * percent);
a.position = a.position.sub(correction.mul(1.0 / a.mass));
b.position = b.position.add(correction.mul(1.0 / b.mass));
// 计算冲击力并施加伤害
double impact = Math.abs(impulseScalar);
a.takeDamage(impact);
b.takeDamage(impact);
return true;
}
}
三、蒙特卡洛射击优化
3.1 问题建模
玩家的决策空间是一个二维连续空间：（发射角度 θ，初速度 v）。直接遍历所有组合代价极高。蒙特卡洛方法通过随机采样大量 (θ, v) 组合，模拟飞行轨迹，统计摧毁猪的数量与剩余结构稳定度，从而逼近最优解。
/**
* 射击方案
*/
class Shot {
double angle; // 弧度
double speed; // 米/秒
double score; // 模拟得分
Shot(double angle, double speed) {
this.angle = angle;
this.speed = speed;
this.score = -1;
}
}
/**
* 蒙特卡洛射击优化器
* 在有限的模拟步数内，通过随机采样寻找最佳发射参数
*/
class MonteCarloOptimizer {
// 角度搜索范围：0 ~ 80度（避免朝地面发射）
static final double ANGLE_MIN = Math.toRadians(5);
static final double ANGLE_MAX = Math.toRadians(80);
// 速度搜索范围
static final double SPEED_MIN = 5.0;
static final double SPEED_MAX = 25.0;
// 每次评估的最大模拟时长（秒）
static final double MAX_SIM_TIME = 5.0;
// 随机数生成器
private final Random random;
MonteCarloOptimizer(long seed) {
this.random = new Random(seed);
}
/**
* 寻找最优射击方案
* @param worldTemplate 初始世界状态（将被复制用于每次模拟）
* @param iterations 蒙特卡洛采样次数
* @return 最优射击方案
*/
Shot findBestShot(WorldSnapshot worldTemplate, int iterations) {
Shot bestShot = null;
double bestScore = Double.NEGATIVE_INFINITY;
for (int i = 0; i < iterations; i++) {
double angle = ANGLE_MIN + random.nextDouble() * (ANGLE_MAX - ANGLE_MIN);
double speed = SPEED_MIN + random.nextDouble() * (SPEED_MAX - SPEED_MIN);
Shot shot = new Shot(angle, speed);
// 复制世界进行独立模拟，避免污染原状态
PhysicsWorld simWorld = worldTemplate.cloneWorld();
double score = evaluateShot(simWorld, shot);
shot.score = score;
if (score > bestScore) {
bestScore = score;
bestShot = shot;
}
}
return bestShot;
}
3.2 评分函数设计
评分是蒙特卡洛的核心。好的评分函数应同时激励：消灭更多猪、用更少鸟、造成更大结构破坏、更快完成。
/**
* 评估一次射击的得分
* 评分维度：
* 1. 消灭猪的数量（权重最高）
* 2. 造成的总伤害（结构破坏度）
* 3. 飞行效率（水平位移奖励）
* 4. 时间惩罚（飞太久说明轨迹低效）
*/
double evaluateShot(PhysicsWorld world, Shot shot) {
// 找到待发射的小鸟（假设第一个未被销毁的鸟是当前鸟）
Bird bird = null;
for (Entity e : world.getEntities()) {
if (e.type == Entity.Type.BIRD && !e.destroyed) {
bird = (Bird) e;
break;
}
}
if (bird == null) return Double.NEGATIVE_INFINITY;
// 执行发射
bird.launch(shot.angle, shot.speed);
int initialPigs = countPigs(world);
double totalDamage = 0;
double maxX = bird.position.x;
int steps = 0;
int maxSteps = (int) (MAX_SIM_TIME / PhysicsWorld.DT);
// 物理模拟直到超时或鸟停止
for (; steps < maxSteps; steps++) {
world.step();
if (bird.destroyed) break;
maxX = Math.max(maxX, bird.position.x);
// 累计所有实体受到的伤害（通过HP下降近似）
totalDamage += collectDamage(world);
}
int remainingPigs = countPigs(world);
int pigsKilled = initialPigs - remainingPigs;
// 综合评分
double score = pigsKilled * 1000.0 // 杀猪奖励
+ totalDamage * 10.0 // 破坏奖励
+ maxX * 2.0 // 射程奖励
- steps * 0.1; // 时间惩罚
return score;
}
private int countPigs(PhysicsWorld world) {
int count = 0;
for (Entity e : world.getEntities()) {
if (e.type == Entity.Type.PIG && !e.destroyed) count++;
}
return count;
}
private double collectDamage(PhysicsWorld world) {
// 简化：统计当前世界中被销毁的非鸟实体数量作为破坏指标
double dmg = 0;
for (Entity e : world.getEntities()) {
if (e.type != Entity.Type.BIRD && e.destroyed) dmg += e.mass;
}
return dmg;
}
}
四、世界快照与克隆
为了让蒙特卡洛优化器能在不污染真实游戏状态的前提下反复试验，需要实现世界的深拷贝。
/**
* 世界快照
* 保存某一时刻的完整实体状态，支持克隆出独立可运行的物理世界
*/
class WorldSnapshot {
private final List<Entity> entities;
WorldSnapshot(List<Entity> entities) {
this.entities = new ArrayList<>();
for (Entity e : entities) {
this.entities.add(cloneEntity(e));
}
}
private Entity cloneEntity(Entity e) {
Vec2 pos = new Vec2(e.position.x, e.position.y);
Vec2 vel = new Vec2(e.velocity.x, e.velocity.y);
switch (e.type) {
case BIRD:
Bird b = new Bird(pos, e.mass, e.halfWidth);
b.velocity = vel;
b.hp = ((Bird) e).hp;
return b;
case PIG:
Pig p = new Pig(pos, e.mass, e.halfWidth);
p.velocity = vel;
p.hp = ((Pig) e).hp;
return p;
case WOOD_BLOCK:
WoodBlock w = new WoodBlock(pos, e.mass, e.halfWidth, e.halfHeight);
w.velocity = vel;
w.hp = ((WoodBlock) e).hp;
return w;
default:
throw new IllegalStateException("Unknown entity type");
}
}
PhysicsWorld cloneWorld() {
PhysicsWorld w = new PhysicsWorld();
for (Entity e : entities) {
w.addEntity(cloneEntity(e));
}
return w;
}
}
五、完整主程序与场景测试
import java.util.*;
/**
* 愤怒的小鸟简化版主程序
* 构建一个经典场景：弹弓在左侧，右侧堆叠木块与猪
*/
public class AngryBirdsAI {
public static void main(String[] args) {
// 构建初始世界
PhysicsWorld world = new PhysicsWorld();
// 弹弓位置作为参考原点 (0, 2)
Vec2 slingPos = new Vec2(0, 2.0);
// 放置待发射的小鸟
Bird redBird = new Bird(new Vec2(slingPos.x, slingPos.y), 1.0, 0.3);
world.addEntity(redBird);
// 搭建敌方阵地：三层木块 + 中间夹猪
// 底层平台
world.addEntity(new WoodBlock(new Vec2(8.0, 0.5), 5.0, 1.5, 0.5));
world.addEntity(new WoodBlock(new Vec2(11.0, 0.5), 5.0, 1.5, 0.5));
// 中层立柱
world.addEntity(new WoodBlock(new Vec2(8.0, 1.5), 2.0, 0.3, 0.5));
world.addEntity(new WoodBlock(new Vec2(11.0, 1.5), 2.0, 0.3, 0.5));
// 中层平台
world.addEntity(new WoodBlock(new Vec2(9.5, 2.0), 5.0, 2.0, 0.3));
// 放置猪
world.addEntity(new Pig(new Vec2(9.5, 2.6), 2.0, 0.4));
world.addEntity(new Pig(new Vec2(8.0, 1.1), 2.0, 0.4));
// 顶层装饰块
world.addEntity(new WoodBlock(new Vec2(9.5, 2.8), 1.5, 0.4, 0.3));
System.out.println("=== 初始场景 ===");
printWorld(world);
// 创建世界快照
WorldSnapshot snapshot = new WorldSnapshot(world.getEntities());
// 蒙特卡洛优化：采样5000次寻找最优射击参数
System.out.println("\n=== 开始蒙特卡洛优化（5000次采样）===");
MonteCarloOptimizer optimizer = new MonteCarloOptimizer(System.currentTimeMillis());
Shot best = optimizer.findBestShot(snapshot, 5000);
System.out.printf("最优方案：角度=%.2f度, 速度=%.2f m/s, 预估得分=%.2f%n",
Math.toDegrees(best.angle), best.speed, best.score);
// 在真实世界中执行最优射击
System.out.println("\n=== 执行最优射击 ===");
redBird.launch(best.angle, best.speed);
// 模拟5秒
int totalSteps = (int) (5.0 / PhysicsWorld.DT);
for (int i = 0; i < totalSteps; i++) {
world.step();
if (redBird.destroyed) {
System.out.println("小鸟已撞击销毁，模拟结束于第 " + i + " 步");
break;
}
}
System.out.println("\n=== 最终场景 ===");
printWorld(world);
}
static void printWorld(PhysicsWorld world) {
for (Entity e : world.getEntities()) {
String status = e.destroyed ? "[已销毁]" : "";
System.out.printf("%s %s pos=%s vel=%s %s%n",
e.type, status, e.position, e.velocity,
e.type == Entity.Type.PIG ? "HP=" + ((Pig)e).hp :
e.type == Entity.Type.BIRD ? "HP=" + ((Bird)e).hp :
e.type == Entity.Type.WOOD_BLOCK ? "HP=" + ((WoodBlock)e).hp : "");
}
}
}
六、复杂度分析与总结
| 模块 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 物理单步积分 | O(n) | O(n) | n为实体数量，每实体一次向量更新 |
| 碰撞检测 | O(n²) | O(1) | 暴力遍历所有实体对，适合小规模场景 |
| 蒙特卡洛采样 | O(k × n² × t) | O(n) | k为采样次数，t为每轮最大步数 |
本文实现了一个可独立运行的愤怒的小鸟简化物理引擎，核心包含三大算法模块：
- 抛物线物理模拟：基于显式欧拉积分，精确追踪小鸟在重力场中的飞行轨迹。
- AABB碰撞检测：以轴对齐包围盒实现快速碰撞粗判，配合冲量模型完成反弹与伤害计算。
- 蒙特卡洛射击优化：在角度-速度二维参数空间中随机采样，通过评分函数自动搜索最优发射策略。
读者可在此基础上继续扩展：引入更精确的圆形/多边形碰撞、添加旋转与角动量、用遗传算法或模拟退火替代纯随机采样、甚至训练神经网络进行端到端射击决策。
