웨이 포인트를 사용한 Unity A * 길 찾기

Question

내 지형에서 별도의 스크립트를 사용하여 생성 한 웨이 포인트를 사용하여 A * 길 찾기 알고리즘을 만들려고합니다. 지형의 이동 및 이동 불가능 웨이 포인트는 색상에 따라 정의됩니다. 녹색은 통과 할 수 있습니다.

노드의 레이아웃은 링크를 통해 볼 수 있습니다 : https://i.stack.imgur.com/JDZdx.jpg

에 이동 웨이 포인트 목록에 저장됩니다.

길 찾기 알고리즘을 시작하려면 각 통과 가능한 웨이 포인트를 고유 키 (type = gameobject)로 저장 한 사전을 만들었습니다. 각 키의 값은 distance 함수를 사용하여 계산 된 인접 항목 (type = List)입니다.

그런 다음 온라인 참조를 사용하여 내 상황에 맞게 A * 알고리즘을 만들려고했습니다. 각 부분에 대한 주석은 아래의 코드에서 볼 수 있습니다. 'findPath'함수는 실제 알고리즘입니다 (글쎄, 최선의 시도). http://imgur.com/5cF7voO

이 더 많은 경험을 가진 사람이 나에게 몇 가지를 전해 주 시겠어요 : 노드의 그림을 폐쇄 목록 내 -

void findPath() 
    { 

     // Adds start node to open list 
     // take nodes around start node and add to lista* 

     open.Add(startNode); 


     while (open.Count > 0) 
     { 
      nodeDistances = 1000; 
      foreach (GameObject node in open) 
      { 
       GCost = Vector3.Distance(startNode.transform.position, node.transform.position);// G distance form node to start 
       HCost = Vector3.Distance(targetNode.transform.position, node.transform.position); // H distance from node to target 
       FCost = GCost + HCost; 

       if (FCost < nodeDistances) // if current node has smaller F cost than the node before that 
       { 
        tempGCost = GCost; // Gets the lowest G cost 
        tempFCost = FCost; 
        current = node; // Replaces Game Object variable 
        nodeDistances = FCost; 
       } 

      } 

      if (current.transform.position == targetNode.transform.position) 
      { 



       Debug.Log("Goal reached"); 
       break; 
      } 
      open.Remove(current); 
      closed.Add(current); 




      neighbours = attachedToWaypoint[current]; 
      // path.Add(current); 

      foreach (GameObject n in neighbours) 
      { 
       if (!closed.Contains(n)) 
       { 
        float g_score = tempGCost + 1; // Takes current node GCost and adds value of 1 for each neighbour 
        float h_score = Vector3.Distance(n.transform.position, targetNode.transform.position); // Gets distance from each neighbour to the target node 
        float f_score = g_score + h_score; 


        if (closed.Contains(n) && f_score >= tempFCost) // If F cost of neighbour is greater than F cost of current node 

         continue; 


        if (!open.Contains(n) || f_score < tempFCost) // If 'open' list does not currently contain neighbour or neighbours F score is smaller than that of the current node 
        { 

         GCost = g_score; 
         HCost = h_score; 
         tempFCost = GCost + HCost; // update current node F score value to get neighbour with the smallest F score 


         if (!open.Contains(n)) 
         { 
          open.Add(n); // if neihgbour is not in open list, add to open list 
         } 
        } 

       } 
      } 
     } 
    } 

그러나, 폐쇄 목록에 저장된 노드보고, 뭔가 잘못 가고 있음을 알 수있다 어떤면에서 포인터를 집중해야합니까? 또한, 가장 저렴한 경로를 찾으려면 어떻게 사용합니까?

도움을 주시면 매우 감사하겠습니다.

감사합니다,

전체 스크립트 아래 캘빈 :

using System.Collections; 
using System.Collections.Generic; 
using UnityEngine; 


public class TEST : MonoBehaviour 
{ 

    Dictionary<GameObject, List<GameObject>> attachedToWaypoint = new Dictionary<GameObject, List<GameObject>>(); 
    List<GameObject> gameObjectForDic = new List<GameObject>(); 
    GameObject[] waypoints; 
    List<List<GameObject>> nodeData = new List<List<GameObject>>(); 



    List<GameObject> neighbours = new List<GameObject>(); // Not currently used 

    public GameObject enemy; 
    public GameObject player; 
    GameObject startNode; 
    GameObject targetNode; 



    List<GameObject> open = new List<GameObject>(); 
    List<GameObject> closed = new List<GameObject>(); 

    float distanceToEnemy; 
    float distanceToPlayer; 

