A-Star 나쁜 웨이 포인트를 선택하십시오.

Question

---

해결 : 죄송합니다. 나는 부적절하게 경로를 재구성하고 있었다. closedSet에는 처음부터 끝까지 모든 중간 지점이 있다고 생각했지만 다른 중간 지점도 있습니다. 나는 그 개념을 이해하지 못했다. 이제는 일하고있어!

---

나는 여전히 A *에 문제가 있습니다.

내 캐릭터가 경로를 찾고 있지만 때로는지도를 클릭하는 위치에 따라 알고리즘이 최단 경로 또는 경로를 찾지 만 선택하지 않아야하는 노드가 많습니다.

나는 초보자 구현을위한 위키 백과의 및 A * 길 찾기를 수행하려고했습니다,하지만 그들은 나에게 동일한 결과를 제공합니다. 발견 적 알고리즘인지 알고리즘인지는 모르겠지만 뭔가 잘못되었습니다.

그리고이 두 개의 서로 다른 노드를 클릭 문제의 예는 다음과 같습니다

import java.util.ArrayList; 
import java.util.Collections; 
import java.util.TreeSet; 

public class Pathfind { 
public Pathfind(){ 

} 

public ArrayList<Node> findPath(Node start, Node end, ArrayList<Node> nodes){ 

    ArrayList<Node> openSet = new ArrayList<Node>(); 
    ArrayList<Node> closedSet = new ArrayList<Node>(); 

    Node current; 

    openSet.add(start); 

    while(openSet.size() > 0){ 

     current = openSet.get(0); 

     current.setH_cost(ManhattanDistance(current, end)); 

     if(start == end) return null;   
     else if(closedSet.contains(end)){ 
      System.out.println("Path found!"); 
      return closedSet; 
     } 

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

     for(Node n : current.getNeigbours()){   
      if(!closedSet.contains(n)){  
       if(!openSet.contains(n) || (n.getG_cost() < (current.getG_cost()+10))){ 
        n.setParent(current); 
        n.setG_cost(current.getG_cost()+10); 
        n.setH_cost(ManhattanDistance(n, end)); 

         if(!openSet.contains(n)) 
          openSet.add(n); 

        Collections.sort(openSet); 
       } 
      } 
     } 
    }  

    return null; 
} 

private int ManhattanDistance(Node start, Node end){ 
    int cost = start.getPenalty(); 

    int fromX = start.x, fromY = start.y; 
    int toX = end.x, toY = end.y; 

    return cost * (Math.abs(fromX - toX) + Math.abs(fromY - toY)); 
} 

}

Answer 1

당신의 단위는 상/하/좌/우를 걸어 수행 여기 http://i.imgur.com/gtgxi.jpg

는 Pathfind 클래스의 아니면 오직 대각선을 취할 수 있습니까?

는 A * -heuristic에 대한 하나 개의 요구 사항은 admissible 점입니다 - 그것은 결코 이상 -estimate 실제 경로 길이해야합니다. 유닛이 대각선으로 걸을 수 있다면 manhatten 거리가 경로 길이를 과대 추정하므로 A *가 작동하는 것이 보장되지 않습니다.

Answer 2

나는 버그가 조건이라고 생각 : 비용 (g(node)+h(node)가) 현재에서 감소되어있는 경우가 전진 방지 안

if(n.getCost() < current.getCost()){ 

.이 카운터 예제를 보라 : (S 소스이며, T는 대상) 이제

_________ 
|S |x1|x2| 
---------- 
|x3|x4|x5| 
--------- 
|x6|x7|T | 
---------- 

, 당신은 S에있는 가정, 아직 너무 g(S) =0를 이동하고, 맨해튼 거리 휴리스틱에서하지 않은 , h(S) = 4은, 그래서 당신은 x1,x3에서 봐, 지금 f(S)=4

를 얻을 : 각 하나의 단계를 복용 가정, 그들은 g(x1)=g(x3)=1이되며, 모두 동일한 추론에서 h(x1)=h(x3)=3있을 것이다. f(x1)=f(x3)=4이 나오고 if 조건이 아무 것도 열리지 않으므로 S에서 반복을 완료하면 아무 것도 open으로 푸시하지 않고 검색이 종료됩니다. 보조 노트로

---

:
나는 ArrayList로 closedSet의 선택이 효율적이지 않다 생각합니다. 각 op는 O(n)입니다. 여기서 n은 닫힌 노드의 수입니다.더 나은 성능을 위해 Set을 사용해야합니다. HashSet은 현명한 선택이며 삽입 순서를 유지하려면 LinkedHashSet을 사용해야합니다. (참고로 equals()과 hashCode() 메서드를 Node으로 바꿔야합니다.)