引言
抓娃娃机是游乐场和商场中最常见的游戏设备之一。本文将用Java实现一个简化版的抓娃娃游戏，重点讲解其中的核心算法：圆形与矩形的碰撞检测、爪子张合角度计算，以及基于贪心策略的最优抓取目标选择。读者不仅能理解物理碰撞的基本原理，还能掌握如何将几何算法应用到游戏开发中。
问题建模
抓娃娃游戏可以抽象为以下核心问题：
- 娃娃表示：每个娃娃用一个圆形表示，包含圆心坐标
(x, y)和半径r - 爪子表示：爪子由两个对称的夹臂组成，每个夹臂是一条线段，张开角度决定抓取范围
- 碰撞检测：判断爪子是否与某个娃娃发生有效碰撞（即娃娃进入爪子闭合区域）
- 目标选择：在多个娃娃中选择最容易被抓取的目标
核心算法一：圆形与线段的碰撞检测
爪子夹臂可视为线段，判断娃娃（圆）是否与线段相交是抓取检测的基础。
/**
* 抓娃娃游戏核心算法实现
*/
public class ClawMachineGame {
/**
* 二维点
*/
static class Point {
double x, y;
Point(double x, double y) { this.x = x; this.y = y; }
}
/**
* 圆形娃娃
*/
static class Doll {
Point center; // 圆心
double radius; // 半径
double weight; // 重量（影响抓取难度）
String name;
Doll(double x, double y, double r, double w, String name) {
this.center = new Point(x, y);
this.radius = r;
this.weight = w;
this.name = name;
}
}
/**
* 计算点到线段的最近距离
* 这是碰撞检测的核心：圆与线段相交当且仅当圆心到线段距离 <= 半径
*/
public static double pointToSegmentDistance(Point p, Point a, Point b) {
// 向量 AP 和 AB
double apx = p.x - a.x;
double apy = p.y - a.y;
double abx = b.x - a.x;
double aby = b.y - a.y;
// 计算投影参数 t = (AP · AB) / |AB|^2
double abLenSq = abx * abx + aby * aby;
// 如果线段退化为点，直接返回点到点距离
if (abLenSq < 1e-10) {
return Math.sqrt(apx * apx + apy * apy);
}
double t = Math.max(0, Math.min(1, (apx * abx + apy * aby) / abLenSq));
// 最近点坐标 = A + t * AB
double closestX = a.x + t * abx;
double closestY = a.y + t * aby;
// 返回点P到最近点的距离
double dx = p.x - closestX;
double dy = p.y - closestY;
return Math.sqrt(dx * dx + dy * dy);
}
/**
* 判断圆形是否与线段相交
*/
public static boolean circleIntersectsSegment(Point center, double radius,
Point a, Point b) {
return pointToSegmentDistance(center, a, b) <= radius;
}
核心算法二：爪子几何模型与闭合检测
/**
* 爪子类：由两个对称夹臂组成
*/
static class Claw {
Point pivot; // 爪子旋转中心（悬吊点）
double length; // 夹臂长度
double angle; // 爪子朝向角度（弧度）
double openAngle; // 张角（弧度，0表示完全闭合）
Claw(double x, double y, double len) {
this.pivot = new Point(x, y);
this.length = len;
this.angle = 0;
this.openAngle = Math.PI / 3; // 默认张开60度
}
/**
* 计算左右夹臂的端点坐标
* 左臂：pivot -> 沿 (angle - openAngle/2) 方向延伸 length
* 右臂：pivot -> 沿 (angle + openAngle/2) 方向延伸 length
*/
public Point getLeftTip() {
double leftAngle = angle - openAngle / 2;
return new Point(
pivot.x + length * Math.sin(leftAngle),
pivot.y + length * Math.cos(leftAngle)
);
}
public Point getRightTip() {
double rightAngle = angle + openAngle / 2;
return new Point(
pivot.x + length * Math.sin(rightAngle),
pivot.y + length * Math.cos(rightAngle)
);
}
/**
* 判断爪子是否能抓住某个娃娃
* 条件：娃娃圆心到两个夹臂的距离均小于娃娃半径，且娃娃位于爪子下方区域
*/
public boolean canGrab(Doll doll) {
Point leftTip = getLeftTip();
Point rightTip = getRightTip();
// 娃娃必须同时与两个夹臂相交（进入闭合区域）
boolean touchesLeft = circleIntersectsSegment(
doll.center, doll.radius, pivot, leftTip);
boolean touchesRight = circleIntersectsSegment(
doll.center, doll.radius, pivot, rightTip);
// 娃娃必须在爪子下方（y坐标更大，假设y轴向下）
boolean belowPivot = doll.center.y > pivot.y;
return touchesLeft && touchesRight && belowPivot;
}
/**
* 闭合爪子：减小张角
*/
public void close(double delta) {
this.openAngle = Math.max(0, this.openAngle - delta);
}
}
核心算法三：贪心策略选择最优抓取目标
/**
* 贪心策略：选择最容易被抓取的娃娃
* 评估函数综合考虑：距离（越近越好）、重量（越轻越好）、周围拥挤度
*/
public static Doll selectBestTarget(Claw claw, Doll[] dolls) {
Doll best = null;
double bestScore = Double.NEGATIVE_INFINITY;
for (Doll doll : dolls) {
// 计算爪子到娃娃的距离
double dist = Math.sqrt(
Math.pow(doll.center.x - claw.pivot.x, 2) +
Math.pow(doll.center.y - claw.pivot.y, 2)
);
// 计算周围拥挤度：附近其他娃娃越多越难抓
double crowding = 0;
for (Doll other : dolls) {
if (other == doll) continue;
double d = Math.sqrt(
Math.pow(doll.center.x - other.center.x, 2) +
Math.pow(doll.center.y - other.center.y, 2)
);
if (d < doll.radius * 4) {
crowding += 1.0 / (d + 1);
}
}
// 综合评分：距离近加分，重量轻加分，拥挤度低加分
double score = -dist * 0.5 - doll.weight * 2 - crowding * 10;
if (score > bestScore) {
bestScore = score;
best = doll;
}
}
return best;
}
/**
* 移动爪子到目标正上方（简化版，实际可用PID控制或匀速移动）
*/
public static void moveClawAboveTarget(Claw claw, Doll target) {
claw.pivot.x = target.center.x;
// 保持一定高度
claw.pivot.y = target.center.y - claw.length * 0.8;
}
/**
* 主游戏流程演示
*/
public static void main(String[] args) {
// 初始化娃娃：随机放置在娃娃机底部区域
Doll[] dolls = {
new Doll(30, 80, 5, 1.0, "小熊"),
new Doll(50, 85, 6, 1.5, "大熊"),
new Doll(70, 82, 4, 0.8, "小兔"),
new Doll(45, 90, 5, 1.2, "小狗"),
new Doll(60, 88, 4.5, 0.9, "小猫")
};
// 初始化爪子
Claw claw = new Claw(50, 20, 25);
System.out.println("=== 抓娃娃游戏开始 ===");
// 使用贪心策略选择目标
Doll target = selectBestTarget(claw, dolls);
System.out.println("贪心策略选择目标: " + target.name +
" (位置: " + target.center.x + ", " + target.center.y +
", 重量: " + target.weight + ")");
// 移动爪子
moveClawAboveTarget(claw, target);
System.out.println("爪子移动到: (" + claw.pivot.x + ", " + claw.pivot.y + ")");
// 模拟下降并抓取
claw.pivot.y = target.center.y - 5;
System.out.println("爪子下降...");
// 闭合爪子
claw.close(Math.PI / 3);
System.out.println("爪子闭合，张角: " + Math.toDegrees(claw.openAngle) + "°");
// 检测是否抓住
boolean grabbed = claw.canGrab(target);
System.out.println("抓取结果: " + (grabbed ? "成功抓住 " + target.name + "!" : "抓取失败..."));
// 展示碰撞检测原理
System.out.println("\n=== 碰撞检测原理验证 ===");
Point leftTip = claw.getLeftTip();
Point rightTip = claw.getRightTip();
double distLeft = pointToSegmentDistance(target.center, claw.pivot, leftTip);
double distRight = pointToSegmentDistance(target.center, claw.pivot, rightTip);
System.out.println("娃娃圆心到左臂距离: " + String.format("%.4f", distLeft) +
" (半径=" + target.radius + ")");
System.out.println("娃娃圆心到右臂距离: " + String.format("%.4f", distRight) +
" (半径=" + target.radius + ")");
}
}
复杂度分析
- 碰撞检测：判断圆与线段相交的时间复杂度为 O(1)，只需常数次向量运算
- 目标选择：遍历所有娃娃计算评分，时间复杂度为 O(n²)，其中 n 为娃娃数量（因为每个娃娃都要计算与其他所有娃娃的拥挤度）。可优化为 O(n log n) 使用空间索引
- 空间复杂度：O(n) 存储娃娃信息
扩展思考
- 空间索引优化：当娃娃数量很多时，可用四叉树或网格划分加速邻近查询，将目标选择的拥挤度计算从 O(n²) 降到 O(n log n)
- 物理模拟增强：可引入重力、惯性、爪子摆动等物理效果，使用Verlet积分或欧拉方法更新位置
- 机器学习策略：训练强化学习模型（如DQN）替代贪心策略，学习更优的抓取时机和角度
- 多爪协同：扩展为多个爪子同时工作的场景，引入任务分配算法
总结
本文通过Java实现了抓娃娃游戏的核心算法，包括圆与线段的碰撞检测、爪子几何模型和贪心目标选择策略。碰撞检测使用向量投影计算点到线段的最短距离，目标选择则综合距离、重量和拥挤度三个维度进行贪心决策。这些算法在游戏开发、机器人抓取和几何计算领域都有广泛应用。