    float tempFCost; 
    float FCost; 
    float GCost; 
    float HCost; 
    float tempGCost; 
    float accumulatedCost; 
    float accumulatedCostTemp; 
    float nodeDistances; 

    GameObject current; 

    public GameObject parent; 

    List<GameObject> path = new List<GameObject>(); 


    // Use this for initialization 
    void Start() 
    { 
     distanceToEnemy = 1000; 
     distanceToPlayer = 1000; 
     nodeDistances = 10000; 

     waypoints = GameObject.FindGameObjectsWithTag("Waypoint"); 

     storeNodesInDictionary(); 
     findPath(); 
     // findPathtoPlayer(); 
     testing(); 








    } 

    void storeNodesInDictionary() 
    { 
     for (int i = 0; i < waypoints.Length; i++) 
     { 

      nodeData.Add(new List<GameObject>()); 


      float distEnemy = Vector3.Distance(enemy.transform.position, waypoints[i].transform.position); // Closest node to enemy 

      if (distEnemy < distanceToEnemy) 
      { 
       startNode = waypoints[i]; 
       distanceToEnemy = distEnemy; 

      } 



      float distPlayer = Vector3.Distance(player.transform.position, waypoints[i].transform.position);// Closest node to player 

      if (distPlayer < distanceToPlayer) 
      { 
       targetNode = waypoints[i]; 
       distanceToPlayer = distPlayer; 
      } 




      for (int j = 0; j < waypoints.Length; j++) 
      { 
       float distanceSqr = (waypoints[i].transform.position - waypoints[j].transform.position).sqrMagnitude; // Gets distance values 
       if (distanceSqr < 60 && waypoints[i] != waypoints[j]) // Is waypoints are within a spcific distance 
       { 
        nodeData[i].Add(waypoints[j]); 

       } 
      } 

      attachedToWaypoint.Add(waypoints[i], nodeData[i]); // Adds parent node and neighbouring nodes within a 3x3 grid 

     } 

    } 





    void findPath() 
    { 

     // Adds start node to open list 
     // take nodes around start node and add to lista* 

     open.Add(startNode); 


     while (open.Count > 0) 
     { 
      nodeDistances = 1000; 
      foreach (GameObject node in open) 
      { 
       GCost = Vector3.Distance(startNode.transform.position, node.transform.position);// G distance form node to start 
       HCost = Vector3.Distance(targetNode.transform.position, node.transform.position); // H distance from node to target 
       FCost = GCost + HCost; 

       if (FCost < nodeDistances) // if current node has smaller F cost than the node before that 
       { 
        tempGCost = GCost; // Gets the lowest G cost 
        tempFCost = FCost; 
        current = node; // Replaces Game Object variable 
        nodeDistances = FCost; 
       } 

      } 

      if (current.transform.position == targetNode.transform.position) 
      { 



       Debug.Log("Goal reached"); 
       break; 
      } 
      open.Remove(current); 
      closed.Add(current); 




      neighbours = attachedToWaypoint[current]; 
      // path.Add(current); 

      foreach (GameObject n in neighbours) 
      { 
       if (!closed.Contains(n)) 
       { 
        float g_score = tempGCost + 1; // Takes current node GCost and adds value of 1 for each neighbour 
        float h_score = Vector3.Distance(n.transform.position, targetNode.transform.position); // Gets distance from each neighbour to the target node 
        float f_score = g_score + h_score; 


        if (closed.Contains(n) && f_score >= tempFCost) // If F cost of neighbour is greater than F cost of current node 

         continue; 


        if (!open.Contains(n) || f_score < tempFCost) // If 'open' list does not currently contain neighbour or neighbours F score is smaller than that of the current node 
        { 

         GCost = g_score; 
         HCost = h_score; 
         tempFCost = GCost + HCost; // update current node F score value to get neighbour with the smallest F score 


         if (!open.Contains(n)) 
         { 
          open.Add(n); // if neihgbour is not in open list, add to open list 
         } 
        } 

       } 
      } 
     } 
    } 

} 

Answer 1

몇 가지 제안 :

이 Closed위한 좋은 데이터 구조가 HashSet입니다

, 이것은 확실히 당신의 코드를 속도를 높이고 아무튼 것 ' 정말로 많은 변화가 필요합니다.

불행히도 의 올바른 데이터 구조는 priority queue이지만 최상의 성능을 제공하는 타사 구현을 사용하는 것이 좋으면 f 비용이 우선 순위가됩니다. 그렇지 않으면 직접 작성해야합니다.

