每日算法 — 使用java实现滚珠迷宫：重力倾斜控制与A星最短路径

引言

滚珠迷宫（Marble Maze）是一款经典的物理益智游戏：玩家通过倾斜游戏板控制重力方向，引导金属小球在复杂迷宫中滚动，避开陷阱和孔洞，最终到达目标出口。本文用Java实现一个完整的滚珠迷宫游戏，核心算法包括：基于欧拉积分的刚体滚动物理、碰撞检测与响应、以及A星寻路算法在动态重力场中的应用。

核心算法概述

1. 滚动物理模型

小球在倾斜平面上的运动由重力和摩擦力共同决定。重力沿斜面方向的分量提供加速度，滚动摩擦力则与运动方向相反：

a_gravity = g · sin(θ)  // 沿倾斜方向
a_friction = -μ · g · cos(θ) · v̂  // 与速度方向相反

其中 θ 为倾斜角，μ 为滚动摩擦系数。本文采用欧拉法进行数值积分。

2. 碰撞检测与响应

迷宫由墙壁（线段）构成，小球与墙壁的碰撞检测使用线段-圆碰撞算法：

计算圆心到线段的最近点
d = |圆心 - 最近点|
若 d < 球半径：碰撞发生
碰撞响应：沿法线方向弹回，速度反射并乘以弹性系数

3. A星最短路径

在已知迷宫地图的条件下，使用A星算法预先计算从起点到终点的最优路径。由于重力可改变球的滚动方向，传统的四连通/八连通网格扩展为基于可行滚动方向的邻居搜索。

Java实现

滚珠物理引擎

import java.util.ArrayList;
import java.util.List;

/**
 * 滚珠物理引擎：模拟小球在倾斜迷宫中的滚动
 */
public class MarblePhysics {
    // 物理常量
    private static final double GRAVITY = 9.81;           // m/s²
    private static final double MARBLE_RADIUS = 0.008;    // m (8mm)
    private static final double MARBLE_MASS = 0.005;      // kg (5g)
    private static final double FRICTION_COEFF = 0.15;    // 滚动摩擦系数
    private static final double ELASTICITY = 0.7;         // 碰撞弹性系数
    private static final double TIME_STEP = 0.001;        // s (1ms)
    private static final double STOP_SPEED = 0.01;        // 停止阈值

    // 当前重力方向（由板的倾斜角度决定）
    private double gravityAngleX = 0; // 绕X轴倾斜角 (rad)
    private double gravityAngleY = 0; // 绕Y轴倾斜角 (rad)

    /**
     * 小球状态
     */
    public static class Marble {
        public double x, y;     // 位置 (m)
        public double vx, vy;   // 速度 (m/s)
        public boolean active;

        public Marble(double x, double y) {
            this.x = x; this.y = y;
            this.vx = 0; this.vy = 0;
            this.active = true;
        }

        public double speed() {
            return Math.hypot(vx, vy);
        }
    }

    /**
     * 墙壁线段
     */
    public static class Wall {
        public double x1, y1, x2, y2;
        public Wall(double x1, double y1, double x2, double y2) {
            this.x1=x1; this.y1=y1; this.x2=x2; this.y2=y2;
        }
    }

    private Marble marble;
    private List<Wall> walls = new ArrayList<>();
    private List<Hole> holes = new ArrayList<>();

    /**
     * 陷阱孔洞
     */
    public static class Hole {
        public double x, y, radius;
        public Hole(double x, double y, double r) { this.x=x; this.y=y; this.radius=r; }
    }

    public void setMarble(Marble m) { this.marble = m; }
    public void addWall(Wall w) { walls.add(w); }
    public void addHole(Hole h) { holes.add(h); }

    /**
     * 设置板的倾斜角度
     */
    public void setTilt(double angleX, double angleY) {
        // 限制最大倾斜角 ±30度
        double maxTilt = Math.toRadians(30);
        this.gravityAngleX = Math.max(-maxTilt, Math.min(maxTilt, angleX));
        this.gravityAngleY = Math.max(-maxTilt, Math.min(maxTilt, angleY));
    }

