小行星（Asteroids）是一款经典的街机射击游戏。玩家操控飞船在太空中飞行，击碎不断飞来的小行星。大行星被击中后分裂为更小的碎片，直到完全消失。本文用Java实现小行星游戏的核心引擎，讲解四叉树空间划分加速碰撞检测、刚体运动模拟与贪心射击策略，包含完整代码与复杂度分析。
游戏核心机制
小行星游戏涉及多个经典的计算几何与物理模拟问题：
– 刚体运动：每个实体具有位置、速度、角速度，遵循牛顿运动定律
– 碰撞检测：圆形物体间的距离检测，以及射线（子弹）与圆的相交检测
– 空间划分：当实体数量增加时，朴素的 $O(n^2)$ 碰撞检测效率低下，需引入空间加速结构
– 分裂逻辑：大行星被击中后按随机方向分裂为2-3个更小的子行星
四叉树空间划分
四叉树（Quadtree）是二维空间划分的经典数据结构，特别适合处理稀疏分布的动态物体：
– 根节点覆盖整个游戏世界
– 每个节点最多包含 $k$ 个物体（容量阈值）
– 超过容量时节点分裂为4个子象限
– 碰撞检测时只需检查同一节点及相邻节点中的物体
平均情况下，四叉树将碰撞检测复杂度从 $O(n^2)$ 降至 $O(n \log n)$，在物体均匀分布时效果最佳。
核心代码实现
import java.util.*;
/**
* 二维向量与几何工具
*/
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 length() { return Math.sqrt(x * x + y * y); }
double dot(Vec2 v) { return x * v.x + y * v.y; }
Vec2 normalize() { double len = length(); return len > 0 ? new Vec2(x/len, y/len) : new Vec2(0,0); }
Vec2 rotate(double angle) {
double cos = Math.cos(angle), sin = Math.sin(angle);
return new Vec2(x * cos - y * sin, x * sin + y * cos);
}
static double distance(Vec2 a, Vec2 b) { return a.sub(b).length(); }
}
/**
* 边界框（AABB）
*/
class AABB {
double minX, minY, maxX, maxY;
AABB(double minX, double minY, double maxX, double maxY) {
this.minX = minX; this.minY = minY; this.maxX = maxX; this.maxY = maxY;
}
boolean contains(Vec2 p) {
return p.x >= minX && p.x <= maxX && p.y >= minY && p.y <= maxY;
}
boolean intersects(AABB other) {
return !(maxX < other.minX || minX > other.maxX || maxY < other.minY || minY > other.maxY);
}
double centerX() { return (minX + maxX) / 2; }
double centerY() { return (minY + maxY) / 2; }
}
/**
* 游戏实体基类
*/
abstract class Entity {
Vec2 position;
Vec2 velocity;
double radius;
boolean alive;
Entity(Vec2 pos, Vec2 vel, double r) {
this.position = pos;
this.velocity = vel;
this.radius = r;
this.alive = true;
}
void update(double dt, double worldW, double worldH) {
position = position.add(velocity.mul(dt));
// 环绕边界
if (position.x < 0) position.x += worldW;
if (position.x > worldW) position.x -= worldW;
if (position.y < 0) position.y += worldH;
if (position.y > worldH) position.y -= worldH;
}
AABB getBounds() {
return new AABB(position.x - radius, position.y - radius,
position.x + radius, position.y + radius);
}
boolean collidesWith(Entity other) {
return Vec2.distance(position, other.position) < (radius + other.radius);
}
}
/**
* 小行星实体
*/
class Asteroid extends Entity {
enum Size { LARGE(30), MEDIUM(20), SMALL(10); }
Size size;
double rotationSpeed;
Asteroid(Vec2 pos, Vec2 vel, Size size) {
super(pos, vel, size.radius);
this.size = size;
this.rotationSpeed = (Math.random() - 0.5) * 2.0;
}
List<Asteroid> split() {
List<Asteroid> fragments = new ArrayList<>();
if (size == Size.LARGE) {
for (int i = 0; i < 2; i++) {
Vec2 newVel = velocity.add(new Vec2(Math.random()-0.5, Math.random()-0.5).normalize().mul(50));
fragments.add(new Asteroid(new Vec2(position.x, position.y), newVel, Size.MEDIUM));
}
} else if (size == Size.MEDIUM) {
for (int i = 0; i < 3; i++) {
Vec2 newVel = velocity.add(new Vec2(Math.random()-0.5, Math.random()-0.5).normalize().mul(80));
fragments.add(new Asteroid(new Vec2(position.x, position.y), newVel, Size.SMALL));
}
}
return fragments;
}
int getScore() {
return switch(size) { case LARGE -> 20; case MEDIUM -> 50; case SMALL -> 100; };
}
}
/**
* 子弹实体
*/
class Bullet extends Entity {
double lifetime;
static final double MAX_LIFE = 2.0; // 子弹存活2秒
Bullet(Vec2 pos, Vec2 vel) {
super(pos, vel, 2);
this.lifetime = 0;
}
@Override
void update(double dt, double worldW, double worldH) {
super.update(dt, worldW, worldH);
lifetime += dt;
if (lifetime > MAX_LIFE) alive = false;
}
}
/**
* 四叉树节点
*/
class QuadTree {
static final int MAX_OBJECTS = 4;
static final int MAX_LEVELS = 5;
int level;
AABB bounds;
List<Entity> objects;
QuadTree[] nodes; // 4个子节点: NW, NE, SW, SE
QuadTree(int level, AABB bounds) {
this.level = level;
this.bounds = bounds;
this.objects = new ArrayList<>();
this.nodes = null;
}
void clear() {
objects.clear();
if (nodes != null) {
for (QuadTree node : nodes) node.clear();
nodes = null;
}
}
void split() {
double midX = bounds.centerX();
double midY = bounds.centerY();
nodes = new QuadTree[4];
nodes[0] = new QuadTree(level + 1, new AABB(bounds.minX, bounds.minY, midX, midY)); // NW
nodes[1] = new QuadTree(level + 1, new AABB(midX, bounds.minY, bounds.maxX, midY)); // NE
nodes[2] = new QuadTree(level + 1, new AABB(bounds.minX, midY, midX, bounds.maxY)); // SW
nodes[3] = new QuadTree(level + 1, new AABB(midX, midY, bounds.maxX, bounds.maxY)); // SE
}
/**
* 获取实体所属的象限索引，若跨越边界返回-1
*/
int getIndex(Entity e) {
double midX = bounds.centerX();
double midY = bounds.centerY();
AABB b = e.getBounds();
boolean top = b.maxY < midY;
boolean bottom = b.minY > midY;
if (b.maxX < midX) {
if (top) return 0; // NW
if (bottom) return 2; // SW
} else if (b.minX > midX) {
if (top) return 1; // NE
if (bottom) return 3; // SE
}
return -1; // 跨越边界，留在当前节点
}
void insert(Entity e) {
if (nodes != null) {
int index = getIndex(e);
if (index != -1) {
nodes[index].insert(e);
return;
}
}
objects.add(e);
if (objects.size() > MAX_OBJECTS && level < MAX_LEVELS) {
if (nodes == null) split();
Iterator<Entity> it = objects.iterator();
while (it.hasNext()) {
Entity obj = it.next();
int index = getIndex(obj);
if (index != -1) {
nodes[index].insert(obj);
it.remove();
}
}
}
}
/**
* 获取可能与给定实体发生碰撞的所有候选实体
*/
List<Entity> retrieve(Entity e) {
List<Entity> candidates = new ArrayList<>();
retrieveRecursive(e, candidates);
return candidates;
}
private void retrieveRecursive(Entity e, List<Entity> candidates) {
if (nodes != null) {
int index = getIndex(e);
if (index != -1) {
nodes[index].retrieveRecursive(e, candidates);
} else {
// 跨越边界，需要检查所有子节点
for (QuadTree node : nodes) node.retrieveRecursive(e, candidates);
}
}
candidates.addAll(objects);
}
}
/**
* 游戏主引擎
*/
public class AsteroidsEngine {
private static final double WORLD_W = 800;
private static final double WORLD_H = 600;
private static final double DT = 1.0 / 60.0;
private List<Asteroid> asteroids;
private List<Bullet> bullets;
private int score;
private QuadTree quadTree;
private Random random;
public AsteroidsEngine() {
this.asteroids = new ArrayList<>();
this.bullets = new ArrayList<>();
this.score = 0;
this.quadTree = new QuadTree(0, new AABB(0, 0, WORLD_W, WORLD_H));
this.random = new Random();
spawnAsteroids(5);
}
void spawnAsteroids(int count) {
for (int i = 0; i < count; i++) {
Vec2 pos = new Vec2(random.nextDouble() * WORLD_W, random.nextDouble() * WORLD_H);
Vec2 vel = new Vec2(random.nextDouble() - 0.5, random.nextDouble() - 0.5).normalize().mul(30 + random.nextDouble() * 50);
asteroids.add(new Asteroid(pos, vel, Asteroid.Size.LARGE));
}
}
/**
* 游戏主循环更新
*/
void update() {
// 更新所有实体位置
for (Asteroid a : asteroids) a.update(DT, WORLD_W, WORLD_H);
for (Bullet b : bullets) b.update(DT, WORLD_W, WORLD_H);
// 移除死亡实体
bullets.removeIf(b -> !b.alive);
// 构建四叉树
quadTree.clear();
for (Asteroid a : asteroids) if (a.alive) quadTree.insert(a);
for (Bullet b : bullets) if (b.alive) quadTree.insert(b);
// 碰撞检测：子弹 vs 小行星
List<Asteroid> newAsteroids = new ArrayList<>();
for (Bullet bullet : bullets) {
if (!bullet.alive) continue;
List<Entity> candidates = quadTree.retrieve(bullet);
for (Entity e : candidates) {
if (e instanceof Asteroid && e.alive && bullet.collidesWith(e)) {
Asteroid asteroid = (Asteroid) e;
asteroid.alive = false;
bullet.alive = false;
score += asteroid.getScore();
newAsteroids.addAll(asteroid.split());
break;
}
}
}
asteroids.addAll(newAsteroids);
asteroids.removeIf(a -> !a.alive);
// 若所有小行星被消灭，生成新一波
if (asteroids.isEmpty()) {
spawnAsteroids(5 + score / 500);
}
}
/**
* 发射子弹（朝向鼠标位置或最近小行星的贪心策略）
*/
void fireBullet(Vec2 shipPos, Vec2 targetPos) {
Vec2 dir = targetPos.sub(shipPos).normalize();
Vec2 bulletVel = dir.mul(400); // 子弹速度400单位/秒
Vec2 bulletPos = shipPos.add(dir.mul(15)); // 从飞船前方射出
bullets.add(new Bullet(bulletPos, bulletVel));
}
/**
* 贪心射击策略：选择距离最近且威胁最大的小行星作为目标
*/
Asteroid findBestTarget(Vec2 shipPos) {
Asteroid best = null;
double bestScore = Double.MAX_VALUE;
for (Asteroid a : asteroids) {
double dist = Vec2.distance(shipPos, a.position);
// 评分 = 距离 / 尺寸权重，小行星权重更高（威胁更大）
double threatScore = dist / (a.size.radius / 10.0);
if (threatScore < bestScore) {
bestScore = threatScore;
best = a;
}
}
return best;
}
public int getScore() { return score; }
public List<Asteroid> getAsteroids() { return asteroids; }
public List<Bullet> getBullets() { return bullets; }
public static void main(String[] args) {
AsteroidsEngine engine = new AsteroidsEngine();
Vec2 shipPos = new Vec2(WORLD_W / 2, WORLD_H / 2);
// 模拟100帧
for (int frame = 0; frame < 100; frame++) {
// AI自动瞄准最近目标射击
Asteroid target = engine.findBestTarget(shipPos);
if (target != null && frame % 10 == 0) {
engine.fireBullet(shipPos, target.position);
}
engine.update();
System.out.printf("Frame %d: Asteroids=%d, Bullets=%d, Score=%d%n",
frame, engine.getAsteroids().size(), engine.getBullets().size(), engine.getScore());
}
}
}
复杂度分析
四叉树插入：平均 $O(\log n)$，最坏 $O(n)$（所有物体集中在同一区域）。
碰撞查询：平均检索到 $O(\log n + k)$ 个候选物体，$k$ 为同一区域物体数。
完整碰撞检测：对比朴素 $O(n^2)$，四叉树优化后在均匀分布场景下为 $O(n \log n)$。
子弹-行星碰撞：对每颗子弹查询四叉树并做精确圆碰撞检测，总复杂度 $O(b \cdot (\log n + k))$，$b$ 为子弹数。
碰撞检测优化对比
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 暴力检测 | $O(n^2)$ | $O(1)$ | $n < 50$ |
| 四叉树 | $O(n \log n)$ | $O(n)$ | 二维均匀分布 |
| 均匀网格 | $O(n)$ | $O(n)$ | 场景大小固定 |
| KD树 | $O(n \log n)$ | $O(n)$ | 高维稀疏数据 |
小行星游戏场景尺寸固定、物体均匀分布，均匀网格（Uniform Grid） 在实际工程中往往比四叉树更简单高效。但四叉树在动态边界和不均匀分布场景中更具适应性。
物理模拟扩展
当前实现采用简单的欧拉积分。进阶方案包括：
– Verlet积分：更好的能量守恒特性
– 刚体旋转：为小行星添加自旋角速度，使碰撞响应更真实
– 冲量响应：基于动量守恒的碰撞反弹计算
总结
小行星游戏是计算机图形学与实时物理模拟的经典教学案例。本文通过Java实现了完整的游戏引擎，重点展示了四叉树空间划分如何将碰撞检测从 $O(n^2)$ 优化至 $O(n \log n)$，以及基于贪心策略的自动瞄准AI。该框架可扩展为更复杂的太空射击游戏或作为学习空间数据结构的实践项目。
