引言
潜水艇游戏是早期街机与家用主机上的经典题材。玩家操控一艘潜水艇在深海中航行，需要避开敌方驱逐舰的深水炸弹、穿越复杂的海底地形，同时利用声纳系统探测周围环境并收集宝藏。这类游戏的核心魅力在于不完全信息环境下的决策——玩家（和AI）只能依赖声纳的有限探测范围来推断周围态势。本文将用Java实现一个潜水艇AI系统，重点讲解声纳波束传播模型、栅格地图概率更新与A*路径规划三大核心算法。
一、潜水艇的核心挑战建模
将潜水艇游戏抽象为以下数学模型：
- 状态空间：潜水艇的位置 $(x, y)$、深度 $d$、航向 $\theta$、速度 $v$
- 观测空间：声纳返回的距离读数序列 $[r_1, r_2, …, r_n]$，对应不同角度的障碍物距离
- 动作空间：加速、减速、左转、右转、下潜、上浮
- 目标函数：最大化收集的宝藏价值，同时最小化被探测到的概率
二、核心算法详解
2.1 声纳探测模型
声纳（SONAR）通过发射声波并接收回波来探测障碍物。我们采用扇形波束模型：
- 声纳覆盖角度范围 $[-\alpha, +\alpha]$，共 $n$ 个探测方向
- 每个方向上的最大探测距离为 $R_{max}$
- 声波在水中传播速度约为 $1500m/s$，往返时间 $t = 2r / 1500$
对于每个探测方向 $i$，声纳返回的距离 $r_i$ 表示该方向上最近的障碍物距离（若 $r_i = R_{max}$ 则表示无障碍物）。
2.2 栅格地图概率更新
使用占用栅格地图（Occupancy Grid Map）来维护环境信息。地图被划分为 $W \times H$ 的栅格，每个栅格记录被障碍物占用的概率 $p(o)$。
当声纳在方向 $i$ 上测得距离 $r_i$ 时，更新规则如下：
- 对于距离小于 $r_i – \epsilon$ 的栅格：大概率空闲，$p(o) \leftarrow p(o) \cdot 0.3$
- 对于距离在 $[r_i – \epsilon, r_i + \epsilon]$ 内的栅格：大概率被占用，$p(o) \leftarrow 1 – (1 – p(o)) \cdot 0.3$
- 对于距离大于 $r_i + \epsilon$ 的栅格：未知，概率不变
这里 $\epsilon$ 是声纳测距误差，设为半个栅格宽度。
2.3 最优路径规划
潜水艇的路径规划需要同时考虑：
- 路径最短：快速到达目的地
- 隐蔽性：避开敌方探测范围
- 安全性：避开已知的障碍物
我们将这三项指标融合为统一的代价函数：
$$C(node) = g(node) + h(node) + \lambda \cdot threat(node)$$
其中 $g$ 为实际代价，$h$ 为启发式估计（欧几里得距离），$threat$ 为敌方威胁值，$\lambda$ 为权衡系数。
使用A*搜索算法在栅格地图上寻找最优路径。
三、Java完整实现
import java.util.*;
/**
* 潜水艇AI系统
* 核心算法：声纳扇形探测、栅格地图概率更新、A*威胁感知路径规划
*/
public class SubmarineAI {
// 地图参数
private static final int MAP_WIDTH = 80; // 地图宽度（栅格数）
private static final int MAP_HEIGHT = 60; // 地图高度（栅格数）
private static final double GRID_SIZE = 10.0; // 每个栅格代表10米
// 声纳参数
private static final int SONAR_BEAMS = 24; // 声纳波束数量
private static final double SONAR_ANGLE = Math.PI; // 声纳覆盖角度（180度前向）
private static final double MAX_RANGE = 150.0; // 最大探测距离（米）
private static final double RANGE_NOISE = 5.0; // 测距噪声（米）
// 潜水艇参数
private static final double MAX_SPEED = 8.0; // 最大速度（米/秒）
private static final double TURN_RATE = 0.08; // 转向速率（弧度/秒）
/**
* 二维坐标点
*/
public static class Point {
public double x, y;
public Point(double x, double y) {
this.x = x;
this.y = y;
}
public double distanceTo(Point other) {
double dx = x - other.x;
double dy = y - other.y;
return Math.sqrt(dx * dx + dy * dy);
}
public Point add(Point other) {
return new Point(x + other.x, y + other.y);
}
public Point mul(double scalar) {
return new Point(x * scalar, y * scalar);
}
}
/**
* 栅格单元，维护占用概率和威胁等级
*/
public static class GridCell {
public double occupancyProb; // 被障碍物占用的概率 [0, 1]
public double threatLevel; // 敌方威胁等级 [0, 1]
public boolean isKnown; // 是否已被声纳探测过
public GridCell() {
this.occupancyProb = 0.5; // 初始未知状态
this.threatLevel = 0.0;
this.isKnown = false;
}
}
/**
* 声纳系统：发射扇形波束并模拟回波探测
*/
public static class SonarSystem {
private int beams;
private double maxRange;
private double fov; // field of view
public SonarSystem(int beams, double maxRange, double fov) {
this.beams = beams;
this.maxRange = maxRange;
this.fov = fov;
}
/**
* 执行一次声纳扫描
* @param subPos 潜水艇位置
* @param heading 航向角度（弧度）
* @param obstacles 真实障碍物列表
* @return 各波束方向的探测距离数组
*/
public double[] scan(Point subPos, double heading, List<Point> obstacles) {
double[] ranges = new double[beams];
double startAngle = heading - fov / 2;
double angleStep = fov / (beams - 1);
for (int i = 0; i < beams; i++) {
double angle = startAngle + i * angleStep;
ranges[i] = castRay(subPos, angle, obstacles);
}
return ranges;
}
/**
* 射线投射：从起点沿角度发射射线，返回最近的障碍物距离
*/
private double castRay(Point origin, double angle, List<Point> obstacles) {
Point dir = new Point(Math.cos(angle), Math.sin(angle));
double closestDist = maxRange;
// 简化处理：假设障碍物为点状，实际游戏中应使用线段或多边形
for (Point obs : obstacles) {
// 计算障碍物是否在射线方向上
Point toObs = new Point(obs.x - origin.x, obs.y - origin.y);
double proj = toObs.x * dir.x + toObs.y * dir.y;
if (proj > 0 && proj < maxRange) {
// 计算垂直距离
Point projPoint = new Point(origin.x + dir.x * proj, origin.y + dir.y * proj);
double perpDist = projPoint.distanceTo(obs);
// 如果障碍物在射线附近（考虑一定宽度）
if (perpDist < GRID_SIZE * 2) {
double dist = origin.distanceTo(obs);
// 加入测距噪声
dist += (Math.random() - 0.5) * 2 * RANGE_NOISE;
closestDist = Math.min(closestDist, Math.max(0, dist));
}
}
}
return closestDist;
}
}
/**
* 栅格地图管理器：维护占用概率和威胁地图
*/
public static class GridMap {
private GridCell[][] cells;
private int width, height;
public GridMap(int width, int height) {
this.width = width;
this.height = height;
this.cells = new GridCell[height][width];
for (int y = 0; y < height; y++) {
for (int x = 0; x < width; x++) {
cells[y][x] = new GridCell();
}
}
}
public GridCell getCell(int x, int y) {
if (x < 0 || x >= width || y < 0 || y >= height) return null;
return cells[y][x];
}
public Point gridToWorld(int gx, int gy) {
return new Point(gx * GRID_SIZE + GRID_SIZE / 2, gy * GRID_SIZE + GRID_SIZE / 2);
}
public int worldToGridX(double wx) {
return (int) (wx / GRID_SIZE);
}
public int worldToGridY(double wy) {
return (int) (wy / GRID_SIZE);
}
/**
* 根据声纳扫描结果更新栅格地图
*/
public void updateFromSonar(Point subPos, double heading, double[] ranges) {
double startAngle = heading - SONAR_ANGLE / 2;
double angleStep = SONAR_ANGLE / (ranges.length - 1);
for (int i = 0; i < ranges.length; i++) {
double angle = startAngle + i * angleStep;
double range = ranges[i];
updateBeam(subPos, angle, range);
}
}
/**
* 更新单个声纳波束覆盖的栅格
*/
private void updateBeam(Point origin, double angle, double range) {
Point dir = new Point(Math.cos(angle), Math.sin(angle));
double step = GRID_SIZE / 2; // 沿射线步进距离
double epsilon = GRID_SIZE; // 障碍物位置不确定性
for (double d = 0; d < range - epsilon; d += step) {
Point p = new Point(origin.x + dir.x * d, origin.y + dir.y * d);
int gx = worldToGridX(p.x);
int gy = worldToGridY(p.y);
GridCell cell = getCell(gx, gy);
if (cell != null) {
// 大概率空闲：p(o) = p(o) * 0.3
cell.occupancyProb *= 0.3;
cell.isKnown = true;
}
}
// 障碍物所在区域
for (double d = Math.max(0, range - epsilon); d <= range + epsilon; d += step) {
Point p = new Point(origin.x + dir.x * d, origin.y + dir.y * d);
int gx = worldToGridX(p.x);
int gy = worldToGridY(p.y);
GridCell cell = getCell(gx, gy);
if (cell != null) {
// 大概率占用：p(o) = 1 - (1 - p(o)) * 0.3
cell.occupancyProb = 1 - (1 - cell.occupancyProb) * 0.3;
cell.isKnown = true;
}
}
}
/**
* 更新敌方威胁地图（模拟敌方驱逐舰的探测范围）
*/
public void updateThreat(Point enemyPos, double detectionRange) {
int centerGx = worldToGridX(enemyPos.x);
int centerGy = worldToGridY(enemyPos.y);
int radius = (int) (detectionRange / GRID_SIZE) + 1;
for (int dy = -radius; dy <= radius; dy++) {
for (int dx = -radius; dx <= radius; dx++) {
int gx = centerGx + dx;
int gy = centerGy + dy;
GridCell cell = getCell(gx, gy);
if (cell != null) {
Point cellCenter = gridToWorld(gx, gy);
double dist = cellCenter.distanceTo(enemyPos);
if (dist < detectionRange) {
// 威胁等级随距离衰减：越近威胁越大
double threat = 1.0 - (dist / detectionRange);
cell.threatLevel = Math.max(cell.threatLevel, threat);
}
}
}
}
}
}
/**
* A*节点，用于路径搜索
*/
public static class AStarNode implements Comparable<AStarNode> {
public int x, y;
public double g; // 从起点到当前节点的实际代价
public double h; // 启发式估计（到终点的距离）
public double f; // 总代价 f = g + h + threatCost
public AStarNode parent;
public AStarNode(int x, int y) {
this.x = x;
this.y = y;
this.g = Double.MAX_VALUE;
this.h = 0;
this.f = Double.MAX_VALUE;
}
@Override
public int compareTo(AStarNode other) {
return Double.compare(this.f, other.f);
}
@Override
public boolean equals(Object obj) {
if (this == obj) return true;
if (!(obj instanceof AStarNode)) return false;
AStarNode other = (AStarNode) obj;
return this.x == other.x && this.y == other.y;
}
@Override
public int hashCode() {
return x * 31 + y;
}
}
/**
* A*路径规划器：在栅格地图上寻找兼顾最短距离和最低威胁的路径
*/
public static class PathPlanner {
private static final double THREAT_WEIGHT = 80.0; // 威胁代价权重
private static final double OCCUPANCY_THRESHOLD = 0.7; // 障碍物阈值
private static final int[][] DIRECTIONS = {
{0, 1}, {1, 0}, {0, -1}, {-1, 0}, // 四连通
{1, 1}, {1, -1}, {-1, 1}, {-1, -1} // 八连通
};
/**
* 执行A*搜索
* @param map 栅格地图
* @param startGx 起点栅格X
* @param startGy 起点栅格Y
* @param goalGx 终点栅格X
* @param goalGy 终点栅格Y
* @return 路径点列表（从起点到终点）
*/
public List<Point> findPath(GridMap map, int startGx, int startGy, int goalGx, int goalGy) {
PriorityQueue<AStarNode> openSet = new PriorityQueue<>();
Set<String> closedSet = new HashSet<>();
AStarNode startNode = new AStarNode(startGx, startGy);
startNode.g = 0;
startNode.h = heuristic(startGx, startGy, goalGx, goalGy);
startNode.f = startNode.h;
openSet.add(startNode);
while (!openSet.isEmpty()) {
AStarNode current = openSet.poll();
String key = current.x + "," + current.y;
if (closedSet.contains(key)) continue;
closedSet.add(key);
// 到达目标
if (current.x == goalGx && current.y == goalGy) {
return reconstructPath(current, map);
}
// 扩展邻居
for (int[] dir : DIRECTIONS) {
int nx = current.x + dir[0];
int ny = current.y + dir[1];
GridCell cell = map.getCell(nx, ny);
if (cell == null || closedSet.contains(nx + "," + ny)) continue;
// 跳过高占用概率的栅格
if (cell.occupancyProb > OCCUPANCY_THRESHOLD) continue;
// 计算移动代价
double moveCost = (dir[0] != 0 && dir[1] != 0) ? GRID_SIZE * 1.414 : GRID_SIZE;
// 威胁代价：当前栅格的威胁等级
double threatCost = cell.threatLevel * THREAT_WEIGHT;
double tentativeG = current.g + moveCost + threatCost;
AStarNode neighbor = new AStarNode(nx, ny);
if (tentativeG < neighbor.g) {
neighbor.g = tentativeG;
neighbor.h = heuristic(nx, ny, goalGx, goalGy);
neighbor.f = neighbor.g + neighbor.h;
neighbor.parent = current;
openSet.add(neighbor);
}
}
}
return new ArrayList<>(); // 无可行路径
}
private double heuristic(int x1, int y1, int x2, int y2) {
// 欧几里得距离
double dx = x1 - x2;
double dy = y1 - y2;
return Math.sqrt(dx * dx + dy * dy) * GRID_SIZE;
}
private List<Point> reconstructPath(AStarNode goal, GridMap map) {
List<Point> path = new ArrayList<>();
AStarNode current = goal;
while (current != null) {
path.add(map.gridToWorld(current.x, current.y));
current = current.parent;
}
Collections.reverse(path);
return path;
}
}
/**
* 潜水艇实体
*/
public static class Submarine {
public Point position;
public double heading; // 航向（弧度，0为右方）
public double speed;
public double depth;
public Submarine(Point pos, double heading) {
this.position = pos;
this.heading = heading;
this.speed = 0;
this.depth = 50; // 初始深度50米
}
public void update(double dt, double turnInput, double speedInput) {
// 转向
heading += turnInput * TURN_RATE * dt;
// 速度变化
speed += speedInput * 2.0 * dt;
speed = Math.max(0, Math.min(MAX_SPEED, speed));
// 位置更新
position.x += Math.cos(heading) * speed * dt;
position.y += Math.sin(heading) * speed * dt;
}
}
// 模拟场景
private Submarine submarine;
private GridMap gridMap;
private SonarSystem sonar;
private PathPlanner planner;
private Point goal;
private List<Point> obstacles;
private Point enemyShip;
public SubmarineAI() {
this.submarine = new Submarine(new Point(50, 50), 0);
this.gridMap = new GridMap(MAP_WIDTH, MAP_HEIGHT);
this.sonar = new SonarSystem(SONAR_BEAMS, MAX_RANGE, SONAR_ANGLE);
this.planner = new PathPlanner();
this.goal = new Point(700, 500);
this.enemyShip = new Point(400, 300);
// 生成随机障碍物
this.obstacles = new ArrayList<>();
Random rand = new Random(42);
for (int i = 0; i < 30; i++) {
obstacles.add(new Point(rand.nextDouble() * 800, rand.nextDouble() * 600));
}
}
/**
* 执行一帧模拟
*/
public void simulateFrame(double dt) {
// 1. 声纳扫描并更新地图
double[] sonarData = sonar.scan(submarine.position, submarine.heading, obstacles);
gridMap.updateFromSonar(submarine.position, submarine.heading, sonarData);
// 2. 更新敌方威胁地图
gridMap.updateThreat(enemyShip, 200.0);
// 3. 路径规划
int subGx = gridMap.worldToGridX(submarine.position.x);
int subGy = gridMap.worldToGridY(submarine.position.y);
int goalGx = gridMap.worldToGridX(goal.x);
int goalGy = gridMap.worldToGridY(goal.y);
List<Point> path = planner.findPath(gridMap, subGx, subGy, goalGx, goalGy);
// 4. AI决策：根据路径控制潜水艇
double turnInput = 0;
double speedInput = 0.5;
if (path.size() > 1) {
Point nextWaypoint = path.get(Math.min(3, path.size() - 1));
double dx = nextWaypoint.x - submarine.position.x;
double dy = nextWaypoint.y - submarine.position.y;
double targetHeading = Math.atan2(dy, dx);
// 计算转向差
double headingDiff = targetHeading - submarine.heading;
// 归一化到 [-π, π]
while (headingDiff > Math.PI) headingDiff -= 2 * Math.PI;
while (headingDiff < -Math.PI) headingDiff += 2 * Math.PI;
turnInput = Math.max(-1, Math.min(1, headingDiff * 2));
}
submarine.update(dt, turnInput, speedInput);
// 输出状态
System.out.printf("Sub: (%.1f, %.1f), heading=%.2f, pathNodes=%d%n",
submarine.position.x, submarine.position.y,
submarine.heading, path.size());
}
public void runSimulation(int frames) {
System.out.println("=== 潜水艇AI模拟开始 ===");
for (int i = 0; i < frames; i++) {
simulateFrame(0.1);
if (submarine.position.distanceTo(goal) < 30) {
System.out.println("到达目标！任务完成！");
break;
}
}
}
public static void main(String[] args) {
SubmarineAI ai = new SubmarineAI();
ai.runSimulation(200);
}
}
四、算法复杂度分析
| 算法模块 | 时间复杂度 | 空间复杂度 | 关键参数 |
|---|---|---|---|
| 声纳射线投射 | $O(b \cdot n)$ | $O(b)$ | $b$ 为波束数，$n$ 为障碍物数 |
| 栅格地图更新 | $O(b \cdot r)$ | $O(W \cdot H)$ | $r$ 为射线覆盖栅格数 |
| 威胁地图更新 | $O(R^2)$ | $O(W \cdot H)$ | $R$ 为威胁半径（栅格数） |
| A*路径规划 | $O(E \log V)$ | $O(V)$ | $V = W \cdot H$，$E \approx 8V$ |
其中 $W \times H$ 为地图栅格总数。对于 $80 \times 60$ 的地图，A*搜索可在毫秒级完成。
五、扩展与优化方向
- SLAM同步定位与建图：结合潜水艇的运动模型，使用粒子滤波或扩展卡尔曼滤波同时估计自身位置和环境地图
- 动态避障：引入RRT*或DWA（动态窗口法）处理移动障碍物
- 深度维度扩展：将二维平面扩展为三维空间，考虑深度对声纳传播速度的影响
- 多目标优化：使用NSGA-II等算法同时优化路径长度、隐蔽性和能量消耗
六、总结
本文从潜水艇这一经典深海游戏出发，完整实现了基于Java的AI导航系统。核心算法涵盖了声纳扇形波束探测、占用栅格地图概率更新与威胁感知A*路径规划。通过这些算法的组合，潜水艇AI能够在不完全信息环境下自主探索未知海域、规避敌方威胁并抵达目标位置。希望读者能够理解不完全信息决策系统的核心设计思想，并将其应用到自己的游戏AI或机器人导航项目中。