    /**
     * 单步物理模拟
     */
    public void step() {
        if (!marble.active || marble.speed() < STOP_SPEED) {
            // 即使速度很低，重力仍会导致滑动
            if (gravityAngleX == 0 && gravityAngleY == 0) return;
        }

        // 计算重力加速度分量
        double ax = GRAVITY * Math.sin(gravityAngleY);
        double ay = GRAVITY * Math.sin(gravityAngleX);

        // 摩擦力（与运动方向相反）
        double speed = marble.speed();
        if (speed > STOP_SPEED) {
            double frictionDecel = FRICTION_COEFF * GRAVITY * TIME_STEP;
            double nx = marble.vx / speed;
            double ny = marble.vy / speed;
            ax -= frictionDecel * nx;
            ay -= frictionDecel * ny;
        }

        // 更新速度
        marble.vx += ax * TIME_STEP;
        marble.vy += ay * TIME_STEP;

        // 更新位置
        double newX = marble.x + marble.vx * TIME_STEP;
        double newY = marble.y + marble.vy * TIME_STEP;

        // 碰撞检测与响应
        for (Wall w : walls) {
            double[] resolved = resolveWallCollision(newX, newY, w);
            newX = resolved[0];
            newY = resolved[1];
        }

        marble.x = newX;
        marble.y = newY;

        // 检测是否落入陷阱
        for (Hole h : holes) {
            double dist = Math.hypot(marble.x - h.x, marble.y - h.y);
            if (dist < h.radius - MARBLE_RADIUS * 0.5) {
                marble.active = false;
                return;
            }
        }
    }

    /**
     * 线段-圆碰撞检测与响应
     */
    private double[] resolveWallCollision(double cx, double cy, Wall w) {
        // 计算圆心到线段的最近点
        double dx = w.x2 - w.x1;
        double dy = w.y2 - w.y1;
        double lenSq = dx*dx + dy*dy;

        double t = Math.max(0, Math.min(1,
                ((cx-w.x1)*dx + (cy-w.y1)*dy) / lenSq));
        double closestX = w.x1 + t * dx;
        double closestY = w.y1 + t * dy;

        double distX = cx - closestX;
        double distY = cy - closestY;
        double dist = Math.hypot(distX, distY);

        if (dist < MARBLE_RADIUS && dist > 1e-9) {
            // 碰撞法向量
            double nx = distX / dist;
            double ny = distY / dist;

            // 位置校正
            double overlap = MARBLE_RADIUS - dist;
            cx += nx * overlap;
            cy += ny * overlap;

            // 速度反射
            double dot = marble.vx * nx + marble.vy * ny;
            if (dot < 0) { // 只有朝向墙壁的速度分量才反射
                marble.vx -= (1 + ELASTICITY) * dot * nx;
                marble.vy -= (1 + ELASTICITY) * dot * ny;
            }
        }

        return new double[]{cx, cy};
    }

    public Marble getMarble() { return marble; }
    public List<Wall> getWalls() { return walls; }
    public List<Hole> getHoles() { return holes; }
}

A星寻路算法

import java.util.*;

/**
 * A星寻路：在迷宫网格中寻找从起点到终点的最短路径
 */
public class AStarPathfinder {

    /**
     * 网格节点
     */
    public static class Node {
        public int x, y;
        public double g; // 从起点到当前节点的实际代价
        public double h; // 启发式估计（到终点的欧氏距离）
        public Node parent;

        public Node(int x, int y) {
            this.x = x; this.y = y;
            this.g = Double.MAX_VALUE;
            this.h = 0;
        }

        public double f() { return g + h; }

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

        @Override
        public int hashCode() { return Objects.hash(x, y); }
    }

    private boolean[][] walkable; // true=可通行
    private int width, height;

    public AStarPathfinder(boolean[][] walkable) {
        this.walkable = walkable;
        this.height = walkable.length;
        this.width = walkable[0].length;
    }

    /**
     * A星寻路
     * @param start 起点 (grid坐标)
     * @param goal 终点 (grid坐标)
     * @return 路径节点列表，若无路径则返回空列表
     */
    public List<Node> findPath(Node start, Node goal) {
        PriorityQueue<Node> openSet = new PriorityQueue<>(Comparator.comparingDouble(Node::f));
        Set<Node> closedSet = new HashSet<>();

        start.g = 0;
        start.h = heuristic(start, goal);
        openSet.add(start);

        Map<String, Node> nodeMap = new HashMap<>();
        nodeMap.put(key(start), start);

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

            if (current.x == goal.x && current.y == goal.y) {
                return reconstructPath(current);
            }

            closedSet.add(current);

            for (Node neighbor : getNeighbors(current)) {
                if (closedSet.contains(neighbor)) continue;

                double tentativeG = current.g + distance(current, neighbor);
                String nKey = key(neighbor);
                Node existing = nodeMap.get(nKey);

                if (existing == null || tentativeG < existing.g) {
                    Node n = existing != null ? existing : new Node(neighbor.x, neighbor.y);
                    n.g = tentativeG;
                    n.h = heuristic(n, goal);
                    n.parent = current;
                    nodeMap.put(nKey, n);
                    openSet.remove(n);
                    openSet.add(n);
                }
            }
        }

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

