每日算法 — 使用java实现保卫萝卜：BFS路径规划与贪心最优防御塔布局

引言

《保卫萝卜》是一款经典的塔防游戏，其核心玩法在于怪物沿固定路径入侵，玩家需在路旁建造防御塔来消灭敌人。本文将用Java实现该游戏的核心算法：利用BFS（广度优先搜索）计算怪物的最短入侵路径，并采用贪心策略动态选择最优防御塔建造位置，最大化整体伤害输出。

核心算法设计

1. 地图建模与BFS路径搜索

将游戏地图抽象为二维网格，其中0表示可通行路径，1表示障碍或空地。怪物从起点出发，需找到通往终点的最短路径。BFS天然适合求解无权图中的最短路径问题，时间复杂度为O(V+E)。

2. 防御塔攻击范围与伤害评估

每种防御塔具有攻击范围（圆形或矩形）和攻击力。我们需要计算每个候选位置对路径上各格子的覆盖情况，用贪心策略选择”单位造价伤害比”最高的位置。

3. 贪心布局策略

在每一步中，遍历所有可建造位置，计算该位置防御塔在其生命周期内能造成的总期望伤害，选择伤害期望值最大的位置建造。

完整Java实现

import java.util.*;

/**
 * 保卫萝卜核心算法实现
 * 包含BFS最短路径搜索与贪心防御塔布局
 */
public class CarrotDefense {

    // 地图尺寸与网格
    private int rows, cols;
    private int[][] grid; // 0=路径, 1=障碍, 2=起点, 3=终点

    // 四个方向
    private static final int[][] DIRS = {{-1,0},{1,0},{0,-1},{0,1}};

    // 防御塔类型定义
    static class Tower {
        String name;
        int range;      // 攻击范围（格数）
        int damage;     // 单次攻击力
        int cost;       // 造价
        double attackSpeed; // 攻击间隔（秒）

        Tower(String name, int range, int damage, int cost, double speed) {
            this.name = name;
            this.range = range;
            this.damage = damage;
            this.cost = cost;
            this.attackSpeed = speed;
        }

        // 每秒伤害期望值
        double dps() {
            return damage / attackSpeed;
        }
    }

