c# - Unity A* 使用航路点的寻路

Question

我正在尝试使用我在地形上使用单独的脚本生成的航路点创建 A* 寻路算法。地形上可穿越和不可穿越的航路点由其颜色定义 - 绿色表示可穿越。

节点的布局可以通过以下链接查看: /image/JDZdx.jpg

可穿越的航路点存储在列表中。

为了开始寻路算法，我创建了一个字典，将每个可穿越的路径点存储为一个唯一的键(类型 = 游戏对象)。每个键的值是使用距离函数计算的其邻居(类型 = 列表)。

然后我尝试使用在线引用创建一个 A* 算法，并根据我的情况进行调整。每个部分的注释可以在我下面的代码中看到。函数“findPath”是实际的算法(好吧，这是我最好的尝试)。

 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
                        }
                    }

                }
            }
        }
    }

但是，查看存储在封闭列表中的节点，很明显出了问题 - 封闭列表中的节点图片:http://imgur.com/5cF7voO

请有经验的人指点一下我应该关注哪方面？此外，您将如何使用它来找到最便宜的路径？

任何帮助将不胜感激。

谢谢，卡尔文

完整脚本如下:

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 ，这肯定会加快您的代码速度，而且实际上不需要太多更改。

不幸的是，Open 的正确数据结构是 priority queue ，但是 c# 没有内置，如果您可以使用第三方实现来获得最佳性能，那么 f 成本将是您的首要任务。否则，您将需要自己编写。

就您的关闭列表图片而言，它看起来还不错，但据我所知，该错误可能与以下行有关:

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

g 成本应该是从 startNode 到节点的实际距离，但您使用相同的函数来计算 g 和计算 h。这就像一直使用两条直线，如果你想象它会如何尝试通过一条曲折的路径，旁边有一条直线路径旁路，它会一直沿着曲折的路径走下去，以为它是直行的从起始节点到当前节点。

下面是我在调查时对代码所做的，您可以随意使用它。

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
                }
            }
        }
    }
}