每日算法 — 使用java实现大鱼吃小鱼：贪心层级进化与空间分区碰撞检测

游戏场景与算法概述

《大鱼吃小鱼》是一款经典的海洋生存游戏，玩家控制小鱼通过吃掉更小的鱼来成长，同时躲避更大的捕食者。本文用Java实现两个核心算法：贪心层级进化策略（最优进食顺序决策）和网格空间分区碰撞检测（大量鱼类场景下的高效碰撞判断）。

核心算法一：贪心层级进化策略

海洋中散布着大小各异的鱼，小鱼需要做出最优进食决策。贪心策略的核心是：在当前可见范围内，选择”单位时间内成长收益最高”的目标。

import java.util.*;

public class EvolutionStrategy {
    public static class Fish {
        public double x, y, size, speed;
        public boolean isPlayer;
        public Fish(double x, double y, double size, double speed, boolean isPlayer) {
            this.x = x; this.y = y; this.size = size; this.speed = speed; this.isPlayer = isPlayer;
        }
        public double distanceTo(Fish other) {
            return Math.hypot(this.x - other.x, this.y - other.y);
        }
    }

    // 贪心策略：选择最佳进食目标
    public Fish selectBestPrey(Fish player, List<Fish> allFish) {
        Fish best = null;
        double bestScore = Double.NEGATIVE_INFINITY;

        for (Fish f : allFish) {
            if (f == player || f.size >= player.size * 0.9) continue; // 不能吃

            double dist = player.distanceTo(f);
            double timeToReach = dist / player.speed;
            double growthValue = f.size * 0.2; // 吃掉后获得的成长值
            double riskFactor = calculateRisk(player, f, allFish);

            // 评分 = 成长收益 / 到达时间 - 风险惩罚
            double score = growthValue / (timeToReach + 1) - riskFactor;

            if (score > bestScore) {
                bestScore = score;
                best = f;
            }
        }
        return best;
    }

    // 计算前往目标路径上的风险：附近有大鱼则风险高
    private double calculateRisk(Fish player, Fish target, List<Fish> allFish) {
        double risk = 0;
        double midX = (player.x + target.x) / 2;
        double midY = (player.y + target.y) / 2;

        for (Fish f : allFish) {
            if (f.size <= player.size) continue; // 只考虑比自己大的
            double distToPath = pointToSegmentDist(f.x, f.y, player.x, player.y, target.x, target.y);
            if (distToPath < f.size + player.size) {
                risk += f.size / (distToPath + 1);
            }
        }
        return risk;
    }

    private double pointToSegmentDist(double px, double py, double ax, double ay, double bx, double by) {
        double abx = bx - ax, aby = by - ay;
        double apx = px - ax, apy = py - ay;
        double t = Math.max(0, Math.min(1, (apx * abx + apy * aby) / (abx * abx + aby * aby)));
        return Math.hypot(px - (ax + t * abx), py - (ay + t * aby));
    }
}

核心算法二：网格空间分区碰撞检测

当海洋中有数百条鱼时，两两比较的O(n²)碰撞检测会成为性能瓶颈。我们使用均匀网格（Uniform Grid）将空间划分为若干单元格，只需检测同格及相邻格内的鱼。

public class GridCollisionDetector {
    private static final double CELL_SIZE = 100.0;
    private Map<Long, List<Fish>> grid = new HashMap<>();

    private long cellKey(int cx, int cy) {
        return ((long)cx << 32) | (cy & 0xFFFFFFFFL);
    }

    // 将鱼插入对应网格单元
    public void insert(Fish fish) {
        int cx = (int)(fish.x / CELL_SIZE);
        int cy = (int)(fish.y / CELL_SIZE);
        grid.computeIfAbsent(cellKey(cx, cy), k -> new ArrayList<>()).add(fish);
    }

    // 清空并重构图格（每帧调用）
    public void rebuild(List<Fish> allFish) {
        grid.clear();
        for (Fish f : allFish) insert(f);
    }

    // 检测所有碰撞对：仅检查同格及8邻域
    public List<Collision> detectCollisions() {
        List<Collision> collisions = new ArrayList<>();
        Set<String> checked = new HashSet<>();

        for (Map.Entry<Long, List<Fish>> entry : grid.entrySet()) {
            long key = entry.getKey();
            int cx = (int)(key >> 32);
            int cy = (int)key;

            List<Fish> cellFish = entry.getValue();
            List<Fish> neighbors = new ArrayList<>(cellFish);

            // 加入8个相邻格子的鱼
            for (int dx = -1; dx <= 1; dx++) {
                for (int dy = -1; dy <= 1; dy++) {
                    if (dx == 0 && dy == 0) continue;
                    List<Fish> nf = grid.get(cellKey(cx + dx, cy + dy));
                    if (nf != null) neighbors.addAll(nf);
                }
            }

            // 碰撞检测
            for (int i = 0; i < cellFish.size(); i++) {
                Fish a = cellFish.get(i);
                for (int j = 0; j < neighbors.size(); j++) {
                    Fish b = neighbors.get(j);
                    if (a == b) continue;
                    String pairKey = a.hashCode() < b.hashCode() 
                        ? a.hashCode() + "-" + b.hashCode()
                        : b.hashCode() + "-" + a.hashCode();
                    if (checked.contains(pairKey)) continue;
                    checked.add(pairKey);

                    double dist = a.distanceTo(b);
                    if (dist < (a.size + b.size) / 2) {
                        collisions.add(new Collision(a, b, dist));
                    }
                }
            }
        }
        return collisions;
    }

    public static class Collision {
        public Fish predator, prey;
        public double distance;
        public Collision(Fish a, Fish b, double d) {
            this.distance = d;
            if (a.size > b.size) { predator = a; prey = b; }
            else { predator = b; prey = a; }
        }
    }
}

复杂度分析

当空间均匀分布时，网格法将复杂度从O(n²)降到接近O(n)。

总结

本文通过贪心策略实现最优进食决策，利用均匀网格大幅加速碰撞检测。读者可以进一步探索四叉树替代均匀网格处理非均匀分布场景，或引入A*寻路让AI鱼具备智能追击行为。