每日算法 — 使用java实现Simon记忆：有限状态机与序列模式识别

Simon记忆（Simon Game）是一款经典的电子记忆游戏，1978年由Milton Bradley公司推出。游戏通过闪烁不同颜色的按钮并播放对应音调来生成一个逐渐增长的序列，玩家需要准确复述整个序列。本文将使用Java实现完整的Simon记忆游戏，重点讲解有限状态机（Finite State Machine, FSM）的设计、随机序列生成算法以及模式匹配验证的核心逻辑。

游戏机制与算法核心

Simon记忆的核心机制可以抽象为三个算法问题：

1. 序列生成：如何生成足够随机且可预测难度增长的按键序列
2. 状态管理：游戏在”等待开始”、”播放序列”、”等待输入”、”验证结果”、”游戏结束”等状态间流转
3. 模式验证：如何高效比对玩家输入与目标序列

有限状态机设计

Simon记忆游戏天然适合用有限状态机建模。我们定义以下状态：

• IDLE：初始状态，等待玩家开始
• GENERATING：生成新一轮序列
• PLAYING：向玩家播放序列
• WAITING_INPUT：等待玩家输入
• CHECKING：验证玩家输入
• LEVEL_COMPLETE：本关通过，准备升级
• GAME_OVER：游戏结束

状态之间的转换由事件触发：玩家点击开始、序列播放完成、玩家按下按钮、验证通过/失败等。

Java实现

核心类结构

import java.util.*;

/**
 * Simon记忆游戏核心实现
 * 包含有限状态机、序列生成与模式验证
 */
public class SimonGame {

    // 颜色枚举，对应四个按钮
    public enum Color {
        RED, GREEN, BLUE, YELLOW
    }

    // 游戏状态枚举
    public enum GameState {
        IDLE, GENERATING, PLAYING, WAITING_INPUT, 
        CHECKING, LEVEL_COMPLETE, GAME_OVER
    }

    private final List<Color> sequence;      // 目标序列
    private final List<Color> playerInput;   // 玩家输入序列
    private int currentLevel;                // 当前关卡
    private int sequenceIndex;               // 播放/验证时的当前索引
    private GameState currentState;          // 当前状态
    private final Random random;             // 随机数生成器
    private final List<GameListener> listeners; // 状态监听器

    // 每关新增的序列长度（经典Simon为每关+1）
    private static final int SEQUENCE_INCREMENT = 1;
    // 初始序列长度
    private static final int INITIAL_LENGTH = 1;

    public SimonGame() {
        this.sequence = new ArrayList<>();
        this.playerInput = new ArrayList<>();
        this.currentLevel = 0;
        this.sequenceIndex = 0;
        this.currentState = GameState.IDLE;
        this.random = new Random();
        this.listeners = new ArrayList<>();
    }

    /**
     * 状态转换方法
     * 所有状态变更必须经过此方法，确保状态机的一致性
     */
    private void transitionTo(GameState newState) {
        GameState oldState = this.currentState;
        this.currentState = newState;

        // 触发状态转换回调
        for (GameListener listener : listeners) {
            listener.onStateChanged(oldState, newState);
        }

        // 根据新状态执行对应逻辑
        switch (newState) {
            case GENERATING:
                generateSequence();
                transitionTo(GameState.PLAYING);
                break;
            case PLAYING:
                sequenceIndex = 0;
                playSequence();
                break;
            case LEVEL_COMPLETE:
                currentLevel++;
                notifyListeners(l -> l.onLevelComplete(currentLevel));
                transitionTo(GameState.GENERATING);
                break;
            case GAME_OVER:
                notifyListeners(l -> l.onGameOver(currentLevel, sequence.size()));
                break;
            default:
                break;
        }
    }

    /**
     * 序列生成算法
     * 每关在当前序列基础上追加SEQUENCE_INCREMENT个随机颜色
     * 使用Random生成均匀分布的颜色索引
     */
    private void generateSequence() {
        // 第一关时清空序列
        if (currentLevel == 0) {
            sequence.clear();
        }

        Color[] colors = Color.values();
        for (int i = 0; i < SEQUENCE_INCREMENT; i++) {
            // nextInt(bound)生成[0, bound)的均匀分布整数
            int colorIndex = random.nextInt(colors.length);
            sequence.add(colors[colorIndex]);
        }

        System.out.println("[生成序列] 当前长度: " + sequence.size() + 
                          ", 序列: " + sequence);
    }

