每日算法 — 使用java实现塔防：图论路径规划与贪心防御塔布局

引言

塔防游戏（Tower Defense）是策略游戏中的经典类型，核心玩法是在敌人行进路径旁布置防御塔，阻止敌人到达终点。从算法角度看，塔防问题涉及图论中的最短路径计算、几何覆盖问题以及资源分配的贪心优化。本文将使用Java实现塔防游戏的核心AI系统，重点讲解Dijkstra算法规划敌人最短路径、贪心策略优化防御塔覆盖布局以及A*寻路处理动态障碍。

地图与路径表示

public class TowerDefenseMap {
    public static final int EMPTY = 0;
    public static final int PATH = 1;
    public static final int TOWER = 2;
    public static final int START = 3;
    public static final int END = 4;

    private final int rows, cols;
    private final int[][] grid;
    private final List<Point> enemyPath = new ArrayList<>();

    public TowerDefenseMap(int rows, int cols) {
        this.rows = rows; this.cols = cols;
        this.grid = new int[rows][cols];
    }

    public boolean isValid(int r, int c) {
        return r >= 0 && r < rows && c >= 0 && c < cols;
    }

    public boolean canBuildTower(int r, int c) {
        return isValid(r, c) && grid[r][c] == EMPTY;
    }

    public void placeTower(int r, int c) {
        if (canBuildTower(r, c)) {
            grid[r][c] = TOWER;
        }
    }

    public void removeTower(int r, int c) {
        if (isValid(r, c) && grid[r][c] == TOWER) {
            grid[r][c] = EMPTY;
        }
    }

    public int getCell(int r, int c) {
        return isValid(r, c) ? grid[r][c] : -1;
    }

    public int getRows() { return rows; }
    public int getCols() { return cols; }
}

class Point {
    int row, col;
    Point(int r, int c) { this.row = r; this.col = c; }

    double distanceTo(Point other) {
        return Math.sqrt(Math.pow(this.row - other.row, 2) + Math.pow(this.col - other.col, 2));
    }
}

Dijkstra最短路径规划

public class PathFinder {

    /**
     * Dijkstra算法：在可通行格子中寻找从起点到终点的最短路径
     * 塔占据的格子不可通行，敌人必须绕行
     */
    public List<Point> findShortestPath(TowerDefenseMap map, Point start, Point end) {
        int rows = map.getRows(), cols = map.getCols();
        double[][] dist = new double[rows][cols];
        Point[][] parent = new Point[rows][cols];
        boolean[][] visited = new boolean[rows][cols];

        for (double[] row : dist) Arrays.fill(row, Double.POSITIVE_INFINITY);
        dist[start.row][start.col] = 0;

        // 优先队列：(距离, 点)
        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingDouble(n -> n.dist));
        pq.offer(new Node(start, 0));

        int[][] directions = {{-1,0},{1,0},{0,-1},{0,1}};

        while (!pq.isEmpty()) {
            Node current = pq.poll();
            Point p = current.point;

            if (visited[p.row][p.col]) continue;
            visited[p.row][p.col] = true;

            if (p.row == end.row && p.col == end.col) break;

            for (int[] d : directions) {
                int nr = p.row + d[0], nc = p.col + d[1];
                if (!map.isValid(nr, nc)) continue;

                int cell = map.getCell(nr, nc);
                // 塔和障碍物不可通行
                if (cell == TowerDefenseMap.TOWER) continue;

                double newDist = dist[p.row][p.col] + 1.0;
                if (newDist < dist[nr][nc]) {
                    dist[nr][nc] = newDist;
                    parent[nr][nc] = p;
                    pq.offer(new Node(new Point(nr, nc), newDist));
                }
            }
        }

        // 回溯路径
        return reconstructPath(parent, start, end);
    }

    private List<Point> reconstructPath(Point[][] parent, Point start, Point end) {
        List<Point> path = new ArrayList<>();
        Point current = end;
        while (current != null) {
            path.add(current);
            if (current.row == start.row && current.col == start.col) break;
            current = parent[current.row][current.col];
        }
        Collections.reverse(path);
        return path;
    }

    static class Node {
        Point point;
        double dist;
        Node(Point p, double d) { this.point = p; this.dist = d; }
    }
}

