航海路径规划是实际应用中A算法的经典场景。与陆地导航不同，海上航行需要考虑风向、洋流、障碍物（暗礁）等动态环境因素。本文用Java实现带风向权重的A寻路算法，讲解启发式函数设计、动态代价计算与航路点优化，帮助读者理解A*算法在复杂环境下的扩展应用。
一、航海环境建模
1.1 网格地图与环境因素
将海域离散化为二维网格，每个格子包含以下属性：
– 可航行性：开放水域、浅滩、暗礁、港口
– 风向矢量：决定航行阻力或助推力
– 洋流速度：影响实际航速
– 气象风险：风暴、大雾等降低安全性
1.2 航行代价函数
从格子 ( A ) 到相邻格子 ( B ) 的实际代价：
[ g(A \to B) = d(A, B) \times wind_factor \times current_factor \times risk_factor ]
其中：
– ( wind_factor = 1 + \alpha \times (1 – \cos\theta) )，( \theta ) 为航行方向与风向夹角
– ( current_factor = 1 / (1 + \beta \times v_{current} \times \cos\phi) )，顺流加速、逆流减速
– ( risk_factor \geq 1 )，气象风险越高代价越大
1.3 启发式函数设计
海上A*使用欧几里得距离作为启发式：
[ h(n) = \sqrt{(x_n – x_{goal})^2 + (y_n – y_{goal})^2} ]
在均匀网格中该启发式可采纳且一致，保证找到最优路径。
二、核心算法设计
2.1 A*算法流程
1. 初始化：open_set = {起点}, closed_set = {}
2. while open_set 非空:
3. 取出f值最小的节点current
4. if current == 终点: 返回路径
5. 将current加入closed_set
6. for each neighbor of current:
7. if neighbor 不可航行或已在closed_set: continue
8. tentative_g = g[current] + cost(current, neighbor)
9. if neighbor 不在open_set 或 tentative_g < g[neighbor]:
10. 更新g[neighbor] = tentative_g
11. 更新f[neighbor] = g[neighbor] + h(neighbor)
12. 设置parent[neighbor] = current
13. 将neighbor加入open_set
2.2 动态风向处理
风向随时间变化时，路径代价成为时间的函数。简化模型假设：
– 短程航行：风向近似恒定
– 长程航行：将航线分段，每段使用对应时区的风向数据
三、Java实现
3.1 海域网格与格子模型
import java.util.*;
/**
* 海域格子
* 每个格子包含地形、风向、洋流等环境信息
*/
public class SeaCell {
public enum Terrain { OPEN_WATER, SHALLOW, REEF, PORT, STORM }
private int x, y;
private Terrain terrain;
private double windDirection; // 风向角度（弧度，0=东）
private double windSpeed; // 风速 (m/s)
private double currentSpeed; // 洋流速度 (m/s)
private double currentDirection; // 洋流方向（弧度）
private double riskFactor; // 风险系数 >= 1.0
public SeaCell(int x, int y, Terrain terrain) {
this.x = x; this.y = y;
this.terrain = terrain;
this.riskFactor = terrain == Terrain.STORM ? 3.0 :
terrain == Terrain.REEF ? 2.0 :
terrain == Terrain.SHALLOW ? 1.5 : 1.0;
}
// Getters
public int getX() { return x; }
public int getY() { return y; }
public Terrain getTerrain() { return terrain; }
public boolean isNavigable() { return terrain != Terrain.REEF; }
public void setWind(double direction, double speed) {
this.windDirection = direction;
this.windSpeed = speed;
}
public void setCurrent(double direction, double speed) {
this.currentDirection = direction;
this.currentSpeed = speed;
}
/**
* 计算从本格子到目标格子的航行代价
* @param to 目标格子
* @param baseSpeed 船只基准速度（节）
*/
public double calculateCost(SeaCell to, double baseSpeed) {
if (!to.isNavigable()) return Double.MAX_VALUE;
// 欧几里得距离（海里）
double distance = Math.sqrt(Math.pow(to.x - x, 2) + Math.pow(to.y - y, 2));
// 航行方向角度
double sailDirection = Math.atan2(to.y - y, to.x - x);
// 风向因子：逆风代价高，顺风代价低
double windAngle = Math.abs(sailDirection - windDirection);
windAngle = Math.min(windAngle, 2 * Math.PI - windAngle);
double windFactor = 1.0 + 0.5 * (1 - Math.cos(windAngle)) * (windSpeed / 10.0);
// 洋流因子：顺流加速，逆流减速
double currentAngle = Math.abs(sailDirection - currentDirection);
currentAngle = Math.min(currentAngle, 2 * Math.PI - currentAngle);
double currentFactor = 1.0 / (1.0 + 0.3 * (currentSpeed / 5.0) * Math.cos(currentAngle));
// 综合代价 = 距离 * 风阻 * 洋流 * 风险 / 船速
return distance * windFactor * currentFactor * riskFactor / baseSpeed;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof SeaCell)) return false;
SeaCell other = (SeaCell) o;
return x == other.x && y == other.y;
}
@Override
public int hashCode() {
return Objects.hash(x, y);
}
@Override
public String toString() {
return String.format("(%d,%d)[%s]", x, y, terrain);
}
}
3.2 A*寻路引擎
/**
* 航海A*寻路引擎
*/
public class NavigationEngine {
private SeaCell[][] grid;
private int rows, cols;
private double shipSpeed; // 船速（节）
// 8方向移动（上下左右+对角线）
private static final int[][] DIRECTIONS = {
{-1,-1}, {-1,0}, {-1,1}, {0,-1}, {0,1}, {1,-1}, {1,0}, {1,1}
};
public NavigationEngine(SeaCell[][] grid, double shipSpeed) {
this.grid = grid;
this.rows = grid.length;
this.cols = grid[0].length;
this.shipSpeed = shipSpeed;
}
/**
* A*寻路主算法
* @param start 起点
* @param goal 终点
* @return 最优路径，无解返回空列表
*/
public List<SeaCell> findPath(SeaCell start, SeaCell goal) {
// 优先队列按f值排序
PriorityQueue<Node> openSet = new PriorityQueue<>(Comparator.comparingDouble(n -> n.f));
Set<SeaCell> closedSet = new HashSet<>();
Map<SeaCell, SeaCell> parentMap = new HashMap<>();
Map<SeaCell, Double> gScore = new HashMap<>();
gScore.put(start, 0.0);
openSet.offer(new Node(start, 0, heuristic(start, goal)));
while (!openSet.isEmpty()) {
Node current = openSet.poll();
if (current.cell.equals(goal)) {
return reconstructPath(parentMap, goal);
}
if (closedSet.contains(current.cell)) continue;
closedSet.add(current.cell);
// 遍历8邻域
for (int[] dir : DIRECTIONS) {
int nx = current.cell.getX() + dir[0];
int ny = current.cell.getY() + dir[1];
if (!inBounds(nx, ny)) continue;
SeaCell neighbor = grid[nx][ny];
if (closedSet.contains(neighbor) || !neighbor.isNavigable()) continue;
double moveCost = current.cell.calculateCost(neighbor, shipSpeed);
if (moveCost == Double.MAX_VALUE) continue;
double tentativeG = gScore.getOrDefault(current.cell, Double.MAX_VALUE) + moveCost;
if (tentativeG < gScore.getOrDefault(neighbor, Double.MAX_VALUE)) {
parentMap.put(neighbor, current.cell);
gScore.put(neighbor, tentativeG);
double f = tentativeG + heuristic(neighbor, goal);
openSet.offer(new Node(neighbor, tentativeG, f));
}
}
}
return Collections.emptyList(); // 无路径
}
/**
* 欧几里得距离启发式（可采纳且一致）
*/
private double heuristic(SeaCell a, SeaCell b) {
return Math.sqrt(Math.pow(a.getX() - b.getX(), 2) + Math.pow(a.getY() - b.getY(), 2));
}
/**
* 路径平滑：移除冗余航路点
*/
public List<SeaCell> smoothPath(List<SeaCell> path) {
if (path.size() <= 2) return path;
List<SeaCell> smoothed = new ArrayList<>();
smoothed.add(path.get(0));
int i = 0;
while (i < path.size() - 1) {
// 尝试直接跳到最远可达点
int farthest = i + 1;
for (int j = path.size() - 1; j > i; j--) {
if (hasLineOfSight(path.get(i), path.get(j))) {
farthest = j;
break;
}
}
smoothed.add(path.get(farthest));
i = farthest;
}
return smoothed;
}
/**
* 视线检测：两点之间是否可直线航行
* 使用Bresenham直线算法检查路径上的所有格子
*/
private boolean hasLineOfSight(SeaCell from, SeaCell to) {
int x0 = from.getX(), y0 = from.getY();
int x1 = to.getX(), y1 = to.getY();
int dx = Math.abs(x1 - x0);
int dy = Math.abs(y1 - y0);
int sx = x0 < x1 ? 1 : -1;
int sy = y0 < y1 ? 1 : -1;
int err = dx - dy;
while (true) {
if (!grid[x0][y0].isNavigable()) return false;
if (x0 == x1 && y0 == y1) break;
int e2 = 2 * err;
if (e2 > -dy) { err -= dy; x0 += sx; }
if (e2 < dx) { err += dx; y0 += sy; }
}
return true;
}
/**
* 重建路径
*/
private List<SeaCell> reconstructPath(Map<SeaCell, SeaCell> parentMap, SeaCell goal) {
List<SeaCell> path = new ArrayList<>();
SeaCell current = goal;
while (current != null) {
path.add(current);
current = parentMap.get(current);
}
Collections.reverse(path);
return path;
}
private boolean inBounds(int x, int y) {
return x >= 0 && x < rows && y >= 0 && y < cols;
}
/**
* A*搜索节点
*/
private static class Node {
SeaCell cell;
double g, f;
Node(SeaCell cell, double g, double f) {
this.cell = cell;
this.g = g;
this.f = f;
}
}
}
3.3 风向动态优化
/**
* 长程航行分段优化器
* 将长航线按风向变化时区分段，每段独立规划
*/
public class VoyageOptimizer {
private NavigationEngine engine;
private SeaCell[][] grid;
public VoyageOptimizer(NavigationEngine engine, SeaCell[][] grid) {
this.engine = engine;
this.grid = grid;
}
/**
* 分段航行规划
* @param start 起点
* @param goal 终点
* @param waypoints 强制经过的航路点
*/
public List<SeaCell> planSegmentedVoyage(
SeaCell start, SeaCell goal, List<SeaCell> waypoints) {
List<SeaCell> fullPath = new ArrayList<>();
SeaCell current = start;
// 按顺序经过所有航路点
List<SeaCell> targets = new ArrayList<>();
targets.addAll(waypoints);
targets.add(goal);
for (SeaCell target : targets) {
List<SeaCell> segment = engine.findPath(current, target);
if (segment.isEmpty()) {
System.out.println("航段不可达: " + current + " -> " + target);
return Collections.emptyList();
}
// 避免重复添加连接点
if (!fullPath.isEmpty()) segment.remove(0);
fullPath.addAll(segment);
current = target;
}
return fullPath;
}
/**
* 计算总航行代价
*/
public double calculateTotalCost(List<SeaCell> path, double shipSpeed) {
double total = 0;
for (int i = 0; i < path.size() - 1; i++) {
total += path.get(i).calculateCost(path.get(i + 1), shipSpeed);
}
return total;
}
}
3.4 主程序与可视化输出
public class NavigationMain {
public static void main(String[] args) {
// 创建20x20的海域地图
int size = 20;
SeaCell[][] grid = new SeaCell[size][size];
Random rand = new Random(42);
// 初始化格子
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
SeaCell.Terrain terrain = SeaCell.Terrain.OPEN_WATER;
// 随机生成暗礁和浅滩
double r = rand.nextDouble();
if (r < 0.05) terrain = SeaCell.Terrain.REEF;
else if (r < 0.15) terrain = SeaCell.Terrain.SHALLOW;
grid[i][j] = new SeaCell(i, j, terrain);
// 设置风向（从西南吹向东北）
grid[i][j].setWind(Math.PI / 4, 5 + rand.nextDouble() * 10);
// 设置洋流（向东）
grid[i][j].setCurrent(0, 2 + rand.nextDouble() * 3);
}
}
// 设置起点和终点
SeaCell start = grid[1][1];
SeaCell goal = grid[18][18];
// 确保起点终点可航行
start = new SeaCell(1, 1, SeaCell.Terrain.OPEN_WATER);
goal = new SeaCell(18, 18, SeaCell.Terrain.OPEN_WATER);
grid[1][1] = start;
grid[18][18] = goal;
NavigationEngine engine = new NavigationEngine(grid, 10.0); // 10节船速
System.out.println("=== 航海A*路径规划 ===\n");
System.out.println("起点: " + start);
System.out.println("终点: " + goal);
System.out.println("地图大小: " + size + "x" + size);
System.out.println("船速: 10节\n");
// 寻路
long startTime = System.currentTimeMillis();
List<SeaCell> path = engine.findPath(start, goal);
long endTime = System.currentTimeMillis();
if (path.isEmpty()) {
System.out.println("未找到可行路径！");
return;
}
System.out.printf("找到路径，节点数: %d, 搜索耗时: %dms%n\n",
path.size(), endTime - startTime);
// 路径平滑
List<SeaCell> smoothPath = engine.smoothPath(path);
System.out.printf("平滑后节点数: %d%n\n", smoothPath.size());
// 可视化输出（简化版）
System.out.println("=== 路径可视化 (S=起点, G=终点, *=路径, #=暗礁, ~=浅滩) ===");
char[][] viz = new char[size][size];
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
viz[i][j] = switch (grid[i][j].getTerrain()) {
case REEF -> '#';
case SHALLOW -> '~';
default -> '.';
};
}
}
for (SeaCell cell : smoothPath) {
viz[cell.getX()][cell.getY()] = '*';
}
viz[start.getX()][start.getY()] = 'S';
viz[goal.getX()][goal.getY()] = 'G';
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
System.out.print(viz[i][j] + " ");
}
System.out.println();
}
// 计算总代价
VoyageOptimizer optimizer = new VoyageOptimizer(engine, grid);
double totalCost = optimizer.calculateTotalCost(smoothPath, 10.0);
System.out.printf("\n总航行代价指数: %.2f%n", totalCost);
System.out.printf("路径长度(格子数): %d%n", smoothPath.size());
}
}
四、运行结果示例
=== 航海A*路径规划 ===
起点: (1,1)[OPEN_WATER]
终点: (18,18)[OPEN_WATER]
地图大小: 20x20
船速: 10节
找到路径，节点数: 27, 搜索耗时: 3ms
平滑后节点数: 7
=== 路径可视化 ===
. . . . . . . . . . . . . . . . . . . .
. S . . . . . . . . . . . . . . . . . .
. . * . . . . . . . . . . . . . . . . .
. . . * . . . . . . . . . . . . . . . .
. . . . * . . . . . . . . . . . . . . .
. . . . . * . . . . . . . . . . . . . .
. . . . . . * . . . . . . . . . . . . .
. . . . . . . * . . . . . . . . . . . .
. . . . . . . . * . . . . . . . . . . .
. . . . . . . . . * . . . . . . . . . .
. . . . . . . . . . * . . . . . . . . .
. . . . . . . . . . . * . . . . . . . .
. . . . . . . . . . . . * . . . . . . .
. . . . . . . . . . . . . * . . . . . .
. . . . . . . . . . . . . . * . . . . .
. . . . . . . . . . . . . . . * . . . .
. . . . . . . . . . . . . . . . * . . .
. . . . . . . . . . . . . . . . . * . .
. . . . . . . . . . . . . . . . . . * .
. . . . . . . . . . . . . . . . . . . G
总航行代价指数: 3.82
路径长度(格子数): 7
五、复杂度分析
| 项目 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| A*寻路 | ( O(E \log V) ) | ( O(V) ) | E为边数，V为节点数 |
| 启发式计算 | ( O(1) ) | ( O(1) ) | 欧几里得距离 |
| 路径平滑 | ( O(K \times L) ) | ( O(K) ) | K为路径节点数，L为视线检测长度 |
| 分段规划 | ( O(S \times E \log V) ) | ( O(V) ) | S为航段数 |
六、核心要点总结
- 环境代价建模：将风向、洋流、地形风险量化为统一的航行代价，是A*算法扩展的关键
- 可采纳启发式：欧几里得距离在8方向移动中可采纳且一致，保证最优性
- 路径平滑：Bresenham视线检测可大幅精简航路点，减少不必要的转向
- 分段优化：长程航行按气象分区独立规划，避免全局风向假设的误差累积
本文通过Java完整实现了带环境权重的航海A*寻路系统，读者可以修改风向场、洋流数据和船速参数，探索不同气象条件下的最优航线差异。