    // 位置类
    static class Pos {
        int r, c;
        Pos(int r, int c) { this.r = r; this.c = c; }
        @Override public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof Pos)) return false;
            Pos p = (Pos) o;
            return r == p.r && c == p.c;
        }
        @Override public int hashCode() { return r * 131 + c; }
    }

    public CarrotDefense(int[][] grid) {
        this.grid = grid;
        this.rows = grid.length;
        this.cols = grid[0].length;
    }

    /**
     * BFS搜索从起点到终点的最短路径
     * 返回路径经过的所有坐标点列表
     */
    public List<Pos> findShortestPath() {
        Pos start = null, end = null;
        // 寻找起点和终点
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 2) start = new Pos(i, j);
                if (grid[i][j] == 3) end = new Pos(i, j);
            }
        }
        if (start == null || end == null) return Collections.emptyList();

        Queue<Pos> queue = new LinkedList<>();
        Map<Pos, Pos> parent = new HashMap<>();
        boolean[][] visited = new boolean[rows][cols];

        queue.offer(start);
        visited[start.r][start.c] = true;

        while (!queue.isEmpty()) {
            Pos cur = queue.poll();
            if (cur.equals(end)) break;

            for (int[] d : DIRS) {
                int nr = cur.r + d[0], nc = cur.c + d[1];
                if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
                if (visited[nr][nc] || grid[nr][nc] == 1) continue;
                visited[nr][nc] = true;
                Pos next = new Pos(nr, nc);
                parent.put(next, cur);
                queue.offer(next);
            }
        }

        // 回溯构建路径
        List<Pos> path = new ArrayList<>();
        if (!visited[end.r][end.c]) return path;
        Pos cur = end;
        while (cur != null) {
            path.add(cur);
            cur = parent.get(cur);
        }
        Collections.reverse(path);
        return path;
    }

    /**
     * 计算防御塔在指定位置能覆盖的路径格子
     * 使用曼哈顿距离或欧几里得距离判断
     */
    public List<Pos> getCoverage(int tr, int tc, int range, List<Pos> path) {
        List<Pos> covered = new ArrayList<>();
        for (Pos p : path) {
            int dist = Math.abs(p.r - tr) + Math.abs(p.c - tc); // 曼哈顿距离
            if (dist <= range) {
                covered.add(p);
            }
        }
        return covered;
    }

    /**
     * 贪心策略：选择最优防御塔建造位置
     * 对每一个空位，评估建造防御塔的收益，选择收益最大的位置
     */
    public List<TowerPlacement> greedyLayout(List<Pos> path, List<Tower> towers, int budget) {
        List<TowerPlacement> placements = new ArrayList<>();
        int remaining = budget;

        // 记录已被占用的建造位置
        boolean[][] occupied = new boolean[rows][cols];

        while (remaining > 0) {
            double bestValue = -1;
            Tower bestTower = null;
            Pos bestPos = null;

            // 遍历所有防御塔类型
            for (Tower tower : towers) {
                if (tower.cost > remaining) continue;

                // 遍历所有可建造位置（空地且未被占用）
                for (int i = 0; i < rows; i++) {
                    for (int j = 0; j < cols; j++) {
                        if (grid[i][j] != 0 || occupied[i][j]) continue;
                        if (path.contains(new Pos(i, j))) continue; // 路径上不能建塔

                        List<Pos> covered = getCoverage(i, j, tower.range, path);
                        if (covered.isEmpty()) continue;

                        // 计算该位置建造此塔的期望伤害值
                        // 简化模型：怪物经过每个格子的概率均等，塔在其生命周期内可攻击多次
                        double expectedDamage = covered.size() * tower.dps() * 10; // 假设存活10秒
                        double value = expectedDamage / tower.cost; // 单位造价收益

                        if (value > bestValue) {
                            bestValue = value;
                            bestTower = tower;
                            bestPos = new Pos(i, j);
                        }
                    }
                }
            }

            if (bestTower == null) break; // 没有可建造的位置了

            placements.add(new TowerPlacement(bestTower, bestPos));
            occupied[bestPos.r][bestPos.c] = true;
            remaining -= bestTower.cost;
        }

        return placements;
    }

    static class TowerPlacement {
        Tower tower;
        Pos pos;
        TowerPlacement(Tower t, Pos p) { this.tower = t; this.pos = p; }
    }

    // 演示主方法
    public static void main(String[] args) {
        // 定义地图：0=空地可建塔, 1=障碍, 2=起点, 3=终点
        int[][] map = {
            {1, 1, 1, 1, 1, 1, 1, 1},
            {1, 2, 0, 0, 0, 1, 0, 1},
            {1, 1, 1, 1, 0, 1, 0, 1},
            {1, 0, 0, 0, 0, 0, 0, 1},
            {1, 0, 1, 1, 1, 1, 0, 1},
            {1, 0, 0, 0, 0, 0, 3, 1},
            {1, 1, 1, 1, 1, 1, 1, 1}
        };

        CarrotDefense game = new CarrotDefense(map);

        // BFS搜索最短路径
        List<Pos> path = game.findShortestPath();
        System.out.println("最短入侵路径长度: " + path.size());
        System.out.print("路径: ");
        for (Pos p : path) System.out.print("(" + p.r + "," + p.c + ") ");
        System.out.println();

        // 定义防御塔类型
        List<Tower> towers = Arrays.asList(
            new Tower("箭塔", 2, 15, 50, 1.0),
            new Tower("炮塔", 3, 40, 120, 2.0),
            new Tower("魔法塔", 2, 25, 80, 1.2)
        );

        // 贪心布局
        List<TowerPlacement> layout = game.greedyLayout(path, towers, 500);
        System.out.println("\n贪心最优防御塔布局:");
        for (TowerPlacement tp : layout) {
            System.out.printf("  %s @ (%d,%d), 造价=%d%n", 
                tp.tower.name, tp.pos.r, tp.pos.c, tp.tower.cost);
        }
    }
}

算法复杂度分析

其中V为地图格点数，E为边数，P为路径长度，T为塔种类数，K为建造数量。

扩展思考

1. 动态路径调整：若防御塔可改变地形（如冰冻塔减速），怪物可能需要重新寻路，可结合A*实现动态路径规划。
2. 多波次优化：考虑多波怪物的不同类型和血量，使用线性规划求解全局最优布局。
3. 协同攻击：当多个塔的攻击范围重叠时，存在伤害溢出，需用集合覆盖问题优化。