防御塔模型与覆盖计算

public class DefenseTower {
    public enum Type {
        ARROW(3, 2.0, 1.0, 50),   // 弓箭塔：射程2，攻速1，伤害50
        CANNON(5, 3.5, 0.5, 120), // 炮塔：射程3.5，攻速0.5，伤害120（范围）
        MAGIC(4, 2.5, 0.8, 80),   // 魔法塔：射程2.5，攻速0.8，伤害80（减速）
        SNIPER(8, 5.0, 0.3, 200); // 狙击塔：射程5，攻速0.3，伤害200

        final int cost;
        final double range;
        final double attackSpeed;
        final int damage;

        Type(int cost, double range, double speed, int dmg) {
            this.cost = cost; this.range = range;
            this.attackSpeed = speed; this.damage = dmg;
        }
    }

    private final Type type;
    private final Point position;
    private double cooldown = 0;

    public DefenseTower(Type type, Point position) {
        this.type = type; this.position = position;
    }

    /**
     * 计算该塔对路径点的覆盖效果
     */
    public double calculatePathCoverage(List<Point> path) {
        double totalDamage = 0;
        for (Point pathPoint : path) {
            double d = position.distanceTo(pathPoint);
            if (d <= type.range) {
                // 伤害随距离衰减（可选）
                totalDamage += type.damage * type.attackSpeed;
            }
        }
        return totalDamage;
    }

    /**
     * 获取该塔射程范围内覆盖的路径点列表
     */
    public List<Point> getCoveredPathPoints(List<Point> path) {
        List<Point> covered = new ArrayList<>();
        for (Point p : path) {
            if (position.distanceTo(p) <= type.range) {
                covered.add(p);
            }
        }
        return covered;
    }

    public Type getType() { return type; }
    public Point getPosition() { return position; }
    public int getCost() { return type.cost; }
    public double getRange() { return type.range; }
}

贪心防御塔布局算法

public class TowerPlacementOptimizer {

    /**
     * 贪心策略：每次选择"单位成本覆盖率最高"的位置放置防御塔
     * 
     * 覆盖率定义为：塔射程范围内路径点的期望总伤害
     */
    public List<DefenseTower> greedyPlacement(TowerDefenseMap map, List<Point> path,
                                               int budget, List<DefenseTower.Type> availableTypes) {
        List<DefenseTower> placedTowers = new ArrayList<>();
        int remainingBudget = budget;

        // 候选位置：路径周围的可建造格子
        Set<Point> candidates = generateCandidatePositions(map, path);

        while (remainingBudget > 0) {
            double bestEfficiency = 0;
            DefenseTower bestTower = null;
            Point bestPos = null;
            DefenseTower.Type bestType = null;

            for (Point pos : candidates) {
                if (!map.canBuildTower(pos.row, pos.col)) continue;

                for (DefenseTower.Type type : availableTypes) {
                    if (type.cost > remainingBudget) continue;

                    DefenseTower tower = new DefenseTower(type, pos);
                    double coverage = tower.calculatePathCoverage(path);
                    double efficiency = coverage / type.cost; // 单位成本覆盖率

                    if (efficiency > bestEfficiency) {
                        bestEfficiency = efficiency;
                        bestTower = tower;
                        bestPos = pos;
                        bestType = type;
                    }
                }
            }

            if (bestTower == null) break; // 无法继续建造

            // 放置最优塔
            map.placeTower(bestPos.row, bestPos.col);
            placedTowers.add(bestTower);
            remainingBudget -= bestType.cost;

            // 移除已使用的位置
            candidates.remove(bestPos);
        }

        return placedTowers;
    }

