每日算法 — 使用java实现贪吃蛇：粒子群优化与群体智能路径探索策略

引言

贪吃蛇是程序员入门必写的经典游戏，传统实现通常依赖人工规则或简单的贪心策略。本文将跳出常规思路，用Java实现基于粒子群优化（Particle Swarm Optimization, PSO）的贪吃蛇AI。通过模拟鸟群捕食行为，让多条”虚拟蛇”在状态空间中协作搜索最优路径，展示群体智能算法在游戏AI中的独特魅力。

问题建模

传统贪吃蛇AI的局限

• 贪心策略：只看当前最近食物，容易将自己逼入死胡同
• A*搜索：需要大量计算，在蛇身很长时性能下降
• 哈密顿回路：安全但缺乏灵活性，路径冗长

PSO的适用性分析

将贪吃蛇的决策空间建模为连续优化问题：
– 每个”粒子”代表一条虚拟蛇的完整路径规划（从当前位置到食物的一系列方向）
– 适应度函数综合考虑：路径长度、安全性（与自身距离）、到达食物的可能性
– 粒子之间共享最优解信息，通过速度和位置更新迭代优化

核心算法：粒子群优化

标准PSO公式

v[i] = w * v[i] + c1 * r1 * (pbest[i] - x[i]) + c2 * r2 * (gbest - x[i])
x[i] = x[i] + v[i]

其中：
– v[i]：粒子i的速度
– x[i]：粒子i的位置（编码为方向序列）
– pbest[i]：粒子i的历史最优位置
– gbest：全局最优位置
– w：惯性权重
– c1, c2：学习因子

离散化PSO

由于贪吃蛇的方向是离散的（上/下/左/右），需要对标准PSO进行离散化改造：
– 速度通过sigmoid函数映射为选择各方向的概率
– 位置更新通过概率采样确定下一步方向

完整Java实现

package snake.pso;

import java.util.*;

/**
 * 贪吃蛇 - 粒子群优化与群体智能路径探索AI
 * 
 * 核心功能：
 * 1. 贪吃蛇游戏引擎（移动、吃食物、碰撞检测）
 * 2. 粒子群编码：将蛇的路径规划编码为粒子位置
 * 3. 适应度函数：综合路径长度、安全性和食物可达性
 * 4. 离散PSO迭代：速度更新、sigmoid映射、路径采样
 */
public class SnakePSO {

    private static final Random RAND = new Random();
    private static final int[] DR = {-1, 1, 0, 0}; // UP, DOWN, LEFT, RIGHT
    private static final int[] DC = {0, 0, -1, 1};
    private static final String[] DIR_NAME = {"UP", "DOWN", "LEFT", "RIGHT"};

    private final int rows, cols;

    /**
     * 蛇的状态
     */
    public static class Snake {
        public LinkedList<int[]> body; // 蛇身，头部在队首
        public int direction;          // 当前方向
        public boolean alive;

        public Snake(int startRow, int startCol) {
            body = new LinkedList<>();
            body.addFirst(new int[]{startRow, startCol});
            direction = 3; // 初始向右
            alive = true;
        }

        public int headR() { return body.getFirst()[0]; }
        public int headC() { return body.getFirst()[1]; }

        public Snake copy() {
            Snake s = new Snake(headR(), headC());
            s.body.clear();
            for (int[] p : this.body) {
                s.body.addLast(new int[]{p[0], p[1]});
            }
            s.direction = this.direction;
            s.alive = this.alive;
            return s;
        }
    }

    /**
     * 粒子：代表一条虚拟蛇的路径规划
     */
    public static class Particle {
        public double[][] velocity;    // 速度矩阵 [路径长度][4方向]
        public int[][] position;       // 位置：每一步选择的方向索引
        public int[][] pbest;          // 历史最优路径
        public double pbestFitness;    // 历史最优适应度

        public Particle(int pathLength) {
            velocity = new double[pathLength][4];
            position = new int[pathLength][1];
            pbest = new int[pathLength][1];
            pbestFitness = Double.NEGATIVE_INFINITY;

            // 随机初始化路径
            for (int i = 0; i < pathLength; i++) {
                position[i][0] = RAND.nextInt(4);
            }
        }
    }

    public SnakePSO(int rows, int cols) {
        this.rows = rows;
        this.cols = cols;
    }

