每日算法 — 使用java实现超级玛丽：平台碰撞检测与A星路径规划

一、游戏简介与算法目标

超级玛丽（Super Mario）是经典的横版平台跳跃游戏，玩家控制角色在2D关卡中奔跑、跳跃，躲避敌人并收集金币。游戏的核心挑战在于精确的物理碰撞检测和智能的敌人/玩家路径规划。

本文的核心算法目标包括：
1. AABB碰撞检测：角色与平台、敌人、道具之间的轴对齐包围盒检测
2. 平台物理模拟：重力、跳跃抛物线、速度摩擦等物理效果
3. A星路径规划：为AI敌人或自动演示计算从起点到终点的最优路径
4. TileMap地图表示：使用二维网格高效表示关卡地形

二、核心算法原理

2.1 TileMap地图表示

将关卡划分为固定大小的瓦片网格（如16×16像素），每个瓦片标记为：
– EMPTY(0)：可通行
– SOLID(1)：不可通行的平台/地面
– COIN(2)：金币
– ENEMY(3)：敌人出生点

这种表示将连续空间离散化，碰撞检测从O(n²)降到O(1)（只需查询角色所在瓦片）。

2.2 AABB碰撞检测

轴对齐包围盒（Axis-Aligned Bounding Box）碰撞检测：

两个AABB相交的条件：
box1.minX < box2.maxX && box1.maxX > box2.minX &&
box1.minY < box2.maxY && box1.maxY > box2.minY

2.3 A星路径规划

A星算法在TileMap上寻找最短路径：
– g(n)：从起点到节点n的实际代价
– h(n)：从节点n到终点的启发式估计（使用曼哈顿距离）
– f(n) = g(n) + h(n)：节点n的总评估代价

每次扩展f值最小的节点，直到到达终点。

2.4 平台物理

简化物理模型：
– 重力加速度：vy += g × dt
– 跳跃初速度：vy = -jumpSpeed（按下跳跃键时）
– 水平摩擦：vx = friction（每帧衰减）
– 最大速度限制*：|vx| ≤ maxSpeed

三、Java完整实现

import java.util.*;

/**
 * 超级玛丽核心算法：平台碰撞检测与A星路径规划
 * 核心算法：TileMap、AABB碰撞检测、平台物理模拟、A星寻路
 */
public class SuperMario {

    // 瓦片类型
    enum TileType {
        EMPTY,   // 0-空地
        SOLID,   // 1-固体平台
        COIN,    // 2-金币
        GOAL     // 3-终点旗帜
    }

    // 碰撞盒
    static class AABB {
        double x, y;      // 中心坐标
        double width, height; // 宽高

        AABB(double x, double y, double width, double height) {
            this.x = x;
            this.y = y;
            this.width = width;
            this.height = height;
        }

        double minX() { return x - width / 2; }
        double maxX() { return x + width / 2; }
        double minY() { return y - height / 2; }
        double maxY() { return y + height / 2; }

        /**
         * AABB碰撞检测核心算法
         * 时间复杂度: O(1)
         */
        boolean intersects(AABB other) {
            return this.minX() < other.maxX() && this.maxX() > other.minX()
                && this.minY() < other.maxY() && this.maxY() > other.minY();
        }

        /**
         * 获取碰撞深度（用于碰撞响应）
         */
        double[] getOverlap(AABB other) {
            double overlapX = Math.min(this.maxX(), other.maxX()) 
                            - Math.max(this.minX(), other.minX());
            double overlapY = Math.min(this.maxY(), other.maxY()) 
                            - Math.max(this.minY(), other.minY());
            return new double[]{overlapX, overlapY};
        }
    }

    // 游戏实体
    static class Entity {
        AABB bbox;           // 碰撞盒
        double vx, vy;       // 速度
        boolean onGround;    // 是否着地
        boolean facingRight; // 朝向

        Entity(double x, double y, double w, double h) {
            this.bbox = new AABB(x, y, w, h);
            this.vx = 0;
            this.vy = 0;
            this.onGround = false;
            this.facingRight = true;
        }
    }