    /**
     * 生成候选位置：路径周围曼哈顿距离为2以内的可建造格子
     */
    private Set<Point> generateCandidatePositions(TowerDefenseMap map, List<Point> path) {
        Set<Point> candidates = new HashSet<>();
        for (Point p : path) {
            for (int dr = -2; dr <= 2; dr++) {
                for (int dc = -2; dc <= 2; dc++) {
                    int nr = p.row + dr, nc = p.col + dc;
                    if (map.canBuildTower(nr, nc)) {
                        candidates.add(new Point(nr, nc));
                    }
                }
            }
        }
        return candidates;
    }

    /**
     * 改进策略：考虑塔的协同效应
     * 避免过度集中，追求路径全覆盖
     */
    public List<DefenseTower>协同优化布局(TowerDefenseMap map, List<Point> path,
                                           int budget, List<DefenseTower.Type> availableTypes) {
        List<DefenseTower> placedTowers = new ArrayList<>();
        int remainingBudget = budget;
        Set<Point> uncoveredPath = new HashSet<>(path);
        Set<Point> candidates = generateCandidatePositions(map, path);

        while (remainingBudget > 0 && !uncoveredPath.isEmpty()) {
            double bestScore = -1;
            DefenseTower bestTower = null;
            Point bestPos = null;

            for (Point pos : candidates) {
                if (!map.canBuildTower(pos.row, pos.col)) continue;

                for (DefenseTower.Type type : availableTypes) {
                    if (type.cost > remainingBudget) continue;

                    DefenseTower tower = new DefenseTower(type, pos);
                    Set<Point> newlyCovered = new HashSet<>(tower.getCoveredPathPoints(path));
                    newlyCovered.retainAll(uncoveredPath); // 只计算新覆盖的点

                    // 评分：优先覆盖未覆盖区域，同时考虑总伤害
                    double coverageBonus = newlyCovered.size() * 1000;
                    double damageScore = tower.calculatePathCoverage(path);
                    double score = (coverageBonus + damageScore) / type.cost;

                    if (score > bestScore) {
                        bestScore = score;
                        bestTower = tower;
                        bestPos = pos;
                    }
                }
            }

            if (bestTower == null) break;

            map.placeTower(bestPos.row, bestPos.col);
            placedTowers.add(bestTower);
            remainingBudget -= bestTower.getCost();
            uncoveredPath.removeAll(bestTower.getCoveredPathPoints(path));
            candidates.remove(bestPos);
        }

        return placedTowers;
    }
}

A*动态寻路（敌人AI）

public class AStarPathfinder {

    /**
     * A*寻路：敌人智能选择路径，考虑防御塔威胁
     * 启发函数使用曼哈顿距离
     */
    public List<Point> findPathAStar(TowerDefenseMap map, Point start, Point end,
                                      List<DefenseTower> enemyTowers) {
        int rows = map.getRows(), cols = map.getCols();
        double[][] gScore = new double[rows][cols];
        double[][] fScore = new double[rows][cols];
        Point[][] parent = new Point[rows][cols];
        boolean[][] closed = new boolean[rows][cols];

        for (double[] row : gScore) Arrays.fill(row, Double.POSITIVE_INFINITY);
        for (double[] row : fScore) Arrays.fill(row, Double.POSITIVE_INFINITY);

        gScore[start.row][start.col] = 0;
        fScore[start.row][start.col] = heuristic(start, end);

        PriorityQueue<AStarNode> open = new PriorityQueue<>(
            Comparator.comparingDouble(n -> n.fScore));
        open.offer(new AStarNode(start, fScore[start.row][start.col]));

        int[][] directions = {{-1,0},{1,0},{0,-1},{0,1}};

        while (!open.isEmpty()) {
            AStarNode current = open.poll();
            Point p = current.point;

            if (closed[p.row][p.col]) continue;
            closed[p.row][p.col] = true;

            if (p.row == end.row && p.col == end.col) {
                return reconstructPath(parent, start, end);
            }

            for (int[] d : directions) {
                int nr = p.row + d[0], nc = p.col + d[1];
                if (!map.isValid(nr, nc)) continue;
                if (map.getCell(nr, nc) == TowerDefenseMap.TOWER) continue;
                if (closed[nr][nc]) continue;

                double moveCost = 1.0 + calculateThreatCost(nr, nc, enemyTowers);
                double tentativeG = gScore[p.row][p.col] + moveCost;

                if (tentativeG < gScore[nr][nc]) {
                    gScore[nr][nc] = tentativeG;
                    fScore[nr][nc] = tentativeG + heuristic(new Point(nr, nc), end);
                    parent[nr][nc] = p;
                    open.offer(new AStarNode(new Point(nr, nc), fScore[nr][nc]));
                }
            }
        }

        return new ArrayList<>(); // 无路径
    }

