我正在制作一个游戏,其中一个棋子必须被护送到节点 F。存储在 2D 数组中的值表示:
Pawn (starting point): I
Destination: F
例如,
Node [row=2, col=1]
Node [row=2, col=2]
Node [row=1, col=2]
Node [row=0, col=2]
Node [row=0, col=3]
Node [row=0, col=4]
Node [row=1, col=4]
Node [row=2, col=4]
Node [row=2, col=5]
Search Path without diagonals
0 1 2 3 4 5 6
0 - - * * * - -
1 - - * B * - -
2 - I* * B * *F -
3 - - - B - - -
4 - - - - - - -
5 - - - - - - -
我的实现的问题是它一步一步地进行。我希望能够检测到方向何时发生变化并仅添加此 Action ,我该如何实现这一点?例如,我不想像之前的示例那样一一访问所有节点,而是希望:
Node [row=2, col=1]
Node [row=2, col=2] // Right
Node [row=0, col=2] // Top
Node [row=0, col=4] // Right
Node [row=2, col=4] // Bottom
Node [row=2, col=5] // Right
我怎样才能做到这一点?
最佳答案
我没有检查算法实现,但看起来您正在以 Node 对象列表的形式获取结果。它可能看起来像这样:
List<Node> path = aStar.findPath();
那么您需要做的就是从结果中排除所有中间节点。您可以在实际算法之后执行此操作(免责声明:未经测试的代码):
List<Node> path = aStar.findPath();
//a path with intermediate nodes removed
List<Node> filteredPath = new ArrayList<>(path.size());
for(int i=0; i<path.size(); i++) {
Node current = path.get(i);
//the first and the last element get into the result in any case
if(i==0 || i==path.size()-1) {
filteredPath.add(current);
} else {
//for the elements in between we are detecting the direction change
Node previous = path.get(i-1);
Node next = path.get(i+1);
//is the step from the previous node to this one vertical
boolean isPreviousStepVertical = current.getCol()==previous.getCol();
//is the step from this node to the next one vertical
boolean isNextStepVertical = current.getCol()==next.getCol();
//we only add the nodes for which the direction has changed
if(isPreviousStepVertical!=isNextStepVertical) {
filteredPath.add(current);
}
}
}
这个想法是检查每个节点的方向是否实际发生变化(从垂直到水平,或反之亦然),并只保留必要的节点。
我假设棋子不能沿对角线移动,也不能移回到已经访问过的单元格。否则,您需要计算节点之间的实际方向 vector 并将它们与每个节点进行比较。
更新:为了使 AStar 实现按预期工作,您需要注释掉与 addAdjacentUpperRow
和 addAdjacentLowerRow
中对角线移动相对应的四行,例如:
checkNode(currentNode, col - 1, upperRow, getDiagonalCost()); // Comment this if diagonal movements are not allowed
此后,一切都按预期进行:https://ideone.com/77MAxg
关于java - 使用 A* 查找最短路径,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59082075/