引言
飞机大战是经典竖版射击游戏，屏幕中同时存在大量子弹、敌机和道具，频繁的创建销毁对象会导致严重的GC压力。本文用Java实现飞机大战的核心系统，重点讲解对象池模式复用游戏对象，以及空间哈希（Spatial Hashing）算法将碰撞检测复杂度从O(n²)降到O(1)级别。
核心算法概览
- 对象池模式：预创建对象池，避免运行时频繁new对象和GC
- 空间哈希：将屏幕划分为均匀网格，仅检测同网格内的碰撞对
- 敌机行为模式：正弦波移动、追踪射击、编队变换三种AI模式
对象池模式实现
import java.util.*;
/**
* 泛型对象池，支持任意可复用对象
*/
public class ObjectPool<T> {
private Queue<T> pool;
private int capacity;
private ObjectFactory<T> factory;
public interface ObjectFactory<T> {
T create();
void reset(T obj); // 归还前重置状态
}
public ObjectPool(int capacity, ObjectFactory<T> factory) {
this.capacity = capacity;
this.factory = factory;
this.pool = new ArrayDeque<>(capacity);
// 预创建对象
for (int i = 0; i < capacity; i++) {
pool.offer(factory.create());
}
}
/**
* 从池中获取对象，池空时创建新对象（兜底）
*/
public T acquire() {
T obj = pool.poll();
if (obj == null) {
obj = factory.create(); // 池耗尽时动态创建
}
return obj;
}
/**
* 归还对象到池中
*/
public void release(T obj) {
if (obj != null && pool.size() < capacity) {
factory.reset(obj);
pool.offer(obj);
}
}
public int available() { return pool.size(); }
}
/**
* 子弹实体
*/
class Bullet {
double x, y;
double vx, vy;
boolean active;
int damage;
boolean isPlayerBullet; // 区分玩家子弹和敌机子弹
void reset() {
active = false;
x = y = vx = vy = 0;
damage = 0;
}
}
/**
* 敌机实体
*/
class EnemyPlane {
double x, y;
double speed;
int hp;
boolean active;
int behaviorType; // 0=直线下落, 1=正弦波, 2=追踪
double behaviorTimer;
double shootInterval;
double lastShotTime;
int score;
void reset() {
active = false;
x = y = speed = 0;
hp = 0;
behaviorType = 0;
}
}
空间哈希碰撞检测
将屏幕划分为固定大小的网格单元，每个对象只注册到其所在的网格，碰撞检测时只检查同网格和相邻网格内的对象。
import java.util.*;
/**
* 空间哈希网格，用于高效碰撞检测
*/
public class SpatialHash {
private int cellSize; // 网格单元边长（通常取最大对象直径）
private Map<Long, List<GameObject>> grid;
public SpatialHash(int cellSize) {
this.cellSize = cellSize;
this.grid = new HashMap<>();
}
/**
* 将坐标映射到网格单元键
* 使用long打包两个int避免哈希冲突
*/
private long getKey(int cellX, int cellY) {
return ((long) cellX << 32) | (cellY & 0xFFFFFFFFL);
}
/**
* 插入对象到空间哈希
*/
public void insert(GameObject obj) {
int minCellX = (int) (obj.x / cellSize);
int maxCellX = (int) ((obj.x + obj.width) / cellSize);
int minCellY = (int) (obj.y / cellSize);
int maxCellY = (int) ((obj.y + obj.height) / cellSize);
for (int cx = minCellX; cx <= maxCellX; cx++) {
for (int cy = minCellY; cy <= maxCellY; cy++) {
long key = getKey(cx, cy);
grid.computeIfAbsent(key, k -> new ArrayList<>()).add(obj);
}
}
}
/**
* 查询与指定矩形可能相交的所有对象
*/
public List<GameObject> query(double x, double y, double w, double h) {
Set<GameObject> result = new HashSet<>();
int minCellX = (int) (x / cellSize);
int maxCellX = (int) ((x + w) / cellSize);
int minCellY = (int) (y / cellSize);
int maxCellY = (int) ((y + h) / cellSize);
for (int cx = minCellX; cx <= maxCellX; cx++) {
for (int cy = minCellY; cy <= maxCellY; cy++) {
long key = getKey(cx, cy);
List<GameObject> cell = grid.get(key);
if (cell != null) result.addAll(cell);
}
}
return new ArrayList<>(result);
}
/**
* 清空所有网格，每帧开始前调用
*/
public void clear() {
grid.clear();
}
// 游戏对象基类
static class GameObject {
double x, y, width, height;
boolean active;
}
}
游戏管理器与碰撞系统
public class GameManager {
private ObjectPool<Bullet> bulletPool;
private ObjectPool<EnemyPlane> enemyPool;
private List<Bullet> activeBullets;
private List<EnemyPlane> activeEnemies;
private SpatialHash spatialHash;
private PlayerPlane player;
private double screenWidth = 480, screenHeight = 800;
private int cellSize = 64; // 空间哈希单元大小
public GameManager() {
// 初始化对象池
bulletPool = new ObjectPool<>(200, new ObjectPool.ObjectFactory<>() {
@Override
public Bullet create() { return new Bullet(); }
@Override
public void reset(Bullet b) { b.reset(); }
});
enemyPool = new ObjectPool<>(50, new ObjectPool.ObjectFactory<>() {
@Override
public EnemyPlane create() { return new EnemyPlane(); }
@Override
public void reset(EnemyPlane e) { e.reset(); }
});
activeBullets = new ArrayList<>();
activeEnemies = new ArrayList<>();
spatialHash = new SpatialHash(cellSize);
player = new PlayerPlane(screenWidth / 2, screenHeight - 100);
}
/**
* 生成玩家子弹
*/
public void spawnPlayerBullet(double x, double y) {
Bullet b = bulletPool.acquire();
b.x = x; b.y = y;
b.vx = 0; b.vy = -8; // 向上飞行
b.active = true;
b.damage = 1;
b.isPlayerBullet = true;
activeBullets.add(b);
}
/**
* 生成敌机
*/
public void spawnEnemy(int type) {
EnemyPlane e = enemyPool.acquire();
e.x = Math.random() * (screenWidth - 40) + 20;
e.y = -40;
e.speed = 2 + Math.random() * 2;
e.hp = (type == 0) ? 1 : (type == 1) ? 3 : 5;
e.active = true;
e.behaviorType = type;
e.behaviorTimer = 0;
e.shootInterval = 1500 + Math.random() * 1000;
e.lastShotTime = 0;
e.score = (type + 1) * 100;
activeEnemies.add(e);
}
/**
* 游戏主循环
*/
public void update(double currentTime) {
// 1. 更新空间哈希
spatialHash.clear();
// 注册玩家
spatialHash.insert(player);
// 注册所有敌机
for (EnemyPlane e : activeEnemies) {
if (e.active) spatialHash.insert(e);
}
// 注册所有子弹
for (Bullet b : activeBullets) {
if (b.active) spatialHash.insert(b);
}
// 2. 更新所有对象位置
updateBullets();
updateEnemies(currentTime);
player.update();
// 3. 碰撞检测
checkCollisions(currentTime);
// 4. 回收越界/死亡对象
recycleObjects();
}
private void updateBullets() {
for (Bullet b : activeBullets) {
if (!b.active) continue;
b.x += b.vx;
b.y += b.vy;
// 越界标记
if (b.y < -10 || b.y > screenHeight + 10 ||
b.x < -10 || b.x > screenWidth + 10) {
b.active = false;
}
}
}
private void updateEnemies(double currentTime) {
for (EnemyPlane e : activeEnemies) {
if (!e.active) continue;
// 行为模式更新
e.behaviorTimer += 0.016; // 假设60FPS
switch (e.behaviorType) {
case 0: // 直线下落
e.y += e.speed;
break;
case 1: // 正弦波移动
e.y += e.speed;
e.x += Math.sin(e.behaviorTimer * 3) * 2;
break;
case 2: // 追踪玩家
e.y += e.speed * 0.7;
if (e.x < player.x) e.x += 1;
else if (e.x > player.x) e.x -= 1;
break;
}
// 敌机射击
if (currentTime - e.lastShotTime > e.shootInterval) {
spawnEnemyBullet(e);
e.lastShotTime = currentTime;
}
}
}
private void spawnEnemyBullet(EnemyPlane e) {
Bullet b = bulletPool.acquire();
b.x = e.x + 20; // 敌机中心
b.y = e.y + 40;
b.vx = 0; b.vy = 4; // 向下飞行
b.active = true;
b.damage = 1;
b.isPlayerBullet = false;
activeBullets.add(b);
}
/**
* 使用空间哈希进行高效碰撞检测
*/
private void checkCollisions(double currentTime) {
// 玩家子弹 vs 敌机
for (Bullet b : activeBullets) {
if (!b.active || !b.isPlayerBullet) continue;
// 空间哈希查询子弹周围的潜在碰撞对象
List<SpatialHash.GameObject> candidates =
spatialHash.query(b.x, b.y, 8, 16);
for (SpatialHash.GameObject obj : candidates) {
if (obj instanceof EnemyPlane) {
EnemyPlane e = (EnemyPlane) obj;
if (!e.active) continue;
// AABB碰撞检测
if (checkAABBCollision(b.x, b.y, 8, 16,
e.x, e.y, 40, 40)) {
e.hp -= b.damage;
b.active = false;
if (e.hp <= 0) {
e.active = false;
player.addScore(e.score);
}
break; // 一颗子弹只打一架敌机
}
}
}
}
// 敌机子弹 vs 玩家
for (Bullet b : activeBullets) {
if (!b.active || b.isPlayerBullet) continue;
if (checkAABBCollision(b.x, b.y, 8, 16,
player.x, player.y, 40, 40)) {
b.active = false;
player.takeDamage(b.damage);
}
}
// 敌机 vs 玩家（撞击）
for (EnemyPlane e : activeEnemies) {
if (!e.active) continue;
if (checkAABBCollision(e.x, e.y, 40, 40,
player.x, player.y, 40, 40)) {
e.active = false;
player.takeDamage(3);
}
}
}
/**
* AABB矩形碰撞检测
*/
private boolean checkAABBCollision(double x1, double y1, double w1, double h1,
double x2, double y2, double w2, double h2) {
return x1 < x2 + w2 && x1 + w1 > x2 &&
y1 < y2 + h2 && y1 + h1 > y2;
}
/**
* 回收死亡/越界对象到对象池
*/
private void recycleObjects() {
// 回收子弹
Iterator<Bullet> bit = activeBullets.iterator();
while (bit.hasNext()) {
Bullet b = bit.next();
if (!b.active) {
bit.remove();
bulletPool.release(b);
}
}
// 回收敌机
Iterator<EnemyPlane> eit = activeEnemies.iterator();
while (eit.hasNext()) {
EnemyPlane e = eit.next();
if (!e.active || e.y > screenHeight + 50) {
eit.remove();
enemyPool.release(e);
}
}
}
public int getScore() { return player.getScore(); }
public boolean isGameOver() { return !player.isAlive(); }
}
/**
* 玩家飞机
*/
class PlayerPlane extends SpatialHash.GameObject {
private int hp = 5;
private int score = 0;
private double speed = 6;
PlayerPlane(double x, double y) {
this.x = x; this.y = y;
this.width = 40; this.height = 40;
this.active = true;
}
void update() {
// 边界限制
if (x < 0) x = 0;
if (x > 440) x = 440;
if (y < 0) y = 0;
if (y > 760) y = 760;
}
void moveLeft() { x -= speed; }
void moveRight() { x += speed; }
void moveUp() { y -= speed; }
void moveDown() { y += speed; }
void takeDamage(int dmg) { hp -= dmg; }
void addScore(int s) { score += s; }
boolean isAlive() { return hp > 0; }
int getScore() { return score; }
}
主程序入口
public class AirplaneGame {
public static void main(String[] args) {
GameManager manager = new GameManager();
double currentTime = 0;
// 生成一些敌机
for (int i = 0; i < 5; i++) {
manager.spawnEnemy(i % 3);
}
// 模拟游戏运行300帧（约5秒）
for (int frame = 0; frame < 300; frame++) {
currentTime += 16.67; // 60FPS
// 模拟玩家射击
if (frame % 10 == 0) {
manager.spawnPlayerBullet(240, 700);
}
// 每60帧生成新敌机
if (frame % 60 == 0) {
manager.spawnEnemy(frame / 60 % 3);
}
manager.update(currentTime);
if (frame % 60 == 0) {
System.out.println("Frame " + frame +
", Score: " + manager.getScore() +
", GameOver: " + manager.isGameOver());
}
}
}
}
复杂度分析
| 检测方式 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 暴力O(n²) | O(n²) | O(n) | 对象极少时 |
| 空间哈希 | O(n) 平均，O(n²) 最坏 | O(n) | 大量对象均匀分布 |
| 四叉树 | O(n log n) | O(n) | 对象密度差异大 |
空间哈希的核心优势在于：当对象均匀分布时，每个网格单元内的对象数量是常数，查询和插入都接近O(1)。对于飞机大战这种弹幕密集但均匀分布的场景，空间哈希是最佳选择。
总结
本文以飞机大战为载体，讲解了对象池模式避免GC压力、空间哈希将碰撞检测复杂度从O(n²)优化到O(n)。读者可以扩展：
– 实现四叉树或均匀网格替代空间哈希，适应更复杂的密度分布
– 加入道具系统（炸弹清屏、双倍火力等），使用对象池统一管理
– 实现敌机BOSS的复杂行为树和弹幕模式
