每日算法 — 使用java实现坦克大战：BFS路径规划与A*寻路算法

引言

坦克大战是经典街机游戏，核心玩法包括玩家操控坦克移动射击、敌方坦克自动追踪、子弹碰撞检测等。本文用Java实现坦克大战的AI核心，重点讲解敌方坦克的BFS路径规划与A*寻路算法，让AI坦克能够智能绕过障碍物追击玩家。

核心算法概览

敌方坦克AI需要解决三个核心问题：
1. 路径搜索：在带障碍的网格地图中找到从当前位置到玩家的最短路径
2. 避障策略：BFS保证最短路径，A通过启发式函数加速搜索
3. 动态更新*：玩家移动后实时重新计算路径

地图建模

将游戏地图抽象为二维网格，每个格子有三种状态：空地、障碍物、玩家位置。

public class GameMap {
    public static final int EMPTY = 0;   // 空地
    public static final int WALL = 1;    // 钢墙（不可破坏）
    public static final int BRICK = 2;   // 砖墙（可破坏）
    public static final int WATER = 3;   // 水域（不可通过）
    public static final int PLAYER = 4;  // 玩家坦克

    private int[][] grid;
    private int rows, cols;

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

    // 判断坐标是否可通行（BFS/A*的邻居扩展依据）
    public boolean isWalkable(int x, int y) {
        if (x < 0 || x >= rows || y < 0 || y >= cols) return false;
        return grid[x][y] == EMPTY || grid[x][y] == PLAYER;
    }

    // 设置格子状态
    public void setCell(int x, int y, int type) {
        grid[x][y] = type;
    }

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

BFS路径规划

BFS（广度优先搜索）适用于无权图的最短路径搜索。敌方坦克在网格上移动，每次可向上下左右四个方向前进一格，BFS能保证找到步数最少的路径。

import java.util.*;

public class BFSPathfinder {

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

    /**
     * BFS寻找从start到target的最短路径
     * @param map 游戏地图
     * @param start 起点坐标 [x, y]
     * @param target 终点坐标 [x, y]
     * @return 路径点列表，若不可达返回空列表
     */
    public List<int[]> findPath(GameMap map, int[] start, int[] target) {
        int rows = map.getRows();
        int cols = map.getCols();
        boolean[][] visited = new boolean[rows][cols];
        int[][] parent = new int[rows][cols]; // 记录每个点的父节点方向
        Arrays.fill(parent, -1);

        Queue<int[]> queue = new LinkedList<>();
        queue.offer(start);
        visited[start[0]][start[1]] = true;

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();

            // 到达目标
            if (curr[0] == target[0] && curr[1] == target[1]) {
                return reconstructPath(parent, start, target, rows, cols);
            }

            // 扩展四个邻居
            for (int i = 0; i < 4; i++) {
                int nx = curr[0] + DIRS[i][0];
                int ny = curr[1] + DIRS[i][1];

                if (map.isWalkable(nx, ny) && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    parent[nx * cols + ny] = curr[0] * cols + curr[1]; // 记录父节点
                    queue.offer(new int[]{nx, ny});
                }
            }
        }

        return new ArrayList<>(); // 不可达
    }

    // 从终点回溯 reconstruct 路径
    private List<int[]> reconstructPath(int[][] parent, int[] start, int[] target, 
                                        int rows, int cols) {
        List<int[]> path = new ArrayList<>();
        int currIdx = target[0] * cols + target[1];
        int startIdx = start[0] * cols + start[1];

        while (currIdx != startIdx) {
            int x = currIdx / cols;
            int y = currIdx % cols;
            path.add(0, new int[]{x, y});
            currIdx = parent[x][y];
        }
        path.add(0, start);
        return path;
    }
}

A*寻路算法优化

BFS在地图较大时搜索范围过广。A算法引入曼哈顿距离*作为启发式函数，优先扩展离目标更近的节点，大幅提升搜索效率。

import java.util.*;

public class AStarPathfinder {

