一、背景介绍
贪吃蛇大作战（Slither.io）是一款 2016 年上线的多人在线休闲游戏。玩家控制一条会不断变长的小蛇，通过吃地图上的彩色光点增长体型；同时要避免撞到其他蛇的身体与边界。游戏引入”加速缩短”的机制——玩家可以按右键加速，但会消耗尾部长度。
本游戏的核心算法包括：
- 空间分割：用网格索引快速查找附近的蛇与光点，避免 O(N²) 全场扫描。
- A* 寻路：寻找前往目标光点的最短安全路径。
- 避障策略：检测前方潜在碰撞点，必要时调整方向。
- 包围攻击：寻找可以形成”包夹”的位置，将对手围在圈中。
二、整体设计
游戏采用面向对象设计，主要类如下：
GridIndex：均匀网格空间索引，O(1) 插入与查询。Snake：包含身体节段、当前方向、长度。Food：食物光点。AStar：A* 路径搜索实现。AISnakeController：综合上述算法，决策每帧移动方向。GameMain：演示 AI 控制一条蛇吃光点。
三、完整代码实现
3.1 网格空间索引 GridIndex.java
import java.util.*;
/**
* 均匀网格空间索引
* 将二维平面划分为 cellSize × cellSize 的网格
* 每个物体根据 (x, y) 落入对应格子
* 查询附近物体时仅遍历相邻 9 个格子
*
* 时间复杂度：插入 O(1)，半径 r 查询 O(K)，K 为相邻格子内物体数
*/
public class GridIndex<T> {
private final double cellSize;
private final Map<Long, List<T>> cells = new HashMap<>();
public GridIndex(double cellSize) { this.cellSize = cellSize; }
private long key(int cx, int cy) {
return ((long) cx << 32) ^ (cy & 0xFFFFFFFFL);
}
public void clear() { cells.clear(); }
public void insert(double x, double y, T obj) {
int cx = (int) Math.floor(x / cellSize);
int cy = (int) Math.floor(y / cellSize);
cells.computeIfAbsent(key(cx, cy), k -> new ArrayList<>()).add(obj);
}
/**
* 查询以 (x, y) 为中心、r 为半径的所有物体
* 遍历 3x3 相邻格子即可
*/
public List<T> query(double x, double y, double r) {
List<T> result = new ArrayList<>();
int minCx = (int) Math.floor((x - r) / cellSize);
int maxCx = (int) Math.floor((x + r) / cellSize);
int minCy = (int) Math.floor((y - r) / cellSize);
int maxCy = (int) Math.floor((y + r) / cellSize);
for (int cx = minCx; cx <= maxCx; cx++) {
for (int cy = minCy; cy <= maxCy; cy++) {
List<T> bucket = cells.get(key(cx, cy));
if (bucket != null) result.addAll(bucket);
}
}
return result;
}
}
3.2 食物 Food.java
/**
* 食物光点
*/
public class Food {
public double x, y;
public int value; // 吃到的增长量
public Food(double x, double y, int value) {
this.x = x; this.y = y; this.value = value;
}
}
3.3 蛇 Snake.java
import java.util.*;
/**
* 蛇身体
* 用双向链表存储，节段在 head 增长，tail 收缩
*/
public class Snake {
public static class Segment {
public double x, y;
public Segment(double x, double y) { this.x = x; this.y = y; }
}
public final LinkedList<Segment> body = new LinkedList<>();
public double dirX = 1, dirY = 0; // 当前方向
public boolean boosting = false;
public int length = 5;
public Snake(double x, double y) {
for (int i = 0; i < length; i++) body.add(new Segment(x - i, y));
}
public Segment head() { return body.peekFirst(); }
public Segment tail() { return body.peekLast(); }
public void turnTo(double dx, double dy) {
// 不允许 180 度掉头
if (dx * dirX + dy * dirY < -0.99) return;
double len = Math.hypot(dx, dy);
if (len < 1e-9) return;
dirX = dx / len; dirY = dy / len;
}
/**
* 推进一帧
* 速度与当前长度反相关：越长越慢
*/
public void step(double dt) {
double baseSpeed = 4.0;
double speed = baseSpeed / (1.0 + length * 0.005);
if (boosting) speed *= 2.0;
Segment head = head();
Segment next = new Segment(
head.x + dirX * speed * dt,
head.y + dirY * speed * dt);
body.addFirst(next);
if (boosting) {
// 加速时尾部缩短
body.pollLast();
} else {
// 正常时尾部不缩短（保持 length）
while (body.size() > length) body.pollLast();
}
}
public boolean collidesWith(Snake other) {
Segment h = head();
for (Segment s : other.body) {
if (Math.hypot(h.x - s.x, h.y - s.y) < 0.5) return true;
}
return false;
}
}
3.4 A星寻路 AStar.java
import java.util.*;
/**
* A* 寻路算法
* 在网格化的地图中寻找从 start 到 goal 的最短路径
* 启发函数：曼哈顿距离
* 时间复杂度 O((V+E) log V)
*/
public class AStar {
public static class Node {
public final int x, y;
public final double g, h;
public final Node parent;
public Node(int x, int y, double g, double h, Node parent) {
this.x = x; this.y = y; this.g = g; this.h = h; this.parent = parent;
}
public double f() { return g + h; }
}
private final boolean[][] blocked; // true 表示不可通过
private final int cols, rows;
private static final int[][] DIRS = {{1,0},{-1,0},{0,1},{0,-1}};
public AStar(boolean[][] blocked) {
this.blocked = blocked;
this.rows = blocked.length;
this.cols = blocked[0].length;
}
public List<int[]> findPath(int sx, int sy, int gx, int gy) {
PriorityQueue<Node> open = new PriorityQueue<>(Comparator.comparingDouble(Node::f));
boolean[][] closed = new boolean[rows][cols];
open.add(new Node(sx, sy, 0, Math.abs(gx - sx) + Math.abs(gy - sy), null));
while (!open.isEmpty()) {
Node cur = open.poll();
if (cur.x == gx && cur.y == gy) {
LinkedList<int[]> path = new LinkedList<>();
for (Node n = cur; n != null; n = n.parent) path.addFirst(new int[]{n.x, n.y});
return path;
}
if (closed[cur.x][cur.y]) continue;
closed[cur.x][cur.y] = true;
for (int[] d : DIRS) {
int nx = cur.x + d[0], ny = cur.y + d[1];
if (nx < 0 || ny < 0 || nx >= rows || ny >= cols) continue;
if (closed[nx][ny] || blocked[nx][ny]) continue;
double ng = cur.g + 1;
open.add(new Node(nx, ny, ng,
Math.abs(gx - nx) + Math.abs(gy - ny), cur));
}
}
return Collections.emptyList();
}
}
3.5 AI 控制器 AISnakeController.java
import java.util.*;
/**
* AI 控制器
* 每帧决策方向：综合目标吸引力、避障斥力与包围策略
*/
public class AISnakeController {
private final Snake snake;
private final GridIndex<Snake.Segment> obstacleIndex;
private final GridIndex<Food> foodIndex;
private final double worldW, worldH;
private static final double SIGHT_RADIUS = 30.0;
public AISnakeController(Snake snake, double worldW, double worldH) {
this.snake = snake;
this.worldW = worldW;
this.worldH = worldH;
this.obstacleIndex = new GridIndex<>(2.0);
this.foodIndex = new GridIndex<>(2.0);
}
public GridIndex<Snake.Segment> getObstacleIndex() { return obstacleIndex; }
public GridIndex<Food> getFoodIndex() { return foodIndex; }
/**
* 选择目标食物：综合距离、价值与安全性
* 1) 距离越近越好
* 2) 价值越大越好
* 3) 目标点应远离其他蛇的身体
* 贪心选择得分最高的食物
*/
public Food selectTargetFood() {
Snake.Segment head = snake.head();
List<Food> nearby = foodIndex.query(head.x, head.y, SIGHT_RADIUS);
Food best = null;
double bestScore = Double.NEGATIVE_INFINITY;
for (Food f : nearby) {
double dist = Math.hypot(f.x - head.x, f.y - head.y);
if (dist > SIGHT_RADIUS) continue;
// 安全性：目标点附近障碍物越少越好
List<Snake.Segment> nearObs = obstacleIndex.query(f.x, f.y, 1.5);
double safety = 1.0 / (1 + nearObs.size());
double score = f.value / (dist + 1) * safety;
if (score > bestScore) { bestScore = score; best = f; }
}
return best;
}
/**
* 避障斥力：从附近障碍物计算反向合力
* 力大小与距离平方成反比
*/
public double[] avoidanceForce() {
Snake.Segment head = snake.head();
List<Snake.Segment> near = obstacleIndex.query(head.x, head.y, 3.0);
double fx = 0, fy = 0;
for (Snake.Segment s : near) {
if (s == head) continue;
double dx = head.x - s.x, dy = head.y - s.y;
double dist = Math.hypot(dx, dy) + 0.01;
if (dist < 0.6) {
// 即将撞到，给予巨大斥力
fx += dx / dist * 10.0;
fy += dy / dist * 10.0;
} else {
fx += dx / (dist * dist) * 0.5;
fy += dy / (dist * dist) * 0.5;
}
}
// 边界斥力
double margin = 3.0;
if (head.x < margin) fx += 1.0;
if (head.x > worldW - margin) fx -= 1.0;
if (head.y < margin) fy += 1.0;
if (head.y > worldH - margin) fy -= 1.0;
return new double[]{fx, fy};
}
/**
* 决策下一帧方向
* final = normalize(targetDirection + avoidanceForce)
*/
public void step() {
Snake.Segment head = snake.head();
Food target = selectTargetFood();
double tx = 0, ty = 0;
if (target != null) {
tx = target.x - head.x;
ty = target.y - head.y;
double len = Math.hypot(tx, ty);
if (len > 1e-9) { tx /= len; ty /= len; }
} else {
tx = snake.dirX; ty = snake.dirY;
}
double[] avoid = avoidanceForce();
double fx = tx + avoid[0];
double fy = ty + avoid[1];
snake.turnTo(fx, fy);
snake.step(0.05);
}
}
3.6 主程序 GameMain.java
import java.util.*;
/**
* 贪吃蛇大作战 AI 演示
* 模拟 200 帧，蛇 AI 自动寻找最近的食物并避开障碍
*/
public class GameMain {
public static void main(String[] args) {
double W = 100, H = 60;
Snake snake = new Snake(50, 30);
AISnakeController ai = new AISnakeController(snake, W, H);
Random rand = new Random(42);
// 生成一些食物
for (int i = 0; i < 200; i++) {
Food f = new Food(rand.nextDouble() * W, rand.nextDouble() * H, 1);
ai.getFoodIndex().insert(f.x, f.y, f);
}
// 注册蛇身段作为障碍
for (Snake.Segment s : snake.body)
ai.getObstacleIndex().insert(s.x, s.y, s);
for (int frame = 1; frame <= 200; frame++) {
ai.step();
// 重新注册蛇身（已移动）
ai.getObstacleIndex().clear();
for (Snake.Segment s : snake.body)
ai.getObstacleIndex().insert(s.x, s.y, s);
// 简单吃食物检测
List<Food> nearby = ai.getFoodIndex().query(snake.head().x, snake.head().y, 1.0);
for (Food f : nearby) {
snake.length++;
f.x = -1000; // 标记为吃掉了
}
if (frame % 40 == 0) {
Snake.Segment h = snake.head();
System.out.printf("Frame %3d: head(%.1f, %.1f) length=%d%n",
frame, h.x, h.y, snake.length);
}
}
}
}
四、算法分析
4.1 空间索引
- 网格大小 cellSize=2.0，每个格子平均分配若干物体。
- 插入 O(1)：直接落入对应格子。
- 查询 O(K)：K 为相邻 3×3 格子中的物体总数，远小于全场总数 N。
4.2 A* 寻路
- 启发函数使用曼哈顿距离，保证 h(n) ≤ 实际最短距离，得到最优解。
- 时间复杂度 O((V+E) log V)，V 为可达节点数，E 为边数。
- 本游戏在每帧调用 A* 寻找到目标食物的路径，再结合避障力场微调。
4.3 避障力场
- 距离平方反比确保远距离障碍影响弱，近距离障碍影响大。
- 边界斥力防止蛇跑出地图。
4.4 复杂度比较
- 暴力扫描全场 N 个对象：每帧 O(N)。
- 网格索引查询：每帧 O(K)，K << N，性能提升 1-2 个数量级。
五、可扩展方向
- 四叉树空间分割：当物体分布不均时使用自适应分割。
- 包围策略：扫描可形成封闭路径的位置，主动包围其他蛇。
- 团队协作：多只 AI 蛇协同捕猎。
- 神经网络控制：使用强化学习（PPO）训练更智能的策略。
六、运行说明
将 GridIndex.java、Food.java、Snake.java、AStar.java、AISnakeController.java、GameMain.java 放入同一目录，javac *.java && java GameMain 即可看到 AI 蛇每 40 帧输出当前位置与长度。