    private double heuristic(Point a, Point b) {
        return Math.abs(a.row - b.row) + Math.abs(a.col - b.col);
    }

    /**
     * 威胁成本：经过防御塔附近的路径成本增加
     */
    private double calculateThreatCost(int r, int c, List<DefenseTower> towers) {
        double threat = 0;
        for (DefenseTower t : towers) {
            double d = Math.sqrt(Math.pow(r - t.getPosition().row, 2) 
                               + Math.pow(c - t.getPosition().col, 2));
            if (d <= t.getRange()) {
                threat += t.getType().damage / (d + 0.1);
            }
        }
        return threat * 0.01; // 权重系数
    }

    static class AStarNode {
        Point point;
        double fScore;
        AStarNode(Point p, double f) { this.point = p; this.fScore = f; }
    }

    private List<Point> reconstructPath(Point[][] parent, Point start, Point end) {
        List<Point> path = new ArrayList<>();
        Point current = end;
        while (current != null) {
            path.add(current);
            if (current.row == start.row && current.col == start.col) break;
            current = parent[current.row][current.col];
        }
        Collections.reverse(path);
        return path;
    }
}

完整模拟系统

public class TowerDefenseSimulator {
    public static void main(String[] args) {
        // 创建10x10地图
        TowerDefenseMap map = new TowerDefenseMap(10, 10);
        Point start = new Point(0, 0);
        Point end = new Point(9, 9);

        // 初始路径
        PathFinder pathFinder = new PathFinder();
        List<Point> initialPath = pathFinder.findShortestPath(map, start, end);
        System.out.println("初始路径长度: " + initialPath.size());

        // 可用防御塔类型
        List<DefenseTower.Type> availableTypes = Arrays.asList(
            DefenseTower.Type.ARROW,
            DefenseTower.Type.CANNON,
            DefenseTower.Type.MAGIC
        );

        // 贪心布局
        TowerPlacementOptimizer optimizer = new TowerPlacementOptimizer();
        List<DefenseTower> towers = optimizer.协同优化布局(map, initialPath, 30, availableTypes);

        System.out.println("\n=== 防御塔布局 ===");
        for (DefenseTower t : towers) {
            System.out.printf("%s塔 位置(%d,%d) 射程%.1f 伤害%d%n",
                t.getType(), t.getPosition().row, t.getPosition().col,
                t.getRange(), t.getType().damage);
        }

        // 敌人重新寻路
        AStarPathfinder aStar = new AStarPathfinder();
        List<Point> newPath = aStar.findPathAStar(map, start, end, towers);
        System.out.println("\n敌人绕行路径长度: " + newPath.size());

        // 计算总覆盖伤害
        double totalCoverage = 0;
        for (DefenseTower t : towers) {
            totalCoverage += t.calculatePathCoverage(newPath);
        }
        System.out.printf("路径总覆盖伤害: %.2f%n", totalCoverage);
    }
}

复杂度分析

其中V为地图格子数，C为候选位置数，T为塔类型数，P为路径点数，b为分支因子，d为深度。

总结

本文从图论和优化角度分析了塔防游戏的核心算法，通过Dijkstra计算最短路径、贪心策略优化防御塔布局、A*算法实现敌人智能绕行。这些算法不仅在游戏开发中有广泛应用，其思想也可以延伸到网络路由优化、安防监控覆盖等实际工程问题中。