    private static final int[][] DIRS = {{-1,0},{1,0},{0,-1},{0,1}};

    // A*节点：记录坐标、g值（起点代价）、h值（启发估计）
    static class Node implements Comparable<Node> {
        int x, y;
        int g; // 从起点到当前节点的实际代价
        int h; // 到目标的估计代价（曼哈顿距离）
        Node parent;

        Node(int x, int y, int g, int h, Node parent) {
            this.x = x; this.y = y;
            this.g = g; this.h = h;
            this.parent = parent;
        }

        int f() { return g + h; } // 总评估值

        @Override
        public int compareTo(Node o) {
            return Integer.compare(this.f(), o.f());
        }
    }

    /**
     * A*寻路，返回最短路径
     * 启发函数使用曼哈顿距离：|x1-x2| + |y1-y2|
     */
    public List<int[]> findPath(GameMap map, int[] start, int[] target) {
        int rows = map.getRows();
        int cols = map.getCols();

        PriorityQueue<Node> openSet = new PriorityQueue<>();
        boolean[][] closedSet = new boolean[rows][cols];

        Node startNode = new Node(start[0], start[1], 0, 
                                  heuristic(start, target), null);
        openSet.offer(startNode);

        while (!openSet.isEmpty()) {
            Node curr = openSet.poll();

            // 已处理过则跳过（优先队列中可能存在旧节点）
            if (closedSet[curr.x][curr.y]) continue;
            closedSet[curr.x][curr.y] = true;

            // 到达目标
            if (curr.x == target[0] && curr.y == target[1]) {
                return reconstructPath(curr);
            }

            // 扩展邻居
            for (int[] d : DIRS) {
                int nx = curr.x + d[0];
                int ny = curr.y + d[1];

                if (!map.isWalkable(nx, ny) || closedSet[nx][ny]) continue;

                int ng = curr.g + 1; // 每步代价为1
                int nh = heuristic(new int[]{nx, ny}, target);
                openSet.offer(new Node(nx, ny, ng, nh, curr));
            }
        }

        return new ArrayList<>(); // 不可达
    }

    // 曼哈顿距离启发式（网格四方向移动的最优下界）
    private int heuristic(int[] a, int[] b) {
        return Math.abs(a[0] - b[0]) + Math.abs(a[1] - b[1]);
    }

    // 回溯 reconstruct 路径
    private List<int[]> reconstructPath(Node end) {
        List<int[]> path = new LinkedList<>();
        Node curr = end;
        while (curr != null) {
            path.add(0, new int[]{curr.x, curr.y});
            curr = curr.parent;
        }
        return path;
    }
}

敌方坦克AI控制器

将寻路算法封装为敌方坦克的AI控制器，每帧根据玩家位置更新路径。

public class EnemyTankAI {
    private AStarPathfinder pathfinder;
    private List<int[]> currentPath;
    private int pathIndex;
    private int[] tankPos;   // 当前位置 [x, y]
    private int[] playerPos; // 玩家位置 [x, y]
    private long lastUpdateTime;
    private static final long UPDATE_INTERVAL = 500; // 每500ms重新计算路径

    public EnemyTankAI() {
        this.pathfinder = new AStarPathfinder();
        this.currentPath = new ArrayList<>();
        this.pathIndex = 0;
    }

    /**
     * 更新AI状态，由游戏主循环每帧调用
     */
    public void update(GameMap map, int[] tankPos, int[] playerPos, long currentTime) {
        this.tankPos = tankPos;
        this.playerPos = playerPos;

        // 定时重新规划路径（玩家可能已移动）
        if (currentTime - lastUpdateTime > UPDATE_INTERVAL || currentPath.isEmpty()) {
            currentPath = pathfinder.findPath(map, tankPos, playerPos);
            pathIndex = 0;
            lastUpdateTime = currentTime;
        }

        // 沿路径移动一步
        moveAlongPath();
    }

