时间戳

首页 > 解决方案 > 使用 A* 查找最短路径

java - 使用 A* 查找最短路径

问题描述

我正在制作一个棋子必须被护送到节点 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    -   -   -   -   -   -   -

我的实现的问题是它一步一步地经历。我希望能够检测到方向何时改变并且只添加这个动作，我该如何做到这一点？例如，我不想像之前的示例中那样一一访问所有节点，而是希望：

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

我怎样才能做到这一点？

标签： javashortest-pathdijkstraa-star

解决方案

我没有检查算法实现，但 tt 似乎您将结果作为 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);
          }

    } 
}

这个想法是检查每个节点的方向是否实际改变（从垂直到水平，反之亦然），并且只保留必要的节点。

我假设一个棋子不能对角移动，也不能回到已经访问过的单元格。否则，您需要计算节点之间的实际方向向量并将它们与每个方向进行比较。

更新：要使您的 AStar 实现按预期工作，您需要注释掉对应于addAdjacentUpperRow和的对角线移动的四行addAdjacentLowerRow，例如：

checkNode(currentNode, col - 1, upperRow, getDiagonalCost()); // Comment this if diagonal movements are not allowed

在此之后，一切都按预期工作：https ://ideone.com/77MAxg

推荐阅读