我正在尝试使用我在地形上使用单独脚本生成的路标创建A *寻路算法 . 地形上的可穿越和不可穿越的航点由其颜色定义 - 绿色可穿越 .
通过以下链接可以看到节点的布局：https://i.stack.imgur.com/JDZdx.jpg
可遍历的航路点存储在列表中 .
为了启动寻路算法，我创建了一个字典，将每个可遍历的航路点存储为一个唯一的密钥（type = gameobject） . 每个键的值是使用距离函数计算的邻居（type = List） .
然后我尝试使用在线参考创建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
}
}
}
}
}
}
}
1 回答
一些建议：
Closed的良好数据结构是HashSet，这肯定会加速你的代码，并不需要太多的改变 .不幸的是，
Open的正确数据结构是priority queue，但是c＃没有内置的数据结构，如果您使用能够提供最佳性能的第三方实现，那么f成本将是您的首选 . 否则你需要自己编写 .至于你的封闭列表图片看起来并不坏，但从我能够找出的bug可能是以下行：
g cost应该是从startNode到节点的实际距离，但是您使用相同的函数来计算用于计算h的g . 这就像在整个时间里使用两条直线一样，如果你想象它会如何通过一条直线路径绕过它的锯齿形路径，它会一直沿着曲折的路径走下去，一直认为它是直的从startNode到当前节点 .
以下是我在调查时对代码所做的操作，你可以用它做什么 .