    private void moveAlongPath() {
        if (pathIndex < currentPath.size() - 1) {
            pathIndex++;
            int[] next = currentPath.get(pathIndex);
            tankPos[0] = next[0];
            tankPos[1] = next[1];
        }
    }

    // 获取下一步移动方向（用于动画和朝向）
    public int getNextDirection() {
        if (pathIndex >= currentPath.size() - 1) return -1;
        int[] curr = currentPath.get(pathIndex);
        int[] next = currentPath.get(pathIndex + 1);
        if (next[0] < curr[0]) return 0; // 上
        if (next[0] > curr[0]) return 1; // 下
        if (next[1] < curr[1]) return 2; // 左
        if (next[1] > curr[1]) return 3; // 右
        return -1;
    }
}

子弹碰撞检测

坦克发射的子弹需要检测是否击中墙壁或敌方坦克，使用简单的矩形碰撞检测。

public class Bullet {
    private double x, y;
    private double speed = 5.0;
    private int direction; // 0上 1下 2左 3右

    public Bullet(double x, double y, int direction) {
        this.x = x; this.y = y; this.direction = direction;
    }

    public void update() {
        switch (direction) {
            case 0: y -= speed; break;
            case 1: y += speed; break;
            case 2: x -= speed; break;
            case 3: x += speed; break;
        }
    }

    /**
     * AABB矩形碰撞检测
     * @param rectX, rectY, width, height 目标矩形
     */
    public boolean checkCollision(double rectX, double rectY, double width, double height) {
        return x < rectX + width && x + 4 > rectX &&
               y < rectY + height && y + 4 > rectY;
    }

    // 将子弹坐标映射到网格坐标，检测是否击中墙体
    public boolean checkWallCollision(GameMap map) {
        int gridX = (int) (y / 32); // 假设每个格子32像素
        int gridY = (int) (x / 32);
        if (gridX < 0 || gridX >= map.getRows() || gridY < 0 || gridY >= map.getCols())
            return true; // 超出边界视为碰撞
        return map.getCell(gridX, gridY) == GameMap.WALL ||
               map.getCell(gridX, gridY) == GameMap.BRICK;
    }
}

主程序入口

public class TankBattleGame {
    public static void main(String[] args) {
        // 初始化13x13地图
        GameMap map = new GameMap(13, 13);

        // 设置外围钢墙
        for (int i = 0; i < 13; i++) {
            map.setCell(0, i, GameMap.WALL);
            map.setCell(12, i, GameMap.WALL);
            map.setCell(i, 0, GameMap.WALL);
            map.setCell(i, 12, GameMap.WALL);
        }

        // 设置内部障碍物
        map.setCell(3, 3, GameMap.BRICK);
        map.setCell(3, 4, GameMap.BRICK);
        map.setCell(4, 3, GameMap.BRICK);
        map.setCell(8, 8, GameMap.WALL);
        map.setCell(8, 9, GameMap.WALL);

        int[] playerPos = {1, 1};
        int[] enemyPos = {11, 11};

        EnemyTankAI enemyAI = new EnemyTankAI();
        AStarPathfinder pathfinder = new AStarPathfinder();

        // 测试A*寻路
        List<int[]> path = pathfinder.findPath(map, enemyPos, playerPos);
        System.out.println("A*找到路径长度：" + path.size());
        for (int[] p : path) {
            System.out.println("(" + p[0] + "," + p[1] + ")");
        }
    }
}

复杂度分析

其中 m、n 为地图行列数。A的启发式函数（曼哈顿距离）满足可采纳性（admissible），即永不高估实际代价，因此A保证找到最优解。

总结

本文通过坦克大战游戏场景，讲解了BFS与A两种路径搜索算法。BFS作为基础保证最短路径正确性，A通过曼哈顿距离启发式大幅剪枝搜索空间。读者可以在此基础上扩展：
– 加入权重地图（不同地形移动代价不同），改用Dijkstra或带权A*
– 实现多敌方坦克的协同追击策略
– 加入子弹躲避逻辑，让AI更加智能