    // A星节点
    static class AStarNode implements Comparable<AStarNode> {
        int x, y;           // 网格坐标
        double g, h;        // 实际代价和启发式代价
        AStarNode parent;   // 父节点

        AStarNode(int x, int y) {
            this.x = x;
            this.y = y;
            this.g = Double.POSITIVE_INFINITY;
            this.h = 0;
            this.parent = null;
        }

        double f() { return g + h; }

        @Override
        public int compareTo(AStarNode other) {
            return Double.compare(this.f(), other.f());
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof AStarNode)) return false;
            AStarNode other = (AStarNode) o;
            return this.x == other.x && this.y == other.y;
        }

        @Override
        public int hashCode() {
            return x * 131 + y;
        }
    }

    // 物理参数
    private static final double GRAVITY = 800.0;       // 重力加速度(px/s²)
    private static final double JUMP_SPEED = 400.0;    // 跳跃初速度(px/s)
    private static final double MOVE_SPEED = 200.0;    // 水平移动速度(px/s)
    private static final double FRICTION = 0.85;       // 地面摩擦系数
    private static final double AIR_RESISTANCE = 0.98; // 空气阻力
    private static final double MAX_FALL_SPEED = 600.0;// 最大下落速度
    private static final double TILE_SIZE = 32.0;      // 瓦片大小(px)

    private TileType[][] tileMap;    // 关卡地图
    private int mapWidth, mapHeight; // 地图尺寸(瓦片数)
    private Entity player;           // 玩家角色
    private Entity goal;             // 终点
    private int coinsCollected;      // 收集金币数
    private double dt = 1.0 / 60.0;  // 固定时间步长(60fps)

    public SuperMario(int width, int height) {
        this.mapWidth = width;
        this.mapHeight = height;
        this.tileMap = new TileType[height][width];
        this.coinsCollected = 0;
        initializeMap();
    }

    /**
     * 初始化示例关卡
     */
    private void initializeMap() {
        // 默认全部为空
        for (int y = 0; y < mapHeight; y++) {
            for (int x = 0; x < mapWidth; x++) {
                tileMap[y][x] = TileType.EMPTY;
            }
        }

        // 生成地面和平台
        // 地面层
        for (int x = 0; x < mapWidth; x++) {
            tileMap[mapHeight - 1][x] = TileType.SOLID;
            tileMap[mapHeight - 2][x] = TileType.SOLID;
        }

        // 一些平台
        int[][] platforms = {
            {5, mapHeight - 5, 3},   // x, y, width
            {10, mapHeight - 7, 4},
            {16, mapHeight - 6, 3},
            {22, mapHeight - 8, 5},
            {28, mapHeight - 5, 3}
        };

        for (int[] p : platforms) {
            for (int i = 0; i < p[2]; i++) {
                tileMap[p[1]][p[0] + i] = TileType.SOLID;
            }
        }

        // 放置金币
        tileMap[mapHeight - 3][6] = TileType.COIN;
        tileMap[mapHeight - 3][7] = TileType.COIN;
        tileMap[mapHeight - 8][11] = TileType.COIN;
        tileMap[mapHeight - 8][12] = TileType.COIN;
        tileMap[mapHeight - 7][17] = TileType.COIN;
        tileMap[mapHeight - 9][24] = TileType.COIN;

        // 终点
        tileMap[mapHeight - 3][mapWidth - 3] = TileType.GOAL;

        // 初始化玩家和终点实体
        player = new Entity(TILE_SIZE * 1.5, TILE_SIZE * (mapHeight - 3.5), 
                           TILE_SIZE * 0.8, TILE_SIZE * 0.9);
        goal = new Entity(TILE_SIZE * (mapWidth - 3), TILE_SIZE * (mapHeight - 3.5),
                         TILE_SIZE, TILE_SIZE);
    }

    /**
     * 获取瓦片类型
     */
    public TileType getTile(int tileX, int tileY) {
        if (tileX < 0 || tileX >= mapWidth || tileY < 0 || tileY >= mapHeight) {
            return TileType.SOLID; // 地图外视为固体
        }
        return tileMap[tileY][tileX];
    }

    /**
     * 设置瓦片类型
     */
    public void setTile(int tileX, int tileY, TileType type) {
        if (tileX >= 0 && tileX < mapWidth && tileY >= 0 && tileY < mapHeight) {
            tileMap[tileY][tileX] = type;
        }
    }

    /**
     * 将像素坐标转换为瓦片坐标
     */
    public int[] pixelToTile(double px, double py) {
        return new int[]{(int) (px / TILE_SIZE), (int) (py / TILE_SIZE)};
    }

    /**
     * 物理更新：重力、摩擦、速度积分
     */
    public void updatePhysics(Entity entity) {
        // 应用重力
        entity.vy += GRAVITY * dt;
        entity.vy = Math.min(entity.vy, MAX_FALL_SPEED);

        // 应用摩擦/阻力
        if (entity.onGround) {
            entity.vx *= FRICTION;
        } else {
            entity.vx *= AIR_RESISTANCE;
        }

        // 速度积分得到位移
        double newX = entity.bbox.x + entity.vx * dt;
        double newY = entity.bbox.y + entity.vy * dt;

        // X方向碰撞检测与响应
        entity.bbox.x = newX;
        resolveHorizontalCollision(entity);

        // Y方向碰撞检测与响应
        entity.bbox.y = newY;
        resolveVerticalCollision(entity);
    }

    /**
     * 水平方向碰撞解析
     */
    private void resolveHorizontalCollision(Entity entity) {
        // 获取实体占据的瓦片范围
        int minTX = (int) (entity.bbox.minX() / TILE_SIZE);
        int maxTX = (int) (entity.bbox.maxX() / TILE_SIZE);
        int minTY = (int) (entity.bbox.minY() / TILE_SIZE);
        int maxTY = (int) (entity.bbox.maxY() / TILE_SIZE);

        for (int ty = minTY; ty <= maxTY; ty++) {
            for (int tx = minTX; tx <= maxTX; tx++) {
                if (getTile(tx, ty) == TileType.SOLID) {
                    AABB tileBox = new AABB(
                        tx * TILE_SIZE + TILE_SIZE / 2,
                        ty * TILE_SIZE + TILE_SIZE / 2,
                        TILE_SIZE, TILE_SIZE
                    );

                    if (entity.bbox.intersects(tileBox)) {
                        double[] overlap = entity.bbox.getOverlap(tileBox);
                        // 水平碰撞：根据速度方向推出
                        if (entity.vx > 0) {
                            entity.bbox.x = tileBox.minX() - entity.bbox.width / 2 - 0.1;
                        } else if (entity.vx < 0) {
                            entity.bbox.x = tileBox.maxX() + entity.bbox.width / 2 + 0.1;
                        }
                        entity.vx = 0;
                    }
                }
            }
        }
    }

    /**
     * 垂直方向碰撞解析
     */
    private void resolveVerticalCollision(Entity entity) {
        entity.onGround = false;

        int minTX = (int) (entity.bbox.minX() / TILE_SIZE);
        int maxTX = (int) (entity.bbox.maxX() / TILE_SIZE);
        int minTY = (int) (entity.bbox.minY() / TILE_SIZE);
        int maxTY = (int) (entity.bbox.maxY() / TILE_SIZE);

        for (int ty = minTY; ty <= maxTY; ty++) {
            for (int tx = minTX; tx <= maxTX; tx++) {
                TileType tile = getTile(tx, ty);
                if (tile == TileType.SOLID || tile == TileType.GOAL) {
                    AABB tileBox = new AABB(
                        tx * TILE_SIZE + TILE_SIZE / 2,
                        ty * TILE_SIZE + TILE_SIZE / 2,
                        TILE_SIZE, TILE_SIZE
                    );

                    if (entity.bbox.intersects(tileBox)) {
                        if (entity.vy > 0) {
                            // 下落撞到地面
                            entity.bbox.y = tileBox.minY() - entity.bbox.height / 2 - 0.1;
                            entity.onGround = true;
                            entity.vy = 0;
                        } else if (entity.vy < 0) {
                            // 上升撞到天花板
                            entity.bbox.y = tileBox.maxY() + entity.bbox.height / 2 + 0.1;
                            entity.vy = 0;
                        }
                    }
                }

                // 检测金币收集
                if (tile == TileType.COIN) {
                    AABB coinBox = new AABB(
                        tx * TILE_SIZE + TILE_SIZE / 2,
                        ty * TILE_SIZE + TILE_SIZE / 2,
                        TILE_SIZE, TILE_SIZE
                    );
                    if (entity.bbox.intersects(coinBox)) {
                        coinsCollected++;
                        setTile(tx, ty, TileType.EMPTY);
                        System.out.println("收集金币! 总计: " + coinsCollected);
                    }
                }
            }
        }
    }

    /**
     * 玩家跳跃
     */
    public void jump() {
        if (player.onGround) {
            player.vy = -JUMP_SPEED;
            player.onGround = false;
        }
    }

    /**
     * 玩家水平移动
     */
    public void moveHorizontal(double direction) {
        player.vx += direction * MOVE_SPEED * 0.3;
        player.vx = Math.max(-MOVE_SPEED, Math.min(MOVE_SPEED, player.vx));
        player.facingRight = direction > 0;
    }

    /**
     * A星路径规划核心算法
     * 在TileMap上寻找从起点到终点的最短路径
     * 时间复杂度: O(n log n)，n为访问节点数
     */
    public List<int[]> findPathAStar(int startX, int startY, int endX, int endY) {
        PriorityQueue<AStarNode> openSet = new PriorityQueue<>();
        Set<String> closedSet = new HashSet<>();
        Map<String, AStarNode> nodeMap = new HashMap<>();

        AStarNode start = new AStarNode(startX, startY);
        start.g = 0;
        start.h = heuristic(startX, startY, endX, endY);
        openSet.add(start);
        nodeMap.put(startX + "," + startY, start);

        // 移动方向：上下左右，以及对角线（可选）
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

        while (!openSet.isEmpty()) {
            AStarNode current = openSet.poll();
            String key = current.x + "," + current.y;

            if (closedSet.contains(key)) continue;
            closedSet.add(key);

            // 到达终点
            if (current.x == endX && current.y == endY) {
                return reconstructPath(current);
            }

            // 扩展邻居
            for (int[] dir : directions) {
                int nx = current.x + dir[0];
                int ny = current.y + dir[1];

                // 边界检查
                if (nx < 0 || nx >= mapWidth || ny < 0 || ny >= mapHeight) continue;

                // 障碍物检查：目标位置必须是空的或终点
                TileType tile = getTile(nx, ny);
                if (tile == TileType.SOLID) continue;

                String nKey = nx + "," + ny;
                if (closedSet.contains(nKey)) continue;

                double tentativeG = current.g + 1; // 每步代价为1

                AStarNode neighbor = nodeMap.get(nKey);
                if (neighbor == null) {
                    neighbor = new AStarNode(nx, ny);
                    nodeMap.put(nKey, neighbor);
                }

                if (tentativeG < neighbor.g) {
                    neighbor.g = tentativeG;
                    neighbor.h = heuristic(nx, ny, endX, endY);
                    neighbor.parent = current;
                    openSet.add(neighbor);
                }
            }
        }

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

    /**
     * 曼哈顿距离启发式函数
     */
    private double heuristic(int x1, int y1, int x2, int y2) {
        return Math.abs(x1 - x2) + Math.abs(y1 - y2);
    }

    /**
     * 重建路径
     */
    private List<int[]> reconstructPath(AStarNode endNode) {
        List<int[]> path = new ArrayList<>();
        AStarNode current = endNode;
        while (current != null) {
            path.add(0, new int[]{current.x, current.y});
            current = current.parent;
        }
        return path;
    }

    /**
     * AI自动寻路并移动玩家
     */
    public void aiMoveToGoal() {
        int[] startTile = pixelToTile(player.bbox.x, player.bbox.y);
        int[] endTile = pixelToTile(goal.bbox.x, goal.bbox.y);

        List<int[]> path = findPathAStar(startTile[0], startTile[1], 
                                         endTile[0], endTile[1]);

        if (path.size() < 2) {
            System.out.println("无法找到路径！");
            return;
        }

        System.out.println("A星路径规划完成，路径长度: " + path.size() + " 步");

        // 显示路径前10个点
        System.out.print("路径预览: ");
        for (int i = 0; i < Math.min(10, path.size()); i++) {
            System.out.print("(" + path.get(i)[0] + "," + path.get(i)[1] + ") ");
        }
        System.out.println(path.size() > 10 ? "..." : "");
    }

    /**
     * 打印当前地图状态
     */
    public void printMap() {
        int[] pTile = pixelToTile(player.bbox.x, player.bbox.y);
        System.out.println("\n=== 当前关卡地图 ===");
        for (int y = 0; y < mapHeight; y++) {
            for (int x = 0; x < mapWidth; x++) {
                if (x == pTile[0] && y == pTile[1]) {
                    System.out.print("P"); // 玩家位置
                } else {
                    switch (tileMap[y][x]) {
                        case EMPTY: System.out.print("."); break;
                        case SOLID: System.out.print("#"); break;
                        case COIN:  System.out.print("$"); break;
                        case GOAL:  System.out.print("G"); break;
                    }
                }
            }
            System.out.println();
        }
        System.out.printf("玩家位置: (%.1f, %.1f) 瓦片: (%d, %d)%n",
            player.bbox.x, player.bbox.y, pTile[0], pTile[1]);
        System.out.printf("速度: (%.1f, %.1f) 着地: %s%n",
            player.vx, player.vy, player.onGround);
    }

    /**
     * 模拟游戏运行
     */
    public void simulateGame() {
        System.out.println("=== 超级玛丽平台碰撞与A星寻路模拟 ===\n");

        // 初始状态
        printMap();

        // 执行A星路径规划
        aiMoveToGoal();

        // 模拟玩家操作序列：右移 -> 跳跃 -> 右移 -> 右移 -> 跳跃
        System.out.println("\n=== 模拟玩家操作 ===");
        String[] actions = {"right", "jump", "right", "right", "right", 
                           "jump", "right", "right", "jump", "right"};

        for (String action : actions) {
            switch (action) {
                case "right":
                    moveHorizontal(1);
                    System.out.println("操作: 右移");
                    break;
                case "jump":
                    jump();
                    System.out.println("操作: 跳跃");
                    break;
            }

            // 物理更新多帧
            for (int i = 0; i < 20; i++) {
                updatePhysics(player);
            }

            printMap();
        }

        System.out.println("\n游戏结束统计:");
        System.out.println("收集金币: " + coinsCollected);
        System.out.printf("最终位置: (%.1f, %.1f)%n", player.bbox.x, player.bbox.y);
    }

    public static void main(String[] args) {
        SuperMario game = new SuperMario(35, 12); // 35x12的关卡
        game.simulateGame();
    }
}

四、算法复杂度分析

五、扩展思考

1. 四叉树空间划分：当场景中实体数量庞大时，可用四叉树将空间分层划分，将碰撞检测从O(n²)降到O(n log n)。
2. 连续碰撞检测（CCD）：高速移动的实体可能在单帧内穿过薄墙，可用射线检测预测碰撞时间。
3. 导航网格（NavMesh）：A星在TileMap上的路径可能呈现锯齿状，导航网格可生成更平滑的路径。
4. 行为树AI：敌人的AI可用行为树建模，包含巡逻、追击、攻击等状态切换逻辑。

六、总结

本文通过超级玛丽游戏讲解了AABB碰撞检测、TileMap地图表示、平台物理模拟和A星路径规划四个核心算法。Java实现从基础瓦片地图出发，构建了完整的2D平台游戏物理引擎和寻路系统。该框架可扩展至更复杂的关卡设计和多智能体协作场景。