游戏概述与算法思路
大鱼吃小鱼是一款经典的休闲益智游戏。玩家控制一条小鱼在海洋中游动，通过吃掉比自己小的鱼来成长，同时躲避比自己大的鱼。随着体积的增长，玩家可以捕食更大的目标，最终成为海洋霸主。
从算法角度看，这款游戏的核心挑战在于：
- 大量实体的碰撞检测：海洋中同时存在数十条鱼，每帧都需要检测每条鱼是否与其他鱼发生碰撞。暴力 $O(n^2)$ 的检测方式在实体数量增加时会急剧退化。
- 最优进食决策：面对多个可捕食的目标，如何选择最优路径以最大化成长效率。
- 敌人AI行为：其他鱼的自主移动、追逐与逃跑策略。
本文将使用四叉树（Quadtree）空间划分算法解决高效碰撞检测问题，并采用贪心策略实现最优进食决策，提供完整的Java实现。
四叉树空间划分算法
算法原理
四叉树是一种树形数据结构，用于对二维空间进行递归划分。每个节点代表一个矩形区域，并包含四个子节点（左上、右上、左下、右下）。当区域内对象数量超过阈值时，区域被划分为四个相等子区域。
四叉树的核心优势在于：查询某个对象附近的潜在碰撞对象时，只需遍历与该对象边界框相交的节点，将 $O(n^2)$ 的碰撞检测优化到接近 $O(n \log n)$。
四叉树节点结构
/**
* 四叉树节点，代表二维空间中的一个矩形区域
*/
class QuadtreeNode {
// 区域边界
private final double x, y, width, height;
// 当前节点存储的对象（叶子节点）
private final List<Fish> objects;
// 子节点（非叶子节点）
private QuadtreeNode[] children;
// 最大容量，超过则分裂
private static final int MAX_OBJECTS = 4;
// 最大深度，防止无限细分
private static final int MAX_DEPTH = 5;
private final int depth;
public QuadtreeNode(double x, double y, double width, double height, int depth) {
this.x = x;
this.y = y;
this.width = width;
this.height = height;
this.depth = depth;
this.objects = new ArrayList<>();
}
}
插入与查询操作
/**
* 将鱼插入四叉树
*/
public void insert(Fish fish) {
// 如果是叶子节点且未满，直接存储
if (children == null && objects.size() < MAX_OBJECTS) {
objects.add(fish);
return;
}
// 需要分裂或已经是非叶子节点
if (children == null && depth < MAX_DEPTH) {
split();
// 将已有对象重新分配到子节点
List<Fish> existing = new ArrayList<>(objects);
objects.clear();
for (Fish f : existing) {
insertIntoChildren(f);
}
}
// 将新对象插入子节点
if (children != null) {
insertIntoChildren(fish);
} else {
// 达到最大深度，继续存储在当前节点
objects.add(fish);
}
}
/**
* 将对象插入合适的子节点
*/
private void insertIntoChildren(Fish fish) {
Rectangle bounds = fish.getBounds();
for (QuadtreeNode child : children) {
if (child.contains(bounds)) {
child.insert(fish);
return;
}
}
// 跨越多个子节点，保留在当前节点
objects.add(fish);
}
/**
* 查询与给定边界框可能相交的所有对象
*/
public void query(Rectangle range, List<Fish> result) {
// 当前节点区域与查询范围不相交，直接返回
if (!intersects(range)) {
return;
}
// 检查当前节点存储的对象
for (Fish fish : objects) {
if (fish.getBounds().intersects(range)) {
result.add(fish);
}
}
// 递归查询子节点
if (children != null) {
for (QuadtreeNode child : children) {
child.query(range, result);
}
}
}
/**
* 分裂当前节点为四个子象限
*/
private void split() {
double halfW = width / 2;
double halfH = height / 2;
children = new QuadtreeNode[4];
// 左上、右上、左下、右下
children[0] = new QuadtreeNode(x, y, halfW, halfH, depth + 1);
children[1] = new QuadtreeNode(x + halfW, y, halfW, halfH, depth + 1);
children[2] = new QuadtreeNode(x, y + halfH, halfW, halfH, depth + 1);
children[3] = new QuadtreeNode(x + halfW, y + halfH, halfW, halfH, depth + 1);
}
AABB碰撞检测与进食判定
轴对齐边界框（AABB）
每条鱼使用AABB包围盒进行碰撞检测。AABB的优势在于相交测试仅需简单的数值比较，计算开销极小。
/**
* 轴对齐边界框
*/
class Rectangle {
public double x, y, width, height;
public Rectangle(double x, double y, double width, double height) {
this.x = x;
this.y = y;
this.width = width;
this.height = height;
}
/**
* 判断两个AABB是否相交
*/
public boolean intersects(Rectangle other) {
return this.x < other.x + other.width &&
this.x + this.width > other.x &&
this.y < other.y + other.height &&
this.y + this.height > other.y;
}
}
鱼的实体类设计
/**
* 鱼实体类，包含位置、大小、速度等属性
*/
class Fish {
private double x, y; // 位置坐标
private double size; // 大小（半径）
private double speed; // 移动速度
private double vx, vy; // 速度向量
private boolean isPlayer; // 是否为玩家控制
private boolean alive; // 是否存活
private static final double BASE_SPEED = 2.0;
private static final double GROWTH_RATE = 0.15;
public Fish(double x, double y, double size, boolean isPlayer) {
this.x = x;
this.y = y;
this.size = size;
this.isPlayer = isPlayer;
this.alive = true;
this.speed = BASE_SPEED / Math.sqrt(size); // 大鱼速度更慢
this.vx = Math.random() * 2 - 1;
this.vy = Math.random() * 2 - 1;
normalizeVelocity();
}
/**
* 获取AABB边界框（用于四叉树和碰撞检测）
*/
public Rectangle getBounds() {
return new Rectangle(x - size, y - size, size * 2, size * 2);
}
/**
* 归一化速度向量
*/
private void normalizeVelocity() {
double len = Math.sqrt(vx * vx + vy * vy);
if (len > 0) {
vx = (vx / len) * speed;
vy = (vy / len) * speed;
}
}
/**
* 移动鱼的位置
*/
public void move(double worldWidth, double worldHeight) {
x += vx;
y += vy;
// 边界反弹
if (x - size < 0 || x + size > worldWidth) {
vx = -vx;
x = Math.max(size, Math.min(x, worldWidth - size));
}
if (y - size < 0 || y + size > worldHeight) {
vy = -vy;
y = Math.max(size, Math.min(y, worldHeight - size));
}
}
/**
* 计算与另一条鱼的距离
*/
public double distanceTo(Fish other) {
double dx = this.x - other.x;
double dy = this.y - other.y;
return Math.sqrt(dx * dx + dy * dy);
}
/**
* 判断是否可以吃掉另一条鱼
* 规则：自身大小 > 对方大小 * 1.2（需要明显大于）
*/
public boolean canEat(Fish other) {
return this.size > other.size * 1.2 && this.alive && other.alive;
}
/**
* 吃掉另一条鱼，自身体积增长
*/
public void eat(Fish prey) {
if (canEat(prey)) {
// 面积增长：新面积 = 原面积 + 猎物面积 * 增长率
double myArea = Math.PI * size * size;
double preyArea = Math.PI * prey.size * prey.size;
double newArea = myArea + preyArea * GROWTH_RATE;
this.size = Math.sqrt(newArea / Math.PI);
prey.alive = false;
// 速度随体型增大而降低
this.speed = BASE_SPEED / Math.sqrt(size);
normalizeVelocity();
}
}
// Getters
public double getX() { return x; }
public double getY() { return y; }
public double getSize() { return size; }
public boolean isAlive() { return alive; }
public boolean isPlayer() { return isPlayer; }
public double getVX() { return vx; }
public double getVY() { return vy; }
public void setVelocity(double vx, double vy) {
this.vx = vx;
this.vy = vy;
normalizeVelocity();
}
}
贪心策略：最优进食决策
策略设计
玩家鱼需要在众多目标中选择最优的捕食对象。贪心策略的核心思想是：在每一步选择当前状态下”收益最高且风险最低”的目标。
定义目标评分函数：
$$
Score(target) = \frac{GrowthValue}{Distance} \times SafetyFactor
$$
其中：
– $GrowthValue$：吃掉目标后的体积增长量
– $Distance$：当前位置到目标的距离（鼓励优先吃近处目标）
– $SafetyFactor$：安全因子，路径上是否存在更大的鱼威胁
/**
* 贪心决策器，为玩家鱼选择最优进食目标
*/
class GreedyDecision {
private static final double DANGER_DISTANCE = 150.0; // 危险距离阈值
/**
* 为玩家鱼计算最优移动方向
* @param player 玩家控制的鱼
* @param allFish 所有鱼的列表
* @param worldWidth 世界宽度
* @param worldHeight 世界高度
* @return 最优速度向量 [vx, vy]
*/
public double[] decideDirection(Fish player, List<Fish> allFish,
double worldWidth, double worldHeight) {
Fish bestTarget = null;
double bestScore = Double.NEGATIVE_INFINITY;
for (Fish target : allFish) {
if (target == player || !target.isAlive()) continue;
double dist = player.distanceTo(target);
if (player.canEat(target)) {
// 可吃目标：计算收益分
double growthValue = target.getSize() * target.getSize();
// 距离越近分数越高，使用反比关系
double distanceBonus = 1000.0 / (dist + 10);
double safety = evaluateSafety(player, target, allFish, dist);
double score = growthValue * distanceBonus * safety;
if (score > bestScore) {
bestScore = score;
bestTarget = target;
}
} else if (target.canEat(player)) {
// 危险目标：逃跑方向
double dangerScore = -2000.0 / (dist + 1);
if (dangerScore > bestScore) {
bestScore = dangerScore;
bestTarget = target; // 记录为需要远离的目标
}
}
}
if (bestTarget == null) {
// 没有目标时保持当前方向
return new double[]{player.getVX(), player.getVY()};
}
double dx = bestTarget.getX() - player.getX();
double dy = bestTarget.getY() - player.getY();
// 如果是危险目标（不能吃反而会被吃），反向逃跑
if (bestTarget.canEat(player)) {
dx = -dx;
dy = -dy;
}
// 归一化方向向量
double len = Math.sqrt(dx * dx + dy * dy);
if (len > 0) {
return new double[]{dx / len, dy / len};
}
return new double[]{0, 0};
}
/**
* 评估前往目标路径的安全性
* @return 安全因子，1.0表示完全安全，越小越危险
*/
private double evaluateSafety(Fish player, Fish target, List<Fish> allFish, double targetDist) {
double safety = 1.0;
for (Fish other : allFish) {
if (other == player || other == target || !other.isAlive()) continue;
// 只考虑比玩家大的鱼
if (!other.canEat(player)) continue;
double distToPlayer = player.distanceTo(other);
// 如果大敌人在附近，降低安全因子
if (distToPlayer < DANGER_DISTANCE) {
safety *= (distToPlayer / DANGER_DISTANCE);
}
}
return Math.max(safety, 0.1); // 最低保留0.1的安全分
}
}
游戏引擎核心逻辑
import java.util.*;
/**
* 大鱼吃小鱼游戏主引擎
*/
public class BigFishGame {
private static final double WORLD_WIDTH = 800;
private static final double WORLD_HEIGHT = 600;
private static final int INITIAL_FISH_COUNT = 30;
private static final int MAX_FISH_COUNT = 50;
private List<Fish> fishes;
private Fish player;
private QuadtreeNode quadtree;
private GreedyDecision decision;
private Random random;
public BigFishGame() {
this.fishes = new ArrayList<>();
this.decision = new GreedyDecision();
this.random = new Random();
initializeGame();
}
/**
* 初始化游戏：创建玩家和初始鱼群
*/
private void initializeGame() {
// 创建玩家鱼（中等大小）
player = new Fish(WORLD_WIDTH / 2, WORLD_HEIGHT / 2, 15, true);
fishes.add(player);
// 生成初始鱼群
for (int i = 0; i < INITIAL_FISH_COUNT; i++) {
spawnRandomFish();
}
}
/**
* 在随机位置生成一条鱼
*/
private void spawnRandomFish() {
double x = random.nextDouble() * (WORLD_WIDTH - 40) + 20;
double y = random.nextDouble() * (WORLD_HEIGHT - 40) + 20;
// 大小范围：5~25
double size = random.nextDouble() * 20 + 5;
fishes.add(new Fish(x, y, size, false));
}
/**
* 游戏主循环的单个更新帧
*/
public void update() {
// 1. 构建四叉树（每帧重建，处理动态对象）
quadtree = new QuadtreeNode(0, 0, WORLD_WIDTH, WORLD_HEIGHT, 0);
for (Fish fish : fishes) {
if (fish.isAlive()) {
quadtree.insert(fish);
}
}
// 2. 玩家AI决策（使用贪心策略）
double[] dir = decision.decideDirection(player, fishes, WORLD_WIDTH, WORLD_HEIGHT);
player.setVelocity(dir[0], dir[1]);
// 3. 移动所有鱼
for (Fish fish : fishes) {
if (fish.isAlive()) {
fish.move(WORLD_WIDTH, WORLD_HEIGHT);
}
}
// 4. 使用四叉树进行高效碰撞检测与进食
processCollisions();
// 5. 清理死亡的鱼并补充新鱼
cleanupAndRespawn();
}
/**
* 使用四叉树进行碰撞检测
*/
private void processCollisions() {
Set<String> processedPairs = new HashSet<>();
for (Fish fish : fishes) {
if (!fish.isAlive()) continue;
// 查询四叉树获取潜在碰撞对象
List<Fish> candidates = new ArrayList<>();
Rectangle queryRange = fish.getBounds();
// 扩大查询范围以捕获边界相交的情况
queryRange = new Rectangle(
queryRange.x - 5, queryRange.y - 5,
queryRange.width + 10, queryRange.height + 10
);
quadtree.query(queryRange, candidates);
for (Fish other : candidates) {
if (fish == other || !other.isAlive()) continue;
// 避免重复处理同一对
String pairId = fish.hashCode() < other.hashCode()
? fish.hashCode() + "-" + other.hashCode()
: other.hashCode() + "-" + fish.hashCode();
if (processedPairs.contains(pairId)) continue;
processedPairs.add(pairId);
// AABB碰撞检测
if (fish.getBounds().intersects(other.getBounds())) {
// 判断谁吃谁
if (fish.canEat(other)) {
fish.eat(other);
} else if (other.canEat(fish)) {
other.eat(fish);
}
}
}
}
}
/**
* 清理死亡鱼并维持鱼群数量
*/
private void cleanupAndRespawn() {
fishes.removeIf(f -> !f.isAlive());
int aliveCount = (int) fishes.stream().filter(Fish::isAlive).count();
while (aliveCount < MAX_FISH_COUNT) {
spawnRandomFish();
aliveCount++;
}
}
/**
* 获取当前游戏状态（用于渲染）
*/
public List<Fish> getFishes() {
return Collections.unmodifiableList(fishes);
}
public Fish getPlayer() {
return player;
}
/**
* 主方法：运行简单的文本模拟
*/
public static void main(String[] args) {
BigFishGame game = new BigFishGame();
System.out.println("=== 大鱼吃小鱼 算法模拟 ===");
System.out.println("玩家初始大小: " + game.getPlayer().getSize());
for (int frame = 1; frame <= 100; frame++) {
game.update();
if (frame % 20 == 0) {
long aliveCount = game.getFishes().stream().filter(Fish::isAlive).count();
System.out.printf("第%3d帧 | 玩家大小: %.2f | 存活鱼数: %d%n",
frame, game.getPlayer().getSize(), aliveCount);
}
// 玩家死亡则结束
if (!game.getPlayer().isAlive()) {
System.out.println("玩家被吃掉了！游戏结束。");
break;
}
}
System.out.println("最终玩家大小: " + game.getPlayer().getSize());
}
}
四叉树完整实现
/**
* 四叉树完整实现
*/
class QuadtreeNode {
private final double x, y, width, height;
private final List<Fish> objects;
private QuadtreeNode[] children;
private final int depth;
private static final int MAX_OBJECTS = 4;
private static final int MAX_DEPTH = 6;
public QuadtreeNode(double x, double y, double width, double height, int depth) {
this.x = x;
this.y = y;
this.width = width;
this.height = height;
this.depth = depth;
this.objects = new ArrayList<>();
}
public void insert(Fish fish) {
if (children == null && objects.size() < MAX_OBJECTS) {
objects.add(fish);
return;
}
if (children == null && depth < MAX_DEPTH) {
split();
List<Fish> temp = new ArrayList<>(objects);
objects.clear();
for (Fish f : temp) insertIntoChildren(f);
}
if (children != null) {
insertIntoChildren(fish);
} else {
objects.add(fish);
}
}
private void insertIntoChildren(Fish fish) {
Rectangle b = fish.getBounds();
for (QuadtreeNode child : children) {
if (child.contains(b)) { child.insert(fish); return; }
}
objects.add(fish);
}
public void query(Rectangle range, List<Fish> result) {
if (!intersects(range)) return;
for (Fish f : objects) {
if (f.getBounds().intersects(range)) result.add(f);
}
if (children != null) {
for (QuadtreeNode c : children) c.query(range, result);
}
}
private void split() {
double hw = width / 2, hh = height / 2;
children = new QuadtreeNode[4];
children[0] = new QuadtreeNode(x, y, hw, hh, depth + 1);
children[1] = new QuadtreeNode(x + hw, y, hw, hh, depth + 1);
children[2] = new QuadtreeNode(x, y + hh, hw, hh, depth + 1);
children[3] = new QuadtreeNode(x + hw, y + hh, hw, hh, depth + 1);
}
private boolean contains(Rectangle r) {
return r.x >= x && r.x + r.width <= x + width &&
r.y >= y && r.y + r.height <= y + height;
}
private boolean intersects(Rectangle r) {
return x < r.x + r.width && x + width > r.x &&
y < r.y + r.height && y + height > r.y;
}
}
复杂度分析
| 操作 | 暴力检测 | 四叉树优化 | 说明 |
|---|---|---|---|
| 碰撞检测 | $O(n^2)$ | $O(n \log n)$ | 四叉树将空间分层，每个对象只需检测同区域邻居 |
| 插入对象 | — | $O(\log n)$ | 平均深度为 $\log_4 n$ |
| 区域查询 | $O(n)$ | $O(\log n + k)$ | $k$ 为查询结果数量 |
| 内存开销 | $O(1)$ | $O(n)$ | 需要存储树结构和对象引用 |
算法优化扩展
1. 动态速度调整
当前实现中大鱼速度更慢，符合物理直觉。可以进一步引入流体阻力模型，使速度变化更加平滑：
public void accelerate(double ax, double ay) {
vx += ax;
vy += ay;
double len = Math.sqrt(vx * vx + vy * vy);
if (len > maxSpeed) {
vx = (vx / len) * maxSpeed;
vy = (vy / len) * maxSpeed;
}
}
2. 群体行为（Boids算法）
为普通鱼添加简单的群体行为，使游戏更具真实感：
– 分离：避免与邻近鱼过度拥挤
– 对齐：与邻近鱼保持相似的速度方向
– 聚合：向邻近鱼的平均位置靠拢
3. 八叉树扩展到3D
如果将游戏扩展到三维空间，可将四叉树升级为八叉树（Octree），将空间划分为8个子立方体，算法逻辑完全相同。
总结
本文通过实现大鱼吃小鱼游戏，深入讲解了以下核心算法：
- 四叉树空间划分：将 $O(n^2)$ 的碰撞检测优化到接近 $O(n \log n)$，是处理大量动态实体碰撞的经典方案。
- AABB碰撞检测：使用轴对齐边界框进行快速相交判断，是游戏开发中最基础的碰撞检测技术。
- 贪心进食策略：通过定义评分函数综合考量成长收益、距离和安全因子，实现高效的局部最优决策。
这些算法不仅适用于游戏开发，四叉树空间划分还广泛应用于地理信息系统（GIS）、粒子模拟、图像压缩等领域。掌握这些基础算法，对于理解更复杂的空间数据结构和AI决策系统具有重要意义。
