A *查找路徑無效

Question

我想實現的A *路徑，但我得到一個錯誤的結果：

綠色斑點是路徑，紅色斑點的障礙。

Invalid path A*

具體這部分是錯誤的：

Going to the tree and back

爲什麼要樹和背部，然後按照正確的路徑？我錯過了什麼？

這是我實現：

public List<Spot> process(GameBodyObject me, Point target, ArrayList<GameBodyObject> others) throws Exception { 

    if(grid == null) { 
     throw new Exception("You have to initialize AStar first."); 
    } 

    grid.unsetObstacleForObject(me); 

    Spot start = grid.getSpotAtPosition(me.getPosition().getX(), me.getPosition().getY()); 
    Spot end = grid.getSpotAtPosition(target.getX(), target.getY()); 

    end = grid.moveSpotSoThatItDoesntCollide(end, me.getRadius()); 

    List<Spot> openSet = new ArrayList<Spot>(grid.getMaxSize()); 
    List<Spot> closedSet = new ArrayList<>(); 
    List<Spot> path = new ArrayList<>(); 

    openSet.add(start); 

    while(openSet.size() > 0) { 

     int winner = 0; 
     for(int i = 1; i < openSet.size(); i++) { 
      if(openSet.get(i).getF() < openSet.get(winner).getF()) { 
       winner = i; 
      } 
     } 

     Spot current = openSet.get(winner); 

     /*int i = 1; 
     for(Spot s : Arrays.asList(openSet.getArray())) { 
      if(s != null) { 
       System.out.println(i + ". " + s.getF()); 
       i++; 
      } 
     }*/ 

     if(current.equals(end)) { 
      // We are done, reconstruct the path... 
      Spot temp = current; 
      path.add(temp); 
      while(temp.getPrevious() != null) { 
       path.add(temp.getPrevious()); 
       temp = temp.getPrevious(); 
      } 

      grid.resetObstacles(); 
      return path; 
     } 

     openSet.remove(current); 
     closedSet.add(current); 

     List<Spot> neighbors = current.getNeighbors(); 

     for(Spot neighbor : neighbors) { 
      if(!closedSet.contains(neighbor) && !grid.isCollidingWithObstacle(neighbor, me.getRadius())) { 
       double tempG = current.getG() + 1; 
       if(openSet.contains(neighbor)) { 
        if(tempG < neighbor.getG()) { 
         neighbor.setG(tempG); 
        } 
       } else { 
        neighbor.setG(tempG); 
        openSet.add(neighbor); 
       } 

       neighbor.setH(heuristic(neighbor, end)); 
       neighbor.setF(neighbor.getG() + neighbor.getH()); 
       neighbor.setPrevious(current); 
      } 
     } 

    } 

    grid.resetObstacles(); 
    return new ArrayList<>(); 
} 

public double heuristic(Spot spot, Spot end) { 
    double dx = spot.getX() - end.getX(); 
    double dy = spot.getY() - end.getY(); 
    return Math.abs(dx) + Math.abs(dy); 
} 

Answer 1

所以好像我在heuristics有一個問題，我把它改爲：

public double heuristic(Spot spot, Spot end) { 
    double dx = spot.getAbsoluteX() - end.getAbsoluteX(); 
    double dy = spot.getAbsoluteY() - end.getAbsoluteY(); 
    //return Math.sqrt(dx * dx + dy * dy); 
    return Math.abs(dx) + Math.abs(dy); 
} 

，現在它工作正常。