    /**
     * 模拟蛇按给定路径移动，返回最终适应度
     * 
     * @param snake     初始蛇状态
     * @param food      食物位置
     * @param path      方向路径
     * @return 适应度值（越高越好）
     */
    public double simulatePath(Snake snake, int[] food, int[] path) {
        Snake sim = snake.copy();
        int steps = 0;
        int maxSteps = rows * cols;
        boolean ate = false;

        for (int dir : path) {
            if (!sim.alive) break;

            // 不能180度掉头
            if (Math.abs(dir - sim.direction) == 1 && (dir + sim.direction) % 2 == 1
                && sim.body.size() > 1) {
                // UP(0)-DOWN(1) 或 LEFT(2)-RIGHT(3) 不能反向
                if ((dir == 0 && sim.direction == 1) || (dir == 1 && sim.direction == 0)
                    || (dir == 2 && sim.direction == 3) || (dir == 3 && sim.direction == 2)) {
                    dir = sim.direction; // 保持原方向
                }
            }

            int nr = sim.headR() + DR[dir];
            int nc = sim.headC() + DC[dir];

            // 碰撞检测
            if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) {
                sim.alive = false;
                break;
            }
            for (int[] seg : sim.body) {
                if (seg[0] == nr && seg[1] == nc) {
                    sim.alive = false;
                    break;
                }
            }
            if (!sim.alive) break;

            sim.body.addFirst(new int[]{nr, nc});
            sim.direction = dir;

            if (nr == food[0] && nc == food[1]) {
                ate = true;
                break; // 吃到食物，停止
            } else {
                sim.body.removeLast(); // 没吃到，尾巴前进
            }
            steps++;
            if (steps > maxSteps) break;
        }

