每日算法 — 使用java实现打地鼠：贪心策略与反应时间统计

打地鼠（Whack-a-Mole）是一款考验反应速度的经典街机游戏，地鼠随机从多个洞穴中冒出，玩家需要在限定时间内尽可能多地击中它们。本文用Java实现一个带AI决策的打地鼠系统，核心讲解贪心策略如何决定最优击打顺序，以及基于滑动窗口的反应时间统计模型。

游戏规则与算法建模

假设游戏界面有N个洞穴排成一行，地鼠按批次随机出现，每只地鼠有存活时间T。玩家每次移动锤子需要时间cost，必须在目标消失前完成击打。AI需要解决的核心问题是：当多只地鼠同时出现时，如何规划击打顺序以最大化得分？

这本质上是一个带时间窗口的调度问题，可建模为：
– 每个地鼠是一个任务，有出现时间start、存活截止时间deadline、位置pos、分值score
– 玩家从位置p移动到位置q需要时间|p-q|×moveCost
– 在deadline前到达并完成击打才能获得score

贪心策略设计

最优击打策略采用贪心选择：每次从当前可到达的地鼠中，选择单位时间收益最高且剩余时间最紧迫的目标。具体规则：

1. 可到达性筛选：计算从当前位置到达每只地鼠所需时间，筛选出deadline允许到达的目标。
2. 紧急度排序：优先选择deadline最早的地鼠，避免错过。
3. 得分密度权衡：在紧急度相近时，优先选择分值高、距离近的目标。

Java 实现

import java.util.*;

public class WhackAMole {
    static class Mole {
        int id, pos, score;
        long appearTime, deadline; // 毫秒时间戳
        boolean hit = false;

        Mole(int id, int pos, int score, long appear, long aliveMs) {
            this.id = id; this.pos = pos; this.score = score;
            this.appearTime = appear; this.deadline = appear + aliveMs;
        }
    }

    static class GameResult {
        int totalScore, hitCount, missCount;
        double avgReactionMs;
        List<Long> reactionTimes = new ArrayList<>();
    }

    private final int moveCostPerUnit; // 每单位距离移动耗时(ms)
    private final int hitCost; // 击打动作耗时(ms)
    private int currentPos = 0;
    private long currentTime = 0;

    public WhackAMole(int moveCost, int hitCost) {
        this.moveCostPerUnit = moveCost;
        this.hitCost = hitCost;
    }

    // 贪心策略：选择最优目标
    public Mole selectTarget(List<Mole> activeMoles) {
        Mole best = null;
        double bestPriority = Double.NEGATIVE_INFINITY;

        for (Mole m : activeMoles) {
            if (m.hit) continue;
            int dist = Math.abs(m.pos - currentPos);
            long travelTime = (long) dist * moveCostPerUnit + hitCost;
            long arriveTime = currentTime + travelTime;

            if (arriveTime > m.deadline) continue; // 来不及

            long slack = m.deadline - arriveTime; // 剩余缓冲时间
            // 优先级 = 得分 / (距离+1) + 紧急度奖励（缓冲越小越紧急）
            double priority = (double) m.score / (dist + 1) + 1000.0 / (slack + 1);
            if (priority > bestPriority) {
                bestPriority = priority;
                best = m;
            }
        }
        return best;
    }

    // 模拟完整游戏流程
    public GameResult playGame(List<Mole> moles, long gameDurationMs) {
        GameResult result = new GameResult();
        PriorityQueue<Mole> appearQueue = new PriorityQueue<>(Comparator.comparingLong(m -> m.appearTime));
        appearQueue.addAll(moles);
        List<Mole> active = new ArrayList<>();

        while (currentTime < gameDurationMs) {
            // 将新出现的地鼠加入活动列表
            while (!appearQueue.isEmpty() && appearQueue.peek().appearTime <= currentTime) {
                active.add(appearQueue.poll());
            }

            // 清理已过期的地鼠
            Iterator<Mole> it = active.iterator();
            while (it.hasNext()) {
                Mole m = it.next();
                if (m.deadline < currentTime && !m.hit) {
                    it.remove();
                    result.missCount++;
                }
            }

            Mole target = selectTarget(active);
            if (target == null) {
                // 没有可击打目标，快进时间到下一个地鼠出现
                currentTime = appearQueue.isEmpty() ? gameDurationMs : appearQueue.peek().appearTime;
                continue;
            }

            // 执行移动和击打
            int dist = Math.abs(target.pos - currentPos);
            long travelTime = (long) dist * moveCostPerUnit;
            currentTime += travelTime + hitCost;
            currentPos = target.pos;
            target.hit = true;

            long reaction = currentTime - target.appearTime;
            result.reactionTimes.add(reaction);
            result.totalScore += target.score;
            result.hitCount++;
            active.remove(target);
        }

        // 统计反应时间
        if (!result.reactionTimes.isEmpty()) {
            long sum = 0;
            for (long rt : result.reactionTimes) sum += rt;
            result.avgReactionMs = (double) sum / result.reactionTimes.size();
        }
        return result;
    }

    // 滑动窗口反应时间统计：分析玩家/AI的反应能力变化趋势
    public static double[] slidingWindowAvg(List<Long> reactionTimes, int windowSize) {
        int n = reactionTimes.size();
        double[] avgs = new double[n];
        long windowSum = 0;
        LinkedList<Long> window = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            window.addLast(reactionTimes.get(i));
            windowSum += reactionTimes.get(i);
            if (window.size() > windowSize) {
                windowSum -= window.pollFirst();
            }
            avgs[i] = (double) windowSum / window.size();
        }
        return avgs;
    }

    public static void main(String[] args) {
        Random rand = new Random(42);
        List<Mole> moles = new ArrayList<>();
        long gameDuration = 30000; // 30秒游戏

        // 随机生成50只地鼠
        for (int i = 0; i < 50; i++) {
            long appear = rand.nextInt((int) gameDuration);
            int pos = rand.nextInt(10); // 10个洞穴
            int score = 10 + rand.nextInt(90); // 10-100分
            long alive = 800 + rand.nextInt(1200); // 存活0.8-2秒
            moles.add(new Mole(i, pos, score, appear, alive));
        }

        WhackAMole game = new WhackAMole(50, 100); // 每格50ms，击打100ms
        GameResult result = game.playGame(moles, gameDuration);

        System.out.println("Hits: " + result.hitCount + " | Misses: " + result.missCount);
        System.out.println("Total Score: " + result.totalScore);
        System.out.println("Avg Reaction: " + String.format("%.1f", result.avgReactionMs) + "ms");

        // 滑动窗口分析
        double[] trend = slidingWindowAvg(result.reactionTimes, 5);
        System.out.println("Reaction trend (last 5 avg): " + 
            String.format("%.1f", trend[trend.length - 1]) + "ms");
    }
}

复杂度分析

• 时间复杂度：每次选择目标需要O(M)遍历活跃地鼠列表，M为同时出现的地鼠数。总复杂度O(K×M)，K为地鼠总数。
• 空间复杂度：O(M)存储活跃地鼠列表，以及O(K)存储反应时间记录。

策略对比与扩展

对于更复杂的场景（如连击奖励、炸弹惩罚），贪心策略可扩展为带权调度，或引入强化学习训练最优策略网络。