我正在尝试使用我在地形上使用单独的脚本生成的航路点创建 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
}
}
}
}
}
}
}
最佳答案
一些建议:
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
}
}
}
}
}
关于c# - Unity A* 使用航路点的寻路，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/41927807/