Bir 2D dizisinde A * pathfinding uygulaması

Question

Bir 2D döşeme haritası oluşturma sürecindeyim ve şimdi A * pathfinding'ı uygulamaya çalışıyorum. the Wikipedia pseudocode for A*'u takip ediyorum.

Algoritma tarafından alınan kararlarda bazı garip davranışlar dışında işler oldukça iyi gidiyor. Bugüne kadar

Benim kod:

bu kodu çalıştırarak sonucu

void Pathfinding(Point from, Point destination) { 

    goalNode = new Node(destination, 0, 0); 
    startNode = new Node(from, 0, ManhattanDistance(from, destination)); 

    open = new List<Node>();   //list of nodes 
    closed = new List<Node>(); 
    open.Add(startNode);    //Add starting point 

    while(open.Count > 0) { 

     node = getBestNode();     //Get node with lowest F value 
     if(node.position == goalNode.position) { 
      Debug.Log("Goal reached"); 
      getPath(node); 
      break; 
     } 
     removeNode(node, open); 
     closed.Add(node); 

     List<Node> neighbors = getNeighbors(node); 
     foreach(Node n in neighbors) { 
      float g_score = node.G + 1; 
      float h_score = ManhattanDistance(n.position, goalNode.position); 
      float f_score = g_score + h_score; 

      if(isValueInList(n, closed) && f_score >= n.F) 
       continue; 

      if(!isValueInList(n, open) || f_score < n.F) { 
       n.parent = node; 
       n.G = g_score; 
       n.G = h_score; 
       if(!isValueInList(n, open)) { 
        map_data[n.position.x, n.position.y] = 4; 
        open.Add(n); 
       } 
      } 
     } 
    } 
} 

:

Mavi açık listesi ve yeşilden düğümleri olan hedef düğüme seçtiği yol . ÇÖZÜM

: - hayır sipariş yoktur Kodunuzdaki iken

void Pathfinding(Point from, Point destination) { 

    goalNode = new Node(destination, 0, 0); 
    startNode = new Node(from, 0, ManhattanDistance(from, destination)); 

    open = new List<Node>();   //list of nodes 
    closed = new List<Node>(); 
    open.Add(startNode);    //Add starting point 

    while(open.Count > 0) { 

     node = getBestNode();     //Get node with lowest F value 
     if(node.position == goalNode.position) { 
      Debug.Log("Goal reached"); 
      getPath(node); 
      break; 
     } 
     removeNode(node, open); 
     closed.Add(node); 

     List<Node> neighbors = getNeighbors(node); 
     foreach(Node n in neighbors) { 
      float g_score = node.G + 1; 
      float h_score = ManhattanDistance(n.position, goalNode.position); 
      float f_score = g_score + h_score; 

      if(isValueInList(n, closed) && f_score >= n.F) 
       continue; 

      if(!isValueInList(n, open) || f_score < n.F) { 
       n.parent = node; 
       n.G = g_score; 
       n.H = h_score; 
       if(!isValueInList(n, open)) { 
        map_data[n.position.x, n.position.y] = 4; 
        open.Add(n); 
       } 
      } 
     } 
    } 
} 

Answer 1

İlk olarak, açık Düğümler olmalıdır , azalan düzende sıralanmış. Mesafeyi (g) ve sezgiyi (h) hesaplarsınız, ancak asla kullanmazsınız. Sen

Saniye (her tekrarında listeleri sıralama verimli olmayacaktır gibi) listelerin yerine sipariş kabıkullanmayı düşünmelisiniz, sen olmalıdır

n.G = h_score; 

olarak düğümünde sezgisel değeri saklamıyoruz

n.H = h_score;