引言
《球球大作战》是一款风靡全球的休闲竞技游戏，玩家控制一个小球在地图中移动，通过吞噬食物和其他 smaller 的球来不断变大，同时需要躲避更大的球和障碍物。在这个看似简单的规则背后，蕴含着丰富的算法问题：如何在复杂环境中规划最优移动路径？如何在追逐食物的同时避开危险？ 本文将用Java实现一个简化版球球大作战AI，核心算法采用A*最短路径搜索结合贪婪避障策略，让AI在竞技场中游刃有余。
核心算法原理
1. A*寻路算法
A*（A-Star）是游戏开发中最经典的路径搜索算法，它综合了Dijkstra算法的完备性和贪婪最佳优先搜索的高效性：
f(n) = g(n) + h(n)
g(n)：从起点到节点n的实际代价（已走路径长度）h(n)：从节点n到目标点的启发式估计代价（通常用曼哈顿距离或欧几里得距离）f(n)：总估计代价，A*每次优先扩展f值最小的节点
当启发函数 h(n) 满足可采纳性（永远不大于实际代价）时，A*保证找到最优路径。
2. 贪婪避障策略
单纯的A*只能找到静态最优路径，但在动态竞技场中需要实时躲避移动的敌人。贪婪避障策略的核心思想是：
- 在A*规划的路径基础上，实时检测前方危险区域
- 若检测到更大球体进入安全半径，立即计算最近的安全躲避方向
- 采用势场法思路：食物产生吸引力，大球产生排斥力，综合决定移动方向
Java完整实现
import java.util.*;
/**
* 球球大作战简化版AI
* 核心算法：A*最短路径搜索 + 贪婪避障策略
*/
public class AgarIOAI {
private static final int MAP_SIZE = 100; // 地图大小
private static final int SAFE_MARGIN = 5; // 安全边距（格子数）
// 地图格子状态
static class Cell {
int x, y;
boolean isObstacle; // 是否为静态障碍物
double dangerLevel; // 动态危险等级（来自大球）
Cell(int x, int y) {
this.x = x;
this.y = y;
this.isObstacle = false;
this.dangerLevel = 0;
}
}
// 球体（玩家或敌人）
static class Ball {
double x, y;
double radius;
boolean isPlayer;
Ball(double x, double y, double radius, boolean isPlayer) {
this.x = x; this.y = y;
this.radius = radius;
this.isPlayer = isPlayer;
}
double distanceTo(Ball other) {
double dx = this.x - other.x;
double dy = this.y - other.y;
return Math.sqrt(dx*dx + dy*dy);
}
boolean canEat(Ball other) {
return this.radius > other.radius * 1.2 && this.distanceTo(other) < this.radius;
}
}
// 食物点
static class Food {
double x, y;
double value;
Food(double x, double y, double value) {
this.x = x; this.y = y;
this.value = value;
}
}
private final Cell[][] grid;
private final Ball player;
private final List<Ball> enemies;
private final List<Food> foods;
public AgarIOAI() {
this.grid = new Cell[MAP_SIZE][MAP_SIZE];
for (int i = 0; i < MAP_SIZE; i++) {
for (int j = 0; j < MAP_SIZE; j++) {
grid[i][j] = new Cell(i, j);
}
}
this.player = new Ball(10, 10, 5, true);
this.enemies = new ArrayList<>();
this.foods = new ArrayList<>();
initMap();
}
/**
* 初始化地图障碍物、敌人和食物
*/
private void initMap() {
// 静态障碍物（绿色刺球）
int[][] obstacles = {{30,30}, {30,31}, {70,70}, {70,71}, {71,70}, {50,20}, {50,21}};
for (int[] o : obstacles) {
if (o[0] < MAP_SIZE && o[1] < MAP_SIZE) grid[o[0]][o[1]].isObstacle = true;
}
// 敌人（更大的球）
enemies.add(new Ball(40, 40, 12, false));
enemies.add(new Ball(80, 25, 15, false));
enemies.add(new Ball(60, 80, 10, false));
// 食物
Random rand = new Random(42);
for (int i = 0; i < 30; i++) {
foods.add(new Food(rand.nextInt(MAP_SIZE), rand.nextInt(MAP_SIZE), 1));
}
}
/**
* 更新动态危险地图
*/
public void updateDangerMap() {
// 重置危险等级
for (int i = 0; i < MAP_SIZE; i++) {
for (int j = 0; j < MAP_SIZE; j++) {
grid[i][j].dangerLevel = 0;
}
}
// 大球周围产生危险场
for (Ball enemy : enemies) {
if (enemy.radius <= player.radius) continue; // 比自己小的不危险
double dangerRadius = enemy.radius + player.radius + SAFE_MARGIN;
int minX = Math.max(0, (int)(enemy.x - dangerRadius));
int maxX = Math.min(MAP_SIZE-1, (int)(enemy.x + dangerRadius));
int minY = Math.max(0, (int)(enemy.y - dangerRadius));
int maxY = Math.min(MAP_SIZE-1, (int)(enemy.y + dangerRadius));
for (int x = minX; x <= maxX; x++) {
for (int y = minY; y <= maxY; y++) {
double dx = x - enemy.x;
double dy = y - enemy.y;
double dist = Math.sqrt(dx*dx + dy*dy);
if (dist < dangerRadius) {
// 距离越近危险越高
grid[x][y].dangerLevel += 1000.0 / (dist + 1);
}
}
}
}
}
/**
* 核心算法1：A*最短路径搜索
* @param start 起点
* @param goal 终点
* @return 路径点列表
*/
public List<int[]> aStarSearch(int[] start, int[] goal) {
PriorityQueue<Node> openSet = new PriorityQueue<>(Comparator.comparingDouble(n -> n.f));
Set<String> closedSet = new HashSet<>();
Map<String, Node> nodeMap = new HashMap<>();
Node startNode = new Node(start[0], start[1], null, 0, heuristic(start, goal));
openSet.add(startNode);
nodeMap.put(key(start[0], start[1]), startNode);
int[][] dirs = {{-1,0}, {1,0}, {0,-1}, {0,1}, {-1,-1}, {-1,1}, {1,-1}, {1,1}};
while (!openSet.isEmpty()) {
Node current = openSet.poll();
if (current.x == goal[0] && current.y == goal[1]) {
return reconstructPath(current);
}
closedSet.add(key(current.x, current.y));
for (int[] d : dirs) {
int nx = current.x + d[0];
int ny = current.y + d[1];
if (nx < 0 || nx >= MAP_SIZE || ny < 0 || ny >= MAP_SIZE) continue;
if (grid[nx][ny].isObstacle) continue;
if (closedSet.contains(key(nx, ny))) continue;
// 移动代价：基础1 + 危险惩罚
double moveCost = (d[0] != 0 && d[1] != 0) ? 1.414 : 1.0;
double dangerPenalty = grid[nx][ny].dangerLevel * 0.1;
double tentativeG = current.g + moveCost + dangerPenalty;
Node neighbor = nodeMap.get(key(nx, ny));
if (neighbor == null || tentativeG < neighbor.g) {
if (neighbor == null) {
neighbor = new Node(nx, ny, current, tentativeG,
tentativeG + heuristic(new int[]{nx, ny}, goal));
nodeMap.put(key(nx, ny), neighbor);
openSet.add(neighbor);
} else {
openSet.remove(neighbor);
neighbor.parent = current;
neighbor.g = tentativeG;
neighbor.f = tentativeG + heuristic(new int[]{nx, ny}, goal);
openSet.add(neighbor);
}
}
}
}
return new ArrayList<>(); // 无路径
}
/**
* 启发函数：欧几里得距离（可采纳）
*/
private double heuristic(int[] a, int[] b) {
double dx = a[0] - b[0];
double dy = a[1] - b[1];
return Math.sqrt(dx*dx + dy*dy);
}
private String key(int x, int y) {
return x + "," + y;
}
private List<int[]> reconstructPath(Node node) {
LinkedList<int[]> path = new LinkedList<>();
while (node != null) {
path.addFirst(new int[]{node.x, node.y});
node = node.parent;
}
return path;
}
static class Node {
int x, y;
Node parent;
double g, f;
Node(int x, int y, Node parent, double g, double f) {
this.x = x; this.y = y;
this.parent = parent;
this.g = g; this.f = f;
}
}
/**
* 核心算法2：贪婪避障策略
* 当A*路径前方有危险时，计算即时躲避方向
*/
public double[] greedyAvoidance() {
double ax = 0, ay = 0; // 加速度方向
// 吸引力：最近的食物
Food bestFood = null;
double bestFoodScore = Double.NEGATIVE_INFINITY;
for (Food f : foods) {
double dx = f.x - player.x;
double dy = f.y - player.y;
double dist = Math.sqrt(dx*dx + dy*dy);
if (dist < 0.1) continue;
// 食物价值与距离的反比
double score = f.value / (dist + 1);
if (score > bestFoodScore) {
bestFoodScore = score;
bestFood = f;
}
}
if (bestFood != null) {
double dx = bestFood.x - player.x;
double dy = bestFood.y - player.y;
double dist = Math.sqrt(dx*dx + dy*dy);
ax += dx / dist * 2; // 食物吸引力
ay += dy / dist * 2;
}
// 排斥力：所有比自己大的球
for (Ball enemy : enemies) {
if (enemy.radius <= player.radius) continue;
double dx = player.x - enemy.x;
double dy = player.y - enemy.y;
double dist = Math.sqrt(dx*dx + dy*dy);
if (dist < 0.1) continue;
double safeDist = enemy.radius + player.radius + SAFE_MARGIN;
if (dist < safeDist * 2) {
// 距离越近排斥越强
double force = 5.0 * (safeDist * 2 - dist) / (safeDist * 2);
ax += dx / dist * force;
ay += dy / dist * force;
}
}
// 归一化
double mag = Math.sqrt(ax*ax + ay*ay);
if (mag > 0) {
ax /= mag;
ay /= mag;
}
return new double[]{ax, ay};
}
/**
* AI决策：A*路径规划 + 贪婪避障的混合策略
*/
public void aiMove() {
updateDangerMap();
// 寻找最优目标（价值最高且可达的食物）
Food target = null;
double bestScore = Double.NEGATIVE_INFINITY;
for (Food f : foods) {
double dx = f.x - player.x;
double dy = f.y - player.y;
double dist = Math.sqrt(dx*dx + dy*dy);
double danger = grid[(int)f.x][(int)f.y].dangerLevel;
double score = f.value / (dist + 1) - danger * 0.01;
if (score > bestScore) {
bestScore = score;
target = f;
}
}
int[] start = {(int)player.x, (int)player.y};
double moveX = 0, moveY = 0;
if (target != null) {
int[] goal = {(int)target.x, (int)target.y};
List<int[]> path = aStarSearch(start, goal);
if (path.size() > 1) {
// 沿A*路径移动
int[] next = path.get(1);
moveX = next[0] - player.x;
moveY = next[1] - player.y;
}
}
// 贪婪避障修正
double[] avoid = greedyAvoidance();
moveX = moveX * 0.6 + avoid[0] * 0.4;
moveY = moveY * 0.6 + avoid[1] * 0.4;
// 限制最大速度
double speed = Math.sqrt(moveX*moveX + moveY*moveY);
double maxSpeed = 3.0;
if (speed > maxSpeed) {
moveX = moveX / speed * maxSpeed;
moveY = moveY / speed * maxSpeed;
}
player.x += moveX;
player.y += moveY;
// 边界限制
player.x = Math.max(player.radius, Math.min(MAP_SIZE - player.radius, player.x));
player.y = Math.max(player.radius, Math.min(MAP_SIZE - player.radius, player.y));
// 吃食物
foods.removeIf(f -> {
double dx = f.x - player.x;
double dy = f.y - player.y;
return Math.sqrt(dx*dx + dy*dy) < player.radius;
});
}
/**
* 控制台可视化
*/
public void render() {
char[][] canvas = new char[MAP_SIZE/2][MAP_SIZE/2];
for (char[] row : canvas) Arrays.fill(row, ' ');
// 障碍物
for (int i = 0; i < MAP_SIZE; i += 2) {
for (int j = 0; j < MAP_SIZE; j += 2) {
if (grid[i][j].isObstacle) canvas[j/2][i/2] = '#';
}
}
// 食物
for (Food f : foods) {
int x = (int)f.x / 2;
int y = (int)f.y / 2;
if (x >= 0 && x < canvas[0].length && y >= 0 && y < canvas.length) {
canvas[y][x] = '.';
}
}
// 敌人
for (Ball e : enemies) {
int x = (int)e.x / 2;
int y = (int)e.y / 2;
if (x >= 0 && x < canvas[0].length && y >= 0 && y < canvas.length) {
canvas[y][x] = e.radius > player.radius ? 'X' : 'x';
}
}
// 玩家
int px = (int)player.x / 2;
int py = (int)player.y / 2;
if (px >= 0 && px < canvas[0].length && py >= 0 && py < canvas.length) {
canvas[py][px] = '@';
}
System.out.print("\033[H\033[2J");
for (char[] row : canvas) {
System.out.println(new String(row));
}
System.out.printf("玩家半径: %.1f | 剩余食物: %d%n", player.radius, foods.size());
}
public static void main(String[] args) throws InterruptedException {
AgarIOAI game = new AgarIOAI();
System.out.println("=== 球球大作战AI模拟 ===");
System.out.println("@ = 玩家, X = 大敌人, x = 小敌人, . = 食物, # = 障碍物");
Thread.sleep(1000);
for (int step = 0; step < 200 && !game.foods.isEmpty(); step++) {
game.aiMove();
game.render();
Thread.sleep(100);
// 模拟成长
if (step % 20 == 0) {
game.player.radius += 0.5;
}
}
System.out.println("模拟结束！");
}
}
算法复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 危险地图更新 | O(E × R²) | O(N²) | E为敌人数量，R为危险半径 |
| A*搜索（无危险） | O(b^d) | O(b^d) | b为分支因子，d为最优路径深度 |
| A*搜索（含危险） | O(N² log N) | O(N²) | N为地图边长，优先队列驱动 |
| 贪婪避障计算 | O(E + F) | O(1) | E为敌人数，F为食物数 |
| 单帧AI决策 | O(N² log N + E×R²) | O(N²) | 主导项为A*搜索 |
总结
本文通过Java实现了一个球球大作战简化版AI，融合了两种核心策略：
-
A*最短路径搜索：在带权网格中寻找从玩家到目标食物的最优路径。通过将动态危险等级融入边的代价中，A*能在规划阶段就主动绕开威胁区域，而非被动碰撞后再躲避。
-
贪婪避障策略：作为A的实时补充，利用人工势场法*思想计算即时移动方向——食物产生吸引力引导接近，大球产生排斥力确保安全距离。两者的加权融合使AI既目标明确又反应灵敏。
这套混合策略广泛适用于各类动态环境路径规划场景，如机器人导航、无人机避障和自动驾驶局部规划。掌握A*与贪婪策略的结合方式，是游戏AI开发中的核心技能。