지금까지 폐쇄 된 목록 사진은하지만 다음 줄을 함께 할 수있는 버그를 알아낼 수 있었던 것과 나쁜에 보이지 않는 등 :

가

GCost = Vector3.Distance(startNode.transform.position, node.transform.position); // G distance from node to start 

G 코드 비용은 startNode에서 노드까지 얻는 실제 거리라고 가정하지만 h를 계산하는 데 g를 계산하는 데 동일한 함수를 사용하고 있습니다. 이것은 마치 두 개의 직선을 사용하는 것과 같습니다. 직선 경로가 지나가는 지그재그 경로를 통해 그것을 어떻게 만들려고하는지 상상한다면, 직선으로 생각할 때마다 지그재그 경로를 따라 갈 것입니다. startNode에서 현재 노드로 이동합니다.

다음은 내가 할 수있는 일을 조사하는 동안 내가 코드에서 한 일입니다.

using System.Collections; 
using System.Collections.Generic; 
using UnityEngine; 
using Some.Namespace.That.Gets.PriorityQueue; 

public class TEST: MonoBehaviour { 

    Dictionary<GameObject, List<GameObject>> attachedToWaypoint = new Dictionary<GameObject, List<GameObject>>(); 

    GameObject[] waypoints; 
    GameObject startNode; 
    GameObject targetNode; 
    GameObject current; 

    PriorityQueue<float, GameObject> open = new PriorityQueue<float, GameObject>(); 
    HashSet<GameObject> closed = new HashSet<GameObject>(); 
    List<GameObject> path = new List<GameObject>(); 

    float distanceToEnemy; 
    float distanceToPlayer; 
    float FCost; 
    float GCost; 
    float HCost; 
    float nodeDistances; 

    public GameObject enemy; 
    public GameObject player; 
    public GameObject parent; 

    // Use this for initialization 
    void Start() { 
     distanceToEnemy = 1000; 
     distanceToPlayer = 1000; 
     nodeDistances = 10000; 

     waypoints = GameObject.FindGameObjectsWithTag("Waypoint"); 
     storeNodesInDictionary(); 
     findPath(); 
     // findPathtoPlayer(); 
     testing(); 
    } 

    void storeNodesInDictionary() { 
     for (int i = 0; i < waypoints.Length; i++) { 
      var waypoint = waypoints[i]; 
      var nodeData = new List<GameObject>(); 
      var waypointPosition = waypoint.transform.position; 

      float distEnemy = Vector3.Distance(enemy.transform.position, waypointPosition); // Closest node to enemy 
      if (distEnemy < distanceToEnemy) { 
       startNode = waypoint; 
       distanceToEnemy = distEnemy; 
      } 

      float distPlayer = Vector3.Distance(player.transform.position, waypointPosition); // Closest node to player 
      if (distPlayer < distanceToPlayer) { 
       targetNode = waypoint; 
       distanceToPlayer = distPlayer; 
      } 

      for (int j = 0; j < waypoints.Length; j++) { 
       if (i == j) 
        continue; 
       var otherWaypoint = waypoints[j]; 
       float distanceSqr = (waypointPosition - otherWaypoint.transform.position).sqrMagnitude; // Gets distance values 
       if (distanceSqr < 60) // Is waypoints are within a spcific distance 
       { 
        nodeData.Add(otherWaypoint); 
       } 
      } 
      attachedToWaypoint.Add(waypoint, nodeData); // Adds parent node and neighbouring nodes within a 3x3 grid 
     } 
    } 

    void findPath() { 
     var startPosition = startNode.transform.position; 
     var targetPosition = targetNode.transform.position; 
     open.Push(Vector3.Distance(startPosition, targetPosition), startNode); 
     while (open.Count > 0) { 
      FCost = open.Pop(out current); 
      var currentPosition = current.transform.position; 
      if (currentPosition == targetPosition) { 
       Debug.Log("Goal reached"); 
       break; 
      } 
      HCost = Vector3.Distance(currentPosition, targetPosition); 
      GCost = FCost - HCost; 
      closed.Add(current); 
      var neighbours = attachedToWaypoint[current]; 
      // path.Add(current); 
      foreach(GameObject n in neighbours) { 
       if (!closed.Contains(n) && !open.Contains(n)) // If 'open' list does not currently contain neighbour or neighbours F score is smaller than that of the current node 
       { 
        var neighbourPosition = n.transform.position; 
        var neighbourFCost = GCost + Vector3.Distance(currentPosition, neighbourPosition) + Vector3.Distance(neighbourPosition, targetPosition) 
        open.Push(neighbourFCost, n); // if neighbour is not in open list, add to open list 
       } 
      } 
     } 
    } 
}