    /**
     * 获取邻居节点（8方向）
     */
    private List<Node> getNeighbors(Node n) {
        List<Node> neighbors = new ArrayList<>();
        int[][] dirs = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};

        for (int[] d : dirs) {
            int nx = n.x + d[0];
            int ny = n.y + d[1];
            if (nx >= 0 && nx < width && ny >= 0 && ny < height && walkable[ny][nx]) {
                neighbors.add(new Node(nx, ny));
            }
        }

        return neighbors;
    }

    private double heuristic(Node a, Node b) {
        // 欧氏距离
        return Math.hypot(a.x - b.x, a.y - b.y);
    }

    private double distance(Node a, Node b) {
        // 对角线移动代价为√2，直线为1
        return Math.hypot(a.x - b.x, a.y - b.y);
    }

    private String key(Node n) {
        return n.x + "," + n.y;
    }

    private List<Node> reconstructPath(Node goal) {
        List<Node> path = new ArrayList<>();
        Node current = goal;
        while (current != null) {
            path.add(0, current);
            current = current.parent;
        }
        return path;
    }
}

迷宫生成器与游戏主控

import java.util.*;

/**
 * 迷宫生成器：使用递归分割算法生成随机迷宫
 */
public class MazeGenerator {

    /**
     * 使用递归分割生成迷宫
     * @param width 网格宽度
     * @param height 网格高度
     * @return true表示可通行，false表示墙壁
     */
    public boolean[][] generateMaze(int width, int height) {
        boolean[][] maze = new boolean[height][width];
        // 初始全部可通行
        for (int y = 0; y < height; y++) {
            Arrays.fill(maze[y], true);
        }

        // 添加外边界墙
        for (int x = 0; x < width; x++) { maze[0][x] = false; maze[height-1][x] = false; }
        for (int y = 0; y < height; y++) { maze[y][0] = false; maze[y][width-1] = false; }

        // 递归分割内部
        divide(maze, 1, 1, width - 2, height - 2);

        // 确保起点和终点可通行
        maze[1][1] = true;
        maze[height-2][width-2] = true;

        return maze;
    }

    private void divide(boolean[][] maze, int x, int y, int w, int h) {
        if (w < 3 || h < 3) return;

        Random rand = new Random();

        // 选择水平或垂直分割
        boolean horizontal = h > w || (h == w && rand.nextBoolean());

        if (horizontal) {
            int wy = y + rand.nextInt(h - 2) + 1;
            // 确保wy为奇数，保持通道宽度
            if (wy % 2 == 0) wy = wy + 1 >= y + h ? wy - 1 : wy + 1;

            int hole = x + rand.nextInt(w);
            for (int i = x; i < x + w; i++) {
                if (i != hole) maze[wy][i] = false;
            }
            divide(maze, x, y, w, wy - y);
            divide(maze, x, wy + 1, w, y + h - wy - 1);
        } else {
            int wx = x + rand.nextInt(w - 2) + 1;
            if (wx % 2 == 0) wx = wx + 1 >= x + w ? wx - 1 : wx + 1;

            int hole = y + rand.nextInt(h);
            for (int i = y; i < y + h; i++) {
                if (i != hole) maze[i][wx] = false;
            }
            divide(maze, x, y, wx - x, h);
            divide(maze, wx + 1, y, x + w - wx - 1, h);
        }
    }

    /**
     * 将网格迷宫转换为物理墙壁列表
     */
    public List<MarblePhysics.Wall> mazeToWalls(boolean[][] maze, double cellSize) {
        List<MarblePhysics.Wall> walls = new ArrayList<>();
        int h = maze.length;
        int w = maze[0].length;

        for (int y = 0; y < h; y++) {
            for (int x = 0; x < w; x++) {
                if (!maze[y][x]) {
                    double cx = x * cellSize;
                    double cy = y * cellSize;
                    // 每个墙壁单元格生成4条边
                    walls.add(new MarblePhysics.Wall(cx, cy, cx + cellSize, cy));
                    walls.add(new MarblePhysics.Wall(cx + cellSize, cy, cx + cellSize, cy + cellSize));
                    walls.add(new MarblePhysics.Wall(cx + cellSize, cy + cellSize, cx, cy + cellSize));
                    walls.add(new MarblePhysics.Wall(cx, cy + cellSize, cx, cy));
                }
            }
        }
        return walls;
    }
}

主程序与可视化框架

import javax.swing.*;
import java.awt.*;
import java.util.List;

/**
 * 滚珠迷宫游戏主程序
 */
