C# - A * algoritması C# 4 yönlü A-yıldızlı yol bulma algoritması yapmaya çalışıyorum ama düzgün çalışması yapamaz

Question

yanlış sonuçlar verir. Ana yöntemde, hangi alanlara erişilebileceğini ve hangilerinin (0 - açık alan, 1 - engel) ayarlanabileceğini gösteren bir örnek 5x5 int dizi haritasına sahibim. Örnek olarak ı (4, 4), bu yüzden yolu duvarı önlemek ve vb devam beklenir de ve HEDEF noktası (3: 1) ile BAŞLAT noktasını ayarlamak ancak yok. Hatta algoritmamın her ebeveyni ve halefini (komşusu) göstermesini sağladım. Benim durumumda, (Harita) Alanda engel olarak işaretlenmiş olmasına rağmen, düğümlerden biri olarak (2,4), nasıl oldu? Yalnızca 0 olarak işaretlenmiş olanları eklemek için GetSuccessors yönteminde açık bir ifade vardır, ancak yine de (2, 4) noktasını içerir. Bir şey GetSuccessors veya FindPath (ana algoritma) ile yanlışsa gerçekten emin değilim.

Örnek harita:

int[,] fields = new int[5, 5] //MAP, 1 - OBSTACLE 
     { 
      { 0, 0, 0, 0, 0 }, 
      { 0, 1, 1, 1, 0 }, 
      { 0, 1, 1, 1, 0 }, 
      { 0, 0, 1, 0, 0 }, 
      { 0, 0, 1, 0, 0 } 
     }; 

Örnek noktası:

Node start = new Node(1, 3); //START LOCATION ON MAP 
Node target = new Node(4, 4); //TARGET LOCATION ON MAP 

Üretilen yol (hedeften START):

4, 4 
3, 4 
2, 4 
1, 3 

Tam kodu (FindPath ve GetSuccessors temel olanlar ama hala diğer yöntemlerle yanlış bir şey yapabilirim):

Ivan belirttiği gibi

using System; 
using System.Collections.Generic; 
using System.Linq; 

namespace FoxLib 
{ 
    public class Node 
    { 
     public Node(int x, int y) 
     { 
      this.x = x; 
      this.y = y; 
     } 
     public int x, y; //POSITION ON MAP 
     public Node parent; //NEEDED TO RETRIEVE PATH LATER 
     public int G, H, F; 
     //G - COST FROM START NODE TO THIS NODE 
     //H - COST FROM THIS NODE TO TARGET (HEURISTIC) 
     //F - G + H; NODE COST 
    } 

    public class Pathfinding 
    { 
     public static void FindPath(int startX, int startY, int targetX, int targetY, int[,] fields) //MAIN ALGORITHM 
     { 
      bool pathFound=false; //IS PATH AVAILABLE? 
      Node start = new Node(startX, startY); //STARTING NODE 
      Node target = new Node(targetX, targetY); //TARGET NODE 
      start.parent = start; 
      start.G = 0; 
      start.H = Math.Abs(target.x - start.x) + Math.Abs(target.y - start.y); 
      start.F = start.G + start.H; 
      Node current = new Node(0, 0); 
      List<Node> openList = new List<Node>(); //NODES WAITING TO BE CHECKED 
      List<Node> closedList = new List<Node>(); //ALREADY CHECKED NODES 
      openList.Add(start); 

      while(openList.Count>0) //DO AS LONG AS THERE ARE STILL NODES TO DISCOVER 
      { 
       current = MinFNode(openList); //FIND NODE WITH LOWEST F COST (LOWER=BETTER PATH) 
       openList.Remove(current); //REMOVE CURRENT NODE FROM QUEUE 

       if ((current.x==target.x)&&(current.y==target.y)) //TARGET FOUND 
       { 
        Console.WriteLine("PATH FOUND"); 
        pathFound = true; 
        //DISPLAY PATH (FROM TARGET TO START) BY CHECKING PARENTS 
        Console.WriteLine("[FULL PATH]"); 
        do 
        { 
         Console.WriteLine(current.x + ", " + current.y); 
         current = current.parent; 
        } while ((current.x != start.x) && (current.y != start.y)); 
        Console.WriteLine(start.x + ", " + start.y); 
        break; 
       } 

       List<Node> successors = GetSuccessors(current.x, current.y, fields); //GET SUCCESSORS 
       foreach (Node node in successors) 
       { 
        node.parent = current; //SET CURRENT NODE AS PARENT TO RETRIEVE PATH LATER 
        node.G = current.G + 10; //10 - DISTANCE FROM CURRENT TO ITS SUCCESSOR, current.G DISTANCE FROM CURRENT TO START 
        node.H = Math.Abs(target.x - node.x) + Math.Abs(target.y - node.y); //HEURISTIC DISTANCE TO TARGET 
        node.F = node.G + node.H; //NODE FINAL COST 

        Console.WriteLine(current.x + ", " + current.y + " PARENT | SUCCESSOR: " + node.x + ", " + node.y); //TEST DISPLAY TO CHECK SUCCESSORS CURRENT NODE PRODUCED 

        if (closedList.FirstOrDefault(l => l.x == node.x && l.y == node.y) != null) //IF SUCCESSOR ALREADY EXISTS ON CLOSED LIST 
        { 
         Node temp = closedList.FirstOrDefault(l => l.x == node.x && l.y == node.y); 
         if (node.F < temp.F) //IF NEW PATH TO THIS NODE IS BETTER? (LOWER F = SHORTER PATH) 
         { 
          closedList.Remove(temp); //REMOVE OLD NODE 
          temp.parent = node.parent; 
          temp.F = node.F; 
          closedList.Add(temp); //ADD UPDATED NODE 
         } 

        } 
        else 
        if(openList.FirstOrDefault(l => l.x == node.x && l.y == node.y) != null) //IF SUCCESSOR ALREADY EXISTS ON OPEN LIST 
        { 
         Node temp = openList.FirstOrDefault(l => l.x == node.x && l.y == node.y); 
         if (node.F < temp.F) //IF NEW PATH TO THIS NODE IS BETTER? (LOWER F = SHORTER PATH) 
         { 
          openList.Remove(temp); //REMOVE OLD NODE 
          temp.parent = node.parent; 
          temp.F = node.F; 
          openList.Add(temp); //ADD UPDATED NODE 
         } 
        } 
        else 
        { 
         openList.Add(node); //ADD SUCCESSOR TO OPEN LIST 
        } 
       } 
       closedList.Add(current); //MARK CURRENT NODE AS CHECKED (NO NEED TO CHECK IT UNTIL BETTER PATH TO THIS NODE IS FOUND) 
      } 
      if(!pathFound) 
      { 
       Console.WriteLine("PATH NOT FOUND"); 
      } 
     } 