    /**
     * 序列播放逻辑
     * 模拟向玩家展示序列的过程
     * 实际GUI中可替换为按钮高亮和音效播放
     */
    private void playSequence() {
        System.out.println("[播放序列] 请记忆以下顺序:");

        for (int i = 0; i < sequence.size(); i++) {
            Color color = sequence.get(i);
            System.out.println("  步骤 " + (i + 1) + ": " + color);

            // 模拟播放延迟，实际应用中使用Timer或动画
            try {
                Thread.sleep(500);
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        }

        // 播放完成后进入等待输入状态
        playerInput.clear();
        transitionTo(GameState.WAITING_INPUT);
    }

    /**
     * 玩家输入处理
     * 在WAITING_INPUT状态下调用
     * @param color 玩家选择的颜色
     */
    public void onPlayerInput(Color color) {
        if (currentState != GameState.WAITING_INPUT) {
            System.out.println("[错误] 当前状态不可输入: " + currentState);
            return;
        }

        playerInput.add(color);
        int inputIndex = playerInput.size() - 1;

        System.out.println("[玩家输入] 索引 " + inputIndex + ": " + color);

        // 每次输入后立即验证当前位，实现即时反馈
        transitionTo(GameState.CHECKING);
        boolean isCorrect = verifyCurrentInput(inputIndex);

        if (!isCorrect) {
            transitionTo(GameState.GAME_OVER);
            return;
        }

        // 输入正确，检查是否完成本关
        if (playerInput.size() >= sequence.size()) {
            transitionTo(GameState.LEVEL_COMPLETE);
        } else {
            transitionTo(GameState.WAITING_INPUT);
        }
    }

    /**
     * 模式匹配验证
     * 验证玩家输入的指定索引位置是否与目标序列一致
     * 时间复杂度: O(1) - 直接索引比对
     * @param index 需要验证的索引位置
     * @return true表示匹配，false表示不匹配
     */
    private boolean verifyCurrentInput(int index) {
        if (index >= sequence.size() || index >= playerInput.size()) {
            return false;
        }

        Color expected = sequence.get(index);
        Color actual = playerInput.get(index);
        boolean match = (expected == actual);

        System.out.println("[验证] 期望: " + expected + ", 实际: " + actual + 
                          ", 结果: " + (match ? "正确" : "错误"));

        return match;
    }

    /**
     * 验证完整序列（备用方法）
     * 时间复杂度: O(n)，n为序列长度
     */
    public boolean verifyFullSequence() {
        if (playerInput.size() != sequence.size()) {
            return false;
        }

        for (int i = 0; i < sequence.size(); i++) {
            if (sequence.get(i) != playerInput.get(i)) {
                return false;
            }
        }
        return true;
    }

    // 游戏控制方法

    public void startGame() {
        if (currentState != GameState.IDLE && currentState != GameState.GAME_OVER) {
            System.out.println("[错误] 游戏已在进行中");
            return;
        }

        sequence.clear();
        playerInput.clear();
        currentLevel = 1;
        sequenceIndex = 0;

        System.out.println("[游戏开始] 准备好了吗？");
        transitionTo(GameState.GENERATING);
    }

    public void resetGame() {
        sequence.clear();
        playerInput.clear();
        currentLevel = 0;
        sequenceIndex = 0;
        transitionTo(GameState.IDLE);
        System.out.println("[游戏重置]");
    }

    public GameState getCurrentState() {
        return currentState;
    }

    public int getCurrentLevel() {
        return currentLevel;
    }

    public List<Color> getSequence() {
        return Collections.unmodifiableList(sequence);
    }

    // 监听器相关

    public void addListener(GameListener listener) {
        listeners.add(listener);
    }

    private void notifyListeners(java.util.function.Consumer<GameListener> action) {
        for (GameListener listener : listeners) {
            action.accept(listener);
        }
    }

    /**
     * 游戏事件监听器接口
     */
    public interface GameListener {
        void onStateChanged(GameState oldState, GameState newState);
        void onLevelComplete(int level);
        void onGameOver(int reachedLevel, int sequenceLength);
    }
}

带种子重现的序列生成器

为了实现可重现的序列（便于测试和调试），我们可以扩展随机序列生成，支持通过种子固定序列：

/**
 * 可控随机序列生成器
 * 支持通过种子重现相同的序列，便于测试和调试
 */
public class SeededSequenceGenerator {