public class MarbleMazeGame extends JPanel {
    private static final double CELL_SIZE = 0.02; // m (2cm per grid cell)
    private static final int PIXEL_SCALE = 40;    // pixels per meter

    private MarblePhysics physics;
    private boolean[][] mazeGrid;
    private List<AStarPathfinder.Node> path;
    private double goalX, goalY;
    private java.util.List<double[]> trajectory = new java.util.ArrayList<>();

    public MarbleMazeGame() {
        setPreferredSize(new Dimension(600, 600));
        setBackground(Color.DARK_GRAY);
        initGame();
    }

    private void initGame() {
        // 生成迷宫
        MazeGenerator gen = new MazeGenerator();
        int gridW = 25, gridH = 25;
        mazeGrid = gen.generateMaze(gridW, gridH);

        // 创建物理引擎
        physics = new MarblePhysics();
        physics.setMarble(new MarblePhysics.Marble(CELL_SIZE * 1.5, CELL_SIZE * 1.5));

        // 添加墙壁
        List<MarblePhysics.Wall> walls = gen.mazeToWalls(mazeGrid, CELL_SIZE);
        for (MarblePhysics.Wall w : walls) physics.addWall(w);

        // 添加陷阱孔洞
        physics.addHole(new MarblePhysics.Hole(CELL_SIZE * 10, CELL_SIZE * 10, CELL_SIZE));
        physics.addHole(new MarblePhysics.Hole(CELL_SIZE * 18, CELL_SIZE * 15, CELL_SIZE));

        // 目标
        goalX = (gridW - 2) * CELL_SIZE;
        goalY = (gridH - 2) * CELL_SIZE;

        // A星寻路
        AStarPathfinder pf = new AStarPathfinder(mazeGrid);
        path = pf.findPath(
                new AStarPathfinder.Node(1, 1),
                new AStarPathfinder.Node(gridW - 2, gridH - 2)
        );

        System.out.println("迷宫生成完成: " + gridW + "x" + gridH);
        System.out.println("A星路径长度: " + path.size() + " 步");
    }

    /**
     * 更新物理并记录轨迹
     */
    public void updatePhysics() {
        if (!physics.getMarble().active) return;
        physics.step();
        MarblePhysics.Marble m = physics.getMarble();
        trajectory.add(new double[]{m.x, m.y});

        // 检测到达终点
        if (Math.hypot(m.x - goalX, m.y - goalY) < CELL_SIZE) {
            System.out.println("恭喜到达终点！");
            m.active = false;
        }
    }

    @Override
    protected void paintComponent(Graphics g) {
        super.paintComponent(g);
        Graphics2D g2d = (Graphics2D) g;
        g2d.setRenderingHint(RenderingHints.KEY_ANTIALIASING,
                RenderingHints.VALUE_ANTIALIAS_ON);

        int offsetX = 20, offsetY = 20;

        // 绘制迷宫
        g2d.setColor(Color.GRAY);
        for (int y = 0; y < mazeGrid.length; y++) {
            for (int x = 0; x < mazeGrid[0].length; x++) {
                if (!mazeGrid[y][x]) {
                    int px = offsetX + (int)(x * CELL_SIZE * PIXEL_SCALE);
                    int py = offsetY + (int)(y * CELL_SIZE * PIXEL_SCALE);
                    int size = (int)(CELL_SIZE * PIXEL_SCALE) + 1;
                    g2d.fillRect(px, py, size, size);
                }
            }
        }

        // 绘制A星路径
        if (path != null && path.size() > 1) {
            g2d.setColor(new Color(0, 150, 0, 100));
            for (int i = 0; i < path.size() - 1; i++) {
                int x1 = offsetX + (int)(path.get(i).x * CELL_SIZE * PIXEL_SCALE + CELL_SIZE * PIXEL_SCALE / 2);
                int y1 = offsetY + (int)(path.get(i).y * CELL_SIZE * PIXEL_SCALE + CELL_SIZE * PIXEL_SCALE / 2);
                int x2 = offsetX + (int)(path.get(i+1).x * CELL_SIZE * PIXEL_SCALE + CELL_SIZE * PIXEL_SCALE / 2);
                int y2 = offsetY + (int)(path.get(i+1).y * CELL_SIZE * PIXEL_SCALE + CELL_SIZE * PIXEL_SCALE / 2);
                g2d.drawLine(x1, y1, x2, y2);
            }
        }

        // 绘制陷阱
        g2d.setColor(Color.BLACK);
        for (MarblePhysics.Hole h : physics.getHoles()) {
            int px = offsetX + (int)(h.x * PIXEL_SCALE);
            int py = offsetY + (int)(h.y * PIXEL_SCALE);
            int r = (int)(h.radius * PIXEL_SCALE);
            g2d.fillOval(px - r, py - r, r * 2, r * 2);
        }

        // 绘制目标
        g2d.setColor(Color.GREEN);
        int gx = offsetX + (int)(goalX * PIXEL_SCALE);
        int gy = offsetY + (int)(goalY * PIXEL_SCALE);
        g2d.fillOval(gx - 8, gy - 8, 16, 16);

        // 绘制轨迹
        if (trajectory.size() > 1) {
            g2d.setColor(new Color(255, 100, 100, 120));
            for (int i = 1; i < trajectory.size(); i++) {
                int x1 = offsetX + (int)(trajectory.get(i-1)[0] * PIXEL_SCALE);
                int y1 = offsetY + (int)(trajectory.get(i-1)[1] * PIXEL_SCALE);
                int x2 = offsetX + (int)(trajectory.get(i)[0] * PIXEL_SCALE);
                int y2 = offsetY + (int)(trajectory.get(i)[1] * PIXEL_SCALE);
                g2d.drawLine(x1, y1, x2, y2);
            }
        }

        // 绘制小球
        MarblePhysics.Marble m = physics.getMarble();
        int mx = offsetX + (int)(m.x * PIXEL_SCALE);
        int my = offsetY + (int)(m.y * PIXEL_SCALE);
        int mr = Math.max(3, (int)(MarblePhysics.MARBLE_RADIUS * PIXEL_SCALE));
        g2d.setColor(m.active ? Color.CYAN : Color.RED);
        g2d.fillOval(mx - mr, my - mr, mr * 2, mr * 2);
    }