        return calculateFitness(sim, food, steps, ate);
    }

    /**
     * 适应度函数设计
     * 
     * 综合考虑：
     * 1. 是否吃到食物（最高权重）
     * 2. 模拟结束后蛇头到食物的距离（越近越好）
     * 3. 蛇的存活状态
     * 4. 路径的冗余度（步数越少越好）
     * 5. 蛇身周围的空间充裕度（避免自困）
     */
    private double calculateFitness(Snake snake, int[] food, int steps, boolean ate) {
        if (ate) {
            return 10000.0 - steps * 10; // 吃到食物，优先步数少
        }
        if (!snake.alive) {
            return -5000.0 + steps; // 死亡惩罚，但步数多说明活得久
        }

        double fitness = 0;

        // 距离食物越近越好
        int dist = Math.abs(snake.headR() - food[0]) + Math.abs(snake.headC() - food[1]);
        fitness += 5000.0 - dist * 100;

        // 周围空格数量（空间充裕度）
        int freeSpace = countFreeSpace(snake);
        fitness += freeSpace * 5;

        // 步数奖励
        fitness += steps;

        return fitness;
    }

    /**
     * 计算蛇头周围的空闲格子数（BFS）
     */
    private int countFreeSpace(Snake snake) {
        boolean[][] visited = new boolean[rows][cols];
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{snake.headR(), snake.headC()});
        visited[snake.headR()][snake.headC()] = true;

        // 标记蛇身为已访问（障碍物）
        for (int[] seg : snake.body) {
            visited[seg[0]][seg[1]] = true;
        }

        int count = 0;
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            count++;
            for (int d = 0; d < 4; d++) {
                int nr = cur[0] + DR[d];
                int nc = cur[1] + DC[d];
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && !visited[nr][nc]) {
                    visited[nr][nc] = true;
                    queue.add(new int[]{nr, nc});
                }
            }
        }
        return count;
    }

    /**
     * 将连续速度离散化为方向选择概率
     * 
     * @param velocity  4个方向的速度值
     * @return 选择的 direction 索引
     */
    private int sigmoidSelect(double[] velocity, int currentDir) {
        double[] probs = new double[4];
        double sum = 0;

        for (int i = 0; i < 4; i++) {
            // Sigmoid映射
            probs[i] = 1.0 / (1.0 + Math.exp(-velocity[i]));

            // 180度转向的概率降低
            if (Math.abs(i - currentDir) == 1 && (i + currentDir) % 2 == 1
                && (i == 0 && currentDir == 1 || i == 1 && currentDir == 0
                    || i == 2 && currentDir == 3 || i == 3 && currentDir == 2)) {
                probs[i] *= 0.1;
            }
            sum += probs[i];
        }

        // 归一化并轮盘赌选择
        double r = RAND.nextDouble() * sum;
        double acc = 0;
        for (int i = 0; i < 4; i++) {
            acc += probs[i];
            if (r <= acc) return i;
        }
        return RAND.nextInt(4);
    }

    /**
     * 粒子群优化主算法
     * 
     * @param snake         当前蛇状态
     * @param food          食物位置
     * @param swarmSize     粒子群大小
     * @param pathLength    每条路径的规划步数
     * @param maxIter       最大迭代次数
     * @return 全局最优路径
     */
    public int[] optimize(Snake snake, int[] food, int swarmSize, int pathLength, int maxIter) {
        Particle[] swarm = new Particle[swarmSize];
        for (int i = 0; i < swarmSize; i++) {
            swarm[i] = new Particle(pathLength);
        }

        int[][] gbest = null;
        double gbestFitness = Double.NEGATIVE_INFINITY;

        // 初始化pbest和gbest
        for (Particle p : swarm) {
            int[] path = extractPath(p.position);
            double fitness = simulatePath(snake, food, path);
            p.pbestFitness = fitness;
            p.pbest = deepCopy(p.position);

            if (fitness > gbestFitness) {
                gbestFitness = fitness;
                gbest = deepCopy(p.position);
            }
        }

        // PSO迭代
        double w = 0.9;       // 惯性权重
        double c1 = 2.0;      // 个体学习因子
        double c2 = 2.0;      // 社会学习因子
        double wDecay = 0.99; // 惯性衰减

        for (int iter = 0; iter < maxIter; iter++) {
            for (Particle p : swarm) {
                for (int step = 0; step < pathLength; step++) {
                    for (int d = 0; d < 4; d++) {
                        // 标准PSO速度更新
                        double r1 = RAND.nextDouble();
                        double r2 = RAND.nextDouble();

                        double v = w * p.velocity[step][d]
                            + c1 * r1 * (p.pbest[step][0] == d ? 1 : 0 - p.velocity[step][d])
                            + c2 * r2 * (gbest[step][0] == d ? 1 : 0 - p.velocity[step][d]);

                        // 限制速度范围
                        p.velocity[step][d] = Math.max(-5, Math.min(5, v));
                    }

                    // 离散化更新位置
                    int currentDir = (step == 0) ? snake.direction : p.position[step - 1][0];
                    p.position[step][0] = sigmoidSelect(p.velocity[step], currentDir);
                }

                // 评估新位置
                int[] path = extractPath(p.position);
                double fitness = simulatePath(snake, food, path);

                // 更新pbest
                if (fitness > p.pbestFitness) {
                    p.pbestFitness = fitness;
                    p.pbest = deepCopy(p.position);
                }

                // 更新gbest
                if (fitness > gbestFitness) {
                    gbestFitness = fitness;
                    gbest = deepCopy(p.position);
                }
            }

            w *= wDecay;

            // 如果找到能吃到食物的路径，提前终止
            if (gbestFitness > 5000) {
                break;
            }
        }

        return extractPath(gbest);
    }

    private int[] extractPath(int[][] position) {
        int[] path = new int[position.length];
        for (int i = 0; i < position.length; i++) {
            path[i] = position[i][0];
        }
        return path;
    }

    private int[][] deepCopy(int[][] src) {
        int[][] dst = new int[src.length][];
        for (int i = 0; i < src.length; i++) {
            dst[i] = src[i].clone();
        }
        return dst;
    }

    /**
     * 完整的游戏AI循环
     */
    public void runGameAI(int maxFood) {
        Snake snake = new Snake(rows / 2, cols / 2);
        int foodEaten = 0;
        int totalSteps = 0;

        System.out.println("===== 贪吃蛇 PSO群体智能AI =====\n");
        System.out.printf("地图大小: %dx%d | 粒子群: 30 | 路径规划: 50步%n\n", rows, cols);

        while (snake.alive && foodEaten < maxFood) {
            int[] food = generateFood(snake);
            if (food == null) {
                System.out.println("地图已满，游戏胜利！");
                break;
            }

            // PSO规划路径
            int[] path = optimize(snake, food, 30, 50, 100);

            // 执行路径的第一步
            int nextDir = path[0];
            int nr = snake.headR() + DR[nextDir];
            int nc = snake.headC() + DC[nextDir];

            // 安全检查
            boolean safe = true;
            if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) safe = false;
            for (int[] seg : snake.body) {
                if (seg[0] == nr && seg[1] == nc) { safe = false; break; }
            }

            if (!safe) {
                // PSO路径不安全，尝试任意安全方向
                nextDir = findAnySafeDirection(snake);
                if (nextDir == -1) {
                    snake.alive = false;
                    break;
                }
                nr = snake.headR() + DR[nextDir];
                nc = snake.headC() + DC[nextDir];
            }

            snake.body.addFirst(new int[]{nr, nc});
            snake.direction = nextDir;

            if (nr == food[0] && nc == food[1]) {
                foodEaten++;
                System.out.printf("吃到食物 #%d! 蛇长: %d | 步数: %d%n",
                    foodEaten, snake.body.size(), totalSteps);
            } else {
                snake.body.removeLast();
            }
            totalSteps++;
        }

        System.out.printf("\n游戏结束 | 吃到食物: %d | 总步数: %d | 最终蛇长: %d%n",
            foodEaten, totalSteps, snake.body.size());
    }

    private int[] generateFood(Snake snake) {
        List<int[]> freeCells = new ArrayList<>();
        boolean[][] occupied = new boolean[rows][cols];
        for (int[] seg : snake.body) {
            occupied[seg[0]][seg[1]] = true;
        }
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (!occupied[r][c]) freeCells.add(new int[]{r, c});
            }
        }
        if (freeCells.isEmpty()) return null;
        return freeCells.get(RAND.nextInt(freeCells.size()));
    }

    private int findAnySafeDirection(Snake snake) {
        for (int d = 0; d < 4; d++) {
            if (Math.abs(d - snake.direction) == 1 && (d + snake.direction) % 2 == 1) {
                if ((d == 0 && snake.direction == 1) || (d == 1 && snake.direction == 0)
                    || (d == 2 && snake.direction == 3) || (d == 3 && snake.direction == 2)) {
                    continue; // 跳过反向
                }
            }
            int nr = snake.headR() + DR[d];
            int nc = snake.headC() + DC[d];
            if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
            boolean hit = false;
            for (int[] seg : snake.body) {
                if (seg[0] == nr && seg[1] == nc) { hit = true; break; }
            }
            if (!hit) return d;
        }
        return -1;
    }

    // ==================== 测试入口 ====================
    public static void main(String[] args) {
        SnakePSO game = new SnakePSO(15, 15);
        game.runGameAI(20);
    }
}

