引言
接金币是经典街机游戏的简化模型：玩家控制角色在网格中移动收集金币，同时避开随机生成的障碍物。本文用Java实现A*寻路算法，并扩展支持动态障碍物的实时重规划，让AI角色在变化的环境中始终找到最优收集路径。
问题建模
将游戏世界建模为动态加权图：
– 节点：网格中的每个位置
– 静态边：相邻网格的移动代价（平地=1，沼泽=3）
– 动态障碍物：随时间出现/消失的不可通行节点
– 目标：收集所有金币的最短路径（类似旅行商问题变体）
Java实现
import java.util.*;
/**
* 接金币游戏：A*路径规划 + 动态障碍物重规划
*/
public class CoinCollectorAStar {
private final int rows, cols;
private final int[][] grid; // 0=平地, 1=障碍, 2=沼泽, 3=金币
private final boolean[][] dynamicObstacle; // 动态障碍物标记
private final int[][] directions = {{-1,0},{1,0},{0,-1},{0,1}};
public CoinCollectorAStar(int rows, int cols) {
this.rows = rows;
this.cols = cols;
this.grid = new int[rows][cols];
this.dynamicObstacle = new boolean[rows][cols];
}
/**
* 设置地图单元格类型
*/
public void setCell(int r, int c, int type) {
grid[r][c] = type;
}
/**
* 更新动态障碍物（每帧调用）
*/
public void updateDynamicObstacles(List<int[]> obstacles) {
for (boolean[] row : dynamicObstacle) Arrays.fill(row, false);
for (int[] obs : obstacles) {
dynamicObstacle[obs[0]][obs[1]] = true;
}
}
/**
* A*核心搜索
* @param start 起点 [r, c]
* @param goal 终点 [r, c]
* @return 最优路径（坐标列表），不可达返回空列表
*/
public List<int[]> aStar(int[] start, int[] goal) {
PriorityQueue<Node> open = new PriorityQueue<>(Comparator.comparingInt(n -> n.f));
boolean[][] closed = new boolean[rows][cols];
Map<String, Node> nodeMap = new HashMap<>();
Node startNode = new Node(start[0], start[1], 0, heuristic(start, goal), null);
open.offer(startNode);
nodeMap.put(key(start[0], start[1]), startNode);
while (!open.isEmpty()) {
Node current = open.poll();
if (current.r == goal[0] && current.c == goal[1]) {
return reconstructPath(current);
}
if (closed[current.r][current.c]) continue;
closed[current.r][current.c] = true;
// 扩展四个方向
for (int[] d : directions) {
int nr = current.r + d[0];
int nc = current.c + d[1];
if (!inBounds(nr, nc)) continue;
if (closed[nr][nc]) continue;
if (isBlocked(nr, nc)) continue; // 静态或动态障碍
int moveCost = getMoveCost(nr, nc);
int newG = current.g + moveCost;
String k = key(nr, nc);
Node neighbor = nodeMap.get(k);
if (neighbor == null || newG < neighbor.g) {
int h = heuristic(new int[]{nr, nc}, goal);
Node newNode = new Node(nr, nc, newG, newG + h, current);
nodeMap.put(k, newNode);
open.offer(newNode);
}
}
}
return Collections.emptyList(); // 不可达
}
/**
* 启发式函数：对角距离（允许八方向时更优，此处用曼哈顿距离）
*/
private int heuristic(int[] pos, int[] goal) {
return Math.abs(pos[0] - goal[0]) + Math.abs(pos[1] - goal[1]);
}
/**
* 动态障碍物规避：当路径上遇到新障碍时，局部重规划
*/
public List<int[]> navigateWithReplanning(int[] start, List<int[]> coinGoals,
List<int[]> dynamicObs) {
List<int[]> fullPath = new ArrayList<>();
int[] currentPos = start.clone();
// 贪心最近金币：每次去最近的可达金币
Set<String> collected = new HashSet<>();
while (collected.size() < coinGoals.size()) {
// 更新动态障碍物
updateDynamicObstacles(dynamicObs);
// 找最近未收集金币
int[] nearest = null;
int minDist = Integer.MAX_VALUE;
List<int[]> bestPath = null;
for (int[] coin : coinGoals) {
if (collected.contains(key(coin[0], coin[1]))) continue;
List<int[]> path = aStar(currentPos, coin);
if (path.isEmpty()) continue;
int dist = path.size() - 1;
if (dist < minDist) {
minDist = dist;
nearest = coin;
bestPath = path;
}
}
if (nearest == null) {
System.out.println("警告：部分金币不可达！");
break;
}
// 执行路径，期间检测碰撞
for (int i = 1; i < bestPath.size(); i++) {
int[] step = bestPath.get(i);
// 移动前检查动态障碍
if (dynamicObstacle[step[0]][step[1]]) {
// 遇到新障碍！从当前位置重新规划到目标
List<int[]> replanned = aStar(currentPos, nearest);
if (replanned.isEmpty()) break;
bestPath = replanned;
i = 0; // 重新遍历新路径
continue;
}
fullPath.add(step);
currentPos = step.clone();
}
collected.add(key(nearest[0], nearest[1]));
}
return fullPath;
}
/**
* 多目标路径优化：贪心 + 2-opt局部改进
* 解决多金币收集顺序优化问题
*/
public List<int[]> optimizeCoinOrder(int[] start, List<int[]> coins) {
if (coins.isEmpty()) return Collections.emptyList();
// 1. 贪心构造初始解：最近邻
List<int[]> order = new ArrayList<>();
Set<Integer> visited = new HashSet<>();
int[] current = start;
while (order.size() < coins.size()) {
int bestIdx = -1;
int bestDist = Integer.MAX_VALUE;
for (int i = 0; i < coins.size(); i++) {
if (visited.contains(i)) continue;
int dist = heuristic(current, coins.get(i));
if (dist < bestDist) {
bestDist = dist;
bestIdx = i;
}
}
visited.add(bestIdx);
order.add(coins.get(bestIdx));
current = coins.get(bestIdx);
}
// 2. 2-opt局部搜索改进顺序
boolean improved;
do {
improved = false;
for (int i = 0; i < order.size() - 1; i++) {
for (int j = i + 2; j < order.size(); j++) {
// 计算交换前后的路径长度变化（用启发式距离近似）
int[] a = i == 0 ? start : order.get(i - 1);
int[] b = order.get(i);
int[] c = order.get(j);
int[] d = j + 1 < order.size() ? order.get(j + 1) : null;
int before = heuristic(a, b) + heuristic(c, d != null ? d : c);
int after = heuristic(a, c) + heuristic(b, d != null ? d : b);
if (after < before) {
// 翻转i到j的子序列
Collections.reverse(order.subList(i, j + 1));
improved = true;
}
}
}
} while (improved);
// 3. 按优化后的顺序逐个A*寻路
List<int[]> fullPath = new ArrayList<>();
current = start;
for (int[] coin : order) {
List<int[]> path = aStar(current, coin);
if (!path.isEmpty()) {
fullPath.addAll(path.subList(1, path.size()));
current = coin;
}
}
return fullPath;
}
private boolean isBlocked(int r, int c) {
return grid[r][c] == 1 || dynamicObstacle[r][c];
}
private int getMoveCost(int r, int c) {
return grid[r][c] == 2 ? 3 : 1; // 沼泽移动代价为3
}
private boolean inBounds(int r, int c) {
return r >= 0 && r < rows && c >= 0 && c < cols;
}
private String key(int r, int c) {
return r + "," + c;
}
private List<int[]> reconstructPath(Node end) {
List<int[]> path = new LinkedList<>();
Node cur = end;
while (cur != null) {
path.add(0, new int[]{cur.r, cur.c});
cur = cur.parent;
}
return path;
}
private static class Node {
final int r, c;
final int g, f;
final Node parent;
Node(int r, int c, int g, int f, Node parent) {
this.r = r; this.c = c; this.g = g; this.f = f; this.parent = parent;
}
}
public static void main(String[] args) {
CoinCollectorAStar game = new CoinCollectorAStar(10, 10);
// 初始化地图
for (int r = 0; r < 10; r++) {
for (int c = 0; c < 10; c++) {
game.setCell(r, c, 0);
}
}
// 设置静态障碍
game.setCell(2, 2, 1); game.setCell(2, 3, 1); game.setCell(3, 2, 1);
game.setCell(5, 5, 2); game.setCell(5, 6, 2); // 沼泽
// 金币位置
List<int[]> coins = Arrays.asList(
new int[]{1, 8}, new int[]{7, 3}, new int[]{8, 8}
);
for (int[] coin : coins) game.setCell(coin[0], coin[1], 3);
// 动态障碍物（模拟其他角色移动）
List<int[]> dynamicObs = Arrays.asList(new int[]{4, 4}, new int[]{4, 5});
int[] start = {0, 0};
// 测试1：带重规划的多金币收集
List<int[]> path = game.navigateWithReplanning(start, coins, dynamicObs);
System.out.println("收集路径长度: " + path.size());
// 测试2：优化金币收集顺序
List<int[]> optPath = game.optimizeCoinOrder(start, coins);
System.out.println("优化后路径长度: " + optPath.size());
// 打印路径
System.out.println("\n路径坐标:");
for (int[] p : optPath) {
System.out.printf("(%d,%d) ", p[0], p[1]);
}
}
}
动态障碍物处理策略
- 周期性重规划：每N帧或遇到障碍时重新执行A*
- 时间维度A/*：将时间作为第三维，预测障碍物未来位置（本文未实现，可扩展）
- 弹性路径：主路径加备用绕行路径，遇到障碍时快速切换
总结
本文将A算法应用于接金币游戏，核心亮点在于动态障碍物的实时重规划机制：当AI移动过程中遇到新出现的障碍时，立即从当前位置重新调用A计算到目标的替代路径。配合贪心最近邻+2-opt的多目标顺序优化，AI能在复杂动态环境中高效完成金币收集任务。