    /**
     * 设置板的倾斜（模拟重力方向变化）
     */
    public void setBoardTilt(double angleX, double angleY) {
        physics.setTilt(angleX, angleY);
    }

    public static void main(String[] args) {
        SwingUtilities.invokeLater(() -> {
            JFrame frame = new JFrame("滚珠迷宫 — 重力控制与A星寻路");
            MarbleMazeGame game = new MarbleMazeGame();
            frame.add(game);
            frame.pack();
            frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
            frame.setVisible(true);

            // 游戏循环
            javax.swing.Timer timer = new javax.swing.Timer(16, e -> {
                // 自动演示：沿A星路径方向倾斜
                if (game.path != null && game.path.size() > 1 &&
                        game.physics.getMarble().active) {
                    autoTilt(game);
                }
                game.updatePhysics();
                game.repaint();
            });
            timer.start();
        });
    }

    private static void autoTilt(MarbleMazeGame game) {
        MarblePhysics.Marble m = game.physics.getMarble();
        // 找到路径上最近的点
        double minDist = Double.MAX_VALUE;
        int nearestIdx = 0;
        for (int i = 0; i < game.path.size(); i++) {
            AStarPathfinder.Node n = game.path.get(i);
            double dist = Math.hypot(m.x - n.x * CELL_SIZE, m.y - n.y * CELL_SIZE);
            if (dist < minDist) {
                minDist = dist;
                nearestIdx = i;
            }
        }

        // 向下一个路径点倾斜
        if (nearestIdx < game.path.size() - 1) {
            AStarPathfinder.Node next = game.path.get(nearestIdx + 1);
            double dx = next.x * CELL_SIZE - m.x;
            double dy = next.y * CELL_SIZE - m.y;
            double maxTilt = Math.toRadians(15);
            game.setBoardTilt(
                    Math.max(-maxTilt, Math.min(maxTilt, dy * 5)),
                    Math.max(-maxTilt, Math.min(maxTilt, dx * 5))
            );
        }
    }
}

算法复杂度分析

扩展思考

1. 空间哈希优化：将墙壁按空间网格划分，碰撞检测时仅查询小球所在网格及邻接网格，可将复杂度从O(w)降至O(1)。
2. 强化学习控制：使用DQN或PPO训练AI自动学习板的倾斜策略，在复杂迷宫中实现零陷阱通关。
3. 多人协作模式：扩展为双球同时控制，需要协调重力方向使两球都到达各自目标，可建模为多智能体路径规划问题。

总结

本文实现了一个完整的滚珠迷宫游戏系统，包含物理滚动模拟、线段-圆碰撞检测、递归分割迷宫生成、以及A星最短路径算法。自动演示模块展示了如何结合路径规划与物理控制，通过动态调整重力方向引导小球沿最优路径到达终点。该系统可作为物理益智游戏开发、机器人路径规划教学的参考实现。