算法原理深入

离散PSO的核心改造

标准PSO适用于连续空间，而贪吃蛇的方向是离散的。关键改造点：

1. Sigmoid概率映射
   P(选择方向d) = sigmoid(v[d]) = 1 / (1 + exp(-v[d]))
   速度值越大，选择该方向的概率越高。

2. 方向约束编码

3. 180度转向被惩罚（概率乘以0.1）

4. 确保生成的路径在物理上可执行

5. 路径链式依赖

6. 第 t+1 步的方向选择依赖于第 t 步的实际方向
7. 模拟了蛇移动的连续性约束

适应度函数的多目标权衡

群体智能的优势

1. 并行探索：多个粒子同时搜索不同区域
2. 信息共享：gbest引导群体向优质区域集中
3. 跳出局部最优：随机速度和sigmoid采样引入探索性
4. 自适应性：惯性权重衰减实现从探索到利用的过渡

复杂度分析

扩展优化

1. 多食物前瞻：将路径规划扩展到多个食物序列，计算长期收益
2. 混合策略：PSO与BFS安全路径结合，先用PSO找方向，再用BFS验证安全性
3. 自适应参数：根据蛇的长度动态调整粒子数和迭代次数
4. 精英保留：每轮保留 top-k 粒子直接进入下一代

总结

本文用Java实现了基于粒子群优化的贪吃蛇AI，展示了：
– 将离散决策问题编码为连续优化空间的方法
– Sigmoid离散化与方向约束的PSO改造
– 多目标适应度函数的设计与平衡
– 群体智能算法在游戏AI中的工程实践

粒子群优化源自对鸟群捕食行为的模拟，其”个体经验+群体智慧”的协作机制，不仅在游戏AI中表现出色，在神经网络训练、特征选择、调度优化等领域也有广泛应用。理解PSO的核心思想，有助于我们设计更智能的分布式优化系统。