C# AStar 문제가 올바르게 수행되지 않습니다.

Question

현재 A * 길 찾기를하고 있지만 몇 가지 문제가 있습니다. 끝까지 최상의 경로를 잡기 전에 잘못된 경로를 수행합니다. 내가 뭘 잘못하고 있니?

소스 코드 : http://basic.apayostudios.com/AStar.zip

온라인 :

Game.cs http://pastie.org/1656955

Node.cs http://pastie.org/1656956

열거 형 :

public enum NodeType 
{ 
    None, 
    Solid, 
    Start, 
    End 
} 

감사합니다!

Answer 1

체크 아웃 에릭 Lippert의에 의해이 블로그 시리즈 :

Path Finding Using A* in C# 3.0

Answer 2

여기 내 A-star 경로 찾기 기능이 있습니다. 작동하며 원하는대로 솔루션을 학습하고 비교할 때 자유롭게 사용할 수 있습니다. 그러나이 코드에서 빠진 종속성이 있으며 고정 소수점 산술을 사용하고 있습니다. 약간의 변경 없이는 빌드되지 않습니다. 이 코드는 상대적으로 높은 수준이며 리버스 엔지니어링하기에 충분히 쉬워야합니다.

public class AgentPathfinder 
{ 
    class SolutionComparer : IComparer<Solution> 
    { 
     public int Compare(Solution x, Solution y) 
     { 
      return x.Cost.CompareTo(y.Cost); 
     } 
    } 

    class Solution 
    { 
     public List<FixedVector> Path { get; private set; } 

     public FixedVector LastPosition { get { return Path[Path.Count - 1]; } } 

     public Fixed32 Heuristic { get; set; } 
     public Fixed32 Cost { get; set; } 

     public Solution(FixedVector position, Fixed32 heuristic) 
     { 
      Path = new List<FixedVector>(2) { position }; 
      Heuristic = heuristic; 
      Cost = Path.Count + heuristic; 
     } 

     public Solution(FixedVector position 
      , Fixed32 heuristic 
      , List<FixedVector> path) 
     { 
      Path = new List<FixedVector>(path) { position }; 
      Heuristic = heuristic; 
      Cost = Path.Count + heuristic; 
     } 
    } 

    // TODO: replace with pathable terrain data 
    public Map Map { get; set; } 

    public FixedVector Position { get; set; } 
    public FixedVector Destination { get; set; } 

    public List<FixedVector> Path { get; set; } 

    public void Compute() 
    { 
     var visited = new bool[(int)Map.Size.Width, (int)Map.Size.Height]; 

     var pq = new PriorityQueue<Solution>(new SolutionComparer()); 

     var bestFit = new Solution(new FixedVector((int)(Position.X + 0.5) 
      , (int)(Position.Y + 0.5)) 
      , (Destination - Position).Length 
      ); 

     pq.Enqueue(bestFit); 

     while (pq.Count > 0) 
     { 
      var path = pq.Dequeue(); // optimal, thus far 
      if (path.Heuristic < bestFit.Heuristic) // best approximation? 
      { 
       // if we starve all other paths we 
       // fallback to this, which should be the best 
       // approximation for reaching the goal 
       bestFit = path; 
      } 
      for (int i = 0; i < FixedVector.Adjacent8.Length; i++) 
      { 
       var u = path.LastPosition + FixedVector.Adjacent8[i]; 
       if (Map.Size.Contains(u)) 
       { 
        if (Map.IsPathable(u)) 
        { 
         if (!visited[(int)u.X, (int)u.Y]) 
         { 
          // heuristic (straight-line distance to the goal) 
          var h = (Destination - u).Length; 
          var solution = new Solution(u, h, path.Path); 
          if (h < 1) 
          { 
           Path = solution.Path; 
           return; // OK, done 
          } 
          else 
          { 
           // keep looking 
           pq.Enqueue(solution); 
          } 
          visited[(int)u.X, (int)u.Y] = true; 
         } 
        } 
       } 
      } 
     } 

     Path = bestFit.Path; 
    } 
}