     //FIND NODE WITH LOWEST F COST 
     public static Node MinFNode(List<Node> nodes) 
     { 
      Node result = nodes[0]; 
      foreach(Node node in nodes) 
      { 
       if (node.F < result.F) 
        result = node; 
      } 
      return result; 
     } 

     //GET SUCCESSORS OF CURRENT NODE (ONLY THE ONES WITH "0" VALUE) 
     public static List<Node> GetSuccessors(int x, int y, int[,] fields) 
     { 
      List<Node> Successors = new List<Node>(); 
      if ((x - 1 >= 0) && (fields[x - 1, y]==0)) 
       Successors.Add(new Node(x - 1, y)); //LEFT 

      if ((x + 1 < fields.GetLength(0)) && (fields[x + 1, y]==0)) 
       Successors.Add(new Node(x + 1, y)); //RIGHT 

      if ((y - 1 >= 0) && (fields[x, y - 1]==0)) 
       Successors.Add(new Node(x, y - 1)); //UP 

      if ((y + 1 < fields.GetLength(1)) && (fields[x, y + 1]==0)) 
       Successors.Add(new Node(x, y + 1)); //DOWN 

      return Successors; //RETURN LIST OF AVAILABLE SUCCESSORS 
     } 

     static void Main() 
     { 
      int[,] fields = new int[5, 5] //MAP, 1 - OBSTACLE 
      { 
       { 0, 0, 0, 0, 0 }, 
       { 0, 1, 1, 1, 0 }, 
       { 0, 1, 1, 1, 0 }, 
       { 0, 0, 1, 0, 0 }, 
       { 0, 0, 1, 0, 0 } 
      }; 

      Node start = new Node(1, 3); //START LOCATION ON MAP 
      Node target = new Node(4, 4); //TARGET LOCATION ON MAP 

      FindPath(start.x,start.y,target.x,target.y,fields); //MAIN ALGORITHM 

      Console.WriteLine("END"); 
      Console.ReadLine(); 
     } 
    } 


} 

Answer 1

, bir yanlış varsayım gelen çalışıyoruz. İki boyutlu bir dizide, ilk dizin sütun değil, satır numarasıdır. Bu fields[2,4] 0.

Basit düzeltme ... fields[y, x] için tüm fields referanslara indeksleme değiştirdikten sonra bir adım daha yakın olmalıdır ikinci satır, dördüncü sütun ... olduğu anlamına gelir.

Eric'in comment ancak tamamen geçerli oldu. Bunu, küçük bir hata ayıklamayla başarabilmeliydin. Kodda ilerleyin ve gerçekte neler olduğunu görün ve sorunla ilgili daha iyi bir anlayış elde edersiniz. VS2015 Topluluk Sürümü'nün ücretsiz olması nedeniyle pek bir nedeniniz yok ve Windows'da geliştirilmiyorsanız, kodunuz boyunca ilerlemenizi ve programın durumunu çalışırken incelemenizi sağlayacak diğer C# IDE'ler de var. MonoDevelop, Linux ve Mac'te.