引言
球球大作战（Agar.io）是一款风靡全球的休闲竞技游戏，玩家控制一个细胞在地图上移动，通过吞噬食物和比自己小的细胞来不断变大。本文将用Java实现球球大作战的核心算法，重点讲解其中的两个关键技术：基于四叉树（Quadtree）的空间分割碰撞检测，以及贪心增长策略下的最优移动决策。读者将理解如何将空间数据结构应用到实时游戏碰撞检测中。
问题建模
球球大作战可抽象为以下核心问题：
- 球体表示：每个球用圆心坐标
(x, y)和半径r表示，面积决定质量 - 移动规则：球可以向任意方向移动，速度随质量增大而减小
- 吞噬规则：当球A的圆心进入球B的圆内且A半径大于B的1.25倍时，A吞噬B
- 食物生成：地图上随机生成小球作为食物
- 碰撞检测：需要高效检测球与球、球与食物之间的碰撞关系
核心算法一：四叉树空间分割
当地图上有大量球体时，两两比较进行碰撞检测的 O(n²) 复杂度是不可接受的。四叉树将空间递归划分为四个象限，每个节点只存储位于该区域的物体，从而将碰撞检测优化到 O(n log n)。
import java.util.ArrayList;
import java.util.List;
/**
* 球球大作战核心算法实现
*/
public class AgarIOGame {
/**
* 二维点/向量
*/
static class Vector2D {
double x, y;
Vector2D(double x, double y) { this.x = x; this.y = y; }
double distanceTo(Vector2D other) {
double dx = x - other.x;
double dy = y - other.y;
return Math.sqrt(dx * dx + dy * dy);
}
Vector2D add(Vector2D other) {
return new Vector2D(x + other.x, y + other.y);
}
Vector2D multiply(double scalar) {
return new Vector2D(x * scalar, y * scalar);
}
}
/**
* 矩形边界框（用于四叉树节点）
*/
static class Bounds {
double x, y, width, height; // x,y为左上角坐标
Bounds(double x, double y, double w, double h) {
this.x = x; this.y = y; this.width = w; this.height = h;
}
boolean contains(Vector2D point) {
return point.x >= x && point.x <= x + width &&
point.y >= y && point.y <= y + height;
}
boolean intersects(Bounds other) {
return !(other.x > x + width || other.x + other.width < x ||
other.y > y + height || other.y + other.height < y);
}
}
/**
* 球体（玩家或食物）
*/
static class Ball {
Vector2D position; // 位置
double radius; // 半径
String name; // 标识
boolean isPlayer; // 是否是玩家
Ball(double x, double y, double r, String name, boolean isPlayer) {
this.position = new Vector2D(x, y);
this.radius = r;
this.name = name;
this.isPlayer = isPlayer;
}
/**
* 获取球的边界框（用于四叉树）
*/
Bounds getBounds() {
return new Bounds(
position.x - radius, position.y - radius,
radius * 2, radius * 2
);
}
/**
* 计算与另一球是否发生碰撞（距离 < 半径之和）
*/
boolean collidesWith(Ball other) {
double dist = position.distanceTo(other.position);
return dist < (this.radius + other.radius);
}
/**
* 判断是否能吞噬另一球
* 条件：自己半径 > 对方半径 * 1.25 且圆心距离 < 自己半径
*/
boolean canEat(Ball other) {
if (this.radius <= other.radius * 1.25) return false;
double dist = position.distanceTo(other.position);
return dist < this.radius;
}
}
/**
* 四叉树节点
*/
static class Quadtree {
private static final int MAX_OBJECTS = 10; // 节点最大存储数
private static final int MAX_LEVELS = 5; // 最大分割深度
private int level;
private Bounds bounds;
private List<Ball> objects;
private Quadtree[] nodes; // 四个子节点：TL, TR, BL, BR
Quadtree(int level, Bounds bounds) {
this.level = level;
this.bounds = bounds;
this.objects = new ArrayList<>();
this.nodes = null;
}
/**
* 将当前节点分割为四个子节点
*/
void split() {
double subWidth = bounds.width / 2;
double subHeight = bounds.height / 2;
double x = bounds.x;
double y = bounds.y;
nodes = new Quadtree[4];
// 左上
nodes[0] = new Quadtree(level + 1, new Bounds(x, y, subWidth, subHeight));
// 右上
nodes[1] = new Quadtree(level + 1, new Bounds(x + subWidth, y, subWidth, subHeight));
// 左下
nodes[2] = new Quadtree(level + 1, new Bounds(x, y + subHeight, subWidth, subHeight));
// 右下
nodes[3] = new Quadtree(level + 1, new Bounds(x + subWidth, y + subHeight, subWidth, subHeight));
}
/**
* 确定球应该放入哪个象限（0-3）
*/
int getIndex(Ball ball) {
int index = -1;
double verticalMidpoint = bounds.x + bounds.width / 2;
double horizontalMidpoint = bounds.y + bounds.height / 2;
boolean topQuadrant = ball.position.y < horizontalMidpoint &&
ball.position.y + ball.radius * 2 < horizontalMidpoint;
boolean bottomQuadrant = ball.position.y > horizontalMidpoint;
if (ball.position.x < verticalMidpoint &&
ball.position.x + ball.radius * 2 < verticalMidpoint) {
if (topQuadrant) index = 0; // 左上
else if (bottomQuadrant) index = 2; // 左下
} else if (ball.position.x > verticalMidpoint) {
if (topQuadrant) index = 1; // 右上
else if (bottomQuadrant) index = 3; // 右下
}
return index;
}
/**
* 将球插入四叉树
*/
void insert(Ball ball) {
if (nodes != null) {
int index = getIndex(ball);
if (index != -1) {
nodes[index].insert(ball);
return;
}
}
objects.add(ball);
if (objects.size() > MAX_OBJECTS && level < MAX_LEVELS) {
if (nodes == null) {
split();
}
int i = 0;
while (i < objects.size()) {
int index = getIndex(objects.get(i));
if (index != -1) {
nodes[index].insert(objects.remove(i));
} else {
i++;
}
}
}
}
/**
* 检索可能与给定球发生碰撞的所有球
*/
List<Ball> retrieve(List<Ball> returnObjects, Ball ball) {
if (nodes != null) {
int index = getIndex(ball);
if (index != -1) {
nodes[index].retrieve(returnObjects, ball);
} else {
// 跨越多个象限，检索所有子节点
for (Quadtree node : nodes) {
node.retrieve(returnObjects, ball);
}
}
}
returnObjects.addAll(objects);
return returnObjects;
}
/**
* 清空四叉树
*/
void clear() {
objects.clear();
if (nodes != null) {
for (Quadtree node : nodes) {
if (node != null) node.clear();
}
nodes = null;
}
}
}
核心算法二：贪心增长策略
/**
* 游戏世界
*/
static class GameWorld {
double width, height;
List<Ball> players;
List<Ball> foods;
Quadtree quadtree;
GameWorld(double w, double h) {
this.width = w;
this.height = h;
this.players = new ArrayList<>();
this.foods = new ArrayList<>();
this.quadtree = new Quadtree(0, new Bounds(0, 0, w, h));
}
/**
* 每帧更新：重建四叉树并处理碰撞
*/
void update() {
// 清空并重建四叉树
quadtree.clear();
for (Ball p : players) quadtree.insert(p);
for (Ball f : foods) quadtree.insert(f);
// 碰撞检测与吞噬
List<Ball> toRemove = new ArrayList<>();
for (Ball player : players) {
List<Ball> candidates = new ArrayList<>();
quadtree.retrieve(candidates, player);
for (Ball other : candidates) {
if (other == player || toRemove.contains(other)) continue;
if (player.canEat(other)) {
// 吞噬：质量合并，半径增加
double area1 = Math.PI * player.radius * player.radius;
double area2 = Math.PI * other.radius * other.radius;
double newArea = area1 + area2;
player.radius = Math.sqrt(newArea / Math.PI);
toRemove.add(other);
}
}
}
players.removeAll(toRemove);
foods.removeAll(toRemove);
}
/**
* 贪心策略：为玩家选择最优移动方向
* 综合考虑：附近食物收益、危险回避、追击目标
*/
Vector2D getBestDirection(Ball player) {
List<Ball> candidates = new ArrayList<>();
quadtree.retrieve(candidates, player);
Vector2D bestDir = new Vector2D(0, 0);
double bestScore = Double.NEGATIVE_INFINITY;
// 采样多个方向
for (int angle = 0; angle < 360; angle += 30) {
double rad = Math.toRadians(angle);
Vector2D dir = new Vector2D(Math.cos(rad), Math.sin(rad));
Vector2D targetPos = player.position.add(dir.multiply(player.radius * 5));
double score = evaluatePosition(player, targetPos, candidates);
if (score > bestScore) {
bestScore = score;
bestDir = dir;
}
}
return bestDir;
}
/**
* 评估某个位置的收益分数
*/
double evaluatePosition(Ball player, Vector2D pos, List<Ball> nearby) {
double score = 0;
for (Ball other : nearby) {
if (other == player) continue;
double dist = pos.distanceTo(other.position);
if (other.isPlayer) {
if (other.radius > player.radius * 1.25) {
// 危险：大球，回避
score -= 1000.0 / (dist + 1);
} else if (player.radius > other.radius * 1.25) {
// 机会：小球，追击
score += 500.0 / (dist + 1);
}
} else {
// 食物：安全收益
score += 50.0 / (dist + 1);
}
}
// 边界惩罚
if (pos.x < player.radius || pos.x > width - player.radius ||
pos.y < player.radius || pos.y > height - player.radius) {
score -= 2000;
}
return score;
}
}
完整演示
/**
* 主程序：演示游戏流程
*/
public static void main(String[] args) {
GameWorld world = new GameWorld(1000, 1000);
// 创建玩家
Ball player = new Ball(500, 500, 20, "Player1", true);
world.players.add(player);
// 创建一些AI玩家
world.players.add(new Ball(200, 200, 15, "AI_1", true));
world.players.add(new Ball(800, 800, 25, "AI_2", true));
// 生成食物
for (int i = 0; i < 100; i++) {
double fx = Math.random() * 1000;
double fy = Math.random() * 1000;
world.foods.add(new Ball(fx, fy, 3, "Food" + i, false));
}
System.out.println("=== 球球大作战模拟开始 ===");
System.out.println("初始玩家大小: " + player.radius);
System.out.println("食物数量: " + world.foods.size());
System.out.println();
// 模拟10帧
for (int frame = 1; frame <= 10; frame++) {
// 移动玩家（按贪心方向）
Vector2D dir = world.getBestDirection(player);
double speed = Math.max(1, 20 / (player.radius / 10 + 1)); // 越大的球越慢
player.position = player.position.add(dir.multiply(speed));
// 确保在边界内
player.position.x = Math.max(player.radius,
Math.min(world.width - player.radius, player.position.x));
player.position.y = Math.max(player.radius,
Math.min(world.height - player.radius, player.position.y));
world.update();
System.out.println("帧 " + frame + ": 玩家位置 (" +
String.format("%.1f", player.position.x) + ", " +
String.format("%.1f", player.position.y) + ")" +
", 半径: " + String.format("%.2f", player.radius) +
", 剩余食物: " + world.foods.size());
}
// 展示四叉树效率
System.out.println();
System.out.println("=== 碰撞检测效率对比 ===");
int n = world.players.size() + world.foods.size();
System.out.println("物体总数: " + n);
System.out.println("暴力检测复杂度: O(n²) = " + (n * n) + " 次比较");
System.out.println("四叉树检测复杂度: 约 O(n log n)");
System.out.println("对于1000个物体，四叉树通常只需检测约 " + (n * 10) + " 对候选碰撞");
}
}
复杂度分析
- 四叉树插入：平均 O(log n)，最坏 O(n)（所有物体重叠在同一区域）
- 四叉树检索：平均 O(log n + k)，k 为返回的候选对象数
- 碰撞检测：使用四叉树后从 O(n²) 降到平均 O(n log n)
- 贪心策略：每帧 O(m × n)，m 为采样方向数（默认12个），n 为候选对象数
扩展思考
- 空间哈希替代：可用网格（Grid/Spatial Hash）替代四叉树，实现更简单，在物体分布均匀时效率更高
- 球体分裂机制：大球可按空格键分裂为两个小球，增加追击速度，引入分裂/合并策略决策
- 团队合作AI：多个小球协同包抄大球，引入群体智能和编队算法
- 病毒机制：绿色刺球可使大球分裂，引入风险-收益权衡的博弈论分析
总结
本文通过Java实现了球球大作战的核心算法，重点讲解了四叉树空间分割碰撞检测和贪心增长策略。四叉树通过递归空间划分将碰撞检测从 O(n²) 优化到 O(n log n)，是处理大量动态物体碰撞的经典方案。贪心策略则综合考虑食物收益、危险回避和追击机会来决策移动方向。这些技术在大规模多人在线游戏、物理引擎和计算机图形学中有广泛应用。
