C# - алгоритм A * дает неправильные результаты

Question

Я пытаюсь сделать 4-направленный алгоритм поиска траекторий A-Star в C#, но не могу заставить его работать правильно. В основном методе у меня есть пример 5x5 int массив массива, чтобы установить, к каким полям можно обращаться, а какие нет (0 - чистое поле, 1 - препятствие). В качестве примера я установил СТАРТ точка в (1, 3) и TARGET точка в (4, 4), поэтому я ожидал бы путь, чтобы избежать стены и продолжить и т. Д., Но это не так. Я даже сделал свой алгоритм отображением каждого родителя и его преемников (соседей). В моем случае он отображает (2,4) как один из узлов, несмотря на то, что он помечен как препятствие в полях (Карта), как это произошло? В методе есть четкое указание включить метод GetSuccessors только те, которые помечены как 0, но он по-прежнему включает в себя (2, 4) точку. Я не уверен, что что-то не так с GetSuccessors или FindPath (главный алгоритм).

Пример карта:

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 

Произведенный путь (от TARGET для начала):

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

Полный код (FindPath и GetSuccessors являются основными но я все еще могу сделать что-то не так с другими методами):

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

Как указал Иван, вы работаете с ложным предположением. В двумерном массиве первым индексом является номер строки, а не столбец. Это означает, что fields[2,4] - это второй ряд, четвертая колонка ..., которая равна 0.

Простая установка ... переключите индексирование на все ваши ссылки на fields[y, x], и вы должны быть ближе к шагу.

Замечание Эрика было совершенно справедливо. Вы должны были бы забрать это с небольшой отладкой. Пройдите через код и посмотрите, что на самом деле происходит, и вы получите гораздо лучшее представление о проблеме. Поскольку версия VS2015 Community Edition бесплатна, нет оснований для этого, и если вы не работаете в Windows, есть другие C# IDE, которые позволят вам выполнить свой код и изучить состояние программы по мере ее использования. MonoDevelop - это работа на Linux и Mac.