    private final Random random;
    private final SimonGame.Color[] colors;

    public SeededSequenceGenerator() {
        this.random = new Random();
        this.colors = SimonGame.Color.values();
    }

    public SeededSequenceGenerator(long seed) {
        this.random = new Random(seed);
        this.colors = SimonGame.Color.values();
    }

    /**
     * 生成指定长度的随机序列
     * @param length 序列长度
     * @return 颜色序列列表
     */
    public List<SimonGame.Color> generate(int length) {
        List<SimonGame.Color> sequence = new ArrayList<>(length);
        for (int i = 0; i < length; i++) {
            sequence.add(colors[random.nextInt(colors.length)]);
        }
        return sequence;
    }

    /**
     * 生成满足"无连续重复"约束的序列
     * 提升游戏可玩性，避免连续相同颜色造成困惑
     * @param length 序列长度
     * @return 无连续重复的颜色序列
     */
    public List<SimonGame.Color> generateNoConsecutiveRepeat(int length) {
        List<SimonGame.Color> sequence = new ArrayList<>(length);
        SimonGame.Color prev = null;

        for (int i = 0; i < length; i++) {
            SimonGame.Color next;
            do {
                next = colors[random.nextInt(colors.length)];
            } while (next == prev && colors.length > 1);

            sequence.add(next);
            prev = next;
        }
        return sequence;
    }
}

控制台交互演示

import java.util.Scanner;

/**
 * Simon记忆游戏控制台版本
 */
public class SimonConsoleGame {

    public static void main(String[] args) {
        SimonGame game = new SimonGame();
        Scanner scanner = new Scanner(System.in);

        // 添加监听器打印状态
        game.addListener(new SimonGame.GameListener() {
            @Override
            public void onStateChanged(SimonGame.GameState oldState, SimonGame.GameState newState) {
                System.out.println("[状态] " + oldState + " -> " + newState);
            }

            @Override
            public void onLevelComplete(int level) {
                System.out.println("★★★ 恭喜通过第 " + (level - 1) + " 关！★★★\n");
            }

            @Override
            public void onGameOver(int reachedLevel, int sequenceLength) {
                System.out.println("游戏结束！你到达了第 " + reachedLevel + " 关");
                System.out.println("最终序列长度: " + sequenceLength);
            }
        });

        System.out.println("===== Simon记忆游戏 =====");
        System.out.println("指令: start=开始, r=红, g=绿, b=蓝, y=黄, reset=重置, quit=退出");

        while (true) {
            System.out.print("\n> ");
            String cmd = scanner.nextLine().trim().toLowerCase();

            switch (cmd) {
                case "start":
                    game.startGame();
                    break;
                case "r":
                    game.onPlayerInput(SimonGame.Color.RED);
                    break;
                case "g":
                    game.onPlayerInput(SimonGame.Color.GREEN);
                    break;
                case "b":
                    game.onPlayerInput(SimonGame.Color.BLUE);
                    break;
                case "y":
                    game.onPlayerInput(SimonGame.Color.YELLOW);
                    break;
                case "reset":
                    game.resetGame();
                    break;
                case "quit":
                    System.out.println("再见！");
                    return;
                default:
                    System.out.println("未知指令");
            }
        }
    }
}

复杂度分析

扩展思考

1. 难度曲线优化：当前每关仅增加1个元素，可通过非线性增长（如指数增长或斐波那契增长）调整难度
2. 模式识别辅助：为新手提供序列拆分策略，如将序列按颜色分组记忆（chunking策略）
3. 多玩家模式：通过状态机扩展支持对战模式，比较谁的记忆序列更长
4. 音效同步：将状态机与音频播放结合，实现视觉-听觉双重记忆线索

总结

Simon记忆游戏虽然规则简单，但其背后涉及有限状态机的清晰设计、随机序列生成的均匀性保障以及模式匹配验证的高效实现。通过Java枚举和状态转换方法，我们构建了一个易于扩展的游戏框架。读者可以在此基础上添加GUI界面、音效系统和网络对战功能，将经典算法应用于趣味游戏开发中。