该场景是基于回合的情况,玩家必须从源位置 A 向位置 B 移动,但只能移动最大数量的单位。
例如,B 与 A 相距 24 个单位(使用 BFS 计算),我的得分为 12。如何找到距离 B 仅 12 个运动单位的最佳路径?
笔记:
- 不能对角移动
- 有很大的障碍
编辑:这适用于类似于 Clue / Cluedo 的游戏,但只有文本,因此玩家将选择一个“朝向”移动的方向。
这是我尝试过的:
示例网格:(◘ 是障碍物,○ 不是)
○○○○○○○○○○
○○○○○○○○◘◘
○○○◘◘◘○○◘◘
○○○◘◘◘○○B◘
○A○◘◘◘○○◘◘
算法:
if paces == 0, return
try moving col closer to dest.col:
if col == dest.col, move row closer to dest.row
else if adjacent is blocked, move row away from start
这在纸上可以正常工作,除非我自己跑到角落里:
○A→◘◘○○◘◘◘
○○↓◘◘○○B◘◘
○○↓◘◘○○◘◘◘
○○↓◘◘○○↑◘◘
○○↓→→→→→◘◘
解决方案:
public ArrayList<Location> shortestPath(final Location start, final Location dest) {
HashSet<Location> visits = new HashSet<>();
HashMap<Location, Location> links = new HashMap<>();
PriorityQueue<Location> queue = new PriorityQueue<>(Board.GRID_COLS * Board.GRID_ROWS,
new Comparator<Location>() {
@Override
public int compare(Location a, Location b) {
return Integer.compare(getHeuristic(a, dest), getHeuristic(b, dest));
}
});
queue.add(start);
while (!queue.isEmpty()) {
Location current = queue.remove();
if (current.equals(dest)) {
ArrayList<Location> path = reconstruct(current, new LinkedList<Location>(), links);
path.add(dest);
return path;
}
visits.add(current);
for (Location neighbour : getNeighbours(current)) {
if (!visits.contains(neighbour)) {
queue.add(neighbour);
visits.add(neighbour);
links.put(neighbour, current);
}
}
}
return null; // failed
}
// Manhattan distance
private int getHeuristic(Location src, Location dest) {
return Math.abs(dest.row - src.row) + Math.abs(dest.col - src.col);
}
private ArrayList<Location> reconstruct(Location current, LinkedList<Location> list, HashMap<Location, Location> links) {
if (links.containsKey(current)) {
list.addFirst(links.get(current));
return reconstruct(links.get(current), list, links);
} else {
return new ArrayList<>(list);
}
}
private ArrayList<Location> getNeighbours(Location current) {
ArrayList<Location> neighbours = new ArrayList<>();
if (current.row < GRID_ROWS - 1) {
Location n = LOCATIONS[current.row + 1][current.col];
if (isAccessible(n, current)) neighbours.add(n);
}
if (current.row > 0) {
Location n = LOCATIONS[current.row - 1][current.col];
if (isAccessible(n, current)) neighbours.add(n);
}
if (current.col < GRID_COLS - 1) {
Location n = LOCATIONS[current.row][current.col + 1];
if (isAccessible(n, current)) neighbours.add(n);
}
if (current.col > 0) {
Location n = LOCATIONS[current.row][current.col - 1];
if (isAccessible(n, current)) neighbours.add(n);
}
return neighbours;
}