A *使用潇洒技工寻路

1 回答

• 0

  Heuristic: 如果从不过度估计达到目标的成本，则可以接受启发式 . 由于您使用了四个基本方向，因此可接受的启发式方法是在起点和终点之间采用曼哈顿距离（L1-Norm），称之为 dist . 然后将 dist 除以单个破折号中的切片数量 . 使用这种启发式方法会高估's no way you' .

  Computing Optimal Path: 如果使用可接受的启发式算法，则可以使用A-Star计算最佳路径 . 关键是你的 node.getNeighbors() 方法返回与当前节点相邻的邻居，即返回到（N）orth，（S）outh，（E）ast和（W）est，以及从一个破折号可以到达的那些邻居当前节点（即 dashDist -tiles到N / S / E / W） . 该方法可能如下所示：

  public List<Node> getNeighbors(){
      List<Node> neighbors = new LinkedList<Node>();
      neighbors.addAll(this.getAdjacentNeighbors());
      neighbors.addAll(this.getDashableNeighbors());
      return neighbors;
  }
  
  private List<Node> getAdjacentNeighbors(){
      //implement code to get the adjacent neighbors
  }
  
  private List<Node> getDashableNeighbors(){
      //implement code to get the neighbors 1-dash away
  }
  

  One other consideration: 我假设短划线发生在一条直线上...在这种情况下，我建议调查JumpPointSearch algorithm . 它利用了世界上的对称性来减少开放集中的节点数量 .

  回复于 2024-04-16T17:42:59+08:00